ABSTRACT
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, 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.
PAPER
Jur van den Berg, Ming C. Lin, Dinesh Manocha
"Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation" Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), 2008.
Download
PRESENTATION / TUTORIAL
Download (includes lots of videos)
RVO LIBRARY 1.1
An easy to use library offering the general functionality of RVO for simulating multiple agents. Includes documentation and example programs.
Link
Full Video; 250 agents on a circle; Four groups of agents
RELATED WORK
Interactive Navigation of Individual Agents in Crowded Environments
Optimal Reciprocal Collision Avoidance
Hybrid Reciprocal Velocity Obstacles
RVO2 Library
