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

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.

Original languageEnglish (US)
Title of host publication2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Pages5088-5095
Number of pages8
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 IEEE International Conference on Robotics and Automation, ICRA 2013 - Karlsruhe, Germany
Duration: May 6 2013May 10 2013

Publication series

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

Other

Other2013 IEEE International Conference on Robotics and Automation, ICRA 2013
Country/TerritoryGermany
CityKarlsruhe
Period5/6/135/10/13

ASJC Scopus subject areas

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

Fingerprint

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

Cite this