Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding
This addresses the problem of efficiently assigning tasks with sequential goals to multiple agents while avoiding collisions, which is incremental as it builds on existing multi-agent path finding techniques.
The paper tackles the multi-goal task assignment and path finding (MG-TAPF) problem, proving it is NP-hard to solve optimally and presenting algorithms that achieve optimal and bounded-suboptimal solutions, with experimental comparisons on benchmark domains.
We formalize and study the multi-goal task assignment and path finding (MG-TAPF) problem from theoretical and algorithmic perspectives. The MG-TAPF problem is to compute an assignment of tasks to agents, where each task consists of a sequence of goal locations, and collision-free paths for the agents that visit all goal locations of their assigned tasks in sequence. Theoretically, we prove that the MG-TAPF problem is NP-hard to solve optimally. We present algorithms that build upon algorithmic techniques for the multi-agent path finding problem and solve the MG-TAPF problem optimally and bounded-suboptimally. We experimentally compare these algorithms on a variety of different benchmark domains.