Cooperative-ORCA*: Real-Time Proactive Deadlock Avoidance for Continuous-Space Multi-Agent Navigation
2026-06-22 • Robotics
Robotics
AI summaryⓘ
The authors study a problem where many agents, like robots, need to move without bumping into each other. A common solution, ORCA*, picks safe speeds step-by-step but sometimes causes traffic jams (deadlocks) because it can't plan ahead well. Their new methods, C-ORCA* and C-ORCA*-MAPF, look at the agents' full paths to avoid these jams before they happen. This proactive approach makes the system faster and smoother compared to earlier methods that fix jams only after they happen.
Multi-Agent Path FindingORCA*deadlockcollision avoidancereal-time planningtrajectoryflowtimerobot coordination
Authors
Junfeng Wu, Jiaqi Chen, Hongkun Lyu, Kevin Zheng, Andy Li
Abstract
Multi-Agent Path Finding (MAPF) is a problem that requires computing collision-free paths for a set of agents from their start locations to designated goal locations. The problem has broad applications in domains where teams of robots must operate in a coordinated manner. ORCA* is a real time MAPF solver that assigns for each timestep a velocity for each agent. Due to its real time nature, it is myopic to future deadlocks that result from current decisions. ORCA*-MAPF attempts to remedy this limitation by introducing fallback mechanisms when deadlocks are detected. However, post hoc interventions often introduce significant flowtime overhead. In this paper, we introduce C-ORCA* and C-ORCA*-MAPF, continuous space MAPF algorithms that incorporate agents' entire spatial trajectory and their spatial dependencies to proactively prevent deadlocks from occurring, thus avoiding the high flowtime overhead associated with post hoc corrections in ORCA*-MAPF. The C-ORCA* family of algorithms significantly outperform previous state-of-the-art in terms of solve rate, runtime, and flowtime.