多机器人系统任务分配方式的研究与发展

么立双，苏丽颖，李小鹏

（北京工业大学 机电学院，北京 100124）

0 引言

面对复杂的环境与任务，与单机器人相比，多机器人系统具有许多优越性：完成任务效率高、完成任务复杂程度高、信息传递速度快、定位信息准确、系统鲁棒性好以及优化解决问题方案。

著名多机器人系统研究专家Lynne E。Parker从七个方面总结了多机器人系统领域的主要研究内容及亟待解决的问题[1,2]。这七个方面包括：任务分配、动作选择、协调及控制结构；物体运输、操作及构建；通信及感知；运动协调；学习；可重构及可建模机器人；协作定位及地图构建。多机器人系统在完成复杂环境探索任务时，合理选择任务分配机制能大大提高环境探索的效率，是机器人建立环境及完成各种复杂智能任务的关键，在实际应用中具有重要意义。协作定位及地图构建是路径规划、完成复杂环境探索任务的基础。动作选择等研究领域是多机器人系统的自动化和智能化的重要标志。因此，对整个多机器人系统来讲，在协作探索未知环境的过程中，任务分配问题是优化多机器人系统能效的一个重要环节，如何提高任务分配效率是多机器人任务分配研究的关键问题[3,4]。

1 多机器人系统任务分配的问题描述

要使多个机器人共同完成一项任务，首先就要解决该项任务的分解、分配、以及资源的利用等问题。多机器人任务分配问题（MRTA）可定义为：给定一个多机器人系统、一个任务集合以及系统性能评价指标，为每个子任务寻找一台合适的机器人负责执行该子任务，且使得机器人系统执行完任务集合中的全部任务时所获得的受益达到最大。任务分配问题是机器人协作的一个关键问题，它直接影响到机器人之间是否会发生任务冲突、空间冲突以及冲突的程度，直接影响到多机器人系统完成任务的效率。

在静态环境中，机器人要探索的环境信息固定，且信息量相对较少，各机器人之间通信内容以子任务信息和静态环境信息为主。如果以系统完成全部侦察任务所需要移动的路径总长度作为评价分配的最优指标，那么多机器人协同侦察多个目标点的任务分配问题可归结为求解一般形式（各移动体的起点、终点不一定相同）的多旅行商问题[5]（MTSP）。多旅行商问题作为一个纯数学问题难度大、复杂程度高。通常只针对多旅行商问题的传统形式——旅行商问题（TSP）进行讨论。

在动态环境中，由著名学者Brian和Mataric首先提出了动态任务分配问题[6]。该问题可描述为：多机器人系统不确定任务出现的时间和空间位置，且工作环境具有动态不确定性和不完整性等，此时机器人探测任务的分配问题更为复杂。1）各机器人之间的通信内容不但有子任务信息，还包括实时变化的动态环境信息，这就给机器人之间的通信带来了一个通信瓶颈问题。合理选择任务分配机制，能有效缓解带宽压力，降低通信代价，提高探索动态环境的效率。2）任何一个机器人随时都有可能遇到突发状况，在总任务集合不变的条件下，分配到该机器人的子任务要根据环境的变化实现实时改变，这就要求任务分配机制具备实时更新子任务的能力。

无论静态环境，还是动态环境多机器人任务分配的环境都具有以下特点：机器人在执行任务的过程中发现新任务，即任务分配是一种动态任务分配过程；机器人所执行的任务具有优先级差别；任务的分布具有资源聚集区的特征。

2 任务分配机制的主要类型

任务分配机制与系统的协作与协调机制、组织结构、通讯机制、感知及学习等多方面的因素相关，任务分配问题具有多方面的属性特征，可根据不同属性需要从不同方面划分任务分配问题的类型[7,8]。

根据多机器人系统结构中有无中央控制机器人，可将多机器人系统任务分配机制分为集中式任务分配机制和分布式任务分配机制。静态环境中，采用集中式任务分配机制，可得到任务分配的最优解。而对于动态环境，每个机器人所需探测的环境信息量及机器人之间通信量大大增加，集中式任务分配机制不再适合该情况，因此可采用分布式任务分配机制。

2.1 集中式任务分配机制

2.1.1 集中式任务分配方法的一般式

在多机器人任务分配发展最初阶段，大多采用集中式任务分配机制。在该机制中，有一个中央控制机器人，它主要负责收集环境信息，并将任务分割成多个子任务，然后分配给各个机器人。

Burgard、Simmons[9,10]等提出一种基于边界的集中式任务分配机制的协作探测方法。该方法中首先设置一个负责收集地图信息与合成全局地图的中央机器人。然后，在全局地图上找出边界并确定目标点，通过集中式算法可以得到使得总体花费最小的分配方案。最后将任务分配结果下达给各个机器人。如此不断更新地图信息直至全局地图能够覆盖整个探索区域。利用该方法可得到全局最优分配结果，但中央机器人承担复杂计算量和通信量，且鲁棒性差。

