A distributed method for dynamic multi-robot task allocation problems with critical time constraints

被引:86
作者
Chen, Xinye [1 ]
Zhang, Ping [1 ]
Du, Guanglong [1 ]
Li, Fang [1 ]
机构
[1] South China Univ Technol, Sch Comp Sci & Engn, Guangzhou 510006, Guangdong, Peoples R China
基金
中国国家自然科学基金;
关键词
Adaptive system; Distributed task allocation; Multi-robot system; Overall objective; ALGORITHM; COORDINATION; ASSIGNMENT; SEARCH;
D O I
10.1016/j.robot.2019.04.012
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper considers the task allocation problems in a distributed multi-robot system under critical time constraints. Considering the requirement of distributed computing, many existing distributed heuristic task allocation approaches tend to trap in local optimal and cannot obtain high-quality solutions. For a dynamic task allocation problem in a multi-robot system, not only the task information and the robot state may be subject to changes, but also the network status. That is, robots that each robot can communicate with may change over time, and sometimes there may even be no robots that it can communicate with. To solve these problems, a dynamic grouping allocation method is proposed. It builds upon the state-of-the-art consensus-based auction algorithms, extending them in both task inclusion phase and consensus phase. First, a cluster-first strategy and a task inclusion procedure that can be easily applied to the task inclusion phase of the algorithms are proposed, so that the solution quality of each iteration of the algorithms are significantly improved with a reasonable amount of computation. In addition, to increase the exploration capabilities, a proportional selection method is used in the task inclusion procedure when it is likely to trap in a local optimal. Second, the block-information-sharing strategy is used to avoid the possible conflicts that dynamic changes may bring. Numerical simulations demonstrate that the proposed method can provide conflict-free solutions in dynamic environments and can achieve outstanding performance in comparison with the state-of-the-art algorithms. (C) 2019 Elsevier B.V. All rights reserved.
引用
收藏
页码:31 / 46
页数:16
相关论文
共 52 条
[1]   One-to-One Coordination Algorithm for Decentralized Area Partition in Surveillance Missions with a Team of Aerial Robots [J].
Acevedo, Jose J. ;
Arrue, Begona C. ;
Miguel Diaz-Banez, Jose ;
Ventura, Inmaculada ;
Maza, Ivan ;
Ollero, Anibal .
JOURNAL OF INTELLIGENT & ROBOTIC SYSTEMS, 2014, 74 (1-2) :269-285
[2]   Non-additive multi-objective robot coalition formation [J].
Agarwal, Manoj ;
Kumar, Naveen ;
Vig, Lovekesh .
EXPERT SYSTEMS WITH APPLICATIONS, 2014, 41 (08) :3736-3747
[3]  
Alighanbari M, 2005, IEEE DECIS CONTR P, P5668
[4]  
Alireza T. S., 2007, ALL C COMM CONTR COM
[5]  
[Anonymous], 2011, P AIAA INF AER C
[6]  
Ayorkor Korsah G., 2011, THESIS
[7]  
Basu S., 2002, P INT C MACH LEARN, P27
[8]   THE AUCTION ALGORITHM FOR ASSIGNMENT AND OTHER NETWORK FLOW PROBLEMS - A TUTORIAL [J].
BERTSEKAS, DP .
INTERFACES, 1990, 20 (04) :133-149
[9]   Decentralized task allocation for surveillance systems with critical tasks [J].
Binetti, Giulio ;
Naso, David ;
Turchiano, Biagio .
ROBOTICS AND AUTONOMOUS SYSTEMS, 2013, 61 (12) :1653-1664
[10]   A grouping genetic algorithm for the multiple traveling salesperson problem [J].
Brown, Evelyn C. ;
Ragsdale, Cliff T. ;
Carter, Arthur E. .
INTERNATIONAL JOURNAL OF INFORMATION TECHNOLOGY & DECISION MAKING, 2007, 6 (02) :333-347