Efficient nearest-neighbor computation for GPU-based motion planning
Department of Computer Science, UNC Chapel Hill, Chapel Hill, NC, USA
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2010
@conference{pan2010efficient,
title={Efficient nearest-neighbor computation for GPU-based motion planning},
author={Pan, J. and Lauterbach, C. and Manocha, D.},
booktitle={Intelligent Robots and Systems (IROS), 2010 IEEE/RSJ International Conference on},
pages={2243–2248},
issn={2153-0858},
year={2010},
organization={IEEE}
}
We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capabilities of many-core GPUs. Our approach uses locality sensitive hashing and cuckoo hashing to construct an efficient KNNS algorithm that has linear space and time complexity and exploits the multiple cores and data parallelism effectively. In practice, we see magnitude improvement in speed and scalability over prior GPU-based KNNS algorithm. On some benchmarks, our KNNS algorithm improves the performance of overall planner by 20-40 times for CPU-based planner and up to 2 times for GPU-based planner.
May 6, 2011 by hgpu