集中式任务分配机制实现了机器人个体之间运动的紧密协调和最优协调，但是也存在以下缺点：在任务分配时，该机制以牺牲中央机器人自主性为代价；在执行任务过程中，中央机器人一旦出现故障，要求系统必须立即重新设置一个新的中央机器人，否则整个机器人群体可靠性将无法得到保障。不能充分体现多机器人系统的鲁棒性好的特点。当多机器人系统内机器人数量越多时，系统性能就越低，其容错性也就越差。

2.1.2 基于蚁群法的任务分配方式

为解决集中式任务分配机制的上述缺点，意大利学者Dorigo提出一种蚁群算法，并将其成功应用于规划问题和求解组合最优化问题[11]。蚁群算法（ACA）是基于信息素的个体行为协调机制，是一种新型的启发式、分布式协作寻优算法，也被称为蚁群优化算法（ACO）。若以系统完成全部任务所需路径总长作为最优评价指标，则实现最优分配的难点在于子机器人移动路径长度、任务分布与路径规划之间的相互影响，而路径规划问题就是组合优化问题TSP的一般形式。

在基于蚁群算法的任务分配机制中，应考虑以下五个因素[12～14]：路径最短优先原则；信息素量浓度最高优先原则；完成任务时间最短优先原则；任务重要性优先原则及擅长任务优先原则。

在与理想环境不同的条件下，充分考虑任务执行时间，可用最大时间最小。改进的蚁群算法能够得到最优解，但是其并不适用于机器人数已知的任务规划问题，因此蚁群算法还有改进的空间。余伶俐[15]等人提出一种改进蚁群算法解决任务分配问题。该方法首先是用预定阈值和信息素矩阵建立解集，通过计算得到城市图权值和集中式分配中心，并以计算所得的目标函数值作为标准选择一组最优解，再通过局部搜索重新计算城市权值和聚类中心，用这组最优解更新信息素矩阵，并保留本次任务分配所得到的最优解。

姜健在其博士学位论文中提出一种排斥信息素型蚁群算法（PR-ACA）[16]。采用排斥信息素作为任务分配的信息介质，信息素存储的数据信息结构以放射状的节点结构代替经典蚁群算法的图结构。与吸引信息素方法相比，排斥信息素更能减少因机器人过于集中而造成的空间冲突加剧，且在信息素增加的同时能阻止任务聚集区机器人的增加。该算法能够在机器人数量较多的情况下有效减少机器人的空间冲突，并且实现了多机器人搜集任务的自主分配。

刘晓莹等将正交和混沌融入蚁群算法中，提出正交混沌蚁群算法[17]。正交试验法是解决多因素、多水平实验问题的方法，它利用正交表安排试验，对方案作最优设计。而混沌特性是指先产生一组混沌变量（其变量数目与优化变量数目相同），用载波方式将混沌引入优化变量，使其呈现混沌状态，将混沌运动遍历范围放大到优化变量取值范围，利用混沌变量直接搜索。根据正交试验法对任务目标进行聚类，再用混沌特性初始化，能有效改进个体质量，抑制早熟和停滞，降低系统陷入局部最优的概率。

丁滢颍等在基于蚁群算法的多机器人协调过程中加入自适应衰减因子[18]。当衰减因子减小时，信息素值减小，其下一步选择该任务的概率也随之减小，机器人将执行其他任务。在基于蚁群算法的多机器人协作过程中，引入衰减因子可有效防止系统死锁。

2.2 分布式任务分配机制

为体现多机器人系统鲁棒性好的优势，大部分多机器人系统采用分布式构架。分布式任务分配的方法主要有市场法和基于免疫系统的方法。

2.2.1 市场法

市场法定义为：多机器人系统采用全分布式方法，只有目标信息由机器人共享，而机器人间的协作通过投标来体现。机器人根据本地地图计算得到目标点的花费，并将其作为投标价格。根据市场经济充分竞争规律，标将由出价最低的机器人获得，若其他机器人投标价格均高于底价或无法计算该花费，则该点由发现它的机器人获得。若该点已被另一机器人，则它将通知提交的机器人取消该点。当机器人拥有多个目标点时，以花费最小为目标点，即当前目标点。市场法采用公开拍卖机制进行任务分配，每个机器人都可当拍卖主，因此整个构架是分布式的。利用市场法实现任务分配的过程可分为任务发布、任务评价及投标、投标评估及合同授权、合同建立及终止[19]。市场法让机器人个体间竞争以满足自身利益最大化，其积累效果是整个系统的利益。

