Reciprocal Velocity Obstacles for real-time multi-agent navigation

TLDR

The Velocity Obstacle concept, originally for navigating among moving obstacles, serves as the foundation for this work. The paper proposes the Reciprocal Velocity Obstacle concept for real-time multi‑agent navigation. The method models agents as independently navigating without explicit communication, implicitly assuming each agent reacts similarly to avoid collisions, and applies this concept to dense environments with static and moving obstacles. The approach guarantees safe, oscillation‑free motion for each agent and achieves real-time, scalable performance in densely populated environments.

Abstract

In this paper, we propose a new concept - the "Reciprocal Velocity Obstacle"- for real-time multi-agent navigation. We consider the case in which each agent navigates independently without explicit communication with other agents. Our formulation is an extension of the Velocity Obstacle concept [3], which was introduced for navigation among (passively) moving obstacles. Our approach takes into account the reactive behavior of the other agents by implicitly assuming that the other agents make a similar collision-avoidance reasoning. We show that this method guarantees safe and oscillation- free motions for each of the agents. We apply our concept to navigation of hundreds of agents in densely populated environments containing both static and moving obstacles, and we show that real-time and scalable performance is achieved in such challenging scenarios.