GPU-based parallel collision detection for real-time motion planning

Jia Pan, Dinesh Manocha
University of North Carolina, Chapel Hill, NC, USA
Algorithmic Foundations of Robotics IX, Springer Tracts in Advanced Robotics, Volume 68/2011, 211-228, 2011


   title={GPU-based parallel collision detection for real-time motion planning},

   author={Pan, J. and Manocha, D.},

   journal={Algorithmic Foundations of Robotics IX},





Download Download (PDF)   View View   Source Source   



We present parallel algorithms to accelerate collision queries for sample-based motion planning. Our approach is designed for current many-core GPUs and exploits the data-parallelism and multi-threaded capabilities. In order to take advantage of high number of cores, we present a clustering scheme and collision-packet traversal to perform efficient collision queries on multiple configurations simultaneously. Furthermore, we present a hierarchical traversal scheme that performs workload balancing for high parallel efficiency. We have implemented our algorithms on commodity NVIDIA GPUs using CUDA and can perform 500,000 collision queries/second on our benchmarks, which is 10X faster than prior GPU-based techniques. Moreover, we can compute collision-free paths for rigid and articulated models in less than 100 milliseconds for many benchmarks, almost 50-100X faster than current CPU-based planners.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: