Rapidly-exploring random tree

A rapidly exploring random tree (RRT) 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. [1] .[2] They easily handle problems with obstacles and differential constraints (nonholonomic and kinodynamic) and have been widely used in autonomous robotic motion planning.

Part of a series on
Probabilistic
data structures
Random trees
Related
A visualization of an RRT graph after 45 and 390 iterations
An animation of an RRT starting from iteration 0 to 10000

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.[3]

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 (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.

Algorithm

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

Algorithm BuildRRT
    Input: Initial configuration qinit, number of vertices in RRT K, incremental distance Δq)
    Output: RRT graph G

    G.init(qinit)
    for k = 1 to K do
        qrand ← RAND_CONF()
        qnear ← NEAREST_VERTEX(qrand, G)
        qnew ← NEW_CONF(qnear, qrand, Δq)
        G.add_vertex(qnew)
        G.add_edge(qnear, qnew)
    return G
  • "←" denotes assignment. For instance, "largest ← item" means that the value of largest changes to the value of item.
  • "return" terminates the algorithm and outputs the following value.

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. (According to [4] in holonomic problems, this should be omitted and qrand used instead of qnew.)

Variants and improvements for motion planning
  • Parti-game directed RRTs (PDRRTs),[5] a method that combines RRTs with the parti-game method[6] 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),[7] an extension of RRT that samples an input to a stable closed-loop system consisting 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.[8] 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*,[8][9][10] a variant of RRT that converges towards an optimal solution
  • RRT*-Smart,[11] 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*,[12] 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,[13][14][15] RRT* with a fixed number of nodes, which randomly removes a leaf node in the tree in every iteration
  • RRT*-AR,[16] sampling-based alternate routes planning
  • Informed RRT*,[17][18] 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*),[19] 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
  • RRTX and RRT#,[20][21] optimization of RRT* for dynamic environments
  • Theta*-RRT,[22] 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,[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.
  • TB-RRT, [29] Time-based RRT algorithm for rendezvous planning of two dynamic systems.
gollark: Okay, bug found.
gollark: I should probably check the logs.
gollark: GTech™ nanofabricators.
gollark: NIR only right now though.
gollark: Our tape is so red it's infrared.

See also

References
  1. LaValle, Steven M. (October 1998). "Rapidly-exploring random trees: A new tool for path planning" (PDF). Technical Report. Computer Science Department, Iowa State University (TR 98–11).
  2. LaValle, Steven M.; Kuffner Jr., James J. (2001). "Randomized Kinodynamic Planning" (PDF). The International Journal of Robotics Research (IJRR). 20 (5): 378–400. doi:10.1177/02783640122067453.
  3. http://msl.cs.uiuc.edu/rrt/about.html About RRTs, by Steve LaValle
  4. 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%5B%5D
  5. Ranganathan, Ananth; Koenig, Sven. PDRRTs: "Integrating Graph-Based and Cell-Based Planning". In Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), pages 2799–2808, 2004.
  6. Moore, A. W.; Atkeson, C. G., "The parti-game algorithm for variable resolution reinforcement learning in multidimensional state-spaces," Machine Learning, vol. 21, no. 3, pages 199–233, 1995.
  7. Kuwata, Yoshiaki; Teo, Justin; Fiore, Gaston; Karaman, Sertac; Frazzoli, Emilio; How, Jonathan P. (September 2009). "Real-time Motion Planning with Applications to Autonomous Urban Driving" (PDF). IEEE Transactions on Control Systems Technology. 17 (5): 1105–1118. CiteSeerX 10.1.1.169.7922. doi:10.1109/tcst.2008.2012116. hdl:1721.1/52527. Retrieved 10 April 2017.
  8. Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv:1005.0416 [cs.RO].
  9. Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv:1105.1186 [cs.RO].
  10. OlzhasAdi (Jan 26, 2015). "RRT* Brief Explanation" (video). YouTube. Retrieved 3 August 2016.
  11. Islam, Fahad; Nasir, Jauwairia; Malik, Usman; Ayaz, Yasar; Hasan, Osman; "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.
  12. Brunner, M.; Bruggemann, B.; Schulz, D.. "Hierarchical rough terrain motion planning using an optimal sampling-based method," in Int. Conf. on Robotics and Automation (ICRA), Karlsruhe, Germany, 2013.
  13. 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
  14. Adiyatov, Olzhas; Varol, Atakan (2013). "MATLAB Toolbox of RRT, RRT* and RRT*FN algorithms". Retrieved 3 August 2016.
  15. OlzhasAdi (Jan 26, 2015). "RRT*FN Brief Explanation" (video). YouTube. Retrieved 3 August 2016.
  16. Choudhury, Sanjiban; Scherer, Sebastian; Singh, Sanjiv. "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
  17. 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. ISBN 978-1-4799-6934-0.
  18. utiasASRL (Jul 4, 2014). "Informed RRT* @ UTIAS (IROS 2014)" (video). YouTube. Retrieved 3 August 2016.
  19. Naderi, Kourosh; Rajamäki, Joose; Hämäläinen, Perttu (2015). "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=https://dx.doi.org/10.1145/2822013.2822036
  20. RRTX: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles
  21. Comparison of RRTX, RRT# and RRT* when a shortcut is discovered in a static environment
  22. Palmieri, Luigi; Koenig, Sven; Arras, Kai O. "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.
  23. RRT* FND - motion planning in dynamic environments
  24. Ford, Christen (2018-06-12). RRT-GPU and Minecraft: Hardware Accelerated Rapidly Exploring Random Trees in Three Dimensions (Thesis). doi:10.13140/rg.2.2.15658.11207.
  25. Amiryan, Javad; Jamzad, Mansour (2015). Adaptive motion planning with artificial potential fields using a prior path. Robotics and Mechatronics (ICROM), 2015 3rd RSI International Conference on. pp. 731–736.
  26. Sieverling, Arne; Eppner, Clemens; Wolff, Felix; Brock, Oliver (2017). Interleaving motion in contact and in free space for planning under uncertainty (PDF). 2017 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 4011–4073.
  27. Rus, Daniela; Frazzoli, Emilio; Karaman, Sertac; Tumova, Jana; Chaudhari, Pratik; Castro, Luis I. Reyes (2013-05-06). "Incremental Sampling-based Algorithm for Minimum-violation Motion Planning". arXiv:1305.1102v2. Cite journal requires |journal= (help)
  28. "Maciej Kalisiak - RRT-blossom". www.dgp.toronto.edu. Retrieved 2020-01-18.
  29. Sintov, Avishai; Shapiro, Amir (2014). Time-based RRT algorithm for rendezvous planning of two dynamic systems. IEEE International Conference on Robotics and Automation (ICRA).
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.