# Optimal Multi-Agent Path Finding for Precedence Constrained Planning Tasks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 4 of its 28 references that are in the map.
- First posted on arXiv 8 Feb 2022.

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

- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [Cooperative Multi-Agent Path Finding: Beyond Path Planning and Collision Avoidance](https://mlsanity.com/paper/2105.10993/) (2021)

## Abstract (arXiv)

Multi-Agent Path Finding (MAPF) is the problem of finding collision-free paths for multiple agents from their start locations to end locations. We consider an extension to this problem, Precedence Constrained Multi-Agent Path Finding (PC-MAPF), wherein agents are assigned a sequence of planning tasks that contain precedence constraints between them. PC-MAPF has various applications, for example in multi-agent pickup and delivery problems where some objects might require multiple agents to collaboratively pickup and move them in unison. Precedence constraints also arise in warehouse assembly problems where before a manufacturing task can begin, its input resources must be manufactured and delivered. We propose a novel algorithm, Precedence Constrained Conflict Based Search (PC-CBS), which finds makespan-optimal solutions for this class of problems. PC-CBS utilizes a Precedence-Constrained Task-Graph to define valid intervals for each planning task and updates them when precedence conflicts are encountered. We benchmark the performance of this algorithm over various warehouse assembly, and multi-agent pickup and delivery tasks, and use it to evaluate the sub-optimality of a recently proposed efficient baseline.