第3卷第2期 智能系统学报 Vol.3№2 2008年4月 CAAI Transactions on Intelligent Systems Apr.2008 多机器人任务分配的研究与进展 张嵛，刘淑华 (东北师范大学计算机学院，吉林长春130117) 摘要：从多机器人任务分配的类型任务分配方法、任务的死锁与解除以及各种任务分配算法的对比等4个方面， 对多机器人任务分配的最新研究进展进行了概述.分析了多机器人任务分配的发展趋势，指出动态环境和未知环境 下大规模异构机器人任务分配问题的研究是必然趋势，在众多研究方法中，群体智能方法是解决该类问题的未来研 究方向 关键词：多机器人；任务分配；拍卖算法，群体智能 中图分类号：TP242文献标识码：A文章编号：16734785(2008)02-011506 Survey of multrrobot task allocation ZHANG Yu,LIU Shurhua (School of Computer Science,Northeast Normal University,Changchun 130117,China) Abstract:This paper summarizes the latest developments in multi-robot task allocation,including catego- ries of task allocation,methods of task allocation,task deadlock,and its elimination.In addition,trends in methodologies for multi-robot task allocation are analyzed and compared.Our analysis shows that large- scale task allocation for heterogeneous ro bots is a major research area and swarm intelligence will be a good choice to solve this kind of task allocation. Key words :multi-robot;task allocation;auction algorithm;swarm intelligence 多机器人任务分配问题MRTA(multi-ro bot解，但是存在着很多缺点，如不能求解未知环境和动 task allocation)是多机器人系统研究的一个基础问态环境下的任务分配问题等.随着分布式人工智能 题，体现了系统高层组织形式与运行机制，是多机器的不断发展，分布式任务分配方法以其突出的柔性、 人系统实现目标的基础.一方面，任务分配的好坏直 鲁棒性和高效性受到越来越多的关注.与集中式方 接影响整个系统的效率，并且直接关系到系统中各 法相比，分布式任务分配方法能够更快得到解，但是 机器人是否能最大限度发挥自身的能力，避免占用 多为近似最优解 更多的资源：另一方面，当一个机器人没有能力完成 当前任务时，如何在现有机制的基础上，通过有效的 1多机器人任务分配的分类 对话、协商使多机器人合作完成此项任务已经成为 Gerkey基于以下3方面来描述MRTA问 越来越多研究者关注的问题 题： 多机器人任务分配问题可以看作是最优分配问 1)单任务机器人(ST)与多任务机器人(MT): 题(OAP)、整数线性规划问题、调度问题、网络流问 ST是指每个机器人最多只能执行一个任务，而MT 题和组合优化问题早期的多机器人任务分配方 是一些机器人可同时执行多个任务. 法多为集中式的，由一个管理者(leader)负责分配 2)单机器人任务(SR)与多机器人任务(MR): 任务给系统中其他机器人，虽然可以得到全局最优 SR是指每个任务只需要一个机器人完成，MR是指 些任务需要多个机器人完成. 收稿日期：2007-0907. 3)即时分配(IA)与扩展分配(TE):IA是根据 基金项目：国家自然科学基金资助项目(60573067)， 通讯作者：刘淑华，上mail:liush129@126,com. 机器人、任务和环境可用的信息即时将任务分配给 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net第 3 卷第 2 期 智 能 系 统 学 报 Vol. 3 №. 2 2008 年 4 月 CAA I Transactions on Intelligent Systems Apr. 2008 多机器人任务分配的研究与进展 张 嵛 ,刘淑华 (东北师范大学 计算机学院 ,吉林 长春 130117) 摘 要 :从多机器人任务分配的类型、任务分配方法、任务的死锁与解除以及各种任务分配算法的对比等 4 个方面 , 对多机器人任务分配的最新研究进展进行了概述. 分析了多机器人任务分配的发展趋势 ,指出动态环境和未知环境 下大规模异构机器人任务分配问题的研究是必然趋势 ,在众多研究方法中 ,群体智能方法是解决该类问题的未来研 究方向. 关键词 :多机器人 ; 任务分配 ; 拍卖算法 ; 群体智能 中图分类号 : TP242 文献标识码 :A 文章编号 :167324785 (2008) 0220115206 Survey of multi2robot task allocation ZHAN G Yu , L IU Shu2hua (School of Computer Science , Northeast Normal University , Changchun 130117 ,China) Abstract :This paper summarizes t he latest developments in multi2robot task allocation , including catego2 ries of task allocation , methods of task allocation , task deadlock , and its elimination. In addition , trends in met hodologies for multi2robot task allocation are analyzed and compared. Our analysis shows t hat large2 scale task allocation for heterogeneous robots is a major research area and swarm intelligence will be a good choice to solve this kind of task allocation. Keywords :multi2robot ; task allocation ; auction algorithm ; swarm intelligence 收稿日期 :2007209207. 基金项目 :国家自然科学基金资助项目(60573067) . 通讯作者 :刘淑华. E2mail :liush129 @126. com. 多机器人任务分配问题 MRTA ( multi2robot task allocation) 是多机器人系统研究的一个基础问 题 ,体现了系统高层组织形式与运行机制 ,是多机器 人系统实现目标的基础. 一方面 ,任务分配的好坏直 接影响整个系统的效率 ,并且直接关系到系统中各 机器人是否能最大限度发挥自身的能力 ,避免占用 更多的资源 ;另一方面 ,当一个机器人没有能力完成 当前任务时 ,如何在现有机制的基础上 ,通过有效的 对话、协商使多机器人合作完成此项任务已经成为 越来越多研究者关注的问题. 多机器人任务分配问题可以看作是最优分配问 题(OAP) 、整数线性规划问题、调度问题、网络流问 题和组合优化问题[1 ] . 早期的多机器人任务分配方 法多为集中式的 ,由一个管理者 (leader) 负责分配 任务给系统中其他机器人 ,虽然可以得到全局最优 解 ,但是存在着很多缺点 ,如不能求解未知环境和动 态环境下的任务分配问题等. 随着分布式人工智能 的不断发展 ,分布式任务分配方法以其突出的柔性、 鲁棒性和高效性受到越来越多的关注. 与集中式方 法相比 ,分布式任务分配方法能够更快得到解 ,但是 多为近似最优解. 1 多机器人任务分配的分类 Gerkey 基于以下 3 方面来 描述 MRTA 问 题[2 ] : 1) 单任务机器人 (ST) 与多任务机器人 (M T) : ST 是指每个机器人最多只能执行一个任务 ,而 M T 是一些机器人可同时执行多个任务. 2) 单机器人任务 (SR) 与多机器人任务 (MR) : SR 是指每个任务只需要一个机器人完成 ,MR 是指 一些任务需要多个机器人完成. 3) 即时分配 (IA) 与扩展分配 ( TE) : IA 是根据 机器人、任务和环境可用的信息即时将任务分配给