Efficient Performance Impact Algorithms for Multirobot Task Assignment With Deadlines

This article investigates the multirobot task assignment problem with deadlines, where a group of distributed heterogeneous robots needs to collaborate effectively to first maximize the number of successful search and rescue missions and then minimize the robots' total service time. First, a distributed performance impact algorithm is designed to obtain the initial assignment solution, where each robot can compute its assignment solution independently. Subsequently, based on different local search strategies, a disturbance mechanism and two improvement strategies, namely, first, global task inclusion first and decoupled 1-opt second phase and, second, global task inclusion first and coupled 1-opt second phase, are proposed to disrupt and refine the initial solution. The integration of the distributed performance impact algorithm with the two refinement strategies leads to a decoupled performance impact algorithm and a coupled performance impact algorithm, respectively. Extensive numerical simulations and experiments demonstrate the superior performance of the proposed algorithms compared with the existing performance impact algorithm. If more computational running time is allowed, the resulting coupled task assignment algorithm is recommended, as it consistently provides superior solutions. Conversely, the resulting decoupled task assignment algorithm is used because it can achieve a satisfactory solution within a shorter computation time.