多Agent动态任务分配问题

张家良 王迎磊 李复名 周涛

摘要： 针对多Agent动态环境下任务分配问题，建立多Agent动态任务分配模型，提出了基于改进合同网的动态任务分配算法。在合同網的基础上，引入任务中转站处理由环境变化产生的新任务，任务优先级定义任务的处理顺序，并对算法的招标以及投标阶段进行了改进，设定了招标任务闽值和投标任务阈值。仿真结果表明该算法能在各种环境变化下快速更新任务分配方案。

【关键词】动态任务分配 改进合同网 任务中转站 任务优先级

1 引言

随着信息技术以及分布式系统理论的迅速发展，多Agent系统已经引起研究人员的广泛关注。Agent能感知自身以及外界状态变化，并能产生相应的自主行为。多Agent系统概念在军事领域中的运用，是未来战争体系中的关键，连入网络的各作战单元可以看作Agent。由于战争环境复杂多变，且Agent在执行任务过程中能力可能出现变化。因此，研究多Agent动态任务分配问题，对于提高多Agent协同作战能力具有重要的意义。

目前，基于合同网的算法已经广泛运用在求解任务分配问题中。文献[4]通过引入任务熟人集的概念，在招标范围上进行改进，减少招标对象的数量，有效减少了协商时间。文献[5]通过建立条件合同机制，并引入时间网络约束，保证了算法能准确实现任务重分配。文献[6]综合考虑Agent的负载、能力和信任度，提出基于多属性的中标策略，提高了算法求解的效率。但是大多数方法对环境变化产生的任务没有预先处理，导致任务分配时较为混乱。因此，本文在传统合同网基础上，引入任务中转站和任务优先级协助处理任务的分配，并改进了招标和投标阶段，提高了多Agent处理动态任务分配问题的效率。

2 多Agent动态任务分配模型

2.1 多Agent动态任务分配问题

在作战开始前，指挥中心通常会根据己掌握的战场信息，对己方作战单元进行任务预分配。但随着战场环境的变化以及Agent在执行任务过程中出现突发情况，若按照之前的方案执行任务，可能会使得执行任务的效能降低。因此，在出现环境变化后，多Agent需调整自身任务，使得执行任务的效能保持最大。

2.2 多Agent分布式结构

基于Agent的特点，将连入网络的作战单元看作Agent，各Agent通过数据链传递信息，构成多Agent分布式结构，如图1所示。分布式结构里的Agent是独立自治的，互相之间能直接进行通信实现信息交换。分布式结构扩展性强，在遇到环境变化时，无需将信息传递给指挥中心等待决策，自身就可以进行协调控制，从而快速调整。

2.3 多Agent动态任务分配模型

设由N个Agent对M个目标执行任务。每个Agent自身的任务集为Tk，执行任务的效能为U（Tk），k=l，…，N。

多Agent动态任务分配数学模型为：

其中U（J）=J1（T）-J2（T），J1（T）和J2（T）代表执行任务的收益和代价，其中代价分为损耗代价和航程代价。具体定义如下：

以上公式中T为Agent的任务集，即目标列表。S为Agent对目标执行任务的成功概率，Z为Agent对目标执行任务的损伤概率，K为目标的自身价值，L表示执行任务的路程。ω1和ω2是损耗代价函数和航程代价函数的权重系数。

3 传统合同网

3.1 合同网思想

合同网是在上世纪80年代由R Davis和RG Smith提出的一种协商方法。合同网主要运用在分布式系统中，通过模拟经济行为的招标.投标.中标，从而实现任务的传递控制。

基于合同网的动态任务分配主要分为四个阶段：招标、投标、中标和签约。

3.1.1 招标阶段

招标阶段是Agent在任务的执行过程中，发现执行某项任务效能过低，就把任务向外界公布进行招标。

3.1.2 投标阶段

投标阶段是其他Agent收到招标信息后，若还有能力执行任务，则将招标任务纳入自身任务集，并公布标书价格，即执行该招标任务的效能。

3.1.3 中标阶段

中标阶段是招标者收到投标者发送的标书，衡量投标者的标书价格，选出其中价格最优的标书，并向此投标者发送中标信息。

3.1.4 签约阶段

签约阶段是招标者和中标者更新各自任务集。

合同网流程如图2所示。

3.2 传统合同网不足

传统合同网可以在一定程度上解决动态任务分配问题，但在较复杂的场景中，传统合同网有以下不足：

（1）传统合同网在招标阶段，对于各种环境变化而导致的新任务，没有有序的处理方法，使得招标阶段比较混乱。

（2）传统合同网在投标阶段，未对投标Agent做一定的限制，导致其他所有的Agent都参与投标，产生了不必要的信息传递，降低了算法的效率。

（2）某些投标Agent虽然最多再能执行一次任务，但却参与了多项任务的投标，浪费了资源。

4 基于改进合同网的动态任务分配

4.1 任务的初始分配

