Efficient nearest-neighbor computation for GPUbased motion planning

Abstract — We present a novel k-nearest neighbor search algorithm (KNNS) for proximity computation in motion planning algorithm that exploits the computational capa-bilities of many-core GPUs. Our approach uses locality sen-sitive 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 effec-tively. 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. I