# Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Sep 2021.

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

- [Improved Anonymous Multi-Agent Path Finding Algorithm](https://mlsanity.com/paper/2312.10572/) (2023)
- [Solving Multi-Agent Target Assignment and Path Finding with a Single Constraint Tree](https://mlsanity.com/paper/2307.00663/) (2023)
- [Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2401.04003/) (2024)
- [Multi-Agent Path Finding with Real Robot Dynamics and Interdependent Tasks for Automated Warehouses](https://mlsanity.com/paper/2408.14527/) (2024)
- [Fairness in Multi-Agent Planning](https://mlsanity.com/paper/2212.00506/) (2022)
- [ITA-ECBS: A Bounded-Suboptimal Algorithm for the Combined Target-Assignment and Path-Finding Problem](https://mlsanity.com/paper/2404.05223/) (2024)
- [Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints](https://mlsanity.com/paper/2402.08772/) (2024)
- [Solving Multi-Agent Multi-Goal Path Finding Problems in Polynomial Time](https://mlsanity.com/paper/2512.22171/) (2025)
- [Alternating Target-Path Planning for Scalable Multi-Agent Coordination](https://mlsanity.com/paper/2605.07744/) (2026)

## Abstract (arXiv)

Real-time planning for a combined problem of target assignment and path planning for multiple agents, also known as the unlabeled version of Multi-Agent Path Finding (MAPF), is crucial for high-level coordination in multi-agent systems, e.g., pattern formation by robot swarms. This paper studies two aspects of unlabeled-MAPF: (1) offline scenario: solving large instances by centralized approaches with small computation time, and (2) online scenario: executing unlabeled-MAPF despite timing uncertainties of real robots. For this purpose, we propose TSWAP, a novel sub-optimal complete algorithm, which takes an arbitrary initial target assignment then repeats one-timestep path planning with target swapping. TSWAP can adapt to both offline and online scenarios. We empirically demonstrate that Offline TSWAP is highly scalable; providing near-optimal solutions while reducing runtime by orders of magnitude compared to existing approaches. In addition, we present the benefits of Online TSWAP, such as delay tolerance, through real-robot demos.