rapidly exploring random tree

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 its Voronoi region.

As the largest Voronoi 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.

For a general configuration space C, the algorithm in pseudocode is as follows:

{{algorithm-begin|name=BuildRRT|test}}

Input: Initial configuration q_init, number of vertices in RRT K, incremental distance Δq

Output: RRT graph G

G.init(q_init)

for k = 1 to K do

q_rand ← RAND_CONF()

q_near ← NEAREST_VERTEX(q_rand, G)

q_new ← NEW_CONF(q_near, q_rand, Δq)

G.add_vertex(q_new)

G.add_edge(q_near, q_new)

return G

{{algorithm-end}}

In the algorithm above, "RAND_CONF" grabs a random configuration q_rand in C. This may be replaced with a function "RAND_FREE_CONF" that uses samples in C_free, while rejecting those in C_obs using some collision detection algorithm.

"NEAREST_VERTEX" is a function that runs through all vertices v in graph G, calculates the distance between q_rand and v using some measurement function thereby returning the nearest vertex.

"NEW_CONF" selects a new configuration q_new by moving an incremental distance Δq from q_near in the direction of q_rand. (According to Rapidly-Exploring Random Trees: Progress and Prospects (2000), by Steven M. Lavalle, James J. Kuffner, Jr. Algorithmic and Computational Robotics: New Directions, http://eprints.kfupm.edu.sa/60786/1/60786.pdf{{dead link|date=January 2018 |bot=InternetArchiveBot |fix-attempted=yes }} in holonomic problems, this should be omitted and q_rand used instead of q_new.)

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.{{cite arXiv |last1=Karaman |first1=Sertac |last2=Frazzoli |first2=Emilio |eprint=1005.0416 |title=Incremental Sampling-based Algorithms for Optimal Motion Planning |class=cs.RO |date=3 May 2010}} 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*,{{cite arXiv |last1=Karaman |first1=Sertac |last2=Frazzoli |first2=Emilio |eprint=1105.1186 |title=Sampling-based Algorithms for Optimal Motion Planning |class=cs.RO |date=5 May 2011}}{{cite web|author1=OlzhasAdi|title=RRT* Brief Explanation|url=https://www.youtube.com/watch?v=JM7kmWE8Gtc |archive-url=https://ghostarchive.org/varchive/youtube/20211212/JM7kmWE8Gtc| archive-date=2021-12-12 |url-status=live|website=YouTube|accessdate=3 August 2016|format=video|date=Jan 26, 2015}}{{cbignore}} a variant of RRT that converges towards an optimal solution

• LQR-RRT,{{Cite book |last1=Perez |first1=Alejandro |last2=Platt |first2=Robert |last3=Konidaris |first3=George |last4=Kaelbling |first4=Leslie |last5=Lozano-Perez |first5=Tomas |title=2012 IEEE International Conference on Robotics and Automation |chapter=LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics |date=May 2012 |chapter-url=https://ieeexplore.ieee.org/document/6225177 |pages=2537–2542 |doi=10.1109/ICRA.2012.6225177|isbn=978-1-4673-1405-3 |s2cid=1914056 }} a kinodynamic variant for complex or underactuated dynamics

• RRT{{sup|+}},{{Cite journal|last1=Xanthidis|first1=Marios|last2=Esposito|first2=Joel M.|last3=Rekleitis|first3=Ioannis|last4=O’Kane|first4=Jason M.|date=2020-12-01|title=Motion Planning by Sampling in Subspaces of Progressively Increasing Dimension|url=https://doi.org/10.1007/s10846-020-01217-w|journal=Journal of Intelligent & Robotic Systems|language=en|volume=100|issue=3|pages=777–789|doi=10.1007/s10846-020-01217-w|s2cid=3622004 |issn=1573-0409|url-access=subscription}} 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,Islam, Fahad; Nasir, Jauwairia; Malik, Usman; Ayaz, Yasar; Hasan, Osman; "[http://save.seecs.nust.edu.pk/pubs/ICMA2012.pdf RRT*-Smart: Rapid convergence implementation of RRT* towards optimal solution]", in Proceedings of IEEE International Conference on Mechatronics and Automation (ICMA), pages 1651–1656, Chengdu, China, August 2012. a method for accelerating the convergence rate of RRT* by using path optimization (in a similar fashion to Theta*) 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*,Brunner, M.; Bruggemann, B.; Schulz, D.. "[https://www.semanticscholar.org/paper/Hierarchical-rough-terrain-motion-planning-using-Brunner-Br%C3%BCggemann/0a7d2ed587df4bf8c3b6d6038cae5ba131861e43/pdf Hierarchical rough terrain motion planning using an optimal sampling-based method]," in Int. Conf. on Robotics and Automation (ICRA), Karlsruhe, Germany, 2013. a two-phase motion planning method that uses a graph 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,Adiyatov, Olzhas; Varol, Huseyin Atakan. "Rapidly-exploring random tree based memory efficient motion planning". In Mechatronics and Automation (ICMA), 2013 IEEE International Conference on, pages 354–359, 2013. {{doi|10.1109/ICMA.2013.6617944}}{{cite web|author1=Adiyatov, Olzhas|author2=Varol, Atakan|title=MATLAB Toolbox of RRT, RRT* and RRT*FN algorithms|url=http://arms.nu.edu.kz/research/matlab-toolbox-rrt-based-algorithms|accessdate=3 August 2016|date=2013}}{{cite web|author1=OlzhasAdi|title=RRT*FN Brief Explanation|url=https://www.youtube.com/watch?v=Kv0yqVP5iNA |archive-url=https://ghostarchive.org/varchive/youtube/20211212/Kv0yqVP5iNA| archive-date=2021-12-12 |url-status=live|website=YouTube|accessdate=3 August 2016|format=video|date=Jan 26, 2015}}{{cbignore}} RRT* with a fixed number of nodes, which randomly removes a leaf node in the tree in every iteration

• RRT*-AR,Choudhury, Sanjiban; Scherer, Sebastian; Singh, Sanjiv. "[http://repository.cmu.edu/robotics/994/ RRT*-AR: Sampling-based alternate routes planning with applications to autonomous emergency landing of a helicopter]". In Robotics and Automation (ICRA), 2013 IEEE International Conference on, Karlsruhe, 6–10 May 2013, pages 3947–3952. {{doi|10.1109/ICRA.2013.6631133}} sampling-based alternate routes planning

• Informed RRT*,{{cite book |first1=Jonathan D. |last1=Gammell |first2=Siddhartha S.|last2=Srinivasa |first3=Timothy D. |last3=Barfoot |title=2014 IEEE/RSJ International Conference on Intelligent Robots and Systems |chapter=Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic |arxiv=1404.2334 |date=8 Apr 2014 |doi=10.1109/IROS.2014.6942976 |pages=2997–3004 |isbn=978-1-4799-6934-0 |s2cid=12233239 }}{{cite web|author1=utiasASRL|title=Informed RRT* @ UTIAS (IROS 2014) |url=https://www.youtube.com/watch?v=nsl-5MZfwu4 |archive-url=https://ghostarchive.org/varchive/youtube/20211212/nsl-5MZfwu4| archive-date=2021-12-12 |url-status=live|website=YouTube|accessdate=3 August 2016|format=video|date=Jul 4, 2014}}{{cbignore}} 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* (RT-RRT*),Naderi, Kourosh; Rajamäki, Joose; Hämäläinen, Perttu (2015). "[https://mediatech.aalto.fi/~phamalainen/FutureGameAnimation/p113-naderi.pdf RT-RRT*: a real-time path planning algorithm based on RRT*]". In Proceedings of the 8th ACM SIGGRAPH Conference on Motion in Games (MIG '15). ACM, New York, NY, USA, 113–118. {{doi|10.1145/2822013.2822036}} 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{{sup|X}} and RRT{{sup|#}},{{Cite web |url=http://robot.cmpe.boun.edu.tr/wafr2014/papers/paper_35.pdf |title=RRT{{sup|X}}: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles |access-date=2018-03-02 |archive-date=2017-05-19 |archive-url=https://web.archive.org/web/20170519114919/http://robot.cmpe.boun.edu.tr/wafr2014/papers/paper_35.pdf |url-status=dead }}[https://www.youtube.com/watch?v=xq1qAkvgX_Q Comparison of RRTX, RRT# and RRT* when a shortcut is discovered in a static environment] optimization of RRT* for dynamic environments

• Theta*-RRT,Palmieri, Luigi; Koenig, Sven; Arras, Kai O. "[http://idm-lab.org/bib/abstracts/Koen16d.html RRT-Based Nonholonomic Motion Planning Using Any-Angle Path Biasing]". In Robotics and Automation (ICRA), 2016 Proceedings of the IEEE International Conference on, pages 2775-2781, 2016. 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,[https://www.youtube.com/watch?v=hXTnWN8NiKE RRT* FND - motion planning in dynamic environments]Adiyatov, Olzhas; Varol, Huseyin Atakan. "A novel RRT-based algorithm for motion planning in Dynamic environments". In Mechatronics and Automation (ICMA), 2017 IEEE International Conference on, pages 1416-1421, 2017. {{doi|10.1109/ICMA.2017.8016024}} extension of RRT* for -dynamic environments
• RRT-GPU,{{Cite thesis|last=Ford|first=Christen|title=RRT-GPU and Minecraft: Hardware Accelerated Rapidly Exploring Random Trees in Three Dimensions|date=2018-06-12|url=https://www.researchgate.net/publication/325722546|doi=10.13140/rg.2.2.15658.11207}} three-dimensional RRT implementation that utilizes hardware acceleration

• APF-RRT,{{cite conference |last1= Amiryan |first1= Javad |last2= Jamzad |first2= Mansour |date= 2015 |title= Adaptive motion planning with artificial potential fields using a prior path| url= https://www.researchgate.net/publication/308839765 | conference = Robotics and Mechatronics (ICROM), 2015 3rd RSI International Conference on | pages = 731–736 }} a combination of RRT planner with Artificial Potential Fields method that simplify the replanning task

• CERRT,{{cite conference|last1=Sieverling|first1=Arne|last2=Eppner|first2=Clemens|last3=Wolff|first3=Felix|last4=Brock|first4=Oliver|date=2017|title= Interleaving motion in contact and in free space for planning under uncertainty.| url= https://www.robotics.tu-berlin.de/fileadmin/fg170/Publikationen_pdf/Sieverling17_IROS.pdf | conference = 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) | pages = 4011–4073 }} a RRT planner modeling uncertainty, which is reduced exploiting contacts
• MVRRT*,{{cite arXiv|last1=Rus|first1=Daniela|last2=Frazzoli|first2=Emilio|last3=Karaman|first3=Sertac|last4=Tumova|first4=Jana|last5=Chaudhari|first5=Pratik|last6=Castro|first6=Luis I. Reyes|date=2013-05-06|title=Incremental Sampling-based Algorithm for Minimum-violation Motion Planning|class=cs.RO|language=en|eprint=1305.1102}} 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,{{Cite web|url=http://www.dgp.toronto.edu/~mac/research/rrt-blossom/index.html|title=Maciej Kalisiak - RRT-blossom|website=www.dgp.toronto.edu|access-date=2020-01-18}} RRT planner for highly constrained environments.

• RRV,{{Cite book |last1=Tahirovic |first1=Adnan |last2=Ferizbegovic |first2=Mina |title=2018 IEEE International Conference on Robotics and Automation (ICRA) |chapter=Rapidly-Exploring Random Vines (RRV) for Motion Planning in Configuration Spaces with Narrow Passages |date=May 2018 |chapter-url=https://ieeexplore.ieee.org/document/8460186 |pages=7055–7062 |doi=10.1109/ICRA.2018.8460186|isbn=978-1-5386-3081-5 |s2cid=52285080 }} efficiently expand the tree around obstacles and through narrow passages, using dominant eigenvectors around tree nodes.

• RBT,{{Cite book |last1=Lacevic |first1=Bakir |last2=Osmankovic |first2=Dinko |last3=Ademovic |first3=Adnan |title=2016 IEEE International Conference on Robotics and Automation (ICRA) |chapter=Burs of free C-space: A novel structure for path planning |date=May 2016 |chapter-url=https://ieeexplore.ieee.org/document/7487117 |pages=70–76 |doi=10.1109/ICRA.2016.7487117|isbn=978-1-4673-8026-3 |s2cid=15834630 }} uses simple distance computations in the workspace to expand the tree instead of expensive collision check.

• TB-RRT,{{cite conference|chapter-url=https://ieeexplore.ieee.org/document/6907855|chapter=Time-based RRT algorithm for rendezvous planning of two dynamic systems|last1=Sintov|first1=Avishai|last2=Shapiro|first2=Amir|title=2014 IEEE International Conference on Robotics and Automation (ICRA) |date=2014|pages=6745–6750 |doi=10.1109/ICRA.2014.6907855|isbn=978-1-4799-3685-4 |conference=IEEE International Conference on Robotics and Automation (ICRA)}} Time-based RRT algorithm for rendezvous planning of two dynamic systems.

• RRdT*,{{Cite book|last1=Lai|first1=Tin|last2=Ramos|first2=Fabio|last3=Francis|first3=Gilad|title=2019 International Conference on Robotics and Automation (ICRA) |chapter=Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees |date=2019|chapter-url=https://ieeexplore.ieee.org/document/8793618|location=Montreal, QC, Canada|publisher=IEEE|pages=5537–5543|doi=10.1109/ICRA.2019.8793618|isbn=978-1-5386-6027-0|arxiv=1810.03749|s2cid=52945105}}{{cite journal |last1=Lai |first1=Tin |last2=Morere |first2=Philippe |last3=Ramos |first3=Fabio |last4=Francis |first4=Gilad |title=Bayesian Local Sampling-Based Planning |journal=IEEE Robotics and Automation Letters |date=April 2020 |volume=5 |issue=2 |pages=1954–1961 |doi=10.1109/LRA.2020.2969145|arxiv=1909.03452|s2cid=210838739 }} 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,{{Cite journal|last1=Kang|first1=Jin-Gu|last2=Lim|first2=Dong-Woo|last3=Choi|first3=Yong-Sik|last4=Jang|first4=Woo-Jin|last5=Jung|first5=Jin-Woo|date=2021-01-06|title=Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning|journal=Sensors|language=en|volume=21|issue=2|pages=333|doi=10.3390/s21020333|s2cid=231303809 |issn=1424-8220 |doi-access=free |pmid=33419005 |pmc=7825297|bibcode=2021Senso..21..333K }}{{cite arXiv|last1=Kang|first1=Jin-Gu|last2=Jung|first2=Jin-Woo|title=Post Triangular Rewiring Method for Shorter RRT Robot Path Planning|class=cs.RO |date=12 Jul 2021|eprint=2107.05344}} Triangular inequality-based rewiring method with RRT-Connect algorithm to bring it closer to the optimum.

• RRT-Rope,{{Cite book|last1=Petit|first1=Louis|last2=Desbiens|first2=Alexis Lussier|title=2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC) |chapter=RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments |date=2021-10-17|chapter-url=https://ieeexplore.ieee.org/document/9659071|location=Melbourne, Australia|publisher=IEEE|pages=1111–1118|doi=10.1109/SMC52423.2021.9659071|isbn=978-1-6654-4207-7|s2cid=252590377 }} 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),Ranganathan, Ananth; Koenig, Sven. PDRRTs: "[http://idm-lab.org/bib/abstracts/Koen04j.html Integrating Graph-Based and Cell-Based Planning]". In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pages 2799–2808, 2004. a method that combines RRTs with the parti-game methodMoore, A. W.; Atkeson, C. G., "[https://www.ri.cmu.edu/pub_files/pub1/moore_andrew_1995_2/moore_andrew_1995_2.pdf The parti-game algorithm for variable resolution reinforcement learning in multidimensional state-spaces]," Machine Learning, vol. 21, no. 3, pages 199–233, 1995. to refine the search where it is needed (for example around obstacles) to be able to plan faster and solve more motion planning problems than RRT

• Closed-loop rapidly exploring random (CL-RRT),{{cite journal|last1=Kuwata|first1=Yoshiaki|last2=Teo|first2=Justin|last3=Fiore|first3=Gaston|last4=Karaman|first4=Sertac|last5=Frazzoli|first5=Emilio|last6=How|first6=Jonathan P.|title=Real-time Motion Planning with Applications to Autonomous Urban Driving|journal=IEEE Transactions on Control Systems Technology|date=September 2009|volume=17|issue=5|pages=1105–1118|url=http://acl.mit.edu/papers/KuwataTCST09.pdf|accessdate=10 April 2017|doi=10.1109/tcst.2008.2012116|citeseerx=10.1.1.169.7922|hdl=1721.1/52527|s2cid=14526513|archive-date=12 June 2021|archive-url=https://web.archive.org/web/20210612232111/http://acl.mit.edu/papers/KuwataTCST09.pdf|url-status=dead}} 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*){{cite journal

| last1 = Strub

| first1 = Marlin P.

| last2 = Gammell

| first2 = Jonathan D.

| author-link =

| date = 2022

| title = Adaptively Informed Trees (AIT*) and Effort Informed Trees (EIT*): Asymmetric bidirectional sampling-based path planning

| journal = The International Journal of Robotics Research

| volume = 41

| issue = 4

| pages = 390–417

| doi = 10.1177/02783649211069572

| arxiv = 2111.01877

}}

:*Any-angle path planning

:*Probabilistic roadmap

:*Space-filling tree

:*Motion planning

:*Randomized algorithm

{{reflist}}

• {{Commons category-inline|Rapidly exploring random tree}}
• [http://correll.cs.colorado.edu/?p=1623 Java visualizer of RRT and RRT* including map editor]
• [https://github.com/mpdmanash/rrt-star-dubins-sim C++ implementation of RRT using Dubins minimum-time paths]
• [https://ompl.kavrakilab.org/RRTstar_8h_source.html Open Motion Planning Library RRT* implementation]

Category:Search algorithms

Category:Robot navigation

Category:Probabilistic data structures

Category:Path planning