Efficient nearest-neighbor computation for GPU-based motion planning

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.

Authors

• Jia Pan 0001
• Christian Lauterbach
• Dinesh Manocha

Keywords

• Planning
• Graphics processing unit
• Nearest neighbor searches
• Measurement
• Approximation algorithms
• Indexing
• Heuristic algorithms
• Path Planning
• Time Complexity
• Computational Algorithms
• Space Complexity
• Linear Time
• Nearest Neighbor Search
• Parallel Data
• Linear Complexity
• Linear Time Complexity
• Locality Sensitive Hashing
• Dimensional Space
• Urban Planning
• Parallelization
• GB Memory
• Euclidean Space
• Hash Function
• Configuration Space
• Nearest Point
• Parallel Algorithm
• Query Point
• Computational Geometry