Reciprocal Collision Avoidance with Acceleration-Velocity Obstacles

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

The acceleration-velocity obstacle with acceleration interval 2 and time horizon 4   The configuration of robot amidst moving obstacles and the acceleration-velocity obstacles induced by the obstacles for acceleration interval 2 and time horizon 4   Two robots with acceleration constraints avoid collisions with each other while exchanging positions and pass their target location with high speed

Abstract

We present an approach for collision avoidance for mobile robots that takes into account acceleration constraints. We discuss both the case of navigating a single robot among moving obstacles, and the case of multiple robots reciprocally avoiding collisions with each other while navigating a common workspace. Inspired by the concept of velocity obstacles, we introduce the acceleration-velocity obstacle (AVO) to let a robot avoid collisions with moving obstacles while obeying acceleration constraints. AVO characterizes the set of new velocities the robot can safely reach and adopt using proportional control of the acceleration. We extend this concept to reciprocal collision avoidance for multi-robot settings, by letting each robot take half of the responsibility of avoiding pairwise collisions. Our formulation guarantees collision-free navigation even as the robots act independently and simultaneously, without coordination. Our approach is designed for holonomic robots, but can also be applied to kinematically constrained non-holonomic robots such as cars. We have implemented our approach, and we show simulation results in challenging environments with large numbers of robots and obstacles.

Keywords

Path planning for multiple mobile robots or agents; collision avoidance.

Paper

Jur van den Berg, Jamie Snape, Stephen J. Guy, and Dinesh Manocha, "Reciprocal collision avoidance with acceleration-velocity obstacles," IEEE Int. Conf. Robotics and Automation, Shanghai, People's Republic of China, 2011.

Videos

Moving obstacle; positions exchange; circle-16; circle-100 (QuickTime Movie).

Acknowledgments

This work was supported by ARO under Contract W911NF-04-1-0088, by NSF under Award 0636208, Award 0917040, and Award 0904990, by DARPA and RDECOM under Contract WR91CRB-08-C-0137, and by Intel.

Related Work