Efficient Heuristic Algorithm for Precedence-Constrained Multi-Robot Task Assignment

Abstract

Due to the widespread application of multi-robot systems, the efficient task assignment for a team of robots has become particularly critical for performing complex tasks. This paper studies the task assignment problem for multiple robots to visit a group of target locations with precedence constraints, which determine the order/sequence in which certain target locations need to be visited before others. A marginal-cost-based heuristic algorithm is developed to minimize the time for the robots to visit the last target location. The algorithm first uses a timestamp strategy to update the anticipated visiting time of each assigned target and the corresponding earliest time that each successor target can be visited under the precedence constraints. Then, it utilizes the topological sorting technique andthe marginal-cost-based mechanism to insert the feasible target that induces the minimum marginal cost into the robots’ current routes. Numerical simulations demonstrate the effectiveness of the proposed algorithm compared with the popular greedy algorithm and the existing simple iterative auction algorithm.