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

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.