  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.
