Blind RRT: A probabilistically complete distributed RRT

Cesar Rodriguez, Jory Denny, Sam Ade Jacobs, Shawna Thomas, Nancy M. Amato

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

Abstract

Rapidly-Exploring Random Trees (RRTs) have been successful at finding feasible solutions for many types of problems. With motion planning becoming more computationally demanding, we turn to parallel motion planning for efficient solutions. Existing work on distributed RRTs has been limited by the overhead that global communication requires. A recent approach, Radial RRT, demonstrated a scalable algorithm that subdivides the space into regions to increase the computation locality. However, if an obstacle completely blocks RRT growth in a region, the planning space is not covered and is thus not probabilistically complete. We present a new algorithm, Blind RRT, which ignores obstacles during initial growth to efficiently explore the entire space. Because obstacles are ignored, free components of the tree become disconnected and fragmented. Blind RRT merges parts of the tree that have become disconnected from the root. We show how this algorithm can be applied to the Radial RRT framework allowing both scalability and effectiveness in motion planning. This method is a probabilistically complete approach to parallel RRTs. We show that our method not only scales but also overcomes the motion planning limitations that Radial RRT has in a series of difficult motion planning tasks.

Original languageEnglish (US)
Title of host publicationIROS 2013
Subtitle of host publicationNew Horizon, Conference Digest - 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems
Pages1758-1765
Number of pages8
DOIs
StatePublished - 2013
Externally publishedYes
Event2013 26th IEEE/RSJ International Conference on Intelligent Robots and Systems: New Horizon, IROS 2013 - Tokyo, Japan
Duration: Nov 3 2013Nov 8 2013

Publication series

NameIEEE International Conference on Intelligent Robots and Systems
ISSN (Print)2153-0858
ISSN (Electronic)2153-0866

Other

Other2013 26th IEEE/RSJ International Conference on Intelligent Robots and Systems: New Horizon, IROS 2013
CountryJapan
CityTokyo
Period11/3/1311/8/13

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Software
  • Computer Vision and Pattern Recognition
  • Computer Science Applications

Fingerprint Dive into the research topics of 'Blind RRT: A probabilistically complete distributed RRT'. Together they form a unique fingerprint.

  • Cite this

    Rodriguez, C., Denny, J., Jacobs, S. A., Thomas, S., & Amato, N. M. (2013). Blind RRT: A probabilistically complete distributed RRT. In IROS 2013: New Horizon, Conference Digest - 2013 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 1758-1765). [6696587] (IEEE International Conference on Intelligent Robots and Systems). https://doi.org/10.1109/IROS.2013.6696587