Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha
Department of Computer Science, University of North Carolina at Chapel Hill
We present an approach for smooth and collision-free navigation of multiple mobile robots amongst each other. 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 predict their future trajectory 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 build on prior work related to velocity obstacles and reciprocal velocity obstacles and introduce the concept of hybrid reciprocal velocity obstacles (HRVO) for collision avoidance that takes into account the kinematics of the robots and uncertainty in sensor data. We apply our approach to a set of iRobot Create robots using centralized sensing and show natural, direct, and collision-free navigation in several challenging scenarios.
Path planning for multiple mobile robots or agents; collision avoidance.
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. Intell. Robot. Syst., St. Louis, Mo., 2009.
QuickTime Movie (8.4 MB), RealVideo (5.0 MB), Windows Media Video (3.2 MB), YouTube Video.
A C++ library offering the general functionality of the hybrid reciprocal velocity obstacle approach is available for educational, research, and non-profit purposes.
ZIP Archive (0.1 MB).
This work was supported in part by ARO, NSF, DARPA/RDECOM, and Intel.
Jur van den Berg, Ming Lin, and Dinesh Manocha, "Reciprocal velocity obstacles for real-time multi-agent navigation," IEEE Int. Conf. Robot. Autom., Pasadena, Calif., 2008.
Jur van den Berg, Sachin Patil, Jason Sewall, Dinesh Manocha, and Ming Lin, "Interactive navigation of individual agents in crowded environments," Symp. Interact. 3D Graph. Game., Redwood City, Calif., 2008.
Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha, "Reciprocal n-body collision avoidance," Int. Symp. Robot. Res., Lucerne, Switzerland, 2009.
Stephen J. Guy, Jatin Chhugani, Changkyu Kim, Nadathur Satish, Ming Lin, Dinesh Manocha, and Pradeep Dubey, "ClearPath: Highly parallel collision avoidance for multi-agent simulation," ACM SIGGRAPH Eurographics Symp. Comput. Animat., New Orleans, La., 2009.
Jamie Snape and Dinesh Manocha, "Navigating multiple simple-airplanes in 3D workspace," under submission to IEEE Int. Conf. Robot. Autom., Anchorage, Alaska, 2010.
David Wilkie, Jur van den Berg, and Dinesh Manocha, "Generalized velocity obstacles," IEEE RSJ Int. Conf. Intell. Robot. Syst., St. Louis, Mo., 2009.
This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. iRobot is a trademark of iRobot Corporation, registered in the U.S. and other countries. Create is a trademark of iRobot Corporation. Intel is a trademark of Intel Corporation, registered in the U.S. and other countries. Adobe Reader and the Adobe Reader Logo are trademarks of Adobe Systems Incorporated, registered in the U.S. and other countries. The Get Adobe Reader Web Logo is a trademark of Adobe Systems Incorporated, used with permission. QuickTime and the QuickTime Logo are trademarks of Apple Inc., registered in the U.S. and other countries. The Get QuickTime Badge is a trademark of Apple Inc., used with permission. RealVideo is a trademark of RealNetworks Inc., registered in the U.S. and other countries. Windows Media Player and the Windows Media Player Logo are trademarks of Microsoft Corporation, registered in the U.S. and other countries. The Windows Media Player Download Button Logo is a trademark of Microsoft Corporation, used with permission.