Topological Nearest-Neighbor Filtering for Sampling-Based Planners
Read Sandström, Andrew Bregger, Ben Smith, Shawna Thomas, Nancy M. Amato
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.
BibTeX
@inproceedings{icra2018_topologicalneare,
title = {Topological Nearest-Neighbor Filtering for Sampling-Based Planners},
author = {Read Sandström and Andrew Bregger and Ben Smith and Shawna Thomas and Nancy M. Amato},
booktitle = {ICRA 2018},
year = {2018}
}