We present a novel approach for interactive navigation and planning of multiple
agents in crowded scenes with moving obstacles. Our formulation uses a
pre-computed roadmap that provides macroscopic, global connectivity for
way-finding and combines it with fast and localized navigation for each agent.
At runtime, each agent senses the environment independently and computes a
collision-free path based on extended Velocity Obstacles and smoothness
constraints. Furthermore, our algorithm ensures that each agent exhibits no
oscillatory behaviors or gets trapped at a local minimum in crowded
environments. We have tested the performance of our algorithm in several
challenging scenarios with a high density of virtual agents. In practice, the
algorithm performance scales linearly with the number of agents and can run at
interactive rates on multi-core processors.
Jur van den Berg, Sachin Patil, Jason Sewall, Dinesh Manocha, Ming Lin
"Interactive Navigation of Individual Agents in Crowded Environments"
Accepted for publication at Symposium on Interactive 3D Graphics and Games
An easy to use library offering the general functionality of RVO for simulating
multiple agents. Includes documentation and example programs.
Full video ;
1000 agents in an office
250 agents in a stadium
400 agents at a crossroad
400 agents simulated with
motion capture data
Proof of concept : Large-Scale Stadium Evacuation
- 25,750 agents in the scene
- Densely crowded scenario with
- 2D path planning on stadium
Agent color assignment schema:
Agents in the top set of bleachers
are alternatively assigned the colors 'blue' and 'green'
while agents in the bottom set of bleachers are
alternatively assigned the colors 'yellow' and 'magenta'.
This is done to highlight the flows of agents as they
converge at the stadium exits.
Reciprocal Velocity Obstacles
on Motion Planning and Multi-Agent Simulation