Efficient nearest-neighbor computation for GPU-based motion planning

Jia Pan, Christian Lauterbach, Dinesh Manocha
Department of Computer Science, UNC Chapel Hill, Chapel Hill, NC, USA
IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2010


   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},






Download Download (PDF)   View View   Source Source   



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

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: