# Introducing Delays in Multi-Agent Path Finding

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jul 2023.

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

- [When Agents Break Down in Multiagent Path Finding](https://mlsanity.com/paper/2508.03777/) (2025)

## Abstract (arXiv)

We consider a Multi-Agent Path Finding (MAPF) setting where agents have been assigned a plan, but during its execution some agents are delayed. Instead of replanning from scratch when such a delay occurs, we propose delay introduction, whereby we delay some additional agents so that the remainder of the plan can be executed safely. We show that finding the minimum number of additional delays is APX-Hard, i.e., it is NP-Hard to find a (1+varepsilon)-approximation for some varepsilon>0. However, in practice we can find optimal delay-introductions using Conflict-Based Search for very large numbers of agents, and both planning time and the resulting length of the plan are comparable, and sometimes outperform the state-of-the-art heuristics for replanning.