一种多agen系统协调协调的步进式全局规划模型

一种多agen系统协调协调的步进式全局规划模型

1局部规划+增量式策略许多秋季合作和磋商是组织能够顺利完成任务的关键。一般总结计划（pgp）是解决流量差异的协调机制，但假设流量代理是未经授权的。换言之，在调整操作时，资源只有考虑整体利益，而我们通常看到的资源都是私人的，所以我们必须考虑自己的利益。针对于此,本文对PGP进行了改进,提出了一种步进式部分全局规划(PPGP),并主要针对基于时间或资源限制的任务类型,其改进如下:1)在PGP中任务管理Agent通过广播的形式将局部规划分配给其它Agents,然后该Agent接收到来自其它Agents的disagreement信息,而每个disagreement信息都代表该Agent自身的局部规划与任务管理Agent的局部规划的冲突;而在PPGP中,Agents彼此间相互通讯来发现冲突,各Agent是平等的,不存在一个集中管理Agent。2)在PGP中,当探测到冲突后,在解决冲突时,各Agen必须重新开始执行各自的局部规划来协调冲突;而我们在PPGP中,通过丢弃产生冲突的最不重要Agent的非强制性局部规划来加快Agents间达成协商的速度。3)在解决冲突的过程中,我们在PPGP中采用了增量式策略来协调冲突。通过以上的改进,PPGP允许新加入的Agent同原系统中的Agents进行协商,而且当插入一个新的Agent后,原系统中的Agents不必重新开始协商。新的Agent通过探测冲突,并在不给已达成的协商带来新的冲突的情况下解决冲突,以便尽快达成协商。2通过各全球规划协调机制的完善2.1局部规划的生成Agent是多Agent系统的基本组成成分,每个Agent的结构主要包括三个通信子模块:通信接口、规划器和协调器。Agen的逻辑结构如图1所示,下面介绍各通信子模块:通信接口:通信接口用来同其它Agents进行交互信息,Agent通过消息传递模式以点对点或多播的形式进行交互;规划器:规划器接收来自通信接口传来的消息。而该消息可分为两类:一类是该Agent分配的任务,即它所要实现的目标;另一类是其它Agents关于该Agent局部规划的disagreemen信息。因此,处理过程中有两个映射函数:一个是规划构造函数,该函数用来构造规划以达到给定目标,在构造中采用步进方式以使规划细节满足时间约束,其映射关系可表示为:另一个是冲突探测函数,该函数通过分析Agents间的disagreement消息来确定已构建的局部规划与新的Agents局部规划之间的冲突,其映射关系可表示为:然后,规划器将冲突消息传递给协调器。协调器:通过接收规划器传来的冲突消息后,对所有冲突提出解决方案,其映射关系可表示为:Agents之间通过通信了解彼此的规划并预测可能产生的冲突,本文中Agents间是基于消息传递模式来进行通信的。Agent通信的目的主要有以下几种:接收任务、广播局部规划、接收冲突信息和发出冲突解决方案。新加入的Agent通过信息交互来探测原来系统中Agents的协商冲突,同时,它还要解决其自身规划与已达成的协商之间的冲突。本文中,通过放宽原系统中Agents以及该新加入Agent的最不重要的部分局部规划的约束来协调冲突。下面我们建立单个Agent的形式化模型,它可表示为一个三元组:<O,A,C>。其中,O表示该Agent的操作集,A表示该Agent的属性集,C表示该Agent所要达到目标的约束集,即Agent的子任务集,每个子任务就是一个约束,并且子任务都是不可再分的。Agents在协商中采用优先权原则,Agent对其每个部分局部规划分配不同的优先权。我们假设对于强制性约束的优先权p=0,对于非强制性约束的优先权设为p=1,2,…;优先权的值越大,则该约束的重要性就越小。下面给出几个概念:强制性部分局部规划αP0={oαj∈Oα|oαj满足约束cα,j,p(cα,j)=0};非强制性部分局部规划Pαi={oαj∈Oα|oαj满足约束cα,j,p(cα,j)=i};局部规划αP=ki=∪0Pαi,即它是强制性部分局部规划与非强制性部分局部规划的并集。2.2基于局部冲突的开发当一个部分局部规划协商失败,Agent将根据策略分析部分局部规划的整体效用,来决定是否移出该部分局部规划,Agent的策略是优先执行Agent的强制性部分局部规划,然后是非强制性部分局部规划。该策略的意图是:确保Agent协商的最低质量而不是去重新寻找一个新的解决方案。假设有一Agents集Ag={a1,a2,…},这些Agents已经就它们的规划达成了协商,这时有一个新的Agent加入,这可能将破坏已达成的协商。因此,该新加入的Agent将收集所有的冲突信息,以便解决这些冲突。下面我们首先对冲突及其类型进行定义:定义1设有Agenta和Agentb,当Pa与Pb不一致时,我们称Agenta与Agentb产生了冲突。定义2当新加入的Agent的强制性部分局部规划与原多Agents系统中的某个Agent的局部规划冲突,称发生了硬冲突。定义3当新加入的Agent的非强制性部分局部规划与原多Agents系统中的某个Agent的局部规划冲突,称产生了软冲突。定义4当新加入的Agent的局部规划与原多Agents系统中的某个Agent的强制性局部规划冲突,称产生了紧急冲突。定义5当新加入的Agent的局部规划与原多Agents系统中的某个Agent的非强制性局部规划冲突,称产生了非紧急冲突。根据以上定义,我们可以将新加入的Agent(设为AgentN)的冲突分为以下四种类型:1)硬紧急冲突:当AgentN的强制性局部规划与原多Agents系统中的某个Agent的强制性局部规划冲突;2)硬非紧急冲突:当AgentN的强制性局部规划与原多Agents系统中的某个Agent的非强制性局部规划冲突;3)软紧急冲突:当AgentN的非强制性局部规划与原多Agents系统中的某个Agent的强制性局部规划冲突;4)软非紧急冲突:当AgentN的非强制性局部规划与原多Agents系统中的某个Agent的非强制性局部规划冲突;Agents间通过协商来解决冲突,并用规划的效用函数进行衡量,通过比较效用函数的值来选择效用函数值大的规划。每个部分局部规划都有其效用,这里考虑两个方面的特性,即规划的质量和执行规划的代价,而规划的质量可以通过其完成规划所获得的奖赏来衡量。它们分别可用公式(1)～(3)表示:其中,Pai表示某个Agent的部分局部规划,奖赏函数Reward(c)表示约束满足时获得的奖赏值,代价函数cost(o)表示执行的时间。步进式策略按如下步骤执行:step1对冲突集进行排序,Conflicts={硬紧急冲突,硬非紧急冲突,软紧急冲突,软非紧急冲突};step2if时限未到且Conflicts非空then{con=Head(Conflicts);//从冲突集中取出冲突Conflicts=Tail(Conflicts)//将新的冲突加入到冲突集中resolution(con);}//解决冲突;step3if时限已到而Conflicts非空,then抛弃Conflicts中的所有冲突;下面我们将介绍如何解决冲突:5)对硬紧急冲突:如果AgentN的强制性部分局部规划的效用值大于原多Agents系统中的强制性部分局部规划的整体效用值,AgentN将保持现有规划并发出消息,这样原多Agents系统中的Agents将放松对各自的部分局部规划的约束,如果时间允许的话,它们将提出新的局部规划,同时它们还将接收到有关AgentN的部分局部规划时限的消息。相反,如果AgentN的强制性部分局部规划的效用值小于原多Agents系统中的Agents的强制性部分局部规划的整体效用值,则AgentN将接受这些部分局部规划并返回接收消息,然后等待Agents的确认消息,但必须在AgentN的强制性部分局部规划最后时限之前。6)对硬非紧急冲突:AgentN将维持它的强制性部分局部规划而拒绝所有的非强制性部分局部规划。7)对软紧急冲突:AgentN将放松对它非强制性部分局部规划约束或违反相应的约束。8)对软非紧急冲突:该冲突的解决方法与硬紧急冲突的解决方法大致相同,只是它是相对于非强制性部分局部规划而言,这里不再累述了。我们可以看出,该冲突解决的方法是首先解决高优先级别的冲突,以确保最重要的部分局部规划能在最后时限之前执行,同时,也确保了Agents的协商效率。3各局部规划之间的协商我们通过实验对PGP与PPGP进行了比较:在一个多机器人环境中,每个机器人都拥有一个基于时限的局部规划P={p1,p2,p3,…},由于资源的不可共享性,各机器人要想在最后时限之前开始执行其规划,它们必须进行协商,以避免冲突。根据PPGP,首先对各部分局部规划赋予不同的优先级,设p(p1)=0,p(p2)=1,p(p3)=2,……,如此类推。这里p(p1)=0表示p1对于各机器人是强