Auction-Based Task Allocation and Motion Planning for Multi-Robot Systems with Human Supervision

This paper presents a task allocation strategy for a multi-robot system with a human supervisor. The multi-robot system consists of a team of heterogeneous robots with different capabilities that operate in a dynamic scenario that can change in the robots’ capabilities or in the operational requirements. The human supervisor can intervene in the operation scenario by approving the final plan before its execution or forcing a robot to execute a specific task. The proposed task allocation strategy leverages an auction-based method in combination with a sampling-based multi-goal motion planning. The latter is used to evaluate the costs of execution of tasks based on realistic features of paths. The proposed architecture enables the allocation of tasks accounting for priorities and precedence constraints, as well as the quick re-allocation of tasks after a dynamic perturbation occurs –a crucial feature when the human supervisor preempts the outcome of the algorithm and makes manual adjustments. An extensive simulation campaign in a rescue scenario validates our approach in dynamic scenarios comprising a sensor failure of a robot, a total failure of a robot, and a human-driven re-allocation. We highlight the benefits of the proposed multi-goal strategy by comparing it with single-goal motion planning strategies at the state of the art. Finally, we provide evidence for the system efficiency by demonstrating the powerful synergistic combination of the auction-based allocation and the multi-goal motion planning approach.