Multi-Robot Task Allocation with Time Window and Ordering Constraints

Abstract

The multi-robot task allocation problem comprises task assignment, coalition formation, task scheduling, and routing. We extend the distributed constraint optimization problem (DCOP) formalism to allocate tasks to a team of robots. The tasks have time window and ordering constraints. Each robot creates a simple temporal network to maintain the tasks in its schedule. The proposed layered framework, called L-DCOP, forms efficient coalitions among robots to accomplish the tasks more efficiently as a result of their collective abilities. We conduct extensive experiments to assess the performance of the proposed algorithm and compare it against a benchmark auction-based approach. The results show that L-DCOP increases the task completion rate and task completion frequency by 1.7% and 10.1%, respectively, and reduces the task execution time by 52.5% on average.