Collision Avoidance

Stephen J. Guy, Jur van den Berg, Ming Lin, and Dinesh Manocha
Collaborators: Jatin Chhugani (Intel) and Pradeep Dubey (Intel)

  Collision avoidance is a fundamental problem in many areas such as robotics and animation. To that end, we developed new techniques focused on providing fast and robust collision avoidance for multiple agents moving around obstacles and each other.
  ClearPath introduces the idea of formulating multi-agent collision avoidance as a convex optimization problem, and uses that to perform very fast avoidance computation. We also discuss how to efficiently exploit both data-level parallelism (SIMD) and thread-level parallelism.
  ORCA provides a new formulations for collision avoidance using linear programming. With it, we provide guaranteed collision avoidance for multiple independent robots.

*Pedestrians in a Large City - 25,000 agents @ 140 FPS [AVI]
*Office Evacuation Drill - 1,000 agents @ 4,500 FPS [AVI]
*Crossing Circle [AVI]
*Lane Formation [AVI]
*4 Streams [AVI]
*ClearPath vs. OpenSteer [AVI]

ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation
S. J. Guy, J. Chhugani, C. Kim, N. Satish, M. Lin, D. Manocha, and P. Dubey
ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA), Aug. 2009. [PDF] [MOV]

Funded in part by:
Intel Corporation
National Science Foundation
Army Research Office

Related Work
Reciprocal n-body Collision Avoidance
Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha
Robotics Research: The 14th International Symposium ISRR, Springer Tracts in Advanced Robotics (STAR), May 2011.

Independent Navigation of Multiple Mobile Robots with Hybrid Reciprocal Velocity Obstacles
Jamie Snape, Jur van den Berg, Stephen J. Guy, and Dinesh Manocha
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Oct. 2009.

Reciprocal Velocity Obstacles for Real-Time Multi-Agent Navigation
Jur van den Berg, Ming C. Lin, and Dinesh Manocha
IEEE International Conference on Robots and Automation (ICRA), May 2008.