Multi-Agent Path Finding with Stochastic Execution Delays

26 concepts17 papers1 proposal

In the idealized formulation of Multi-Agent Path Finding (MAPF), agents are perfectly synchronized, clockwork entities. They occupy discrete grid cells and transition between adjacent locations in uniform, deterministic time steps. As surveyed by Boyarski et al. in Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges, this mathematical abstraction allows optimal solvers to find paths for hundreds of agents by treating space and time as discrete coordinates.

However, when these plans are deployed on physical hardware—such as warehouse robots or autonomous vehicles—the abstraction shatters. Real-world execution is inherently messy. Mechanical slippage, sensor glitches, communication lags, and dynamic obstacles introduce unexpected, stochastic delays (Ma et al. in Multi-Agent Path Finding with Delay Probabilities; Su in Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution). Empirical validations on physical platforms, such as the Ozobot experiments conducted by Barták et al. in Multi-Agent Path Finding on Ozobots, demonstrate that ignoring these variations leads to severe performance degradation, system deadlocks, or catastrophic collisions.

The Mechanics of Failure: How Delays Propagate

Why does a minor execution delay cause a system-wide failure? In a standard MAPF plan, safety guarantees are tied to specific timestamps. If Agent A is scheduled to pass through cell $(X, Y)$ at $t=5$, and Agent B is scheduled to enter it at $t=6$, their safety depends entirely on Agent A clearing the cell on time.

Idealized Timeline:
Agent A: [--- Cell (X,Y) ---]
Agent B:                     [--- Cell (X,Y) ---]
Result: Safe (No overlap)

Stochastic Delay Timeline:
Agent A: [--- Stutter ---] [--- Cell (X,Y) ---]
Agent B:                   [--- Cell (X,Y) ---]
Result: COLLISION at Cell (X,Y)

As Atzmon et al. point out in Probabilistic Robust Multi-Agent Path Finding, these small deviations do not remain isolated; they propagate through the multi-agent network. A single delayed agent forces trailing agents to halt, creating a cascade of delays that can culminate in system-wide deadlocks. This discrepancy between theoretical models and physical execution is known as the reality gap (Chan et al. in The League of Robot Runners Competition: Goals, Designs, and Implementation).

To bridge this gap, researchers have developed methodologies that move away from rigid, deterministic schedules. These solutions fall into three main paradigms: proactive robustness, reactive plan graphs, and continuous-time modeling.

Proactive Robustness: Planning for Uncertainty

Instead of treating delays as anomalies, proactive algorithms incorporate execution uncertainty directly into the offline planning phase.

Bounded Time Uncertainty

The authors of Safe Multi-Agent Pathfinding with Time Uncertainty (Shahar et al.) introduce the MAPF-TU framework. Here, edge traversal times are not fixed integers but are bounded within an interval $[t_{min}, t_{max}]$. Instead of checking for conflicts at a single timestamp, the conflict-based search algorithm ($CBS_{TU}$) ensures that the time windows during which two agents occupy the same physical location never overlap. The resulting paths are guaranteed to remain collision-free for any execution duration within those bounds.

Probabilistic Robustness

When worst-case bounds are too conservative, planners can optimize for expected distributions. Atzmon et al. propose $p$-robustness in Probabilistic Robust Multi-Agent Path Finding. A plan is considered $p$-robust if the probability of a collision-free execution is at least $p$, given a known probability distribution of delays. By calculating the cumulative probability of independent agent delays along their trajectories, solvers like pR-CBS insert safety margins precisely where conflicts are most likely to occur, balancing path length against safety guarantees.

Reactive Flexibility: Decoupling Time from Order

An alternative to making plans wider or slower is to make them flexible during execution. Instead of forcing agents to adhere to strict timestamps, systems can preserve the topological order of movements.

A Temporal Plan Graph (TPG) operationalizes this by mapping paths to a dependency graph: Agent B cannot enter cell $(X, Y)$ until Agent A has left it, regardless of when that happens. While standard TPGs prevent collisions, they can be overly rigid if an agent experiences a massive delay, forcing everyone behind it to wait indefinitely.

To resolve this rigidity, Su introduced the Bidirectional Temporal Plan Graph (BTPG) in Bidirectional Temporal Plan Graph: Enabling Switchable Passing Orders for More Efficient Multi-Agent Path Finding Plan Execution. BTPGs allow agents to dynamically switch their passing orders on-the-fly in a first-come, first-served manner. If Agent A is delayed on its way to an intersection, the execution layer detects the gap and allows Agent B to safely bypass the conflict point first, significantly reducing unnecessary idle time.

Standard TPG (Rigid):
Agent A (Delayed) ------> Must cross intersection first ------> Agent B waits indefinitely

BTPG (Switchable):
Agent A (Delayed) ---\ /--> Agent B detects gap and crosses first
                      X
Agent B ------------/ \--> Agent A crosses later

Continuous-Time and Asynchronous Execution Models

The root cause of many execution discrepancies is the assumption of discrete, synchronized steps. Physical robots have varying velocities, turning radii, and acceleration profiles (Yakovlev et al. in Prioritized Multi-agent Path Finding for Differential Drive Robots).

To address this, Andreychuk et al. developed Continuous-time Conflict-Based Search (CCBS) in Multi-agent pathfinding with continuous time. CCBS treats time as a continuous variable and accommodates non-uniform action durations and physical agent volumes.

For scenarios where agents possess heterogeneous movement capabilities, Ren et al. proposed Loosely Synchronized Search (LSS) in Loosely Synchronized Search for Multi-agent Path Finding with Asynchronous Actions, allowing optimal pathfinding across asynchronous actions. Extending this to robust execution, Tan et al. introduced T-robust MAPF for continuous-time domains in Robust Multi-Agent Pathfinding with Continuous Time, providing exact collision detection under stochastic delays without relying on grid synchronization.

Online Adaptation and Lifelong Deployment

In highly dynamic environments, such as automated warehouses (Varambally et al. in Which MAPF Model Works Best for Automated Warehousing?) or complex railway shunting yards (van der Linden et al. in TORS: A Train Unit Shunting and Servicing Simulator), delay distributions may change over time due to human interference or environmental wear.

Rather than relying on static offline assumptions, modern frameworks combine online replanning with real-time learning. For instance, Kita et al. utilize Bayesian parameter updates in Online Re-Planning and Adaptive Parameter Update for Multi-Agent Path Finding with Stochastic Travel Times to learn corridor delay probabilities on the fly, updating the pathfinder's internal model as agents navigate.

To minimize the computational overhead of constant replanning, frameworks like PIE (Planning and Improving while Executing), introduced by Zhang et al. in Planning and Exection in Multi-Agent Path Finding: Models and Algorithms (Extended Abstract), allow agents to begin moving using a fast, suboptimal plan and continuously refine their trajectories while in motion. This interleaving of planning and execution ensures that the multi-agent system remains responsive to stochastic disruptions without suffering from real-time computational bottlenecks.

Key Foundational Work

Bringing Multi-agent Path Finding Closer to Reality (2018) — contributed 2 concept elements to this direction.
Multi-Agent Path Finding with Delay Probabilities (2017) — contributed 1 concept elements to this direction.
Search-Based Optimal Solvers for the Multi-Agent Pathfinding Problem: Summary and Challenges (2017) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_stochastic_execution_delays_a7eae8b1,
  title = {stochastic execution delays},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-execution-delays/rdr_a7eae8b1ec5740f083204efb11ed2977},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_stochastic_execution_delays_a7eae8b1_v1,
  title = {stochastic execution delays},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/stochastic-execution-delays/rdr_a7eae8b1ec5740f083204efb11ed2977/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake