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

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.

Original languageEnglish (US)
Title of host publication2018 IEEE International Conference on Robotics and Automation, ICRA 2018
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages3053-3060
Number of pages8
ISBN (Electronic)9781538630815
DOIs
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

Conference

Conference2018 IEEE International Conference on Robotics and Automation, ICRA 2018
CountryAustralia
CityBrisbane
Period5/21/185/25/18

ASJC Scopus subject areas

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

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

Cite this