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

2022/08/02 by Zhong, Xinyi, Li, Jiaoyang, Koenig, Sven +1 · 2 citations
#Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Multiagent Systems (cs.MA) #Robotics (cs.RO)

paper · doi:10.48550/arxiv.2208.01222

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.

Cited by

• GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets
• Collaborative Task Assignment, Sequencing and Multi-agent Path-finding

Related

• Optimal Target Assignment and Path Finding for Teams of Agents
• Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints
• MGCBS: An Optimal and Efficient Algorithm for Solving Multi-Goal Multi-Agent Path Finding Problem
• Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering
• Collaborative Task Assignment, Sequencing and Multi-agent Path-finding