Resolving Deadlocks in Constrained Multi-Agent Navigation

471 concepts331 papers2 proposals

In multi-agent systems, the primary challenge is not just avoiding collisions, but ensuring the system as a whole continues to move. When multiple robots or autonomous vehicles share a workspace, they often encounter deadlocks: states where no agent can progress toward its goal because every available move is blocked by another agent.

Deadlocks are rarely the result of a single agent's failure. Instead, they emerge from the interaction of local collision-avoidance rules that lack a global perspective.

The Geometry of Failure

The most intuitive form of deadlock occurs at physical bottlenecks. In environments like narrow corridors, doorways, or 3D disaster zones, the available space is smaller than the combined volume required for agents to pass one another. Liang He et al. note that decentralized algorithms frequently fail in these "narrow passage" scenarios because agents cannot effectively coordinate the complex sequence of yielding and waiting required to navigate tight quarters.

This is often a topological problem. As Leroy et al. argued, if the initial paths of two agents are topologically incompatible—such as two robots meeting head-on in a passage with no bypass—simply adjusting the timing of their movements will never resolve the conflict. The system requires a fundamental re-routing or a mechanism to "push" agents out of the way, a concept explored by Luna and Bekris through their "Push and Swap" algorithm.

The Local-Global Coordination Gap

Why do sophisticated agents get stuck? The root cause is often the local-global gap. Most decentralized agents make decisions based on their immediate surroundings to maintain real-time responsiveness. However, Zhang et al. point out that robots perceiving only their immediate vicinity fail to account for global traffic patterns, leading to collective gridlock in congested areas.

This lack of foresight manifests in several ways:

  • Reciprocal Oscillations: Coppola et al. describe how two agents may enter a loop where both dodge in the same direction, repeatedly failing to resolve their path conflict.
  • Resource Contention: In early multi-agent planning research, Georgeff observed that independent plans often fail when agents compete for shared tools or physical locations simultaneously.
  • Start-Position Blocking: Andreychuk et al. identified a specific failure mode where high-priority agents inadvertently block the starting tiles of lower-priority agents, preventing the latter from ever beginning their journey.

Symmetry as a Computational Bottleneck

Even when a solution exists, search-based algorithms may stall due to symmetry. Jiaoyang Li et al. identified "corridor" and "target" symmetries where standard pathfinding algorithms waste immense computational effort exploring minor timing variations that do not address the underlying spatial conflict. In these cases, the deadlock isn't just physical; it is a failure of the search logic to recognize that a synchronized, multi-agent maneuver is the only way forward.

Emerging Solutions: Rules and Intent

To bridge the gap between local safety and global liveness, researchers have proposed several coordination mechanisms:

  1. Traffic Rules and Highways: By embedding "highways" or directional constraints into the environment, Cohen et al. and Zhang et al. show that agents can maintain flow efficiency. These rules act as a form of "environmental programming" that reduces the number of possible conflicts.
  2. Intent Sharing: Rather than treating other agents as static obstacles, systems can share future trajectories. Hirata et al. demonstrate that sharing "future paths" with a central roadside unit allows for speed adjustments that prevent intersection gridlock.
  3. Probabilistic Yielding: Ibe et al. introduced "intention vectors" that allow robots to estimate whether a human or another robot intends to yield, enabling smoother "give-way" behaviors at bottlenecks.
  4. Hybrid Planning: Modern approaches like the one proposed by Tan et al. combine raw local sensor data with global motion maps, giving decentralized agents a "bird's-eye view" to resolve deadlocks before they become physical stalls.

Ultimately, resolving multi-agent deadlocks requires moving beyond simple collision avoidance toward cooperative negotiation, where agents recognize that their own progress depends on the synchronized movement of the entire group.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_multi_agent_deadlock_2f15a7b1,
  title = {multi-agent deadlock},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-deadlock/rdr_2f15a7b14dae47bda7ba52cc713d179e},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_multi_agent_deadlock_2f15a7b1_v1,
  title = {multi-agent deadlock},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/multi-agent-deadlock/rdr_2f15a7b14dae47bda7ba52cc713d179e/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake