Topological Nearest-Neighbor Filtering for Sampling-Based Planners

Authors: Read Sandström, Andrew Bregger, Ben Smith, Shawna Thomas, Nancy M. Amato

Venue: Proc. IEEE Int. Conf. on Robotics and Automation (ICRA)
DOI: 10.1109/ICRA.2018.8460896
Link to Publication

Abstract:
Nearest-neighbor finding is a major bottleneck for sampling-based motion planning algorithms. The cost of finding nearest neighbors grows with the size of the roadmap, leading to significant slowdowns for problems which require many configurations to find a solution. Prior work has investigated relieving this pressure with quicker computational techniques, such as kd-trees or locality-sensitive hashing. In this work, we investigate an alternative direction for expediting this process based on workspace connectivity. We present an algorithm called Topological Nearest-Neighbor Filtering, which employs a workspace decomposition to select a topologically relevant set of candidate neighbor configurations as a pre-processing step for a nearest-neighbor algorithm. We investigate the application of this filter to several varieties of RRT and demonstrate that the filter improves both nearest-neighbor time and overall planning performance.

@inproceedings{Amato-tnffsp-2018, 
 author = {Read Sandström and Andrew Bregger and Ben Smith and Shawna Thomas and Nancy M. Amato}, 
 booktitle = {Proc. IEEE Int. Conf. Robot. Autom. (ICRA)}, 
 doi = {10.1109/ICRA.2018.8460896}, 
 location = {Brisbane, Australia}, 
 month = {May}, 
 pages = {3053-3060}, 
 title = {Topological Nearest-Neighbor Filtering for Sampling-Based Planners}, 
 year = {2018} 
}