计算机科学 ›› 2023, Vol. 50 ›› Issue (2): 244-253.doi: 10.11896/jsjkx.220500117
王积旺, 沈立炜
WANG Jiwang, SHEN Liwei
摘要: 在多机器人环境中,具有不同能力的机器人相互协作以完成任务需求。现实情况下,这些任务动态发布,且具有不同的目标和紧急程度,因此需要为每个任务分解出的细粒度动作分配和调度合适的机器人来负责执行这些动作。现有的方法大多适用于静态和同构的任务分配场景,而针对动态异构任务的分配则大多采用独占式的分配策略,导致机器人频繁进入等待状态(即机器人处于被分配了任务到真正开始执行任务之间的闲置阶段)。由于任务存在不同的紧急程度和发布时间,这种分配方式将降低对更紧急任务的响应效率,同时导致更多的等待时间和更长的任务完成时间。针对该问题,提出了一种面向多机器人环境中动态异构任务的细粒度动作分配与调度方法。其中,分配与调度的对象是任务所分解出的细粒度的动作,且一个动作能够由机器人的一种能力承担。面对任务分解出的一组细粒度动作集合,本方法借鉴拍卖算法过程,根据机器人能力、状态及任务信息计算出机器人承担特定动作的最优分配方案。另外,在每一次新任务发布或某一机器人执行完动作时执行分配和调度过程,可以将处于普通任务等待状态的机器人调度至紧急任务,以保证紧急任务优先完成,且缩短机器人的总体等待时间。基于本方法,扩展实现了机器人执行框架(ROSPlan)的执行模块。围绕一组多机器人动态异构任务的模拟实验表明,所提方法相较于采用贪心策略的方法可得到更优的分配方案。
中图分类号:
[1]FIERRO R,CHAIMOWICZ L,KUMAR V.Multi-robot coope-ration[M]//Autonomous Mobile Robots.CRC Press,2018:417-460. [2]XUE F,DONG T,YOU S,et al.A hybrid many-objective competitive swarm optimization algorithm for large-scale multirobot task allocation problem[J].International Journal of Machine Learning and Cybernetics,2021,12(4):943-957. [3]OTTE M,KUHLMAN M J,SOFGE D.Auctions for multi-robot task allocation in communication limited environments[J].Autonomous Robots,2020,44(3):547-584. [4]CORAH M,O'MEADHRA C,GOELK,et al.Communication-efficient planning and mapping for multi-robot exploration in large environments[J].IEEE Robotics and Automation Letters,2019,4(2):1715-1721. [5]HUANG L,DING Y,ZHOU M C,et al.Multiple-solution optimization strategy for multirobot task allocation[J].IEEE Transactions on Systems,Man,and Cybernetics:Systems,2018,50(11):4283-4294. [6]SHRIYAM S,GUPTA S K.Incorporating potential contingency tasks in multi-robot mission planning[C]//2018 IEEE International Conference on Robotics and Automation(ICRA).IEEE,2018:3709-3715. [7]YAN Z,JOUANDEAU N,CHERIFA A.A survey and analysis of multi-robot coordination[J].International Journal of Advanced Robotic Systems,2013,10(12):399. [8]MOTES J,SANDSTRÖM R,LEEH,et al.Multi-robot task and motion planning with subtask dependencies[J].IEEE Robotics and Automation Letters,2020,5(2):3338-3345. [9]TANG F,PARKER L E.Asymtre:Automated synthesis ofmulti-robot task solutions through software reconfiguration[C]//Proceedings of the 2005 IEEE International Conference on Robotics and Automation.IEEE,2005:1501-1508. [10]DAI W,LU H,XIAO J,et al.Multi-robot dynamic task allocation for exploration and destruction[J].Journal of Intelligent & Robotic Systems,2020,98(2):455-479. [11]YAO L S,SU L Y,LI X P.Research and development of task assignment methods for multi-robot systems[J].Manufacturing Automation,2013,35(10):21-24. [12]KOENIG S,KESKINOCAK P,TOVEY C.Progress on agentcoordination with cooperative auctions[C]//Proceedings of the AAAI Conference on Artificial Intelligence.2010. [13]ZLOT R,STENTZ A.Complex task allocation for multiple robots[C]//Proceedings of the 2005 IEEE International Confe-rence on Robotics and Automation.IEEE,2005:1515-1522. [14]KHAMIS A M,ELMOGY A M,KARRAY F O.Complex task allocation in mobile surveillance systems[J].Journal of Intelligent & Robotic Systems,2011,64(1):33-55. [15]GONG J W,HUANG W N,XIONG G M,et al.Genetic algorithm based combinatorial auction method for multi-robot task allocation[J].Journal of Beijing Institute of Technology,2007,16(2):151-156. [16]VERMA J K,RANGAV.Multi-Robot Coordination Analysis,Taxonomy,Challenges and Future Scope[J].Journal of Intelligent & Robotic Systems,2021,102(1):1-36. [17]SARIEL-TALAY S,BALCH T R,ERDOGAN N.Multipletraveling robot problem:A solution based on dynamic task selection and robust execution[J].IEEE/ASME Transactions on Mechatronics,2009,14(2):198-206. [18]TANG F,PARKER L E.A complete methodology for generating multi-robot task solutions using asymtred and market-based task allocation[C]//Proceedings 2007 IEEE International Conference on Robotics and Automation.2007:3351-3353. [19]GERKEY B P,MATARIĆ M J.A formal analysis and taxonomy of task allocation in multi-robot systems[J].The International Journal of Robotics Research,2004,23(9):939-954. [20]ZLOT R,STENTZ A.Complex task allocation for multiple robots[C]//Proceedings of the 2005 IEEE International Confe-rence on Robotics and Automation.IEEE,2005:1515-1522. [21]CHEN J P,YANG Y M,WU Y B.Multi-robot task allocation based on robotic utility value and genetic algorithm[C]//2009 IEEE International Conference on Intelligent Computing and Intelligent Systems.2009:256-260. [22]ZHENG T,YANG L.Optimal ant colony algorithm based multi-robot task allocation and processing sequence scheduling[C]//2008 7th World Congress on Intelligent Control and Automation.2008:5693-5698. [23]WERGER B B,MATARIĆ M J.Broadcast of local eligibility for multi-target observation[M]//Distributed Autonomous Robotic Systems 4.Tokyo:Springer,2000:347-356. [24]BOTELHO S C,ALAMIR.M+:a scheme for multi-robot cooperation through negotiated task allocation and achievement[C]//Proceedings 1999 IEEE International Conference on Robotics and Automation.IEEE,1999:1234-1239. [25]ZHANG Y,LIU S H.Research and progress of multi-robot task assignment[J].Journal of Intelligent Systems,2008,3(2):115-120. [26]PARKER L E.ALLIANCE:An architecture for fault tolerant,cooperative control of heterogeneous mobile robots[C]//Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems(IROS'94).IEEE,1994:776-783. [27]GERKEY B P,MATARIĆ M J.Sold!:auction methods for multirobot coordination[J].IEEE Trans.Robotics Autom,2002,18:758-768. [28]ZLOT R,STENTZ A,DIAS M B,et al.Multi-robot exploration controlled by a market economy[C]//Proceedings 2002 IEEE International Conference on Robotics and Automation.2002:3016-3023. [29]SCHNEIDER E,SKLAR E I,PARSONS S,et al.Auction-based task allocation for multi-robot teams in dynamic environments[C]//Conference Towards Autonomous Robotic Systems.Cham:Springer,2015:246-257. [30]SEENU N,CHETTY R M K,RAMYA M M,et al.Review on state-of-the-art dynamic task allocation strategies for multiple-robot systems[J].Ind.Robot,2020,47:929-942. [31]HAN Y,LI D,CHEN J,et al.A multi-robots task allocation algorithm based on relevance and ability with group collaboration[J].International Journal of Intelligent Engineering and Systems,2010,3:33-41. [32]ELANGO M,NACHIAPPAN S.Balancing multi-robot prioritized task allocation:A simulation approach[C]//2011 IEEE International Conference on Industrial Engineering and Enginee-ring Management.2011:1725-1729. [33]DAS G P,MCGINNITY T M,COLEMAN S,et al.A distributed task allocation algorithm for a multi-robot system in healthcare facilities[J].Journal of Intelligent & Robotic Systems,2015,80:33-58. [34]ELSEFY A E.A task decomposition using(hdec-posmdps) approach for multi-robot exploration and fire searching[J].Journal of Robotics And Mechatronics,2020,7:22-30. [35]ZHENG H,WANG Y.A distributed framework for dynamictask allocation of multi-robot symbolic motion planning[C]//2019 American Control Conference(ACC).2019:3291-3296. [36]XU Y G.An overview of the economic theory of auctions[J].Economic Research,2006,175(3):1605-1615. [37]CASHMORE M,FOX M,LONG D,et al.Rosplan:Planning in the robot operating system[C]//Proceedings of the Interna-tional Conference on Automated Planning and Scheduling.2015. [38]JIANG H N,ZHANG S,LIN Y F,et al.Simulation Optimization and Testing Based on Gazebo of MPI Distributed Paralle-lism[J].Computer Science,2021,48(S2):672-677. [39]LI S P,HAN J B,LU B F,et al.Research on Grasping Techno-logy of Cooperative Robot Guided by Vision[J].Journal of Chongqing Technology and Business University(Natural Science Edition),2022,39(1):42-48. |
[1] | 李虎, 方宝富. 基于积极团队情感基调的情感机器人协作任务分配拍卖算法 Emotional Robot Collaborative Task Assignment Auction Algorithm Based on Positive GroupAffective Tone 计算机科学, 2020, 47(4): 169-177. https://doi.org/10.11896/jsjkx.190900188 |
[2] | 李方伟, 黄旭, 张海波, 刘开健, 贺晓帆. D2D网络中基于分簇的无线资源分配机制 Cluster-based Radio Resource Allocation Mechanism in D2D Networks 计算机科学, 2018, 45(9): 123-128. https://doi.org/10.11896/j.issn.1002-137X.2018.09.019 |
[3] | 武航,钱丽萍,陈庆章. 蜂窝网络分布式中继选择算法 Distributed Relay Selection Algorithms for Cellular Networks 计算机科学, 2016, 43(8): 55-59. https://doi.org/10.11896/j.issn.1002-137X.2016.08.011 |
[4] | 邵杰,杜丽娟,杨静宇. XCSG在多机器人强化学习中的应用 Applications of XCSG in Multi-robot Reinforcement Learning 计算机科学, 2013, 40(8): 249-251. |
[5] | 肖国宝,严宣辉. 一种新型协作多机器人路径规划算法 New Cooperative Multi-robot Path Planning Algorithm 计算机科学, 2013, 40(4): 217-220. |
[6] | 余伶俐,焦继乐,蔡自兴. 一种多机器人任务规划算法及其系统实现 Multi-robot Mission Planning Algorithm and its System Implementation 计算机科学, 2010, 37(6): 252-255. |
|