Rapidly exploring random tree

Last updated
RRT graph1.png
A visualization of an RRT graph after 45 and 390 iterations
Rapidly-exploring Random Tree (RRT) 500x373.gif
An animation of an RRT starting from iteration 0 to 10000

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.

Contents

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]

RRTs can be used to compute approximate control policies to control high dimensional nonlinear systems with state and action constraints.

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 GG.init(qinit)     fork = 1 toKdoqrand ← RAND_CONF()         qnear ← NEAREST_VERTEX(qrand, G)         qnew ← NEW_CONF(qnear, qrand, Δq)         G.add_vertex(qnew)         G.add_edge(qnear, qnew)     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. (According to [4] in holonomic problems, this should be omitted and qrand used instead of qnew.)

Variants and improvements for motion planning

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

See also

Related Research Articles

Reinforcement learning (RL) is an interdisciplinary area of machine learning and optimal control concerned with how an intelligent agent ought to take actions in a dynamic environment in order to maximize the cumulative reward. Reinforcement learning is one of three basic machine learning paradigms, alongside supervised learning and unsupervised learning.

<span class="mw-page-title-main">Dario Floreano</span> Swiss-Italian roboticist and engineer

Dario Floreano is a Swiss-Italian roboticist and engineer. He is Director of the Laboratory of Intelligent System (LIS) at the École Polytechnique Fédérale de Lausanne in Switzerland and was the founding director of the Swiss National Centre of Competence in Research (NCCR) Robotics.

Markus Hendrik Overmars is a Dutch computer scientist and teacher of game programming known for his game development application GameMaker. GameMaker lets people create computer games using a drag-and-drop interface. He is the former head of the Center for Geometry, Imaging, and Virtual Environments at Utrecht University, in the Netherlands. This research center concentrates on computational geometry and its application in areas like computer graphics, robotics, geographic information systems, imaging, multimedia, virtual environments, and games.

Motion planning, also path planning is a computational problem to find a sequence of valid configurations that moves the object from the source to destination. The term is used in computational geometry, computer animation, robotics and computer games.

Obstacle avoidance, in robotics, is a critical aspect of autonomous navigation and control systems. It is the capability of a robot or an autonomous system/machine to detect and circumvent obstacles in its path to reach a predefined destination. This technology plays a pivotal role in various fields, including industrial automation, self-driving cars, drones, and even space exploration. Obstacle avoidance enables robots to operate safely and efficiently in dynamic and complex environments, reducing the risk of collisions and damage.

<span class="mw-page-title-main">Probabilistic roadmap</span> Probabilistic motion planning algorithm

The probabilistic roadmap planner is a motion planning algorithm in robotics, which solves the problem of determining a path between a starting configuration of the robot and a goal configuration while avoiding collisions.

<span class="mw-page-title-main">Steven M. LaValle</span> American computer scientist

Steven M. LaValle is an American computer scientist, and a professor in the Faculty of Information Technology and Electrical Engineering at the University of Oulu. He was also an early founder and head scientist of Oculus VR until it was acquired by Facebook in 2014. He is best known for his work on rapidly exploring random trees (RRTs), the Oculus Rift, and his book, Planning Algorithms, one of the most highly cited texts in the field.

In robotics, Vector Field Histogram (VFH) is a real time motion planning algorithm proposed by Johann Borenstein and Yoram Koren in 1991. The VFH utilizes a statistical representation of the robot's environment through the so-called histogram grid, and therefore places great emphasis on dealing with uncertainty from sensor and modeling errors. Unlike other obstacle avoidance algorithms, VFH takes into account the dynamics and shape of the robot, and returns steering commands specific to the platform. While considered a local path planner, i.e., not designed for global path optimality, the VFH has been shown to produce near optimal paths.

<span class="mw-page-title-main">Visual odometry</span> Determining the position and orientation of a robot by analyzing associated camera images

In robotics and computer vision, visual odometry is the process of determining the position and orientation of a robot by analyzing the associated camera images. It has been used in a wide variety of robotic applications, such as on the Mars Exploration Rovers.

<span class="mw-page-title-main">Velocity obstacle</span> Term in robotics and motion planning

In robotics and motion planning, a velocity obstacle, commonly abbreviated VO, is the set of all velocities of a robot that will result in a collision with another robot at some moment in time, assuming that the other robot maintains its current velocity. If the robot chooses a velocity inside the velocity obstacle then the two robots will eventually collide, if it chooses a velocity outside the velocity obstacle, such a collision is guaranteed not to occur.

<span class="mw-page-title-main">Any-angle path planning</span> Algorithm to find Euclidean shortest paths

Any-angle path planning algorithms are pathfinding algorithms that search for a Euclidean shortest path between two points on a grid map while allowing the turns in the path to have any angle. The result is a path that cuts directly through open areas and has relatively few turns. More traditional pathfinding algorithms such as A* either lack in performance or produce jagged, indirect paths.

