Robust Multi Agent Path Finding under Temporal Uncertainty

This direction is split into other directions: temporal flexibility. Its last version stays readable and citable here.

Version 1 of 197 papers136 conceptsfrozen 2026-10-04

In the idealized world of Multi-Agent Path Finding (MAPF), robots are perfect. They move exactly one grid cell per time step, never slip, and never stall. However, as Hang Ma, Sven Koenig, and T. K. Satish Kumar point out in Multi-Agent Path Finding with Delay Probabilities, real-world execution is messy. A warehouse robot might be slowed by a slick floor, a sensor glitch, or a low battery.

When an algorithm assumes clockwork precision, a single delayed robot can trigger a cascade of collisions or force a computationally expensive system-wide replan. The research direction of Temporal Robustness seeks to bridge this "reality gap" by creating plans that remain safe and efficient even when agents deviate from their schedules.

The Fragility of Space-Time Schedules

Standard MAPF solvers typically output a "space-time" plan: a sequence of coordinates paired with exact timestamps. For example, "Agent A must be at $(3,4)$ at $t=5$."

The problem, as identified by Oriana Peltzer and Mac Schwager in STT-CBS, is that these rigid schedules are brittle. If Agent A is delayed by just one second, it might still be at $(3,3)$ when Agent B—following its own rigid schedule—arrives at $(3,3)$, leading to a collision. In high-density environments, these minor stochastic delays accumulate, causing cascading failures across the entire fleet.

Building in Buffers: k-Robustness

The most intuitive solution is to add "slack" or temporal padding. This is formalized as $k$-robustness. A plan is $k$-robust if it remains collision-free even if any agent is delayed by up to $k$ time steps.

In Symmetry Breaking for k-Robust Multi-Agent Path Finding, Zhe Chen and Daniel Harabor explain that this transforms discrete spatial-temporal constraints into interval-based safety margins. Instead of avoiding a point in time, agents avoid a "shadow" of where an agent might be if it were delayed. While this increases the theoretical cost of the plan, it prevents the need for frequent global re-planning.

From Space-Time to Space-Order

A more fundamental shift in intuition comes from moving away from timestamps entirely. Instead of planning when an agent should be at a location, researchers like Yu Wu and Jiaoyang Li propose planning the order in which they arrive.

In From Space-Time to Space-Order: Directly Planning a Temporal Planning Graph by Redefining CBS, the authors introduce Space-Order CBS. This algorithm plans a Temporal Planning Graph (TPG), which encodes precedence constraints (e.g., "Agent A must pass through the intersection before Agent B").

Why does this work?

  1. Asynchronous Safety: If Agent A is delayed, Agent B simply waits at the entry of the shared space. Safety is maintained by the order, not the clock.
  2. Reduced Coordination: By focusing on "who goes first" rather than "be here at 10.005s," the system slashes unnecessary dependencies. Yu Wu found that this approach can reduce robot-to-robot coordination by up to 90%, making the fleet significantly more resilient to local disruptions.

Probabilistic Resilience

While $k$-robustness handles a fixed worst-case delay, real-world delays are often probabilistic. Dor Atzmon and Roni Stern introduced $p$-robustness in Probabilistic Robust Multi-Agent Path Finding. This framework ensures that the probability of a collision-free execution is at least $p$.

This allows for a more nuanced trade-off: in a warehouse with high-quality floors, you might set $p=0.95$ to keep throughput high, whereas a safety-critical environment might require $p=0.999$. Algorithms like pR-CBS calculate how individual delay probabilities propagate through the system, ensuring that the cumulative risk never exceeds the threshold.

Reactive and Concurrent Adaptation

Finally, the field is moving toward concurrent planning and execution. If a delay is too large for a buffer to absorb, the system must adapt without stopping.

In Multi-Agent Path Execution with Uncertainty, researchers demonstrate that adjusting the temporal order of agents online—allowing a faster agent to bypass a stalled peer—is often more effective than recalculating physical paths. Similarly, the PIE (Planning and Improving while Executing) framework by Yue Zhang and Daniel Harabor in Planning and Exection in Multi-Agent Path Finding suggests that we should start with a "good enough" robust plan and refine it in real-time as the actual execution state becomes known.

By decoupling the where (spatial paths) from the when (temporal execution), these researchers have turned MAPF from a fragile mathematical puzzle into a robust framework for real-world robotics.

Papers in this version

Showing 60 of 97 papers.

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_robust_multi_agent_path_finding_under_te_ebd8ceff,
  title = {Robust Multi Agent Path Finding under Temporal Uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-multi-agent-path-finding-under-temporal-uncertainty/rdr_ebd8ceff4d9e4687bfc3e5ad0915994f},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_robust_multi_agent_path_finding_under_te_ebd8ceff_v1,
  title = {Robust Multi Agent Path Finding under Temporal Uncertainty},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/robust-multi-agent-path-finding-under-temporal-uncertainty/rdr_ebd8ceff4d9e4687bfc3e5ad0915994f/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}