Geometric methods for multi-agent collision avoidance

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

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

8 Scopus citations


We present an approach to reciprocal collision avoidance, where multiple mobile agents must avoid collisions with each other while moving in a common workspace. Each agent acts fully independently, and does not communicate with others. Yet our approach guarantees that all agents will be collision-free for at least a fixed amount of time. Our approach provides a sufficient condition for collision-free motion. Given the agent's objective, the optimal collision-free action can be computed very efficiently, as it is the solution to a two-dimensional linear program. We show our approach on dense and complex simulation scenarios involving thousands of agents at fast real-time running times.

Original languageEnglish (US)
Title of host publicationProceedings of the 26th Annual Symposium on Computational Geometry, SCG'10
Number of pages2
StatePublished - Jul 30 2010
Event26th Annual Symposium on Computational Geometry, SoCG 2010 - Snowbird, UT, United States
Duration: Jun 13 2010Jun 16 2010

Publication series

NameProceedings of the Annual Symposium on Computational Geometry


Other26th Annual Symposium on Computational Geometry, SoCG 2010
Country/TerritoryUnited States
CitySnowbird, UT


  • Collision avoidance
  • Crowd simulation
  • Multi-agent motion planning
  • Robotics
  • Virtual agents


Dive into the research topics of 'Geometric methods for multi-agent collision avoidance'. Together they form a unique fingerprint.

Cite this