在作战开始前，指挥中心根据己知的战场信息，在满足约束条件下，对任务进行预分配，确定各个Agent的任务集，即Agent需要打击的目标列表。保证多Agent系统执行任务的效能最大。本文将执行任务的效能作为目标函数，利用粒子群算法对目标函数进行优化，得到初始任务分配方案。

4.2 具体优化内容

当战场环境出现变化时，如新的目标发现、某Agent失去继续执行任务的能力或者Agent执行某一任务效能突然变低等。若Agent继续按照初始任务分配方案执行任务，可能会造成执行任务的效能降低。因此，本文基于改进合同网进行动态任务分配。

在传统合同网的基础上，引入任务中转站和任务优先级的概念，并对算法的招标和投标阶段进行改进，具体如下。

4.2.1 任務中转站

任务中转站负责协助Agent分布式结构处理协作问题。任务中转站的功能具体有以下几种：

（1）负责储存信息，这些信息包括在执行任务的过程中发现的新任务，Agent损伤导致无法执行任务自身的任务集以及Agent由于自身能力变化而产生的任务。

（2）招标者评估标书时，首先任务中转站评估出各个投标者投递价格最优的标书，然后将各个投标者价格最优标书投递给招标者进行评估。

引入任务中转站有如下几个优点：

（1）可以处理Agent无法处理的情况。如在执行任务过程中发现的新任务。新任务不属于Agent本身的任务，招标Agent无法将该任务直接纳入自身投标任务，此时任务中转站可以将这种情况产生的新任务存在任务中转站中，直接当作招标任务，增强了算法的扩展性。

（2）降低了各Agent之间的通信次数。任务中转站可以预先评估最优标书，从而直接将价格最优的标书直接投递给招标者，减少了Agent的负担。

（3）辅助协调各Agent之间的任务分配。当环境变化不止一种时，任务中转站会根据任务优先级，依次按照优先级处理各种情况产生的新任务，使任务调整过程合理且高效。

4.2.2 任务优先级

本文定义了任务优先级。在各种动态环境中，Agent分布式结构会优先处理优先级高的任务。定义如下：

（1） Agent数量的变化。在Agent执行任务的过程中，某些Agent可能无法执行任务或突然增加Agent的数量，则该Agent本身的任务即当作招标任务处理。这种情况导致的任务优先度最高。

（2）新的任务出现。在Agent执行任务的过程中，可能会发现新的目标，即有新的任务产生。这种情况导致的任务优先度次于第一种情况。

（3） Agent执行某项任务的效能突然变低。在Agent执行任务的过程中，Agent自身能力变化导致执行任务的效能突然变低，需要将此任务当作招标任务处理。这种情况导致的任务优先度最低。

定义任务优先度，使得Agent分布式结构能有序处理环境变化下的任务分配，有效提高了算法的效率。

4.2.3 招标和投标阶段的改进

为了减少不必要的通信量，本文在招标和投标阶段进行了改进，设定了阈值，具体定义如下：

（1）招标任务阈值，只有当招标Agent的执行任务的效能低于阈值时，招标Agent才会将该任务进行招标。

（2）投标Agent阈值，只有当其他Agent执行招标任务的效能高于阈值时，才能进行投标。

4.3 改进合同网的流程

其步骤可总结如下：

（1）确定算法的各种初始参数。

（2）利用粒子群算法，求解得到任务的初始分配方案。

（3）环境变化时，对于Agent能力削弱，若该Agent执行任务的效能低于招标任务阈值，则将此任务纳入任务中转站作为招标任务，对于Agent数量变化以及新任务，则直接纳入任务中转站作为招标任务。任务中转站根据任务优先级，将任务按照优先级定义顺序确定招标任务并进行招标。

（4）其他Agent判断自身是否还有能力进行投标。投标Agent执行招标任务的效能高于投标任务闽值时，才会投递标书。投标Agent的标书由任务中转站进行处理，选出最优标书。

（5）任务中转站将出价最高的标书的投标Agent作为中标者。

（6）各个Agent根据招标投标结果，更新各自的任务集。

（7）判断由环境变化产生的招标任务是否全部分配完毕。若没有分配完毕，则继续执行步骤3到6的内容。若已分配完毕，则算法结束。

5 仿真计算实例

5.1 多Agent初始任务分配方案

本文基于改进合同网对任务分配问题进行仿真计算，首先得到任务初始分配方案。在仿真计算中，假设Agent数目为5个，目标数目为12个，每个Agent执行任务的数量不能超过4个，ω1和ω2分别为0.5和O.l。Agent位置如表l所示，Agent对目标执行任务的成功概率如表2所示。目标自身位置和价值如表3所示，Agent对目标执行任务后的损伤概率如表4所示。

