WOLFRAM NOTEBOOK

Rapidly Exploring Random Tree (RRT) and RRT*

​
tree type
Random Tree
RRT
*
RRT
obstacle type
narrow passage
number of nodes to add:
1
10
100
200
500
exploration bias
0
goal radius
1
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 Demonstration lets you compare 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. Drag the goal locator to search for a path.

Details

This Demonstration shows 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. As shown in the Snapshots, a tree generated by random motion from a randomly selected tree node does not explore very far (Snapshot 1). 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. This Demonstration attempts to construct a path (dark green) from the starting point (red) to the goal locator. Exploration can be biased toward the goal instead of random sampling by changing the corresponding slider.
In this Demonstration, each node on the tree has a tooltip that reports the total distance to this node from the root node at
{0,0}
. In general, the path lengths for RRT* are shorter than RRT. 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–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–894. doi:10.1177/0278364911406761.
[4] Wikipedia. "Rapidly-Exploring Random Tree." (Jan 11, 2018) en.wikipedia.org/wiki/Rapidly-exploring_random _tree.

External Links

Permanent Citation

Wolfram Cloud

You are using a browser not supported by the Wolfram Cloud

Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.


I understand and wish to continue anyway »

You are using a browser not supported by the Wolfram Cloud. Supported browsers include recent versions of Chrome, Edge, Firefox and Safari.