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 , 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.
|Original language||English (US)|
|Title of host publication||Robotics Research - The 14th International Symposium ISRR|
|Number of pages||17|
|State||Published - 2011|
|Event||14th International Symposium of Robotic Research, ISRR 2009 - Lucerne, Switzerland|
Duration: Aug 31 2009 → Sep 3 2009
|Name||Springer Tracts in Advanced Robotics|
|Other||14th International Symposium of Robotic Research, ISRR 2009|
|Period||8/31/09 → 9/3/09|
Bibliographical noteFunding Information:
This research is supported in part by ARO Contracts W911NF-04-1-0088, NSF award 0636208, DARPA/RDECOM Contracts N61339-04-C-0043 and WR91CRB-08-C-0137, Intel, and Microsoft.