Time-Extended Multi-Robot Task Allocation – A Reoptimization Framework with Provable Performance

This work introduces reoptimization approaches with performance guarantees for heterogeneous, time-extended MRTA problems with precedence and synchronization constraints. Reoptimization heuristics and a metaheuristic reoptimization framework are presented for ten relevant problem modifications. An extensive evaluation of the proposed reoptimization approaches clearly indicates their superiority compared to optimization approaches for application in interactive MRTA optimization systems.