A rapidly exploring random tree is an algorithm designed to efficiently search nonconvex, high-dimensional spaces by randomly building a space-filling tree. The tree is constructed incrementally from samples drawn randomly from the search space and is inherently biased to grow towards large unsearched areas of the problem. RRTs were developed by Steven M. LaValle and James J. Kuffner Jr. They easily handle problems with obstacles and differential constraints and have been widely used in autonomousrobotic motion planning. RRTs can be viewed as a technique to generate open-loop trajectories for nonlinear systems with state constraints. An RRT can also be considered as a Monte-Carlo method to bias search into the largest Voronoi regions of a graph in a configuration space. Some variations can even be considered stochastic fractals.
Description
An RRT grows a tree rooted at the starting configuration by using random samples from the search space. As each sample is drawn, a connection is attempted between it and the nearest state in the tree. If the connection is feasible, this results in the addition of the new state to the tree. With uniform sampling of the search space, the probability of expanding an existing state is proportional to the size of its Voronoi region. As the largest Voronoi regions belong to the stateson the frontier of the search, this means that the tree preferentially expands towards large unsearched areas. The length of the connection between the tree and a new state is frequently limited by a growth factor. If the random sample is further from its nearest state in the tree than this limit allows, a new state at the maximum distance from the tree along the line to the random sample is used instead of the random sample itself. The random samples can then be viewed as controlling the direction of the tree growth while the growth factor determines its rate. This maintains the space-filling bias of the RRT while limiting the size of the incremental growth. RRT growth can be biased by increasing the probability of sampling states from a specific area. Most practical implementations of RRTs make use of this to guide the search towards the planning problem goals. This is accomplished by introducing a small probability of sampling the goal to the state sampling procedure. The higher this probability, the more greedily the tree grows towards the goal.
Algorithm
For a general configuration space C, the algorithm in pseudocode is as follows: Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq) Output: RRT graph G G.init fork = 1 toKdo qrand ← RAND_CONF qnear ← NEAREST_VERTEX qnew ← NEW_CONF G.add_vertex G.add_edge returnG In the algorithm above, "RAND_CONF" grabs a random configuration qrand in C. This may be replaced with a function "RAND_FREE_CONF" that uses samples in Cfree, while rejecting those in Cobs using some collision detection algorithm. "NEAREST_VERTEX" is a function that runs through all vertices v in graph G, calculates the distance between qrand and v using some measurement function thereby returning the nearest vertex. "NEW_CONF" selects a new configuration qnew by moving an incremental distance Δq from qnear in the direction of qrand.
Variants and improvements for motion planning
Parti-game directed RRTs, a method that combines RRTs with the parti-game method to refine the search where it is needed to be able to plan faster and solve more motion planning problems than RRT
Closed-loop rapidly-exploring random, an extension of RRT that samples an input to a stable closed-loop systemconsisting of the vehicle and a controller
It has been shown that, under 'mild technical conditions', the cost of the best path in the RRT converges almost surely to a non-optimal value. For that reason, it is desirable to find variants of the RRT that converges to an optimum, like RRT*. Below follows is a list of RRT*-based methods. Not all of the derived methods do themselves converge to an optimum, though.
Rapidly-exploring random graph and RRT*, a variant of RRT that converges towards an optimal solution
A*-RRT and A*-RRT*, a two-phase motion planning method that uses a graph search algorithm to search for an initial feasible path in a low-dimensional space in a first phase, avoiding hazardous areas and preferring low-risk routes, which is then used to focus the RRT* search in the continuous high-dimensional space in a second phase
RRT*FN, RRT* with a fixed number of nodes, which randomly removes a leaf node in the tree in every iteration
RRT*-AR, sampling-based alternate routes planning
Informed RRT*, improves the convergence speed of RRT* by introducing a heuristic, similar to the way in which A* improves upon Dijkstra's algorithm
Real-Time RRT*, a variant of RRT* and informed RRT* that uses an online tree rewiring strategy that allows the tree root to move with the agent without discarding previously sampled paths, in order to obtain real-time path-planning in a dynamic environment such as a computer game
RRT and RRT, optimization of RRT* for dynamic environments
Theta*-RRT, a two-phase motion planning method similar to A*-RRT* that uses a hierarchical combination of any-angle search with RRT motion planning for fast trajectory generation in environments with complex nonholonomic constraints
RRT* FND, extension of RRT* for dynamic environments
