Repeated Sequential Single-Cluster Auctions with Dynamic Tasks for Multi-Robot Task Allocation with Pickup and Delivery

In this paper we study an extension of the multi-robot task allocation problem for online tasks requiring pickup and delivery. We extend our previous work on sequential single-cluster auctions to handle this more complex task allocation problem. Our empirical experiments analyse this technique in the domain of an environment with dynamic task insertion. We consider the trade-off between solution quality and overall planning time in globally reallocating all uncompleted tasks versus local replanning upon the insertion of a new task. Our key result shows that global reallocation of all uncompleted tasks outperforms local replanning in minimising robot path distances.