Documentation

Download

People

Contact: to report bugs or suggest novel functionality, please contact Jur van den Berg or Dinesh Manocha at geom@cs.unc.edu.

Maintained by: Jur van den Berg

Latest Update: 5/26/2008

Simulations of multiple agents sharing a common workspace have gained increasing attention recently, for various purposes such as crowd simulation, navigating a team of mobile robots, computer games, studying natural flocking behavior, traffic engineering, architecture and design, emergency training simulations, etc.

We have presented a novel approach for interactive navigation and planning of large amounts of agents in two-dimensional (crowded) environments. Our formulation uses a precomputed roadmap that provides macroscopic knowledge for wayfinding and combines it with fast and localized navigation for each agent. At runtime, each agent senses the environment independently and computes a collision-free motion based on the “Reciprocal Velocity Obstacle” concept. Our algorithm ensures that each agent exhibits no oscillatory behaviors.

RVO Library is a publicly available C++ implementation of our algorithm. It has a very simple API for third-party applications. The user has to specify obstacles, a roadmap around the obstacles, and the agents and their goals, and the simulation can be performed step-by-step by a simple call to the library. The simulation is fully accessible and manipulable during the simulation. The library automatically exploits multiple processors if they are available for efficient parallellization of the simulation. Please refer to the documentation for details regarding the API and the contents of the distribution.

REQUIREMENTS AND DEPENDENCIES

None. The RVO library is a stand-alone library that does not depend on third-party packages. It should work with any C++ compiler on any platform. It uses OpenMP to exploit multiple processors if they are available on the system, but having multiple processors is not a requirement.

RELATED LINKS

UNC Gamma Group

PUBLICATIONS

• Jur van den Berg, Ming Lin, Dinesh Manocha;
  Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation.
  Proc. IEEE Int. Conf. on Robotics and Automation - ICRA'08, 2008.
• Jur van den Berg, Sachin Patil, Jason Sewall, Dinesh Manocha, Ming Lin;
  Interactive Navigation of Individual Agents in Crowded Environments.
  Proc. Symposium on Interactive 3D Graphics and Games - I3D'08, 2008.
• Hengchin Yeh, Sean Curtis, Sachin Patil, Jur van den Berg, Dinesh Manocha, Ming Lin;
  Composite Agents.
  Symposium on Computer Animation - SCA'08, 2008.

RESEARCH SPONSORS

• ARO
• NSF
• DARPA/RDECOM
• Intel