Predictive Receding-Horizon Multi-Robot Task Allocation with Moving Tasks*

Abstract

This paper addresses a multi-robot task allocation (MRTA) towards moving tasks and presents a novel computationally efficient predictive allocation algorithm that requires solving a linear program (LP) problem. Following the receding horizon control policy, the present algorithm repeats the optimization of future task assignments within an allocation horizon while predicting the evolution of the system. The online optimization is formulated so that the assignment problem is reduced exactly to an LP. The algorithm is also compared with other traditional methods, namely, the greedy approach and a genetic algorithm (GA). Our results show that the algorithm herein proposed outperforms the greedy approach for small prediction horizons and has significantly lower computational load than GA.