Asymptotically-Optimal Topological Nearest-Neighbor Filtering

Read Sandstrom, Jory Denny, Nancy M. Amato

Research output: Contribution to journalArticlepeer-review


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 a significant computational bottleneck for problems which require many configurations to find a solution. In this letter, we develop a method of mapping configurations of a jointed robot to neighborhoods in the workspace that supports fast search for configurations in nearby neighborhoods. This expedites nearest-neighbor search by locating a small set of the most likely candidates for connecting to the query with a local plan. We show that this filtering technique can preserve asymptotically-optimal guarantees with modest requirements on the distance metric. We demonstrate the method's efficacy in planning problems for rigid bodies and both fixed and mobile-base manipulators.

Original languageEnglish (US)
Article number9170802
Pages (from-to)6916-6923
Number of pages8
JournalIEEE Robotics and Automation Letters
Issue number4
StatePublished - Oct 2020
Externally publishedYes


  • Motion and path planning
  • semantic scene understanding

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Biomedical Engineering
  • Human-Computer Interaction
  • Mechanical Engineering
  • Computer Vision and Pattern Recognition
  • Computer Science Applications
  • Control and Optimization
  • Artificial Intelligence


Dive into the research topics of 'Asymptotically-Optimal Topological Nearest-Neighbor Filtering'. Together they form a unique fingerprint.

Cite this