ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation

Loading...
Thumbnail Image
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
ACM SIGGRAPH / Eurographics Association
Abstract
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.
Description

        
@inproceedings{
10.1145:1599470.1599494
, booktitle = {
Eurographics/ ACM SIGGRAPH Symposium on Computer Animation
}, editor = {
Eitan Grinspun and Jessica Hodgins
}, title = {{
ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation
}}, author = {
Guyy, Stephen. J.
and
Chhugani, Jatin
and
Kim, Changkyu
and
Satish, Nadathur
and
Lin, Ming
and
Manocha, Dinesh
and
Dubey, Pradeep
}, year = {
2009
}, publisher = {
ACM SIGGRAPH / Eurographics Association
}, ISSN = {
1727-5288
}, ISBN = {
978-1-60558-610-6
}, DOI = {
10.1145/1599470.1599494
} }
Citation