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.
| Original language | English (US) |
|---|---|
| Title of host publication | Robotics Research - The 14th International Symposium ISRR |
| Pages | 3-19 |
| Number of pages | 17 |
| Edition | STAR |
| DOIs | |
| State | Published - 2011 |
| Event | 14th International Symposium of Robotic Research, ISRR 2009 - Lucerne, Switzerland Duration: Aug 31 2009 → Sep 3 2009 |
Publication series
| Name | Springer Tracts in Advanced Robotics |
|---|---|
| Number | STAR |
| Volume | 70 |
| ISSN (Print) | 1610-7438 |
| ISSN (Electronic) | 1610-742X |
Other
| Other | 14th International Symposium of Robotic Research, ISRR 2009 |
|---|---|
| Country/Territory | Switzerland |
| City | Lucerne |
| Period | 8/31/09 → 9/3/09 |
Bibliographical note
Funding 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.
