# Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 41 references that are in the map.
- First posted on arXiv 2 Jul 2023.

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

- [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)
- [Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2110.14891/) (2021)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [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)
- [Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution](https://mlsanity.com/paper/2109.04264/) (2021)
- [MS*: A New Exact Algorithm for Multi-agent Simultaneous Multi-goal Sequencing and Path Finding](https://mlsanity.com/paper/2103.09979/) (2021)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [A Conflict-Based Search Framework for Multi-Objective Multi-Agent Path Finding](https://mlsanity.com/paper/2101.03805/) (2021)

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

- [ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem](https://mlsanity.com/paper/2404.05223/) (2024)
- [Accelerating Focal Search in Multi-Agent Path Finding with Tighter Lower Bounds](https://mlsanity.com/paper/2503.03779/) (2025)
- [Alternating Target-Path Planning for Scalable Multi-Agent Coordination](https://mlsanity.com/paper/2605.07744/) (2026)

## Abstract (arXiv)

Combined Target-Assignment and Path-Finding problem (TAPF) requires simultaneously assigning targets to agents and planning collision-free paths for agents from their start locations to their assigned targets. As a leading approach to address TAPF, Conflict-Based Search with Target Assignment (CBS-TA) leverages both K-best target assignments to create multiple search trees and Conflict-Based Search (CBS) to resolve collisions in each search tree. While being able to find an optimal solution, CBS-TA suffers from scalability due to the duplicated collision resolution in multiple trees and the expensive computation of K-best assignments. We therefore develop Incremental Target Assignment CBS (ITA-CBS) to bypass these two computational bottlenecks. ITA-CBS generates only a single search tree and avoids computing K-best assignments by incrementally computing new 1-best assignments during the search. We show that, in theory, ITA-CBS is guaranteed to find an optimal solution and, in practice, is computationally efficient.