ClearPath: Highly Parallel Collision Avoidance for Multi-Agent Simulation
Loading...
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}
}