A visualization of an RRT graph after 45 and 390 iterations
An animation of an RRT starting from iteration 0 to 10000
Arapidly exploring random tree (RRT) is analgorithm designed to efficiently searchnonconvex, high-dimensional spaces by randomly building aspace-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 bySteven M. LaValle andJames J. Kuffner Jr.[1][2]They easily handle problems with obstacles and differential constraints (nonholonomic and kinodynamic) and have been widely used inautonomous roboticmotion 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 aMonte-Carlo method to bias search into the largestVoronoi regions of a graph in a configuration space. Some variations can even be consideredstochasticfractals.[3]
RRTs can be used to compute approximate control policies to control high dimensional nonlinear systems with state and action constraints.
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 (passes entirely through free space and obeys any constraints), 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 itsVoronoi region.As the largestVoronoi regions belong to the states on 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 BuildRRT Input: Initial configurationqinit, number of vertices in RRTK, incremental distanceΔq Output: RRT graphGG.init(qinit)fork = 1toKdoqrand ← RAND_CONF()qnear ← NEAREST_VERTEX(qrand,G)qnew ← NEW_CONF(qnear,qrand,Δq)G.add_vertex(qnew)G.add_edge(qnear,qnew)returnG
"←" denotesassignment. For instance, "largest ←item" means that the value oflargest changes to the value ofitem.
"return" terminates the algorithm and outputs the following value.
In the algorithm above, "RAND_CONF" grabs a random configurationqrand inC. This may be replaced with a function "RAND_FREE_CONF" that uses samples inCfree, while rejecting those inCobs using some collision detection algorithm.
"NEAREST_VERTEX" is a function that runs through all verticesv in graphG, calculates the distance betweenqrand andv using some measurement function thereby returning the nearest vertex.
"NEW_CONF" selects a new configurationqnew by moving an incremental distanceΔq fromqnear in the direction ofqrand. (According to[4] in holonomic problems, this should be omitted andqrand used instead ofqnew.)
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.[5] 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 (starting with RRT* itself). Not all of the derived methods do themselves converge to an optimum, though.
Rapidly exploring random graph (RRG) and RRT*,[5][6][7] a variant of RRT that converges towards an optimal solution
RRT+,[9] a family of RRT-based planners aiming to generate solutions for high-dimensional systems in real-time, by progressively searching in lower-dimensional subspaces.
RRT*-Smart,[10] a method foraccelerating the convergence rate of RRT* by using path optimization (in a similar fashion toTheta*) and intelligent sampling (by biasing sampling towards path vertices, which – after path optimization – are likely to be close to obstacles)
A*-RRT and A*-RRT*,[11] a two-phasemotion planning method that uses agraph search algorithm to search for an initial feasible path in a low-dimensional space (not considering the complete state 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,[12][13][14] RRT* with a fixed number of nodes, which randomly removes a leaf node in the tree in every iteration
Informed RRT*,[16][17] improves the convergence speed of RRT* by introducing a heuristic, similar to the way in whichA* improves uponDijkstra's algorithm
Real-Time RRT* (RT-RRT*),[18] 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 obtainreal-time path-planning in a dynamic environment such as a computer game
RRTX and RRT#,[19][20] optimization of RRT* for dynamic environments
Theta*-RRT,[21] a two-phasemotion planning method similar to A*-RRT* that uses a hierarchical combination ofany-angle search with RRT motion planning for fast trajectory generation in environments with complexnonholonomic constraints
RRT* FND,[22][23] extension of RRT* for -dynamic environments
RRT-GPU,[24] three-dimensional RRT implementation that utilizes hardware acceleration
APF-RRT,[25] a combination of RRT planner with Artificial Potential Fields method that simplify the replanning task
CERRT,[26] a RRT planner modeling uncertainty, which is reduced exploiting contacts
MVRRT*,[27] Minimum violation RRT*, an algorithm that finds the shortest route that minimizes the level of unsafety (the "cost" of the environment rules that have been violated, e.g. traffic laws)
RRT-Blossom,[28] RRT planner for highly constrained environments.
RRV,[29] efficiently expand the tree around obstacles and through narrow passages, using dominant eigenvectors around tree nodes.
RBT,[30] uses simple distance computations in the workspace to expand the tree instead of expensive collision check.
TB-RRT,[31] Time-based RRT algorithm for rendezvous planning of two dynamic systems.
RRdT*,[32][33] a RRT*-based planner that uses multiple local trees to actively balances the exploration and exploitation of the space by performing local sampling.
Tri-RRT-Connect,[34][35] Triangular inequality-based rewiring method with RRT-Connect algorithm to bring it closer to the optimum.
RRT-Rope,[36] a method for fast near-optimal path planning using a deterministic shortening approach, very effective in open and large environments.
Parti-game directed RRTs (PDRRTs),[37] a method that combines RRTs with the parti-game method[38] to refine the search where it is needed (for example around obstacles) to be able to plan faster and solve moremotion planning problems than RRT
Closed-loop rapidly exploring random (CL-RRT),[39] an extension of RRT that samples an input to a stable closed-loop system consisting of the vehicle and a controller
Adaptively informed trees (AIT*) and effort informed trees (EIT*)[40]
^Adiyatov, Olzhas; Varol, Huseyin Atakan. "Rapidly-exploring random tree based memory efficient motion planning". InMechatronics and Automation (ICMA), 2013 IEEE International Conference on, pages 354–359, 2013.doi:10.1109/ICMA.2013.6617944
^Gammell, Jonathan D.; Srinivasa, Siddhartha S.; Barfoot, Timothy D. (8 Apr 2014). "Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic".2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2997–3004.arXiv:1404.2334.doi:10.1109/IROS.2014.6942976.ISBN978-1-4799-6934-0.S2CID12233239.
^Adiyatov, Olzhas; Varol, Huseyin Atakan. "A novel RRT-based algorithm for motion planning in Dynamic environments". InMechatronics and Automation (ICMA), 2017 IEEE International Conference on, pages 1416-1421, 2017.doi:10.1109/ICMA.2017.8016024
^Strub, Marlin P.; Gammell, Jonathan D. (2022). "Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning".The International Journal of Robotics Research.41 (4):390–417.arXiv:2111.01877.doi:10.1177/02783649211069572.
_500x373.gif)
