A Distributed Auction Algorithm for Task Assignment With Robot Coalitions

This study addresses the task assignment problem with robot coalitions, as encountered in practical scenarios, such as multiplayer reach-avoid games. Unlike the classical assignment problem where a single robot performs each task, the problem considered here involves tasks that require execution by a robot coalition consisting of two robots. This task assignment problem is a special instance of 3-set packing problem, which is known to be nondeterministic polynomial time (NP)-hard. We introduce the concept of <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-coalition-competitive equilibrium (<inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-CCE) to characterize a kind of approximate solution that offers guaranteed performance. A distributed auction algorithm is developed to find an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula>-CCE within a finite number of iterations. In addition, several enhancements have been implemented to adapt the auction algorithm for practical applications where the task assignment problem may vary over time. Numerical simulations demonstrate that the distributed algorithm achieves satisfactory approximation quality.