Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding

Xinyi Zhong, Jiaoyang Li, Sven Koenig, Hang Ma

20222022 International Conference on Robotics and Automation (ICRA)23 citationsDOI

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.

Topics & Concepts

Task (project management)Bounded functionBenchmark (surveying)Sequence (biology)Path (computing)Computer scienceMathematical optimizationAssignment problemWeapon target assignment problemVariety (cybernetics)Generalized assignment problemAlgorithmTheoretical computer scienceOptimization problemMathematicsArtificial intelligenceGeographyGeneticsGeodesyMathematical analysisBiologyEconomicsManagementProgramming languageRobotic Path Planning AlgorithmsFormal Methods in VerificationSoftware Testing and Debugging Techniques