Topological Nearest-Neighbor Filtering for Sampling-Based Planners

Read Sandstrem, Andrew Bregger, Ben Smith, Shawna Thomas, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Robotics and Automation, ICRA 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages8
ISBN (Electronic)9781538630815
StatePublished - Sep 10 2018
Externally publishedYes
Event2018 IEEE International Conference on Robotics and Automation, ICRA 2018 - Brisbane, Australia
Duration: May 21 2018May 25 2018

Publication series

NameProceedings - IEEE International Conference on Robotics and Automation
ISSN (Print)1050-4729


Conference2018 IEEE International Conference on Robotics and Automation, ICRA 2018

ASJC Scopus subject areas

  • Software
  • Artificial Intelligence
  • Electrical and Electronic Engineering
  • Control and Systems Engineering


Dive into the research topics of 'Topological Nearest-Neighbor Filtering for Sampling-Based Planners'. Together they form a unique fingerprint.

Cite this