Description
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.
Demos
*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]
Publications 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]
Acknowledgements
Funded in part by:
Intel Corporation
National Science Foundation
RDECOM
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.
