Reciprocal n-Body Collision Avoidance¶
Authors: Jur van den Berg, Stephen J. Guy, Ming Lin, Dinesh Manocha
Published: 2011 (Conference Paper)
Source: Springer Tracts in Advanced Robotics
Algorithm: ORCA
DOI: 10.1007/978-3-642-19457-3_1
Summary¶
Abstract¶
In this paper, we present a formal approach to reciprocal n-body collision avoidance , where multiple mobile robots need to avoid collisions with each other while moving in a common workspace. In our formulation, each robot acts fully independently, and does not communicate with other robots. Based on the definition of velocity obstacles [5], we derive sufficient conditions for collision-free motion by reducing the problem to solving a low-dimensional linear program. We test our approach on several dense and complex simulation scenarios involving thousands of robots and compute collision-free actions for all of them in only a few milliseconds. To the best of our knowledge, this method is the first that can guarantee local collision-free motion for a large number of robots in a cluttered workspace.