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 Lin, Dinesh Manocha
"Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation" Accepted
for publication at IEEE International Conference on Robotics and Automation
(ICRA), 2008.
Download
Full Video; 250 agents on a circle ; Four groups of agents
PRESENTATION / TUTORIAL
Download
(includes lots of videos)
RELATED WORK
GAMMA Research
on Motion Planning and Multi-Agent Simulation
Interactive Navigation of
Individual Agents in Crowded Environments
