COLLOQUIUM
Department of Computer Science and Engineering
University of South Carolina
 
Reciprocal Velocity Obstacles for Real-Time
Multiagent Navigation


Jur van den Berg
Department of Computer Science
University of North Carolina at Chapel Hill

Date: March 27, 2009
Time: 1530-1630 (3:30pm-4:30pm)
Place: Swearingen 1A03 (Faculty Lounge)

Abstract

We propose a new concept ---the "Reciprocal Velocity Obstacle"--- for
real-time multiagent 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 thousands 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.

Jur van den Berg is a postdoctoral researcher at the University of
North Carolina at Chapel Hill, where he works with Professors Dinesh
Manocha and Ming Lin.  He completed his MSc at the University of
Gronigen and his Ph.D. at the University of Utrecht in 2007, under the
supervision of Professor Mark Overmars, with a dissertation entitled
"Path Planning in Dynamic Environments."