The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning and network routing. The best-known example of a pebble motion problem is the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.

Rapidly exploring dense trees is a family of planning algorithms that includes the rapidly exploring random tree.

For robot control, Stochastic roadmap simulation is inspired by probabilistic roadmap methods (PRM) developed for robot motion planning.

<span class="mw-page-title-main">James J. Kuffner Jr.</span> American roboticist

James J. Kuffner Jr. is an American roboticist and chief executive officer (CEO) of Woven by Toyota. Dr. Kuffner is also Chief Digital Officer and a member of the Board of Directors of Toyota Motor Corporation. Kuffner continues to serve as an Adjunct Associate Professor at the Robotics Institute at Carnegie Mellon University and as Executive Advisor to Woven by Toyota. Kuffner earned a Ph.D. from the Stanford University Dept. of Computer Science Robotics Laboratory in 1999.

<span class="mw-page-title-main">Oussama Khatib</span> American Roboticist

Oussama Khatib is a roboticist and a professor of computer science at Stanford University, and a Fellow of the IEEE. He is credited with seminal work in areas ranging from robot motion planning and control, human-friendly robot design, to haptic interaction and human motion synthesis. His work's emphasis has been to develop theories, algorithms, and technologies, that control robot systems by using models of their physical dynamics. These dynamic models are used to derive optimal controllers for complex robots that interact with the environment in real-time.

Real-Time Path Planning is a term used in robotics that consists of motion planning methods that can adapt to real time changes in the environment. This includes everything from primitive algorithms that stop a robot when it approaches an obstacle to more complex algorithms that continuously takes in information from the surroundings and creates a plan to avoid obstacles.

<span class="mw-page-title-main">Multi-agent pathfinding</span> Pathfinding problem

The problem of Multi-Agent Pathfinding (MAPF) is an instance of multi-agent planning and consists in the computation of collision-free paths for a group of agents from their location to an assigned target. It is an optimization problem, since the aim is to find those paths that optimize a given objective function, usually defined as the number of time steps until all agents reach their goal cells. MAPF is the multi-agent generalization of the pathfinding problem, and it is closely related to the shortest path problem in the context of graph theory.

<span class="mw-page-title-main">Margarita Chli</span> Greek computer vision and robotics researcher

Margarita Chli is an assistant professor and leader of the Vision for Robotics Lab at ETH Zürich in Switzerland. Chli is a leader in the field of computer vision and robotics and was on the team of researchers to develop the first fully autonomous helicopter with onboard localization and mapping. Chli is also the Vice Director of the Institute of Robotics and Intelligent Systems and an Honorary Fellow of the University of Edinburgh in the United Kingdom. Her research currently focuses on developing visual perception and intelligence in flying autonomous robotic systems.

