Solving multi-goal task assignment and path finding problem with a Single Constraint Tree
Xianzhe Xu, Quan Yin, Yuqi Fu, Mengqiang Yu · 2024
This paper formalize and study the Multi-Goal Task Assignment and Path Finding (MG-TAPF) problem from both theoretical and algorithmic perspectives. The MG-TAPF problem involves determining an assignment scheme for tasks to agents, where each task comprises a series of target locations, and planning collision-free paths for agents to successfully complete the assigned tasks. In this work, we propose the ITA-CBS-MLA algorithm that builds upon CBS-TA-MLA, which aims to find optimal solutions for the MG-TAPF problem. Furthermore, we introduce expanded versions of the algorithm to handle diverse scenarios that may arise in practice. Comprehensive experimental evaluations are conducted on various benchmarks to compare the performance of these algorithms.