分布式系统鲁棒性好，易容错。机器人之间只需要传递标与投标信息，大大减少了机器人之间通信量和计算量，无需考虑NP-Hard问题。与集中式任务分配方法不同的是：它没有中央机器人与全局地图，每个目标点就是一个目标，目标信息包括目标点位置和该机器人到该点的花费（即标的底价）；它不需要预先掌握有关其它机器人的信息，易实现动态分布式任务分配。

Zlot[20]等成功的将市场经济机制用于解决多机器人协作探索问题。然而原始的市场法，也存在一定局限性，比如在基于市场法探索未知环境的大多数的情况下，每个机器人个体单独取得标，使得机器人之间的协作产生一定的局限性。

张飞等针对多个机器人如何充分利用有限通信信息完成环境探测的问题，提出了一种改进的市场法以实现多机器人探索的任务分配[21]。该方法利用标的信息，使用数据融合中的Bayes统计方法更新本地地图。该方法有效解决了市场法中计算代价的局限性，并且不会增加额外的通信量。Lovekesh[22]基于市场法提出了一种用于解决搜集、推物体、目标跟踪和岗哨执勤4种级别机器人的任务分配策略。沿用了传统的任务分配方法，并提出了任务一致性以及各种任务之间机器人的数量分配等新问题。

2.2.2 免疫系统法

为更好地解决个别机器人失效或者通讯信息丢失问题，生物免疫系统逐渐受到人们关注。在机器人领域，可将基于生物免疫系统的人工免疫系统（AIS）应用于机器人的路径规划[7]和多机器人协作[23]。

Jerne在免疫独特网络假说[24]指出免疫系统中B细胞产生的抗体非独立存在，每个抗体上有抗体决定基因、抗原决定基因，抗体通过抗体决定基因接受抗原及其它抗体的正向刺激而浓度提高，通过抗原决定基因接受其它抗体的抑制而浓度下降。因此，Farmer[25]提出计算抗体的机理水平及浓度的动态方程。

人工免疫法是通过模拟生物免疫系统而产生的人工智能方法。基于免疫系统的任务分配方法是采用人体免疫系统作为协作机制，它是没有中央控制器的分布式任务分配协作机制。系统中各机器人的角色是免疫细胞，根据抗原和抗体、抗体和抗体间的相互作用，组成自我保护和自我维持的生命体系，使系统自主选择合适的抗体消灭抗原。机器人自主选择合适的探测点，利用机器人间的相互协作提高环境探测效率，并适应动态变化的环境。

Jun等人利用生物免疫系统分布式机理，提出一种基于人工免疫系统来实现多机器人的群体作业的算法[26]。算法中设定一个抗体间的作用系数，以影响机器人之间的相互协调。

高云园等人针对未知环境的完全探测提出一种基于免疫的探测算法[27]。利用类似蚁群激素的概念，用边界点记忆和遗忘来实现完全探测。机器人在探测过程中留下激素作为局部环境信息，传感器感知的局部环境信息（障碍物和局部激素信息）为探测中抗原信息。环境栅格包括障碍物、已探测和未探测三种状态。以机器人上下左右四个邻近栅格作为目标栅格，产生四个抗体。该算法在抗原值和抗体作用系数上进行改进，抗原综合考虑成本和效益，并实现巧妙避障，充分发挥了系统在探测环境时的自主性、协作性和鲁棒性等优势，提高系统探测环境的效率。

除上述方法外，分布式任务分配的协作机制还有政治体制进行覆盖和探索的方法。虽然分布式的结果不一定是最优，但当团队中有部分机器人失效或通讯信息丢失时，整个系统依然能较好地完成任务。这充分体现了多机器人系统鲁棒性好的特点。

3 研究中存在的问题与发展趋势

任务分配问题是多机器人协调与协作领域范围内首先要解决的关键问题。无论是在静态，还是在动态环境中，只有合理利用任务分配算法，才能提高多机器人系统环境探测效率，使得整个系统在完成全部任务时获得最大收益。本文围绕多机器人系统的任务分配问题，总结了不同环境中多机器人系统任务分配机制算法。虽然多机器人系统在许多领域取得了很大进展，但也存在很多需要进一步深入研究的问题。

静态环境中，集中式分配机制对中央机器人要求较高，其一旦出现故障，整个系统将处于瘫痪状态。因此改进集中式任务分配算法，降低多机器人协调过程中的通信信息量，同时在机器人的基础硬件上进行改进，提高通信网络的带宽，使得多机器人系统在静态环境中能够高效完成环境探索任务。

