GPU-based parallel collision detection for real-time motion planning
University of North Carolina, Chapel Hill, NC, USA
Algorithmic Foundations of Robotics IX, Springer Tracts in Advanced Robotics, Volume 68/2011, 211-228, 2011
@article{pan2011gpu,
title={GPU-based parallel collision detection for real-time motion planning},
author={Pan, J. and Manocha, D.},
journal={Algorithmic Foundations of Robotics IX},
pages={211–228},
year={2011},
publisher={Springer}
}
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.
December 22, 2011 by hgpu
