2387

ClearPath: highly parallel collision avoidance for multi-agent simulation

Stephen J. Guy, Jatin Chhugani, Changkyu Kim, Nadathur Satish, Ming Lin, Dinesh Manocha, Pradeep Dubey
University of North Carolina at Chapel Hill
In SCA ’09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation (2009), pp. 177-187

@conference{guy2009clearpath,

   title={Clearpath: highly parallel collision avoidance for multi-agent simulation},

   author={Guy, S. and others},

   booktitle={Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation},

   pages={177–187},

   year={2009},

   organization={ACM}

}

Download Download (PDF)   View View   Source Source   

806

views

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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: