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 others.
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]
Reciprocal n-body Collision Avoidance
Jur van den Berg, Stephen J. Guy, Ming Lin, and Dinesh Manocha
International Symposium on Robotics Research (ISRR), Sep. 2009. [PDF]
Acknowledgements
Funded in part by:
Intel Corporation
National Science Foundation
RDECOM
Army Research Office
Related Work
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.
|
|