ClearPath
Stephen J. Guy, Jatin Chhugani, Changkyu Kim et al. · ACM SIGGRAPH/Eurographics Symposium on Computer Animation (SCA) · 2009
We present a new local collision avoidance algorithm between multiple agents for real-time simulations. Our approach extends the notion of velocity obstacles from robotics and formulates the conditions for collision free navigation as a quadratic optimization problem. We use a discrete optimization method to efficiently compute the motion of each agent. This resulting algorithm can be parallelized by exploiting data-parallelism and thread-level parallelism. The overall approach, ClearPath, is general and can robustly handle dense scenarios with tens or hundreds of thousands of heterogeneous agents in a few milli-seconds. As compared to prior collision avoidance algorithms, we observe more than an order of magnitude performance improvement.
Cited by 291 works. doi:10.1145/1599470.1599494
Authors
References
- Flocks, herds and schools: A distributed behavioral model
- Flocks, herds and schools: A distributed behavioral model
- Planning Algorithms
- Planning Algorithms
- Motion Planning in Dynamic Environments Using Velocity Obstacles
- Pedestrian and evacuation dynamics
- Reciprocal n-Body Collision Avoidance
- Reciprocal Velocity Obstacles for real-time multi-agent navigation
- Larrabee
- Self-Organized Pedestrian Crowd Dynamics: Experiments, Simulations, and Design Solutions