We present a formal approach to reciprocal collision avoidance, where multiple independent mobile robots or agents need to avoid collisions with each other without communication among agents while moving in a common workspace. Our formulation, optimal reciprocal collision avoidance (ORCA), provides sufficient conditions for collision-free motion by letting each agent take half of the responsibility of avoiding pairwise collisions. Selecting the optimal action for each agent is reduced to solving a low-dimensional linear program, and we prove that the resulting motions are smooth. We test our optimal reciprocal collision avoidance approach on a team of iRobot Create differential-drive mobile robots, as well as on several dense and complex simulation scenarios in both 2D and 3D workspaces involving thousands of agents, and compute collision-free actions for all of them in only a few milliseconds.
Source code is freely available for educational, research, and non-profit purposes as an easy-to-use C++ library. See RVO2 Library.
Reciprocal n-body collision avoidance
Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha
Cédric Pradalier, Roland Siegwart, and Gerhard Hirzinger (eds.), Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics, vol. 70, Springer-Verlag, May 2011, pp. 3-19. [PDF]
Smooth and collision-free navigation for multiple robots under differential-drive constraints
Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha
Proceedings of the 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), October 2010, pp. 4584-4589. [Website]
Funded in part by:
The hybrid reciprocal velocity obstacle
Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha
IEEE Transactions on Robotics (T-RO), volume 27, August 2011.
ClearPath: Highly parallel collision avoidance for multi-agent simulation
Stephen J. Guy, Jatin Chhugani, Changkyu Kim, Nadathur Satish, Ming C. Lin, Dinesh Manocha, and Pradeep Dubey
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), August 2009.
Reciprocal velocity obstacles for real-time multi-agent navigation
Jur van den Berg, Ming C. Lin, and Dinesh Manocha
IEEE International Conference on Robots and Automation (ICRA), May 2008.
