第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 ·