# Multi-Agent Path Finding with Deadlines

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Jun 2018.

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

- [Answer Set Planning: A Survey](https://mlsanity.com/paper/2202.05793/) (2022)
- [Graph-Based Multi-Robot Path Finding and Planning](https://mlsanity.com/paper/2206.11319/) (2022)
- [Optimal and Bounded-Suboptimal Multi-Goal Task Assignment and Path Finding](https://mlsanity.com/paper/2208.01222/) (2022)
- [A Competitive Analysis of Online Multi-Agent Path Finding](https://mlsanity.com/paper/2106.11454/) (2021)
- [DPLL(MAPF): an Integration of Multi-Agent Path Finding and SAT Solving Technologies](https://mlsanity.com/paper/2111.06494/) (2021)
- [Multi-Agent Path Finding via Tree LSTM](https://mlsanity.com/paper/2210.12933/) (2022)
- [Optimal Integrated Task and Path Planning and Its Application to Multi-Robot Pickup and Delivery](https://mlsanity.com/paper/2403.01277/) (2024)

## Abstract (arXiv)

We formalize Multi-Agent Path Finding with Deadlines (MAPF-DL). The objective is to maximize the number of agents that can reach their given goal vertices from their given start vertices within the deadline, without colliding with each other. We first show that MAPF-DL is NP-hard to solve optimally. We then present two classes of optimal algorithms, one based on a reduction of MAPF-DL to a flow problem and a subsequent compact integer linear programming formulation of the resulting reduced abstracted multi-commodity flow network and the other one based on novel combinatorial search algorithms. Our empirical results demonstrate that these MAPF-DL solvers scale well and each one dominates the other ones in different scenarios.