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.

author list (cited authors)

  • Sandstr√∂m, R., Bregger, A., Smith, B., Thomas, S., & Amato, N. M.

citation count

  • 2

publication date

  • May 2018