Collision-free allocation of temporally constrained tasks in multi-robot systems

Multi-robot systems (mRs) are a reference solution for many prominent real-world applications, e.g. management of warehouses or exploration of unknown environments. One of the most fundamental computational problems in MRS is that of planning the assignment of tasks to robots when such tasks have deadlines, i.e. constraints on when the execution must take place.The problem, when multiple objective functions of interest need to be optimized, is both NP-Hard and hard to approximate, and few heuristics are known in the literature to handle it. Unfortunately, none of them guarantees that the trajectories used by the robots when moving between tasks' locations are collision-free at planning time. Rather, they implement a reactive behavior, i.e. they abort the execution of a planned task whenever something goes wrong, e.g. trajectories of robots intersect or a deadline is missed due to some obstacle. This approach induces negative effects on the global performance of the system in the form of waste of energy, due to high distances traveled by the fleet members, or in the form of high convergence time to execute tasks. Therefore, planning the assignments of temporally constrained tasks with the guarantee of avoiding collisions can be a desirable feature for multi-robot systems.In this paper, we present CFAT-D (Collision-Free Allocation of Tasks having Deadlines), a new algorithm that can allocate temporally constrained tasks while guaranteeing that used trajectories are collision-free at planning time. We prove CFAT-D to be correct and showcase its effectiveness through an extensive experimental evaluation. Finally, we provide a roadmap toward the practical implementation of the new strategy in real-world environments. (C) 2019 Elsevier B.V. All rights reserved.