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
Parasol Home | Research | People | General info | Seminars | Resources
Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112
firstname.lastname@example.org Phone 979.458.0722 Fax 979.458.0718
Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards - Contact Webmaster