在解决多机器人任务分配问题的过程中，人们往往将解决问题的关键步骤放在如何降低任务总执行成本和提高机器人系统的总收益，而常常忽视如何降低每个机器人平均完成子任务时间。在今后研究过程中，可以考虑通过降低每个机器人平均完成子任务时间来提高整个机器人系统总体收益。在动态环境下，为保证移动机器人满足实时性的要求，任务分配也应具有实时性。

4 结束语

本文在查阅大量文献基础上，综述了多机器人任务分配的研究领域。在多机器人协调与协作探索未知环境的过程中，如何提高任务分配效率是多机器人任务分配研究的关键问题。本文对任务分配问题的分类、适用范围以及优缺点进行了归纳总结。

针对这些研究内容，分析了存在的问题，并在此基础上对该领域未来的发展趋势进行了展望。

[1] Parker L E.Current research in multi-robot systems[J].Artif i cial Life and Robotics,2003,7(2):1-5.

[2] Parker L E,et al.Status of robotics in the U. S. workshop.national science foundation.Washington, D C,2004.

[3] Gordon D M.The organization of work in social insect colonies[J].Nature,1996,380:121-124.

[4] Parker L E.Multiple Mobile Robot Systems.Siciliano B,et al.Handbook of Robotics,Springer.2008:921-941.

[5] 蔡自兴等.多移动机器人协同原理与技术[M].北京:国防工业出版社,2011:73.

[6] Gerkey B P,et al.A analysis and taxonomy of task allocation in multi-robot systems[J].International Journal of Robotics Research,2004,23(9):939-954.

[7] Gerkey B P,et al.A framework for studying multi-robot task allocation[J].In Proceedings of Multi-robot Systems:From Swarms to Intelligent Automata.Netherhands,Kluwer Academic Publishers,2003.2:15-26.

[8] Dudek G,et al.Taxonomy for multi-agent robotics[J].Autonomous Robots,1996,3(4):375-397.

[9] Burgard W,et al.Collaborative multi-robot exploration[C].IEEE International Conference on Robotics and Automation(ICRA).San Francisco:IEEE Press,2000:476-481

[10] Simmons R， et al.Coordination for multi-robot exploration and mapping[C].In Proceedings of the National Conference on Artif i cal Intelligence.Austin,2000:852-858.

[11] Gambardella L M,et al:A reinforcement learning approach to the traveling sales man problem[C].Proceedings of the Twelfth International Conference on Machine Learning.Palo Alto, CA,1994:252-260.

[12] 万旭等.改进的最大最小蚁群算法在有时间窗车辆路径问题中的应用[J].计算机集成制造系统,2005,11(4):572-576.

[13] Dror M.Note on the complexity of the shortest path models for column generation in VRPTW[J].Operations Research,1994,42(5):977-978.

[14] 任韶萱.蚁群算法在多机器人协作中的应用[J].沈阳理工大学学报.2011,(05):49-53.

[15] 余伶俐等.一种多机器人任务规划算法及其系统实现[J].计算机科学.2010,(06):258-261.

[16] 姜健.多移动机器人协作方法研究[D].哈尔滨:哈尔滨工业大学,2008:56.

[17] 刘晓莹等.一种正交混沌蚁群算法在群机器人任务规划中的应用研究[J].小型微型计算机系统.2010,(1):166-170.

[18] 丁滢颍等.基于蚁群算法的多机器人协作策略[J].机器人.2003,(5):31-35.

[19] 赵慧静.面向任务的多移动机器人体系结构优化的研究[D].沈阳:沈阳理工大学,2010:21.

[20] Zlot R,et,al.Multi-robot exploration controlled by a market economy[C].proceedings of the IEEE International Conference on Robotics and Automation(ICRA).Washington:IEEE Press,2002:3016-3023.

[21] 张飞等.多机器人协作探索的改进市场法[J].控制与决策.2005,(05):37-41.

[22] Lovekesh V, et al.Market-based multi-robot coalition formation.Proceedings of the 8th International Symposium on Distributed Autonomous Robotic Systems[C].Paul,Minnesota,USA,2006:1-10.

[23] Parker L E,et al.Cooperative robot teams applied to the site preparation task[C].Atlanta,USA:Proc of 10th International Conference on Advanced Robotics.IEEE Press,2001:71-77.

[24] Jerne N K.Idiotopic networks and other preconceived ideas[J]. Immunological Review,1984,79:5-24.

[25] Farmer J D, et al.The immune system,adaptation,and machine learning[J].Physica,1986,22(1):187-204.

[26] Jun J H,et al.Realization of cooperative strategies and swarm behavior in distributed autonomous robotic systems using artif i cial immune system[C].Proceedings of the IEEE International Conference on Systems,Man and Cybernetics.Tokyo,Japan,1999:614-619.

[27] 高云园,韦巍.基于免疫机理的多机器人未知环境完全探测研究[J].模式识别与人工智能.2007,(2):51-57.