Preventing Collision Avoidance Deadlocks in Multiagent Navigation for Deterministic Simulation

The Optimal Reciprocal Collision Avoidance (ORCA) algorithm is a foundational method for decentralized multiagent navigation, particularly valued for its lightweight implementation and robustness in crowded contexts. Originally developed for robotics, environmental noise and motion uncertainty are inherent, ORCA has become a standard in video game Artificial Intelligence (AI). However, in highly deterministic environments characterized by small integration time steps, which typically arise in modern asynchronous game simulations, the absence of stochasticity leads to systemic deadlocks in symmetric configurations that do not occur in noisy real-world systems. By analyzing the construction of the half-plane velocity constraints in ORCA, we identify the geometric origin of these deadlocks. We demonstrate that deadlocks occur systematically across all symmetric scenarios for n ∈ [2, 30] agents when exact rotational symmetry is preserved, especially with small time steps or slow agents. We present Revised ORCA Logic (RORCAL), a lightweight post-processing mechanism that introduces minimal directional bias to resolve degenerate solutions while preserving ORCA's computational efficiency. Experimental results show that RORCAL resolves all tested deadlock scenarios with a 2% per-iteration overhead and achieves 23% faster resolution in a 250-agents benchmark through emergent rotational coordination.