基于粒子群优化算法的多智能体系统分布式任务分配

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于粒子群优化算法的多智能体系统分布式任务分配范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：本文提出了一种基于粒子群优化并且具备冲突消解能力的多智能体系统分布式任务分配算法。将多项任务分配给多个智能体是一个基础的资源分配问题，这类问题在很多控制和决策系统中出现，例如多机器人系统以及计算机系统。被用于分布式系统中解决此类问题的算法可以看做是一系列步骤，智能体能够利用这些步骤自动周期性地进行信息交换并更新自己的任务。本文提出的算法经过仿真实验验证，仅需要少量的信息交换即可消解智能体之间任务分配的冲突。

关键词：粒子群优化 分布式 任务分配 冲突消解

中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2014）05-0138-02

多智能体系统（Multi-agent system）自90年代起就是一个热点研究课题，到如今这个领域已经有大量的科学成果。相应地，越来越多的多智能体系统应用被引入工厂、实验室甚至普通家庭。同时这些应用的背景也越来越复杂，例如利用机器人搜救队在灾区搜寻生还者。因此，为了保证多智能体系统的鲁棒性，分布式的任务分配算法是必要的。许多学者以及进行了这方面的研究。然而，这些分布式的任务分配算法需要智能体之间进行大量的通信来达到冲突消解的目的。

本文提出的分布式任务分配算法基于粒子群优化算法。该算法仅仅需要少量的通信解决冲突问题，而且粒子群算法本身只用到基础运算法则，计算效率高。

1 粒子群优化

粒子群优化是在1995年由Eberhart和Kennedy提出，这个算法是模仿鸟群智能：当一群年在寻找食物时，他们会倾向于搜索已经有食物被发现的区域。在粒子群算法中，粒子即是“鸟”而各个粒子的位置对应于所求优化问题的一个可行解。同时，每个粒子都有自己的搜索速度，该速度受全局最优解和个体最优解影响。

粒子群算法公式如下：

其中是粒子i在第k次迭代中的速度，和是加速因子，和是在区间（0，1）上的随机数，是粒子i在第k次迭代中的位置，是经过k次迭代以后找到的个体最优解，是经过k次迭代以后找到的全局最优解。

1.1 粒子位置定义

任务分配问题中的可行解往往对应于Agent的编号，即为离散值而不是连续值，因此找到一个合适的粒子位置定义是将粒子群优化应用到任务分配问题中的关键点。本文采用元素均为整数的向量表示粒子的位置。该向量的维度与任务分配问题中的任务数相同，且各个向量中元素代表一个Agent的编号。表1用一个例子解释了上述向量。

根据这个定义，很明显向量中的元素X必须服从约束。

在程序实现中可以将约束表示如下：

1.2 适应度函数

与粒子位置定义相同，要将粒子群优化应用到任务分配问题中适应度函数是不可或缺的。不同的适应度函数会导致不同的pbest和gbest，从而得到不同的最优解。本文采用一种求和函数作为适应度函数，该函数方程如下：

其中表示Agent i完成任务j可以获得的收益，表示任务j是否分配给了Agent i：如果任务j的确是分配给Agent i 的则=1，否则=0。该适应度函数是计算了任务分配方案的收益。根据具体问题需要，有很多其他形式的适应度函数可以使用。

2 冲突检测及消解

由于粒子群优化算法是在各个Agent上分布式完成的，因此各个Agent得出的最优任务分配结果可能会不一致。为了得到一个没有冲突的统一的结果，各个Agent需要将自己的任务分配结果向量以及相应的收益向量发送给其他Agent。当Agent接受收到其他任务分配结果并发现与自己的任务分配结果不同时，各个Agent会根据收益大小来调整自己的任务分配结果：存在冲突的任务将被分配给收益大的Agent。

和适应度函数一样，冲突消解可以根据不同问题采用不同的调整依据。

3 仿真

本文利用Matlab作为仿真实验环境。Agent和任务是随机的分布在一个100100的二位空间内。最大迭代次数=1000，粒子数量P=100，为Agent和任务间距离的函数。

表2是各个Agent利用粒子群优化找到的最优任务分配方案，可以发现大部分任务的分配结果是统一的，仅有一小部分任务分配存在冲突。再利用上一章节中阐述的冲突消解方法进行处理后，三个Agent得到了一个统一的任务分配方案，见表3。

4 结语

本文提出了一种基于粒子群优化算法的多智能体系统分布式任务分配算法。仿真结果表明该算法能使Agent搜索到理想的任务分配方案并利用冲突消解机制使分配方案得到统一。下一步的主要研究方向为任务束：将有共同点的任务集合为一个任务束。从而不再是将单个任务分配给各个Agent，而是将整个任务束进行分配。这将会进一步提高任务分配效率。

参考文献

[1]Choi Han-Lim， Brunet Luc， Jonathan P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Trans on Robotics， 2009， 25（4）： 912-926.

[2]M Fanti， A Mangini， W Ukovich， V Boschian. New consensus protocols for networks with discrete time dynamics[J]. ACC， 2012， 38-43.

[3]M Fanti， A Mangini， G Pedroncelli， W Ukovich. A quantized consensus algorithm for a multi-agent assignment problem[J]. IEEE International Conference， 2013， 1063-1068.

[4]J Capitan， M Spaan， L Merino， A Ollero. Decentralized multi-robot cooperation with auctioned POMDPs[J]. IEEE Int.Conf.Robot.Autom， 2012， 3323-3328.

[5]Aiguo Fei， Luyou Zhang， Gang Liu， Yuan Wang. The Technique for Air-to-Air Missile Guidance Superiority Handover Based on Particle Swarm Auction Hybrid Algorithm[J]. Journal of Astronautics， 2013， 34（3）： 340-346.

[6]Hendrik Skubch. Modelling and controlling of behavior for autonomous mobile robots[M]. Springer， 2012.

[7]Hendrik Skubch， Michael Wagner， Roland Reichle， Kurt Geihs. A modelling language for cooperative plans in highly dynamic domains[J]. Mechatronics， 2011， 21（2）： 423-433.

[8]Bin Di， Rui Zhou， Quanxin Ding. Distributed coordinated heterogeneous task allocation for unmanned aerial vehicles[J]. Control and decision， 2013， 28（2）： 274-278.

[9]Jie Li， Yao Sun. Research on cluster attack mission planning of USVs based on DAMPSO algorithm[J]. Computer Engineering and Applications， 2013， 49（20）： 1-4.

[10]Jiyong Du， Fengming Zhang， Ji Yang， Husheng Wu. Cooperative task assignment for multiple UCAV using particle swarm optimization[J]. Control and decision， 2012， 27（11）： 1751-1755.