A scalable distributed RRT for motion planning

Sam Ade Jacobs, Nicholas Stradford, Cesar Rodriguez, Shawna Thomas, Nancy M. Amato

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

21 Scopus citations

Abstract

Rapidly-exploring Random Tree (RRT), like other sampling-based motion planning methods, has been very successful in solving motion planning problems. Even so, sampling-based planners cannot solve all problems of interest efficiently, so attention is increasingly turning to parallelizing them. However, one challenge in parallelizing RRT is the global computation and communication overhead of nearest neighbor search, a key operation in RRTs. This is a critical issue as it limits the scalability of previous algorithms. We present two parallel algorithms to address this problem. The first algorithm extends existing work by introducing a parameter that adjusts how much local computation is done before a global update. The second algorithm radially subdivides the configuration space into regions, constructs a portion of the tree in each region in parallel, and connects the subtrees,i removing cycles if they exist. By subdividing the space, we increase computation locality enabling a scalable result. We show that our approaches are scalable. We present results demonstrating almost linear scaling to hundreds of processors on a Linux cluster and a Cray XE6 machine. © 2013 IEEE.
Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages5088-5095
Number of pages8
ISBN (Print)9781467356435
DOIs
StatePublished - May 2013
Externally publishedYes

Fingerprint Dive into the research topics of 'A scalable distributed RRT for motion planning'. Together they form a unique fingerprint.

Cite this