A scalable method for parallelizing sampling-based motion planning algorithms

Sam Ade Jacobs; Kasra Manavi; Juan Burgos; Jory Denny; Shawna Thomas; Nancy M. Amato

doi:10.1109/ICRA.2012.6225334

A scalable method for parallelizing sampling-based motion planning algorithms

Sam Ade Jacobs, Kasra Manavi, Juan Burgos, Jory Denny, Shawna Thomas, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

21 Scopus citations

Abstract

This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine. © 2012 IEEE.

Original language	English (US)
Title of host publication	2012 IEEE International Conference on Robotics and Automation
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	2529-2536
Number of pages	8
ISBN (Print)	9781467314053
DOIs	https://doi.org/10.1109/ICRA.2012.6225334
State	Published - May 2012
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: CRI-0551685, CCF-0833199, CCF-0830753, IIS-096053, IIS-0917266, NSF/DNDO award2008-DN-077-ARI018-02, by the DOE NNSA under the Predictive ScienceAcademic Alliances Program grant DE-FC52-08NA28616, by THECBNHARP award 000512-0097-2009, by Chevron, IBM, Intel, Oracle/Sun andby Award KUS-C1-016-04, made by King Abdullah University of Scienceand Technology (KAUST). This research used resources of the NationalEnergy Research Scientific Computing Center, which is supported by theOffice of Science of the U.S. Department of Energy under Contract No.DE-AC02-05CH11231.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/ICRA.2012.6225334

Cite this

@inproceedings{048df575b5654fc5b254dd14577a1ce1,

title = "A scalable method for parallelizing sampling-based motion planning algorithms",

abstract = "This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine. {\textcopyright} 2012 IEEE.",

author = "Jacobs, {Sam Ade} and Kasra Manavi and Juan Burgos and Jory Denny and Shawna Thomas 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: CRI-0551685, CCF-0833199, CCF-0830753, IIS-096053, IIS-0917266, NSF/DNDO award2008-DN-077-ARI018-02, by the DOE NNSA under the Predictive ScienceAcademic Alliances Program grant DE-FC52-08NA28616, by THECBNHARP award 000512-0097-2009, by Chevron, IBM, Intel, Oracle/Sun andby Award KUS-C1-016-04, made by King Abdullah University of Scienceand Technology (KAUST). This research used resources of the NationalEnergy Research Scientific Computing Center, which is supported by theOffice of Science of the U.S. Department of Energy under Contract No.DE-AC02-05CH11231. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2012",

month = may,

doi = "10.1109/ICRA.2012.6225334",

language = "English (US)",

isbn = "9781467314053",

pages = "2529--2536",

booktitle = "2012 IEEE International Conference on Robotics and Automation",

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

}

TY - GEN

T1 - A scalable method for parallelizing sampling-based motion planning algorithms

AU - Jacobs, Sam Ade

AU - Manavi, Kasra

AU - Burgos, Juan

AU - Denny, Jory

AU - Thomas, Shawna

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: CRI-0551685, CCF-0833199, CCF-0830753, IIS-096053, IIS-0917266, NSF/DNDO award2008-DN-077-ARI018-02, by the DOE NNSA under the Predictive ScienceAcademic Alliances Program grant DE-FC52-08NA28616, by THECBNHARP award 000512-0097-2009, by Chevron, IBM, Intel, Oracle/Sun andby Award KUS-C1-016-04, made by King Abdullah University of Scienceand Technology (KAUST). This research used resources of the NationalEnergy Research Scientific Computing Center, which is supported by theOffice of Science of the U.S. Department of Energy under Contract No.DE-AC02-05CH11231. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2012/5

Y1 - 2012/5

N2 - This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine. © 2012 IEEE.

AB - This paper describes a scalable method for parallelizing sampling-based motion planning algorithms. It subdivides configuration space (C-space) into (possibly overlapping) regions and independently, in parallel, uses standard (sequential) sampling-based planners to construct roadmaps in each region. Next, in parallel, regional roadmaps in adjacent regions are connected to form a global roadmap. By subdividing the space and restricting the locality of connection attempts, we reduce the work and inter-processor communication associated with nearest neighbor calculation, a critical bottleneck for scalability in existing parallel motion planning methods. We show that our method is general enough to handle a variety of planning schemes, including the widely used Probabilistic Roadmap (PRM) and Rapidly-exploring Random Trees (RRT) algorithms. We compare our approach to two other existing parallel algorithms and demonstrate that our approach achieves better and more scalable performance. Our approach achieves almost linear scalability on a 2400 core LINUX cluster and on a 153,216 core Cray XE6 petascale machine. © 2012 IEEE.

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

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

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

U2 - 10.1109/ICRA.2012.6225334

DO - 10.1109/ICRA.2012.6225334

M3 - Conference contribution

SN - 9781467314053

SP - 2529

EP - 2536

BT - 2012 IEEE International Conference on Robotics and Automation

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

A scalable method for parallelizing sampling-based motion planning algorithms

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this