Linear-quadratic regulator rapidly exploring random tree (LQR-RRT) is a sampling based algorithm for kinodynamic planning. A solver is producing random actions which are forming a funnel in the state space. The generated tree is the action sequence which fulfills the cost function. The restriction is, that a prediction model, based on differential equations, is available to simulate a physical system. The method is an extension of the rapidly exploring random tree, a widely used approach to motion planning.

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. 20 (5): 378–400. doi:10.1177/02783640122067453. S2CID   40479452.
  3. ↑ http://msl.cs.uiuc.edu/rrt/about.html Archived 2007-10-21 at the Wayback Machine 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. ↑ Petit, Louis; Desbiens, Alexis Lussier (2021-10-17). "RRT-Rope: A deterministic shortening approach for fast near-optimal path planning in large-scale uncluttered 3D environments". 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC). Melbourne, Australia: IEEE. pp. 1111–1118. doi:10.1109/SMC52423.2021.9659071. ISBN   978-1-6654-4207-7. S2CID   252590377.
  6. ↑ 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.
  7. ↑ 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.
  8. ↑ 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. S2CID   14526513. Archived from the original (PDF) on 12 June 2021. Retrieved 10 April 2017.
  9. 1 2 Karaman, Sertac; Frazzoli, Emilio (3 May 2010). "Incremental Sampling-based Algorithms for Optimal Motion Planning". arXiv: 1005.0416 [cs.RO].
  10. ↑ Karaman, Sertac; Frazzoli, Emilio (5 May 2011). "Sampling-based Algorithms for Optimal Motion Planning". arXiv: 1105.1186 [cs.RO].
  11. ↑ OlzhasAdi (Jan 26, 2015). "RRT* Brief Explanation" (video). YouTube . Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  12. ↑ Perez, Alejandro; Platt, Robert; Konidaris, George; Kaelbling, Leslie; Lozano-Perez, Tomas (May 2012). "LQR-RRT*: Optimal sampling-based motion planning with automatically derived extension heuristics". 2012 IEEE International Conference on Robotics and Automation. pp. 2537–2542. doi:10.1109/ICRA.2012.6225177. ISBN   978-1-4673-1405-3. S2CID   1914056.
  13. ↑ Xanthidis, Marios; Esposito, Joel M.; Rekleitis, Ioannis; O’Kane, Jason M. (2020-12-01). "Motion Planning by Sampling in Subspaces of Progressively Increasing Dimension". Journal of Intelligent & Robotic Systems. 100 (3): 777–789. doi:10.1007/s10846-020-01217-w. ISSN   1573-0409. S2CID   3622004.
  14. ↑ 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.
  15. ↑ 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.
  16. ↑ 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
  17. ↑ Adiyatov, Olzhas; Varol, Atakan (2013). "MATLAB Toolbox of RRT, RRT* and RRT*FN algorithms" . Retrieved 3 August 2016.
  18. ↑ OlzhasAdi (Jan 26, 2015). "RRT*FN Brief Explanation" (video). YouTube . Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  19. ↑ 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
  20. ↑ 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. S2CID   12233239.
  21. ↑ utiasASRL (Jul 4, 2014). "Informed RRT* @ UTIAS (IROS 2014)" (video). YouTube . Archived from the original on 2021-12-12. Retrieved 3 August 2016.
  22. ↑ 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 : 10.1145/2822013.2822036
  23. ↑ "RRTX: Real-Time Motion Planning/Replanning for Environments with Unpredictable Obstacles" (PDF). Archived from the original (PDF) on 2017-05-19. Retrieved 2018-03-02.
  24. ↑ Comparison of RRTX, RRT# and RRT* when a shortcut is discovered in a static environment
  25. ↑ 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.
  26. ↑ RRT* FND - motion planning in dynamic environments
  27. ↑ 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
  28. ↑ 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.
  29. ↑ 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.
  30. ↑ 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.
  31. ↑ 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.1102 [cs.RO].
  32. ↑ "Maciej Kalisiak - RRT-blossom". www.dgp.toronto.edu. Retrieved 2020-01-18.
  33. ↑ Tahirovic, Adnan; Ferizbegovic, Mina (May 2018). "Rapidly-Exploring Random Vines (RRV) for Motion Planning in Configuration Spaces with Narrow Passages". 2018 IEEE International Conference on Robotics and Automation (ICRA). pp. 7055–7062. doi:10.1109/ICRA.2018.8460186. ISBN   978-1-5386-3081-5. S2CID   52285080.
  34. ↑ Lacevic, Bakir; Osmankovic, Dinko; Ademovic, Adnan (May 2016). "Burs of free C-space: A novel structure for path planning". 2016 IEEE International Conference on Robotics and Automation (ICRA). pp. 70–76. doi:10.1109/ICRA.2016.7487117. ISBN   978-1-4673-8026-3. S2CID   15834630.
  35. ↑ Sintov, Avishai; Shapiro, Amir (2014). "Time-based RRT algorithm for rendezvous planning of two dynamic systems". 2014 IEEE International Conference on Robotics and Automation (ICRA). IEEE International Conference on Robotics and Automation (ICRA). pp. 6745–6750. doi:10.1109/ICRA.2014.6907855. ISBN   978-1-4799-3685-4.
  36. ↑ Lai, Tin; Ramos, Fabio; Francis, Gilad (2019). "Balancing Global Exploration and Local-connectivity Exploitation with Rapidly-exploring Random disjointed-Trees". 2019 International Conference on Robotics and Automation (ICRA). Montreal, QC, Canada: IEEE. pp. 5537–5543. arXiv: 1810.03749 . doi:10.1109/ICRA.2019.8793618. ISBN   978-1-5386-6027-0. S2CID   52945105.
  37. ↑ Lai, Tin; Morere, Philippe; Ramos, Fabio; Francis, Gilad (April 2020). "Bayesian Local Sampling-Based Planning". IEEE Robotics and Automation Letters. 5 (2): 1954–1961. arXiv: 1909.03452 . doi:10.1109/LRA.2020.2969145. S2CID   210838739.
  38. ↑ Kang, Jin-Gu; Lim, Dong-Woo; Choi, Yong-Sik; Jang, Woo-Jin; Jung, Jin-Woo (2021-01-06). "Improved RRT-Connect Algorithm Based on Triangular Inequality for Robot Path Planning". Sensors. 21 (2): 333. doi: 10.3390/s21020333 . ISSN   1424-8220. PMC   7825297 . S2CID   231303809.
  39. ↑ Kang, Jin-Gu; Jung, Jin-Woo (12 Jul 2021). "Post Triangular Rewiring Method for Shorter RRT Robot Path Planning". arXiv: 2107.05344 [cs.RO].
  40. ↑ Strub, Marlin P.; Gammell, Jonathan D. (2 Nov 2021). "AIT* and EIT*: Asymmetric bidirectional sampling-based path planning". arXiv: 2111.01877 [cs.RO].
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.