RRT, RRT* & Random Trees

Lecture 24 of Intro to Robotics @ University of Houston.
using http://demonstrations.wolfram.com/RapidlyExploringRandomTreeRRTAndRRT/ by Aaron Becker and Li Huang

A rapidly exploring random tree (RRT) grows a tree rooted at a start node. RRTs are designed to efficiently explore paths in a high-dimensional space. This lecture compares random trees (RTs), RRTs and RRT*. An RT selects a node at random from the tree and adds an edge in a random direction, but an RRT first selects a goal point, then tries to add an edge from the closest node in the tree toward the goal point. RRT* improves on this by rewiring the tree to form shortest paths.

We show a tree defined by red nodes with black edges. Obstacles are drawn in blue, and the goal position is indicated by a locator surrounded by a disc of radius goal radius. This is yellow before the goal is reached and turns green after success. A tree generated by random motion from a randomly selected tree node does not explore very far. A rapidly exploring random tree (RRT) first selects a goal point (drawn in green), then tries to add an edge from the closest node in the tree (blue) toward the goal point. This results in a tree that tends to quickly explore the space, because search is biased into the largest Voronoi regions of a graph defined by the tree. RRT* improves on this by rewiring the tree to form shortest paths. RRT* converges to the shortest path, at the cost of more computation. All three trees are probabilistically complete, meaning if a nonzero width path exists, the tree will eventually find the path.

In general, the path lengths for RRT* are shorter than RRT. The online Mathematica Demonstration lets you try changing the obstacle type, the tree type and the goal location.

RRTs were developed by S. M. LaValle and J. J. Kuffner Jr. in [1] and [2]. They are often used for robot motion planning, especially for high-dimensional problems with obstacles. The RRT* variant was introduced by S. Karaman and E. Frazolli [3].

References
[1] S. M. LaValle, Rapidly-Exploring Random Trees: A New Tool for Path Planning, Computer Science Department, Iowa State University (TR 98-11), 1998.
[2] S. M. LaValle and J. J. Kuffner, Jr., "Randomized Kinodynamic Planning," The International Journal of Robotics Research, 20(5), 2001 pp. 378\[Dash]400. doi:10.1177/02783640122067453.
[3] S. Karaman and E. Frazzoli, "Sampling-Based Algorithms for Optimal Motion Planning," The International Journal of Robotics Research, 30(7), 2011 pp. 846\[Dash]894. doi:10.1177/0278364911406761.
[4] Wikipedia. "Rapidly-Exploring Random Tree." (Jan 11, 2018) en.wikipedia.org/wiki/Rapidly-exploring_random_tree.

This work was supported by the National Science Foundation under Grant No. IIS-1646607 https://nsf.gov/awardsearch/showAward?AWD_ID=1646607

Видео RRT, RRT* & Random Trees канала Aaron Becker