计算机科学 ›› 2023, Vol. 50 ›› Issue (2): 244-253.doi: 10.11896/jsjkx.220500117

• 人工智能 • 上一篇    下一篇

面向多机器人环境中动态异构任务的细粒度动作分配与调度方法

王积旺, 沈立炜   

  1. 复旦大学计算机科学技术学院 上海 201203
    上海市数据科学重点实验室(复旦大学) 上海 201203
  • 收稿日期:2022-05-16 修回日期:2022-07-05 出版日期:2023-02-15 发布日期:2023-02-22
  • 通讯作者: 沈立炜(shenliwei@fudan.edu.cn)
  • 作者简介:(fdwjw@qq.com)
  • 基金资助:
    上海市级科技重大专项(2021SHZDZX0100)

Fine-grained Action Allocation and Scheduling Method for Dynamic Heterogeneous Tasks in Multi-robot Environments

WANG Jiwang, SHEN Liwei   

  1. School of Computer Science,Fudan University,Shanghai 201203,China
    Shanghai Key Laboratory of Data Science(Fudan University),Shanghai 201203,China
  • Received:2022-05-16 Revised:2022-07-05 Online:2023-02-15 Published:2023-02-22
  • Supported by:
    Shanghai Science and Technology Major Special Project(2021SHZDZX0100)

摘要: 在多机器人环境中,具有不同能力的机器人相互协作以完成任务需求。现实情况下,这些任务动态发布,且具有不同的目标和紧急程度,因此需要为每个任务分解出的细粒度动作分配和调度合适的机器人来负责执行这些动作。现有的方法大多适用于静态和同构的任务分配场景,而针对动态异构任务的分配则大多采用独占式的分配策略,导致机器人频繁进入等待状态(即机器人处于被分配了任务到真正开始执行任务之间的闲置阶段)。由于任务存在不同的紧急程度和发布时间,这种分配方式将降低对更紧急任务的响应效率,同时导致更多的等待时间和更长的任务完成时间。针对该问题,提出了一种面向多机器人环境中动态异构任务的细粒度动作分配与调度方法。其中,分配与调度的对象是任务所分解出的细粒度的动作,且一个动作能够由机器人的一种能力承担。面对任务分解出的一组细粒度动作集合,本方法借鉴拍卖算法过程,根据机器人能力、状态及任务信息计算出机器人承担特定动作的最优分配方案。另外,在每一次新任务发布或某一机器人执行完动作时执行分配和调度过程,可以将处于普通任务等待状态的机器人调度至紧急任务,以保证紧急任务优先完成,且缩短机器人的总体等待时间。基于本方法,扩展实现了机器人执行框架(ROSPlan)的执行模块。围绕一组多机器人动态异构任务的模拟实验表明,所提方法相较于采用贪心策略的方法可得到更优的分配方案。

关键词: 多机器人, 动态异构任务, 动作分配与调度, 拍卖算法, ROSPlan

Abstract: In a multi-robot environment,robots with different capabilities collaborate with each other to complete task requirements.Realistically,these tasks are dynamically issued and can have different goals and urgency levels,so it is necessary to allocate and schedule the appropriate robots responsible for executing the fine-grained actions decomposed for each task.Most of the existing approaches are suitable for static and homogeneous task allocation scenarios,while most of the dynamic heterogeneous tasks are assigned using exclusive allocation strategies,which causes the robot to frequently enter into waiting states(i.e.,robots are in the idle phase between being assigned a task and actually starting to execute it).Since tasks vary in urgency levels and release times,this allocation method will reduce the efficiency of response to more urgent tasks,while leading to longer waiting time and task completion time.To address this problem,this paper proposes a fine-grained action allocation and scheduling method for dynamic heterogeneous tasks in a multi-robot environment.In this paper,the object of allocation and scheduling is a fine-grained action decomposed by a task,and an action can be undertaken by one capability of a robot.Faced with a set of fine-grained actions decomposed by the task,this method draws on the auction algorithm process to calculate the optimal allocation scheme for a robot to undertake a specific action based on the robot capabilities,state and task information.In addition,by executing the allocation and scheduling process at each new task release or when a robot finishes executing an action,robots in the general task waiting state can be scheduled to the urgent task to ensure the priority completion of the urgent task and reduce the overall waiting time of the robot.Based on this approach,the execution module ROSPlan is extended and implemented.Simulation experiments around a set of multi-robot dynamic heterogeneous tasks show that the proposed methodr can obtain a better allocation scheme compared to the method using greedy policies.

Key words: Multi-robot, Dynamic heterogeneous tasks, Action allocation and scheduling, Auction algorithms, ROSPlan

中图分类号: 

  • TP311
[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.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!