ABSTRACT
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.
PAPER
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
(I3D), 2008.
Download
LIBRARY
An easy to use library offering the general functionality of RVO for simulating
multiple agents. Includes documentation and example programs.
Link
VIDEOS
Full video ;
1000 agents in an office building ;
400 agents simulated with motion capture data ;
Proof of concept : Large-Scale Stadium Evacuation Simulation ;
Scene Description:
- 25,750 agents in the scene
- Densely crowded scenario with narrow passages
- 2D path planning on stadium floor-plan
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.
RELATED WORK
GAMMA Research
on Motion Planning and Multi-Agent Simulation
Reciprocal Velocity Obstacles
