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

Kensen Shi; Jory Denny; Nancy M. Amato

doi:10.1109/ICRA.2014.6907540

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 proceeding › Conference contribution

33 Scopus citations

Abstract

© 2014 IEEE. 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 language	English (US)
Title of host publication	2014 IEEE International Conference on Robotics and Automation (ICRA)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	4659-4666
Number of pages	8
ISBN (Print)	9781479936854
DOIs	https://doi.org/10.1109/ICRA.2014.6907540
State	Published - May 2014
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledged KAUST grant number(s): KUS-C1-016-04
Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/ICRA.2014.6907540

Cite this

@inproceedings{b87f7dc1a24b4d7ba07df5a238e2614c,

title = "Spark PRM: Using RRTs within PRMs to efficiently explore narrow passages",

abstract = "{\textcopyright} 2014 IEEE. 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.",

author = "Kensen Shi and Jory Denny and Amato, {Nancy M.}",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2014",

month = may,

doi = "10.1109/ICRA.2014.6907540",

language = "English (US)",

isbn = "9781479936854",

pages = "4659--4666",

booktitle = "2014 IEEE International Conference on Robotics and Automation (ICRA)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

}

TY - GEN

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

AU - Shi, Kensen

AU - Denny, Jory

AU - Amato, Nancy M.

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledged KAUST grant number(s): KUS-C1-016-04 Acknowledgements: This research supported in part by NSF awards CNS-0551685, CCF-0833199, CCF-0830753, IIS-0916053, IIS-0917266, EFRI-1240483, RI-1217991, by NIH NCI R25 CA090301-11, by Chevron, IBM, Intel, Oracle/Sun and by Award KUS-C1-016-04, made by King Abdullah University of Science and Technology (KAUST). J. Denny supported in part by an NSF Graduate Research Fellowship. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2014/5

Y1 - 2014/5

N2 - © 2014 IEEE. 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.

AB - © 2014 IEEE. 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.

UR - http://hdl.handle.net/10754/599678

UR - http://ieeexplore.ieee.org/document/6907540/

UR - http://www.scopus.com/inward/record.url?scp=84929208860&partnerID=8YFLogxK

U2 - 10.1109/ICRA.2014.6907540

DO - 10.1109/ICRA.2014.6907540

M3 - Conference contribution

SN - 9781479936854

SP - 4659

EP - 4666

BT - 2014 IEEE International Conference on Robotics and Automation (ICRA)

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

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

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this