Home research People General Info Seminars Resources Intranet
| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Distributed RRT

In this work, a scalable parallel RRT implementation is designed to solve highly complex problems. Unlike the classic RRT, distributed RRT's radially subdivide the environment about the root node into a set of regions for each processor to map. Each branch of the RRT is biased along the length of these subdivisions.

Distributed RRT Illustrations

Figure 1: Example of a radial subdivision for a 2D CSpace from a root node. Each process
concurrently builds a subtree from the root and attempts to connect to goal.

Figure 2: Tree prunning example. The new edge between the red and blue branches causes
a cycle in the red branch, so the dashed edge is identified and removed.

In this work, Blind RRT replaces basic RRT in the Distributed RRT framework. Unlike basic RRT, Blind RRT initially ignores obstacles while growing the distributed RRT. After a while, the RRT's nodes are collision checked which may produce several connected components as both nodes and edges are invalidated. At this point attempts are made to connected these disjoint roadmaps to form as few components as possible.

Blind RRT Illustrations

Figure 1: With Blind Distributed RRT's lazy validity evaluation, the trees can grow
unabated until collision detection is performed. In (a) we have an environment
subdivided into 4 regions. (b) We run Blind Distributed RRT. (c) Collision detection
is performed and invalid nodes and edges are removed. Then in (d) the connected components
connect to other components while avoiding cycles.

Figure 2: Blind RRT expands until a stop condition is met (a).
Free witnesses are retained (b) or only the first free witness
(c) to return a set of expansion nodes.

A Scalable Framework for Parallelizing Sampling-Based Motion Planning Algorithms, Sam Ade Jacobs, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, May 2014.
Ph.D. Thesis(pdf, abstract)

Blind RRT: A Probabilistically Complete Distributed RRT, Cesar Rodriguez, Jory Denny, Sam Jacobs, Shawna L. Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 1758 - 1765, Tokyo, Japan, Nov 2013.
Proceedings(ps, pdf, abstract)

A Scalable Distributed RRT for Motion Planning, Sam Ade Jacobs, Nicholas Stradford, Cesar Rodriguez, Shawna Thomas, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 5088-5095, Karlsruhe, Germany, May 2013.
Proceedings(ps, pdf, abstract)

Supported by King Abdullah University of Science and Technology (KAUST), NSF, Dept. of Education, Texas Higher Education Coordinating Board

Project Alumni:Sam Ade Jacobs,Cesar Rodriguez,Nicholas Stradford

Related Projects
STAPL