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

doi:10.11896/jsjkx.220500117

Abstract

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

CLC Number:

TP311

WANG Jiwang, SHEN Liwei. Fine-grained Action Allocation and Scheduling Method for Dynamic Heterogeneous Tasks in Multi-robot Environments[J].Computer Science, 2023, 50(2): 244-253.

References

[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.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed

Comments

Recommended 0

No Suggested Reading articles found!

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

PDF (PC)

Abstract

Cite this article

share this article

References

Related Articles 4

Metrics

Comments

Recommended 0

[1]	LI Hu, FANG Bao-fu. Emotional Robot Collaborative Task Assignment Auction Algorithm Based on Positive GroupAffective Tone [J]. Computer Science, 2020, 47(4): 169-177.
[2]	SHAO Jie,DU Li-juan and YANG Jing-yu. Applications of XCSG in Multi-robot Reinforcement Learning [J]. Computer Science, 2013, 40(8): 249-251.
[3]	XIAO Guo-bao and YAN Xuan-hui. New Cooperative Multi-robot Path Planning Algorithm [J]. Computer Science, 2013, 40(4): 217-220.
[4]	YU Ling-li,JIAO Ji-le,CAI Zi-xing. Multi-robot Mission Planning Algorithm and its System Implementation [J]. Computer Science, 2010, 37(6): 252-255.