Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding
Conference Paper, Proceedings of (ICRA) International Conference on Robotics and Automation, May, 2022
Abstract
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.
BibTeX
@conference{Zhong-2022-131386,author = {Xinyi Zhong and Jiaoyang Li and Sven Koenig and Hang Ma},
title = {Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding},
booktitle = {Proceedings of (ICRA) International Conference on Robotics and Automation},
year = {2022},
month = {May},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.