经过200次的仿真计算表明，在上述条件下得到的结果具有稳定性。基于上述条件，首先得到初始分配方案集。图4给出了整体效能随迭代次数增加的收敛曲线，随着迭代次数增加，多Agent执行任务的效能值收敛在一个较稳定的数值，证明了算法的收敛性。图5给出各Agent按照预先任务分配示意图，表5给出各Agent任务集和效能值。Aa的目标为4，9，效能值为0.851。Ab的目标为7，11，效能值为0.982。Ac的目标为6，12，效能值为1 095。Ad的目标为10，8，3，效能值为1.639。Ae的目标为1，2，5，效能值为1 564。上述结果为任务的初始分配方案，所消耗时间为2.7s。

5.2 多Agent动态任务分配

得到任务初始分配方案后，在各Agent执行任务过程中，遇到以下情况，基于改进合同网的动态任务分配算法会进行调整，得到最优方案。主要参数设置如下，招标任务阈值a为O.l，投标闽值b为O.l。

5.2.1 Agent数量损失

当执行任务过程中，出现Agent损伤或者无法继续执行任务的情况时，则需要进行动态任务分配。假设Ae无法执行任务时，则将Ae之前执行的任务放入任务中转站中，经算法更新任务分配方案，如图6所示。表6给出各Agent任务集和效能值。与任务的初始分配方案相比，Ae的任务分配给其他有能力的Agent执行，所消耗时间为0.176s。

5.2.2 新目标的发现

当执行任务过程中，发现新的目标需要打击，则需要进行动态任务分配。假设侦察到新目标13，14以及它们的各项参数后，并将这两项任务转入任务中转站，经算法更新任务分配方案，如图7所示。表7给出各Agent任务集和效能值。与任务的初始分配方案相比，新任务目标13，14分配给了Ad，Ae执行，所消耗时间为0.122s。

5.2.3 Agent能力变化

当执行任务过程中，Agent出现能力变化，如对某个目标成功概率降低之类的情况，则需要进行动态任务分配。假设Ad对于目标3的成功概率降低，当执行对目标3打击任务的效能低于招标任务闽值时，则将该任务进行招标，经算法更新任务分配方案，如图8所示。表8给出各Agent任务集和效能值。与任务初始分配方案相比，Ad将对目标3执行的任务招标，Ac中标获得目标3的执行任务权，所消耗时间为0.099s。

5.2.4 Agent数量损失、新目标发现和Agent能力降低同时发生

当执行任务过程，同时发生三种情况。假设Ae损伤或无法执行任务，侦察到新目标13，14以及它们的各项参数，还有Ad对于目标3的成功概率降低，导致执行该任务的效能低于招标任务阈值。将这些任务都转入任务中转站，基于改进合同网的任务分配算法重新更新任务分配方案，如图9所示。表9给出各Agent任务集和效能值。与任务初始分配方案相比，首先Ae的任务集分配给其他有能力的Agent执行，其次将新目标分配给能以更高效能执行任务的Agent，最后Ad将对目标3执行的任务招标，Aa获得执行任务权，所消耗时间为0.161s。

5.3 小结

仿真实验表明，在引入任务中转站以及任务优先级概念后，该算法能够在各种场景变化下快速给出任务分配算法，若按粒子群算法重新得到任務分配算法，所消耗时间为2s以上时，而采用改进合同网的任务分配算法仅耗时0.2s左右，提高了算法求解效率。

6 结论

针对多Agent动态任务分配问题.本文建立了动态任务分配模型，并在传统合同网的基础上，提出改进合同的任务分配算法，引入任务中转站以及任务优先级协助处理任务分配方案，并对算法的招标和投标阶段进行改进，设置了招标任务阈值和投标任务阈值。最后，通过仿真结果验证，该算法能在各种环境变化下，快速更新任务分配方案。

参考文献

[1] Oliveiro E，Fischer K.Multi-agentSystems：Which Research for WhichApplications[J].Robotics andAutonomous Systems， 1999（2 7）：91-106.

[2] C. Hewitt. Viewing controlstructures as patterns of passingmessages [J]. Artificial Intelligence，1997，8 （03）： 323-364.

[3] Alberts，D.S.Network Centric Warfare：Developing and Leveraging InformationSuperiority [M]. Washingt on， DC： CCRPPublications，Aug 1999.

[4]万武南，张蕾.基于任务熟人集的合同网模型的改进[J]，计算机应用，2003，23 （03）：3-5.

[5]龙涛，陈岩，沈林成.基于合同机制的多UCAV分布式协同任务控制[J].航空学报，2007， 28 （02）： 352-357.

[6]裘杭萍，覃垚，胡汭等，多Agent系统中基于改进合同网模型的任务分配研究[J].计算机科学，2012，39 （6A）： 279-281.

[7]C.George.Distributed Systems：Concepts and Design[M].Boston：Addison-Wesley，2011.

[8]霍霄华，陈岩，朱华勇等，多UCAV协同控制中的任务分配模型及算法[J].国防科技大学学报，2006，28 （03）： 83-88.

[9]R.Davis. Negotiation as ametaphor for distributedproblem solving [J]. ArtificialIntelligence，1983 （20）：63-109.

[10]肖玉杰，李杰，刘方等，基于合同网的分布式动态任务分配算法[J].舰船科学技术，2015，37 （03）：113-118.