The Hybrid Reciprocal Velocity Obstacle

Abstract

We present the hybrid reciprocal velocity obstacle for collision-free and oscillation-free navigation of multiple mobile robots or virtual agents. Each robot senses its surroundings and acts independently without central coordination or communication with other robots. Our approach uses both the current position and the velocity of other robots to compute their future trajectories in order to avoid collisions. Moreover, our approach is reciprocal and avoids oscillations by explicitly taking into account that the other robots also sense their surroundings and change their trajectories accordingly. We apply hybrid reciprocal velocity obstacles to iRobot Create mobile robots and demonstrate direct, collision-free, and oscillation-free navigation.

Keywords

Collision avoidance, mobile robots, motion planning, multi-robot systems, navigation.

Papers

• Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha, "The hybrid reciprocal velocity obstacle," IEEE Trans. Robot., vol. 27, 2011.
• Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha, "Independent navigation of multiple mobile robots with hybrid reciprocal velocity obstacles," IEEE/RSJ Int. Conf. Intelligent Robots and Systems, St. Louis, Mo., 2009.

Source Code

GitHub Repository, Documentation

Video

QuickTime Movie (8.4 MB), YouTube Video

Acknowledgments

This work was supported by ARO under Contract DAAD19-02-1-0390 and Contract W911NF-04-1-0088, by NSF under Award 0400134, Award 0429583, and Award 0404088, by DARPA and RDECOM under Contract N61339-04-C-0043, and by Intel.

Related Work

• Stephen J. Guy, Jatin Chhugani, Changkyu Kim et al., "ClearPath: highly parallel collision avoidance for multi-agent simulation," ACM SIGGRAPH/Eurographics Symp. Computer Animation, New Orleans, La., 2009.
• Jur van den Berg, Ming Lin, and Dinesh Manocha, "Reciprocal velocity obstacles for real-time multi-agent navigation," IEEE Int. Conf. Robotics and Automation, Pasadena, Calif., 2008.