Topological Nearest-Neighbor Filtering for Sampling-Based Planners Conference Paper uri icon


  • 2018 IEEE. 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.

name of conference

  • 2018 IEEE International Conference on Robotics and Automation (ICRA)

published proceedings


author list (cited authors)

  • Sandstrom, R., Bregger, A., Smith, B., Thomas, S., & Amato, N. M.

citation count

  • 3

complete list of authors

  • Sandstrom, Read||Bregger, Andrew||Smith, Ben||Thomas, Shawna||Amato, Nancy M

publication date

  • January 2018