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

arXiv: https://arxiv.org/abs/2208.01222 · HTML: https://mlsanity.com/paper/2208.01222/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 2 Aug 2022.

## Builds on (most cited first, 9 of 9)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Lifelong Multi-Agent Path Finding in Large-Scale Warehouses](https://mlsanity.com/paper/2005.07371/) (2020)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees](https://mlsanity.com/paper/1401.3905/) (2014)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [Multi-Goal Multi-Agent Path Finding via Decoupled and Integrated Goal Vertex Ordering](https://mlsanity.com/paper/2009.05161/) (2020)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [Multi-Agent Path Finding with Deadlines](https://mlsanity.com/paper/1806.04216/) (2018)

## Built on by (most cited first, 5 of 5)

- [Large-Scale Multirobot Coverage Path Planning on Grids With Path Deconfliction](https://mlsanity.com/paper/2411.01707/) (2024)
- [Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree](https://mlsanity.com/paper/2307.00663/) (2023)
- [GHOST: Solving the Traveling Salesman Problem on Graphs of Convex Sets](https://mlsanity.com/paper/2511.06471/) (2025)
- [ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem](https://mlsanity.com/paper/2404.05223/) (2024)
- [DMS*: Minimizing Makespan for Multi-Agent Combinatorial Path Finding](https://mlsanity.com/paper/2312.06314/) (2023)

## Abstract (arXiv)

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.