第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 是根据 机器人、任务和环境可用的信息即时将任务分配给
·116· 智能系统学报 第3卷 机器人，不带有对将来分配的规划.而TE是有更多 2.2市场机制方法 可用的信息，如要分配的所有任务的集合或如何获 它是一种基于协商主义的任务分配方法，多机 得任务的模型等 器人系统在某种协议基础上通过机器人之间的相互 基于以上3点将MRTA问题分为8类：1)ST- 协商、谈判来完成任务分配.这种方法适合于在任务 SR-IA;2)ST-SR-TE;3)ST-MR-IA;4)ST-MR-TE; 和机器人状态可知的中小规模异构机器人中进行分 5)MT-SR-IA;6)MT-SR-TE;7)MT-MR-IA; 布式问题的协作求解，能够实现全局最优任务分配， 8)MT-MR-TE.其中ST-SR-IA是最简单的一种情 缺点是机器人必须通过显式的通信有意图的协作」 况，可看作是OAP的实例，也是目前研究最多的一 资源消耗较多，一旦通讯中断性能将明显下降].其 类MRTA问题.通常将任务看作是不可分割的原 典型代表是R.Smith提出的合同网).合同网模型 子单元，忽略任务的内部结构，即给定一组任务T、(CNP)由多个可以互相传递信息的结点组成，基本 一组机器人R和每个机器人执行任务的代价函数 思想是按照市场中的招标投标中标机制来完成 cr,找到一个任务分配方案使全局代价函数值最 各结点间的协商过程 小 传统合同网模型存在许多缺点，而且对于什么 然而，只有少数MRTA问题采用纯粹的ST 时候发布任务，如何评价“标的”值从而得到全局最 SRIA一次性分配结构，大多数都采用它的2个变 优解哪些已分配的任务应该再进行拍卖来保持解 形结构：迭代分配(iterated assignment)和在线分配 的质量，什么时候进行再分配和由谁决定再分配，这 (online assignment).在迭代分配结构下每次迭代 些任务分配中不可避免的问题CNP并未解决 中所有任务是同时分配的，其典型代表有ALLF 近年来各种基于合同网的改进方法被广泛应用 ANCE BLE和M+等.而在线分配是串行分配任 到多机器人任务分配中，目前研究最多的是拍卖算 务的，典型的代表有MURDOCH、First-price auc- 法.拍卖算法因其具有可扩展性而特别适合于分布 tions和Dynamic Role Assignment等 式机器人领域，而且理论上能够保证得到任务的最 优分配.但通讯开销大，多次循环方可收敛到平衡 2 任务分配方法 早期的拍卖算法是集中式的，系统中由一个集中的 目前，多机器人任务分配方法主要有基于行为 管理者进行任务拍卖和任务分配，如Caloud等设计 的分配方法、市场机制方法、群体智能方法、基于线 的GOPHER11.目前多采用分布式拍卖算法，系统 性规划的方法、基于情感招募的方法、基于空闲链的 中每个机器人作为自利的agent参与虚拟市场，通 方法等 过拍卖和投标任务进行任务分配.基于拍卖的任务 2.1基于行为的分配方法 分配问题一般分为3步山 基于行为的任务分配算法一般分为3步： 1)每个机器人根据自身执行指定任务的适合度 1)找到一个具有最大效用的机器人任务对 对任务进行投标； (i,) 2)拍卖机制决定将任务分配给哪个机器人： 2)将任务j分配给机器人i,并不再考虑它们： 3)投标获胜的机器人控制器通过执行一个或多 3)回到第1)步 个动作来完成任务 其典型代表有ALL IANCES]和Broadcast of 2.2.1单物品拍卖 Local Eligibility(BLE)II这2种方法都是通过行为 所谓单物品拍卖算法就是对于一个目标点，向 抑制来实现任务分配的，每个机器人对每个任务有 所有的机器人进行拍卖，参与拍卖的机器人根据它 一定的期望度，并且在行为层直接抑制其他机器人 目前所在的位置和目标点之间的距离出价，距离最 的活动.在2005年Parker又提出一个基于行为的 短的机器人将获得任务，并开始执行，其他机器人继 任务分配机制ASyMTRe!),将环境和感知信息映 续参加剩下目标点的拍卖.如First-price auc- 射到行为模式获得所需的信息流，自动地在机器人 tions ,Dynamic role assignment GAO Ping 间重构各种模式间的连接，综合得到完成任务的行 an4等 为 2.2.2组合拍卖 该方法的特点是实时性、容错性和鲁棒性好，但 Behauh提出了组合拍卖的方法s1,采用一个 只能求得局部最优解 简单的例子证明单物品竞拍有得不到全局最优路径 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
机器人 ,不带有对将来分配的规划. 而 TE 是有更多 可用的信息 ,如要分配的所有任务的集合或如何获 得任务的模型等. 基于以上 3 点将 MRTA 问题分为 8 类 :1) ST2 SR2IA ;2) ST2SR2TE ;3) ST2MR2IA ;4) ST2MR2TE ; 5 ) M T2SR2IA ; 6 ) M T2SR2TE ; 7 ) M T2MR2IA ; 8) M T2MR2TE. 其中 ST2SR2IA 是最简单的一种情 况 ,可看作是 OAP 的实例 ,也是目前研究最多的一 类 MRTA 问题. 通常将任务看作是不可分割的原 子单元 ,忽略任务的内部结构 ,即给定一组任务 T、 一组机器人 R 和每个机器人执行任务的代价函数 cr ,找到一个任务分配方案使全局代价函数值最 小[3 ] . 然而 ,只有少数 MRTA 问题采用纯粹的 ST2 SR2IA 一次性分配结构 ,大多数都采用它的 2 个变 形结构 :迭代分配(iterated assignment) 和在线分配 (online assignment) . 在迭代分配结构下每次迭代 中所有任务是同时分配的 ,其典型代表有 ALL I2 ANCE、BL E 和 M + 等. 而在线分配是串行分配任 务的 ,典型的代表有 MURDOCH 、First2price auc2 tions 和 Dynamic Role Assignment 等. 2 任务分配方法 目前 ,多机器人任务分配方法主要有基于行为 的分配方法、市场机制方法、群体智能方法、基于线 性规划的方法、基于情感招募的方法、基于空闲链的 方法等. 2. 1 基于行为的分配方法 基于行为的任务分配算法一般分为 3 步[4 ] : 1) 找到一个具有最大效用的机器人 ———任务对 (i , j) ; 2) 将任务 j 分配给机器人 i ,并不再考虑它们 ; 3) 回到第 1) 步. 其典型代表有 ALL IANCE [5 ] 和 Broadcast of Local Eligibility (BL E) [6 ]这 2 种方法都是通过行为 抑制来实现任务分配的 ,每个机器人对每个任务有 一定的期望度 ,并且在行为层直接抑制其他机器人 的活动. 在 2005 年 Parker 又提出一个基于行为的 任务分配机制 ASyM TRe [7 ] ,将环境和感知信息映 射到行为模式获得所需的信息流 ,自动地在机器人 间重构各种模式间的连接 ,综合得到完成任务的行 为. 该方法的特点是实时性、容错性和鲁棒性好 ,但 只能求得局部最优解. 2. 2 市场机制方法 它是一种基于协商主义的任务分配方法 ,多机 器人系统在某种协议基础上通过机器人之间的相互 协商、谈判来完成任务分配. 这种方法适合于在任务 和机器人状态可知的中小规模异构机器人中进行分 布式问题的协作求解 ,能够实现全局最优任务分配 , 缺点是机器人必须通过显式的通信有意图的协作 , 资源消耗较多 ,一旦通讯中断性能将明显下降[8 ] . 其 典型代表是 R. Smit h 提出的合同网[9 ] . 合同网模型 (CN P) 由多个可以互相传递信息的结点组成 ,基本 思想是按照市场中的招标 —投标 —中标机制来完成 各结点间的协商过程. 传统合同网模型存在许多缺点 ,而且对于什么 时候发布任务 ,如何评价“标的”值从而得到全局最 优解 ,哪些已分配的任务应该再进行拍卖来保持解 的质量 ,什么时候进行再分配和由谁决定再分配 ,这 些任务分配中不可避免的问题 CN P 并未解决. 近年来各种基于合同网的改进方法被广泛应用 到多机器人任务分配中 ,目前研究最多的是拍卖算 法. 拍卖算法因其具有可扩展性而特别适合于分布 式机器人领域 ,而且理论上能够保证得到任务的最 优分配. 但通讯开销大 ,多次循环方可收敛到平衡. 早期的拍卖算法是集中式的 ,系统中由一个集中的 管理者进行任务拍卖和任务分配 ,如 Caloud 等设计 的 GOPHER [10 ] . 目前多采用分布式拍卖算法 ,系统 中每个机器人作为自利的 agent 参与虚拟市场 ,通 过拍卖和投标任务进行任务分配. 基于拍卖的任务 分配问题一般分为 3 步[11 ] : 1) 每个机器人根据自身执行指定任务的适合度 对任务进行投标 ; 2) 拍卖机制决定将任务分配给哪个机器人 ; 3) 投标获胜的机器人控制器通过执行一个或多 个动作来完成任务. 2. 2. 1 单物品拍卖 所谓单物品拍卖算法就是对于一个目标点 ,向 所有的机器人进行拍卖 ,参与拍卖的机器人根据它 目前所在的位置和目标点之间的距离出价 ,距离最 短的机器人将获得任务 ,并开始执行 ,其他机器人继 续参 加 剩 下 目 标 点 的 拍 卖. 如 First2price auc2 tions [ 12 ] ,Dynamic role assignment [13 ]和 GAO Ping2 an [14 ]等. 2. 2. 2 组合拍卖 Behauh 提出了组合拍卖的方法[15 ] ,采用一个 简单的例子证明单物品竞拍有得不到全局最优路径 ·116 · 智 能 系 统 学 报 第 3 卷
第2期 张嵛，等：多机器人任务分配的研究与进展 ·117· 的缺陷，而组合拍卖的方法相比单物品拍卖更容易 也有越来越多的研究者将群体智能方法应用到多机 产生全局较优解.在组合拍卖算法中，机器人不仅可 器人任务分配中，特别是在动态环境下进行任务分 以对一个目标进行投标，还可以将多个目标看作一 配的情况.比较典型的方法有阈值法和蚁群算法 个标来竞标这种方法不仅能够提高拍卖的效率，而 2.3.1阈值法 且还能降低竞标机器人的风险.典型代表是Trad- 阈值法2)的基本思想是通过感知任务的激励 erbots 或需求调节机器人的选择和此任务的反应阈值.其 2.2.3单层拍卖 中每个任务j都有一个激励值5，当机器人i感知 在单层拍卖中，任务被建模成原子单元，不考虑 到任务j的s,超过它的反应阈值0，时，开始执行该 任务的结构性和复杂性.单层拍卖分为3类：1)目标 任务.当y低于，时，机器人停止执行任务 层拍卖(Goal point-level allocation):2)区域层拍卖2.3.2蚁群算法 (Area-level allocation);3)任务层拍卖(Missiom 根据昆虫学家的观察，蚂蚁通过在走过的路径 level allocation).现存的MRTA算法多为单层拍卖 上释放一种信息素来影响其他蚂蚁的运动，当信息 机制，如First-price auctions!2 Dynamic Role As- 素越强，吸引其他蚂蚁走这一路径的概率就越大，从 signment)、Traderbots!6、M+系统)、MUR- 而增加该路径的信息素浓度，这样就会有更多的蚂 DOCHI8I和DEMiR-CFI等 蚁走这条路径.丁滢颖等设计了一种基于蚁群算法 2.2.4任务树拍卖 的多机器人协作任务分配策略]，成功地解决了多 Zot和Stentz提出一种基于任务树拍卖的分 机器人系统在未知环境工作时自主协作规问题 配方法)，打破了以往的“单层”任务拍卖模式.由于 Dandan Zhang等将阈值法和蚁群算法相结合 任务树具有结构性，因此能够表示复杂的任务.参与 提出一种基于群体智能方法的自适应任务分配策 拍卖的机器人可对树中不同层的节点进行拍卖.这 略2】，通过高层简单的自增强学习模型，对不同类 种方法的优点在于将任务分解和规划有效地融入分 型的任务产生稳定、灵活的劳动分工.底层通过应用 配过程中 蚁群算法使机器人协作完成同种类型的任务 2.2.5逆转拍卖 2.4 基于线性规划的方法 现存的拍卖算法都是机器人投标任务，所谓逆 Gerky和Mataric将MRTA问题看作是0l型 转拍卖是任务发起拍卖并投标机器人具有的服务： 整数线性规划问题241 引入服务智能体(service Agents)和任务智能体2 找到斤个非负整数4，最大化 个软件智能体辅助完成拍卖过程，Lovekesh和Julie 提出的RACHNA2o就是一种基于逆转拍卖的联盟 王，2，U4 满足 形成系统！ 2.3群体智能方法 =1,1≤j≤n 近几年来，一些研究者受到社会性昆虫行为的 启发，通过对社会性昆虫的模拟产生了一系列对于 =1.1≤1≤n 传统问题的新的解决方法，即群智能算法.群体智能 它是针对单机器人单任务(single-robot tasks 指的是“无智能的主体通过合作表现出智能行为的 and single-task robots)而言，即一个机器人只能完 特性” 成一个任务，而一个任务只需一个机器人完成，这是 群体智能在没有集中控制并且不提供全局模型 MRTA中最简单的情况.它不能处理一个任务需要 的前提下，为寻找复杂的分布式问题的解决方案提 多个机器人协作完成的情况(multi-ro bot tasks).早 供了基础.由于群体中相互合作的个体是分布的，没 期解决线性规划问题的方法主要是单纯型法和匈牙 有中心的控制与数据，这样系统更具有鲁棒性，不会 利法，这2种方法本质上都是矩阵的运算，当系统中 由于某一个或者某几个个体的故障而影响整个问题 机器人和任务数增多时，运算量呈指数级增长.一些 的求解，而且个体之间通过非直接通信(stimergy) 基于混合整数线性规划的MRTA方法2s2)虽然能 进行合作，所以当系统中个体增加时系统通信开销 够成功找到最优解，但是通常需要收集所有机器人 增加得十分小，使系统具有更好的可扩充性.因此群 和任务的信息，并通过一个集中管理者来处理这些 体智能方法非常适合于分布式多机器人系统，而且 信息，因此扩展性差效率也低.为了提高系统的可扩 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的缺陷 ,而组合拍卖的方法相比单物品拍卖更容易 产生全局较优解. 在组合拍卖算法中 ,机器人不仅可 以对一个目标进行投标 ,还可以将多个目标看作一 个标来竞标. 这种方法不仅能够提高拍卖的效率 ,而 且还能降低竞标机器人的风险. 典型代表是 Trad2 erbots [ 16 ] . 2. 2. 3 单层拍卖 在单层拍卖中 ,任务被建模成原子单元 ,不考虑 任务的结构性和复杂性. 单层拍卖分为 3 类 :1) 目标 层拍卖( Goal point2level allocation) ;2) 区域层拍卖 (Area2level allocation) ; 3) 任务层拍卖 ( Mission2 level allocation) . 现存的 MRTA 算法多为单层拍卖 机制 ,如 First2price auctions [12 ] 、Dynamic Role As2 signment [ 13 ] 、Traderbots [16 ] 、M + 系 统[17 ] 、MU R2 DOCH [ 18 ]和 DEMiR2CF [19 ]等. 2. 2. 4 任务树拍卖 Zlot 和 Stentz 提出一种基于任务树拍卖的分 配方法[3 ] ,打破了以往的“单层”任务拍卖模式. 由于 任务树具有结构性 ,因此能够表示复杂的任务. 参与 拍卖的机器人可对树中不同层的节点进行拍卖. 这 种方法的优点在于将任务分解和规划有效地融入分 配过程中. 2. 2. 5 逆转拍卖 现存的拍卖算法都是机器人投标任务 ,所谓逆 转拍卖是任务发起拍卖并投标机器人具有的服务. 引入服务智能体 (service Agents) 和任务智能体 2 个软件智能体辅助完成拍卖过程. Lovekesh 和 J ulie 提出的 RACHNA [20 ]就是一种基于逆转拍卖的联盟 形成系统. 2. 3 群体智能方法 近几年来 ,一些研究者受到社会性昆虫行为的 启发 ,通过对社会性昆虫的模拟产生了一系列对于 传统问题的新的解决方法 ,即群智能算法. 群体智能 指的是“无智能的主体通过合作表现出智能行为的 特性”. 群体智能在没有集中控制并且不提供全局模型 的前提下 ,为寻找复杂的分布式问题的解决方案提 供了基础. 由于群体中相互合作的个体是分布的 ,没 有中心的控制与数据 ,这样系统更具有鲁棒性 ,不会 由于某一个或者某几个个体的故障而影响整个问题 的求解 ,而且个体之间通过非直接通信 (stimergy) 进行合作 ,所以当系统中个体增加时系统通信开销 增加得十分小 ,使系统具有更好的可扩充性. 因此群 体智能方法非常适合于分布式多机器人系统 ,而且 也有越来越多的研究者将群体智能方法应用到多机 器人任务分配中 ,特别是在动态环境下进行任务分 配的情况. 比较典型的方法有阈值法和蚁群算法. 2. 3. 1 阈值法 阈值法[21 ]的基本思想是通过感知任务的激励 或需求调节机器人的选择和此任务的反应阈值. 其 中每个任务 j 都有一个激励值 sj ,当机器人 i 感知 到任务 j 的 sj 超过它的反应阈值θij 时 ,开始执行该 任务. 当 sj 低于θij时 ,机器人停止执行任务. 2. 3. 2 蚁群算法 根据昆虫学家的观察 ,蚂蚁通过在走过的路径 上释放一种信息素来影响其他蚂蚁的运动 ,当信息 素越强 ,吸引其他蚂蚁走这一路径的概率就越大 ,从 而增加该路径的信息素浓度 ,这样就会有更多的蚂 蚁走这条路径. 丁滢颖等设计了一种基于蚁群算法 的多机器人协作任务分配策略[22 ] ,成功地解决了多 机器人系统在未知环境工作时自主协作规划问题. Dandan Zhang 等将阈值法和蚁群算法相结合 提出一种基于群体智能方法的自适应任务分配策 略[23 ] ,通过高层简单的自增强学习模型 ,对不同类 型的任务产生稳定、灵活的劳动分工. 底层通过应用 蚁群算法使机器人协作完成同种类型的任务. 2. 4 基于线性规划的方法 Gerky 和 Mataric 将 MRTA 问题看作是 021 型 整数线性规划问题[ 24 ] : 找到 n 2 个非负整数αij ,最大化 ∑ n i =1 ∑ n j = 1 αij Uijωj , 满足 ∑ n i = 1 αij = 1 ,1 ≤j ≤n , ∑ n j =1 αij = 1 ,1 ≤i ≤n. 它是针对单机器人单任务 (single2robot tasks and single2task robots) 而言 ,即一个机器人只能完 成一个任务 ,而一个任务只需一个机器人完成 ,这是 MRTA 中最简单的情况. 它不能处理一个任务需要 多个机器人协作完成的情况(multi2robot tasks) . 早 期解决线性规划问题的方法主要是单纯型法和匈牙 利法 ,这 2 种方法本质上都是矩阵的运算 ,当系统中 机器人和任务数增多时 ,运算量呈指数级增长. 一些 基于混合整数线性规划的 MRTA 方法[25228 ] 虽然能 够成功找到最优解 ,但是通常需要收集所有机器人 和任务的信息 ,并通过一个集中管理者来处理这些 信息 ,因此扩展性差效率也低. 为了提高系统的可扩 第 2 期 张 嵛 ,等 :多机器人任务分配的研究与进展 ·117 ·
·118· 智能系统学报 第3卷 展性和效率，Atay和Bayazit提出了一种基于混合 扰；同时大量的计算往往无法满足多移动机器人系 整数线性规划的紧急(emergent)任务分配方法2) 统任务实时性较高的要求.因此，许多研究者提出了 2.5基于情感招募的方法 一些更为有效的方法， 情感(emotion)是自控制(self-regulation)中一 祖丽楠等3川针对系统运行过程中，由于机器人 种有效的机制，己被应用于智能体控制中，但是很少 和任务的相对数量、位置分布关系以及机器人状态 将其应用到机器人群体控制中.情感招募法不需要 发生转换等原因，而出现的任务死锁情况，在上级人 机器人对彼此建模，是一个分布式的分配方法.在机 机交互计算机中设计了一个基于黑板结构的监控机 器人学中应用情感的方式主要有3种：1)使用情感 构，负责监控任务的死锁并进行协调」 建模机器人群体的行为；2)使用情感产生单个机器 柳林等2]给出了任务执行中存在的死锁情况， 人的行为；3)作为人一机器人接口.Aaron Gage等 并通过将任务的偏序关系作为任务分配顺序的方法 提出一种基于情感招募的分配方法0)，主要采用的 有效地避免了死锁的发生.丁滢颖等2针对基于蚁 是前2种方式， 群算法求解任务分配的方法给出了机器人的任务死 2.6基于空闲链的方法 锁定义，针对这种情况在算法中引入衰减因子，有效 现存的多机器人任务分配算法通常不考虑机器 防止了任务死锁的发生 人间相互作用的影响，如干扰(interference)等，而 Dandan ZHANG等221给出了任务死锁发生的条 假设任务是独立的.Dahl将系统中机器人间的相互 件，而且引入等待时间和容忍时间，当等待时间大于 作用考虑在内，提出一种基于空闲链(vacancy 容忍时间时通过降低“感知”信息素避免死锁的产生 chains))的分布式MRTA模型TAVC】,通过在一个 4任务分配算法的比较 组织中创建和填充空位模型化空闲链，该模型能够显 式地处理群动态(group dynamics)的影响，引入任务 4.1 影响算法的因素 处理频率决定哪些机器人可无干扰地同时工作」 对于现存的任务分配方法一般从以下4个方面 进行评价) 3任务死锁与解除 1)计算需求：重要操作重复的次数.对于MR 3.1任务死锁 TA,累加效用值和效用值的比较等都为重要操作. 在多机器人系统中，随着机器人数目的增加，受 2)通讯需求：机器人间通过网络发送消息的总 系统中有限资源的制约，机器人间的冲突呈指数级 数，不考虑消息的大小 增长，严重影响系统的整体性能，甚至发生死锁.目 3)任务分配情况(task consideration) 前多机器人领域中的“任务死锁”并未有统一的定 4)解的质量：采用竞争因子(competitive fac- 义，一般根据具体的任务域和任务分配方法给出不 tor)评价，竞争因子给出了一个算法在最坏情况下 同的定义和解除方法， 的解 3.2死锁的解除 4.2算法比较 若机器人间通过协商来解决任务死锁问题，将 假设有n个机器、m个任务，上述各种方法的性 会产生较大的通信量，增加机器人的通信负载，而且 能比较如表12所示 对机器人硬件要求很高，且容易受到外界环境的干 表1迭代任务分配算法 Ta ble I Iterated task allocation algorithm 名称 计算需求/迭代 通讯需求/迭代 任务分配情况 解的质量 ALL IANCEIS1 O(mn O(m) 同时分配，可重分配 至少2-competitive BLEI6] O(mn) O(mn) 同时分配，可重分配 2-competitive M+ O(m刊 O(mn) 司时分配，不可重分配 2-competitive ASyMTRel7 O(mn) O(mn 同时分配，可重分配 至少2 competitive 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
展性和效率 ,Atay 和 Bayazit 提出了一种基于混合 整数线性规划的紧急(emergent) 任务分配方法[29 ] . 2. 5 基于情感招募的方法 情感(emotion) 是自控制 (self2regulation) 中一 种有效的机制 ,已被应用于智能体控制中 ,但是很少 将其应用到机器人群体控制中. 情感招募法不需要 机器人对彼此建模 ,是一个分布式的分配方法. 在机 器人学中应用情感的方式主要有 3 种 :1) 使用情感 建模机器人群体的行为 ;2) 使用情感产生单个机器 人的行为 ;3) 作为人 —机器人接口. Aaron Gage 等 提出一种基于情感招募的分配方法[ 30 ] ,主要采用的 是前 2 种方式. 2. 6 基于空闲链的方法 现存的多机器人任务分配算法通常不考虑机器 人间相互作用的影响 ,如干扰 (interference) 等 ,而 假设任务是独立的. Dahl 将系统中机器人间的相互 作用 考虑在内 , 提出一 种基于空 闲链 ( vacancy chains) 的分布式 MRTA 模型 TAVC [31 ] ,通过在一个 组织中创建和填充空位模型化空闲链 ,该模型能够显 式地处理群动态(group dynamics) 的影响 ,引入任务 处理频率决定哪些机器人可无干扰地同时工作. 3 任务死锁与解除 3. 1 任务死锁 在多机器人系统中 ,随着机器人数目的增加 ,受 系统中有限资源的制约 ,机器人间的冲突呈指数级 增长 ,严重影响系统的整体性能 ,甚至发生死锁. 目 前多机器人领域中的“任务死锁”并未有统一的定 义 ,一般根据具体的任务域和任务分配方法给出不 同的定义和解除方法. 3. 2 死锁的解除 若机器人间通过协商来解决任务死锁问题 ,将 会产生较大的通信量 ,增加机器人的通信负载 ,而且 对机器人硬件要求很高 ,且容易受到外界环境的干 扰 ;同时大量的计算往往无法满足多移动机器人系 统任务实时性较高的要求. 因此 ,许多研究者提出了 一些更为有效的方法. 祖丽楠等[31 ]针对系统运行过程中 ,由于机器人 和任务的相对数量、位置分布关系以及机器人状态 发生转换等原因 ,而出现的任务死锁情况 ,在上级人 机交互计算机中设计了一个基于黑板结构的监控机 构 ,负责监控任务的死锁并进行协调. 柳林等[32 ]给出了任务执行中存在的死锁情况 , 并通过将任务的偏序关系作为任务分配顺序的方法 有效地避免了死锁的发生. 丁滢颖等[21 ] 针对基于蚁 群算法求解任务分配的方法给出了机器人的任务死 锁定义 ,针对这种情况在算法中引入衰减因子 ,有效 防止了任务死锁的发生. Dandan ZHAN G等[22 ]给出了任务死锁发生的条 件 ,而且引入等待时间和容忍时间 ,当等待时间大于 容忍时间时通过降低“感知”信息素避免死锁的产生. 4 任务分配算法的比较 4. 1 影响算法的因素 对于现存的任务分配方法一般从以下 4 个方面 进行评价[2 ] . 1) 计算需求 :重要操作重复的次数. 对于 MR2 TA ,累加效用值和效用值的比较等都为重要操作. 2) 通讯需求 :机器人间通过网络发送消息的总 数 ,不考虑消息的大小. 3) 任务分配情况(task consideration) . 4) 解的质量 :采用竞争因子 ( competitive fac2 tor) 评价 ,竞争因子给出了一个算法在最坏情况下 的解. 4. 2 算法比较 假设有 n 个机器、m 个任务 ,上述各种方法的性 能比较如表 1、2 所示. 表 1 迭代任务分配算法 Table 1 Iterated task allocation algorithm 名称 计算需求/ 迭代 通讯需求/ 迭代 任务分配情况 解的质量 ALL IANCE [5 ] O( mn) O( m) 同时分配 ,可重分配 至少 22competitive BL E [6 ] O( mn) O( mn) 同时分配 ,可重分配 22competitive M + [17 ] O( mn) O( mn) 同时分配 ,不可重分配 22competitive ASyMTRe [7 ] O( mn) O( mn) 同时分配 ,可重分配 至少 22competitive ·118 · 智 能 系 统 学 报 第 3 卷
第2期 张嵛，等：多机器人任务分配的研究与进展 ·119· 表2在线任务分配算法 Table 2 Online task allocation algorithm 名称 计算需求/任务 通讯需求/任务 任务分配情况 解的质量 0(1)/投标者 MURDOCHUISI 0(d 串行分配，不可重分配 O(m/拍卖者 3-competitive First-price auctions2 01)/投标者 O(n 串行分配，可重分配 O(m/拍卖者 至少3 competitive Dynamic role assignment 01)/投标者 O(n 串行分配，可重分配 0(W/拍卖者 至少3 competitive 01)/投标者 DEMiR-CFU191 O(n 串行分配，可重分配 至少3 competitive O(W/拍卖者 Robotics and Automation,1998,14(2):220-240. 5 结束语 [6]WERGER B,MA TARIC M J.Broadcast of local eligi- 本文综述了国内外学者提出的各种MRTA方 bility:Behavior based control for strongly cooperative 法，并将各种方法进行比较.随着多机器人被应用到 multi-robot teams[C]//Proceedings of Autonomous A- 越来越多的领域中和任务难度的不断加大，静态环 gents.Barcelona,Spain,2000:21-22. [7]TANG Fang,PARKER L E.ASyMTRe:automated 境下的MRTA方法己不能满足实际应用.在未来 synthesis of multi-robot task solution through software 工作中还有许多方面的问题有待于更深入地研究. reconfiguration[Cl//Proc of IEEE International Confer- 主要包括： ence on Robotics and Automation.S.I.]2005:1501- 1)动态环境和未知环境下的任务分配，以及随 1508. 之而来的任务动态分配和再分配问题； [8]KALRA N,MARTINOLI A.A comparative study of 2)完成任务过程中机器人之间相互干扰、冲突 market-based and threshold-based task allocation C]// 等因素； Distributed Autonomous Robotic Systems(DARS).Min- 3)复杂任务的MRTA方法； neapolis,USA,2006. 4)异构大规模MRTA方法， [9]SMITH R G.The contract net protocol high level com- 5)在通讯阻塞或失效的情况下，MRTA方法的 munication and control in a distributed problem solver [J ]IEEE Trans on Computers,1980(6):1104-1113. 研究； [10]CALOUD P,CHOI W,LA TOMBE J C,et al.YIM 6)群动态对MRTA方法的影响； M.Indoor automation with many mobile robots[C]// 7)MRTA建模. Proceedings of the IEEE/RSI International Conference 参考文献： on Intelligent Robots and Systems.[S.1.].1990:67- 72 [1]GERKEY B P.On multirobot task allocation [D].Los [11]MATARIC MJ,SUKHATME G S,OSTERGAARD Angeles:University of Southern California,2003. E H.Multirobot task allocation in uncertain Environ- [2]GER KEY B P,MA TARIC M J.A formal analysis and ments[J ]Autonomous Robots,2003,14(2):255-263. taxonomy of task allocation in multi-robot systems [J ] [12]ZLOT R,STENTZ A,DIAS M B,et al.Multi-robot International Journal of Robotics Research,2004,23 exploration controlled by a market economy [C]//Proc (9):939954. of the IEEE Intl Conf on Robotics and Automation [3]ZLOT R,STEN TZ A.Complex task allocation for mul- (ICRA).Washington,USA,2002:3016-3023. tiple robot [C]//Proc IEEE Int Conf Robot Autom [13]CHAIMOWICZL,CAMPOS M,KUMAR V.Dynam (ICRA).[S.1..2005:15151522. ic role assignment for cooperative robots[C]//In Proc [4]GER KEY B P,MATARIC MJ.Multi-robot task alloca- of the IEEE intl Conf on Robotics and Automation tion:analyzing the complexity and optimality of key ar- (ICRA).Washington,USA,2002:293-298. chitectures[C]//Proceedings of the IEEE International [14]GAO Ping'an.Multi-robot task allocation for explora- Conference on Robotics and Automation.Taiwan,China, tion[J ]Journal CSUT,2006,13(5):548-551. 2003:3862-3868. [15]BETHAUH M,HUANG H,KESKINECAD P.Robot [5]PARKER L E.ALLIANCE:an architecture for fault tol- exploration with combinatorial auctions[C]//Proceed- erant multirobot cooperation [J ]IEEE Transactions on ings of IEEE RSI International Conference on Intelli- 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
表 2 在线任务分配算法 Table 2 Online task allocation algorithm 名称 计算需求/ 任务 通讯需求/ 任务 任务分配情况 解的质量 MURDOCH [18 ] O(1) / 投标者 O( n) / 拍卖者 O( n) 串行分配 ,不可重分配 32competitive First2price auctions [12 ] O(1) / 投标者 O( n) / 拍卖者 O( n) 串行分配 ,可重分配 至少 32competitive Dynamic role assignment [13 ] O(1) / 投标者 O( n) / 拍卖者 O( n) 串行分配 ,可重分配 至少 32competitive DEMiR2CF [19 ] O(1) / 投标者 O( n) / 拍卖者 O( n) 串行分配 ,可重分配 至少 32competitive 5 结束语 本文综述了国内外学者提出的各种 MRTA 方 法 ,并将各种方法进行比较. 随着多机器人被应用到 越来越多的领域中和任务难度的不断加大 ,静态环 境下的 MRTA 方法已不能满足实际应用. 在未来 工作中还有许多方面的问题有待于更深入地研究. 主要包括 : 1) 动态环境和未知环境下的任务分配 ,以及随 之而来的任务动态分配和再分配问题 ; 2) 完成任务过程中机器人之间相互干扰、冲突 等因素 ; 3) 复杂任务的 MRTA 方法 ; 4) 异构大规模 MRTA 方法 ; 5) 在通讯阻塞或失效的情况下 ,MRTA 方法的 研究 ; 6) 群动态对 MRTA 方法的影响 ; 7) MRTA 建模. 参考文献 : [1 ] GER KEY B P. On multi2robot task allocation [ D ]. Los Angeles: University of Southern California , 2003. [2 ] GER KEY B P , MA TARIC M J. A formal analysis and taxonomy of task allocation in multi2robot systems[J ]. International Journal of Robotics Research , 2004 , 23 (9) :9392954. [3 ]ZLO T R , STEN TZ A. Complex task allocation for mul2 tiple robot [ C ]/ / Proc IEEE Int Conf Robot Autom (ICRA) . [ S. l. ]. 2005 : 151521522. [4 ] GER KEY B P , MA TARIC M J. Multi2robot task alloca2 tion : analyzing the complexity and optimality of key ar2 chitectures[ C ]/ / Proceedings of the IEEE International Conference on Robotics and Automation. Taiwan ,China , 2003 : 386223868. [5 ] PAR KER L E. ALL IANCE:an architecture for fault tol2 erant multirobot cooperation [J ]. IEEE Transactions on Robotics and Automation ,1998 ,14 (2) :2202240. [6 ]WERGER B , MA TARIC M J. Broadcast of local eligi2 bility : Behavior based control for strongly cooperative multi2robot teams[ C]/ / Proceedings of Autonomous A2 gents. Barcelona ,Spain ,2000 :21222. [7 ] TAN G Fang , PAR KER L E. ASyMTRe : automated synthesis of multi2robot task solution through software reconfiguration[C]/ / Proc of IEEE International Confer2 ence on Robotics and Automation. [ S. l. ]. 2005 : 15012 1508. [ 8 ] KALRA N , MARTINOL I A. A comparative study of market2based and threshold2based task allocation [ C ]/ / Distributed Autonomous Robotic Systems (DARS) . Min2 neapolis ,USA ,2006. [ 9 ]SMITH R G. The contract net protocol : high level com2 munication and control in a distributed problem solver [J ]. IEEE Trans on Computers ,1980 (6) : 110421113. [10 ]CALOUD P , CHOI W , LA TOMBE J C , et al. YIM M. Indoor automation with many mobile robots[ C]/ / Proceedings of the IEEE/ RSJ International Conference on Intelligent Robots and Systems. [ S. l. ]. 1990 : 672 72. [11 ]MA TARIC M J , SU KHA TME G S , OSTERGAARD E H. Multi2robot task allocation in uncertain Environ2 ments[J ]. Autonomous Robots ,2003 ,14 (2) : 2552263. [12 ]ZLO T R , STEN TZ A , DIAS M B , et al. Multi2robot exploration controlled by a market economy[ C]/ / Proc of the IEEE Intl Conf on Robotics and Automation (ICRA) . Washington ,USA ,2002 :301623023. [ 13 ]CHAIMOWICZ L , CAMPOS M , KUMAR V. Dynam2 ic role assignment for cooperative robots[ C]/ / In Proc of the IEEE intl Conf on Robotics and Automation (ICRA) . Washington ,USA ,2002 : 2932298. [14 ] GAO Ping′an. Multi2robot task allocation for explora2 tion[J ]. Journal CSU T ,2006 ,13 (5) :5482551. [ 15 ]BETHAU H M , HUAN G H , KESKINECAD P. Robot exploration with combinatorial auctions[ C]/ / Proceed2 ings of IEEE/ RSJ International Conference on Intelli2 第 2 期 张 嵛 ,等 :多机器人任务分配的研究与进展 ·119 ·
·120· 智能系统学报 第3卷 gent Robots and Systems.Las Vegas,Nevada,2003: H.Coordination and control of multiple uavs with tim- 1957-1962. ing constraints and loitering[C]//The American Con- [16]DIAS M B.TraderBots:a new paradigm for robust and trol Conference.Denver,Colorado,2003:5311-5316. efficient multirobot coordination in dynamic environ- [28]A TA Y N,BA YAZIT B.Mixed-integer linear program- ments [D].Pittsburgh:Carnegie Mellon University, ming solution to multi-robot task allocation problem, 2004. WUCSE 54[R].Dept of Computer Science and Engi- [17]BOTEL HO S,ALAMI R.M+:a scheme for multi-ro- neering,Washington University in St Louis,2006. bot cooperation through negotiated task allocation and [29]ATA Y N,BA YAZIT B.Emergent task allocation for achievement [C]//Proc IEEE Int Conf Robot Automat. mobile robots through intentions and directives, Detroit,USA,1999:12341239. WUCSE 2[R].Washington:Washington University in [18]GERKEY B P,MA TARIC M J.Sold !auction meth- St Louis,2007. ods for multirobot coordination[J ]IEEE Transactions [30]GAGE A,MURPHY R,VALAVANIS K P,LONG on Robotics and Automation,2002.18(5):758-786. M.Affective task allocation for distributed multi-robot [19]SARIEL S,BALCH T.A distributed multi-robot coop- teams,CRASAR-TR 26[R].Center for Robot Assis- eration framework for real time task achievement [C]// ted Search Rescue,2004. Distributed Autonomous Robotic Systems.Minneapolis, [31]DAHL T S,MATARIC M,SUKHATME G S.Multi- USA,2006:187196 robot task-allocation through vacancy chains[C]//Pro- [20]VIG L,ADAMS J A.Market-based multi-robot coali- ceedings of IEEE International Conference on Robotics tion formation[C]//Proceedings of the 8th Internation- and Automation..[S.1.].2003:22932298. al Symposium on Distributed Autonomous Robotic Sys- [32]祖丽楠，田彦涛，梅吴.大规模多移动机器人合作任务 tems.Minneapolis,USA,2006:227-236. 的分布自主协作系统[U].机器人，2006,28(5)：470 [21]OLIVERRA D,FERREIRA P R,BAZZAZ A L C.A 477. swarm based approach for task allocation in dynamic a ZU Linan,TIAN Yantao,MEI Hao.Distributed au gents organizations[C]//Autonomous Agents and Mul- tonomous cooperation system for the large-scale cooper- tiagent Systems.New York,2004:1252-1253 ation task of multiple mobile robots [J ]Robot,2006, [22]丁潆颖，何衍，蒋静坪.基于蚁群算法的多机器人协作 28(5):470477 策略D].机器人，2003,25(5)：414418 [33]柳林，季秀才，郑志强.基于市场法及能力分类的多机 DING Yingying,HE Yan,JIANG Jingping.Multi-ro- 器人任务分配方法J1.机器人，2006,28(3)：338-343. bot cooperation method based on the ant algorithm [J]. LIU Lin,JI Xiucai,ZHEN G Zhiqiang.Multi-robot Robot,2003,25(5):414418 task allocation based on market and capability classifica- [23 ]ZHAN G Dandan,XIE Guangming,YU Junzhi, tion[0].Robot,2006,28(3):338-343 WANG Long.Adaptive task assignment for multiple 作者简介： mobile robots via swarm intelligence approach[J].Ro- 张嵛，女，1983生，硕士研究生，主 botics and Autonomous Systems,2007,55:572-588. 要研究方向为多移动机器人： [24]GERKEY B P,MATARIC M J.A framework for studying multi-robot task allocation [C]//Proceedings of the Multi-Robot Systems.Washington,USA,2003: 15326. [25]BELLINGHAMJ,TILERSON M,RICHARDS A.et al.Multi-task allocation and path planning for coopera- 刘淑华，女，1970生，副教授，博士，主 ting uavs[C]//Conference on Coordination,Control 要研究方向为多移动机器人智能规划， and Optimization.Gainesville,USA,2001:1-19 [26]SCHUMACHER C,CHANDLR P,PACHTER M,et al.Uav task assignment with timing constraints[C]// AIAA Guidance,Navigation,and Conference and Ex- hibit.Arlington,Texas,2003. [27]ALIGHANBARI M,KUWATA Y,JONATHAN J 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
gent Robots and Systems. Las Vegas , Nevada , 2003 : 19572 1962. [16 ]DIAS M B. TraderBots: a new paradigm for robust and efficient multirobot coordination in dynamic environ2 ments [ D ]. Pittsburgh : Carnegie Mellon University , 2004. [ 17 ]BO TEL HO S , ALAMI R. M + : a scheme for multi2ro2 bot cooperation through negotiated task allocation and achievement[C]/ / Proc IEEE Int Conf Robot Automat. Detroit ,USA ,1999 :12342 1239. [18 ] GERKEY B P , MA TARIC M J. Sold !: auction meth2 ods for multirobot coordination[J ]. IEEE Transactions on Robotics and Automation ,2002 ,18 (5) :7582786. [ 19 ]SARIEL S , BALCH T. A distributed multi2robot coop2 eration framework for real time task achievement[ C]/ / Distributed Autonomous Robotic Systems. Minneapolis , USA ,2006 :1872196. [20 ]VIG L , ADAMS J A. Market2based multi2robot coali2 tion formation[C]/ / Proceedings of the 8th Internation2 al Symposium on Distributed Autonomous Robotic Sys2 tems. Minneapolis ,USA ,2006 : 2272236. [21 ]OL IVERRA D , FERREIRA P R , BAZZAZ A L C. A swarm based approach for task allocation in dynamic a2 gents organizations[C]/ / Autonomous Agents and Mul2 tiagent Systems. New York ,2004 : 125221253. [22 ]丁潆颖 ,何 衍 ,蒋静坪. 基于蚁群算法的多机器人协作 策略[J ]. 机器人 ,2003 , 25 (5) :4142418. DIN G Yingying , HE Yan , J IAN G Jingping. Multi2ro2 bot cooperation method based on the ant algorithm[J ]. Robot , 2003 , 25 (5) :4142418. [23 ]ZHAN G Dandan , XIE Guangming , YU J unzhi , WAN G Long. Adaptive task assignment for multiple mobile robots via swarm intelligence approach [J ]. Ro2 botics and Autonomous Systems ,2007 ,55 :5722588. [24 ] GER KEY B P , MA TARIC M J. A framework for studying multi2robot task allocation [ C]/ / Proceedings of the Multi2Robot Systems. Washington ,USA ,2003 : 15 ∃ 26. [25 ]BELL IN GHAM J , TIL ERSON M , RICHARDS A , et al. Multi2task allocation and path planning for coopera2 ting uavs [ C ]/ / Conference on Coordination , Control and Optimization. Gainesville ,USA ,2001 :1219. [26 ]SCHUMACHER C , CHANDLR P , PACH TER M , et al. Uav task assignment with timing constraints[ C]/ / AIAA Guidance , Navigation , and Conference and Ex2 hibit. Arlington , Texas , 2003. [27 ]AL IGHANBARI M , KUWA TA Y, JONA THAN J H. Coordination and control of multiple uavs with tim2 ing constraints and loitering[ C]/ / The American Con2 trol Conference. Denver ,Colorado ,2003 :531125316. [28 ]A TA Y N , BA YAZIT B. Mixed2integer linear program2 ming solution to multi2robot task allocation problem , WUCSE 54[ R]. Dept of Computer Science and Engi2 neering , Washington University in St Louis , 2006. [29 ]A TA Y N , BA YAZIT B. Emergent task allocation for mobile robots through intentions and directives , WUCSE 2[ R]. Washington : Washington University in St Louis , 2007. [30 ] GA GE A , MURPH Y R , VALAVANIS K P , LON G M. Affective task allocation for distributed multi2robot teams , CRASAR2TR 26 [ R]. Center for Robot Assis2 ted Search & Rescue , 2004. [ 31 ]DA HL T S , MA TARIC M , SU KHA TME G S. Multi2 robot task2allocation through vacancy chains[C]/ / Pro2 ceedings of IEEE International Conference on Robotics and Automation. [ S. l. ]. 2003 : 229322298. [32 ]祖丽楠 ,田彦涛 ,梅 昊. 大规模多移动机器人合作任务 的分布自主协作系统 [J ]. 机器人 , 2006 , 28 (5) : 4702 477. ZU Linan , TIAN Yantao , MEI Hao. Distributed au2 tonomous cooperation system for the large2scale cooper2 ation task of multiple mobile robots[J ]. Robot , 2006 , 28 (5) :4702477. [33 ]柳 林 ,季秀才 ,郑志强. 基于市场法及能力分类的多机 器人任务分配方法[J ]. 机器人 ,2006 ,28 (3) :3382343. L IU Lin , J I Xiucai , ZHEN G Zhiqiang. Multi2robot task allocation based on market and capability classifica2 tion[J ]. Robot , 2006 , 28 (3) :3382343. 作者简介 : 张 嵛 ,女 ,1983 生 ,硕士研究生 ,主 要研究方向为多移动机器人. 刘淑华 ,女 ,1970 生 ,副教授 ,博士 ,主 要研究方向为多移动机器人、智能规划. ·120 · 智 能 系 统 学 报 第 3 卷