Reciprocal n-body collision avoidance

Jur Van Den Berg, Stephen J. Guy, Ming Lin, Dinesh Manocha

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1002 Scopus citations


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 languageEnglish (US)
Title of host publicationRobotics Research - The 14th International Symposium ISRR
Number of pages17
StatePublished - 2011
Event14th International Symposium of Robotic Research, ISRR 2009 - Lucerne, Switzerland
Duration: Aug 31 2009Sep 3 2009

Publication series

NameSpringer Tracts in Advanced Robotics
ISSN (Print)1610-7438
ISSN (Electronic)1610-742X


Other14th International Symposium of Robotic Research, ISRR 2009

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.


Dive into the research topics of 'Reciprocal n-body collision avoidance'. Together they form a unique fingerprint.

Cite this