Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages

Kensen Shi, Jory Denny, Nancy M. Amato

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

Abstract

Probabilistic RoadMaps (PRMs) have been successful for many high-dimensional motion planning problems. However, they encounter difficulties when mapping narrow passages. While many PRM sampling methods have been proposed to increase the proportion of samples within narrow passages, such difficult planning areas still pose many challenges. We introduce a novel algorithm, Spark PRM, that sparks the growth of Rapidly-expanding Random Trees (RRTs) from narrow passage samples generated by a PRM. The RRT rapidly generates further narrow passage samples, ideally until the passage is fully mapped. After reaching a terminating condition, the tree stops growing and is added to the roadmap. Spark PRM is a general method that can be applied to all PRM variants. We study the benefits of Spark PRM with a variety of sampling strategies in a wide array of environments. We show significant speedups in computation time over RRT, Sampling-based Roadmap of Trees (SRT), and various PRM variants.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE International Conference on Robotics and Automation
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages4659-4666
Number of pages8
ISBN (Electronic)9781479936854, 9781479936854
DOIs
StatePublished - Sep 22 2014
Externally publishedYes
Event2014 IEEE International Conference on Robotics and Automation, ICRA 2014 - Hong Kong, China
Duration: May 31 2014Jun 7 2014

Publication series

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

Other

Other2014 IEEE International Conference on Robotics and Automation, ICRA 2014
Country/TerritoryChina
CityHong Kong
Period5/31/146/7/14

ASJC Scopus subject areas

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

Fingerprint

Dive into the research topics of 'Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages'. Together they form a unique fingerprint.

Cite this