Rapidly exploring Random Trees (RRTs)
Back in June 1998, I introduced the RRT (see this Iowa
State tech report), which is a simple,
iterative algorithm that quickly searches complicated,
high-dimensional spaces for feasible paths. The idea is to
incrementally grow a space-filling tree by sampling the space
at random and connecting the nearest point in the tree to the new
random sample. This results in a simple way to achieve Voronoi
bias, which causes aggressive exploration in the early stages and
then eventually settles on uniform space coverage. For path planning
applications, two trees are usually grown, one from each of the
initial and goal regions, respectively. If they connect to each
other, then a solution is found (see
this paper,
this paper, and Section 5 of
this chapter).
Over the past decades, RRTs have been used in numerous robotic
systems, including DARPA Urban Challenge vehicles, autonomous driving
systems used in in public settings, military UAVs, humanoid robots,
soccer-playing robots, and plenetary explorer prototypes. They have
also been applied outside of robotics, in areas such as art,
computational biology, virtual prototyping, and video games.
Numerous extensions and variants of RRTs exist, with the most widely
known being RRT* from Sertac Karaman at MIT. Implementations of RRTs
appear in various libraries, including the Robot Operating System
(ROS), the
Open Motion Planning
Library (OMPL), the Motion
Strategy Library,
and MATLAB.
A simple Python program (using PyGame) that generates RRTs
is here. See
the RRT Page for more RRT
examples and uses prior to 2003. Based on its impact after two
decades, our first RRT conference paper
(with James Kuffner) was awarded the first-ever IEEE ICRA Milestone Award,
judged to be the most influential of all papers published at ICRA
between 1997 and 2001 (looking retrospectively from 2019).
For deterministic counterparts to RRTs, see Section 5 of this chapter and the IROS 2011 paper that I wrote with James Kuffner. For deep analysis of the mysterious behavior of an RRT that grows in an extremely large disc, see my WAFR 2012 paper with Maxim Arnold and Yuliy Baryshnikov.
Our latest RRT work introduces a steering method that makes the original RRT-based kinodynamic planning algorithm around 1000 times faster! See our IROS 2023 paper, and take our free steering code.
Papers on Rapidly Exploring Random Trees
Bang-bang boosting of RRTs. A. J. LaValle, B. Sakcak, and S. M. LaValle. In IEEE International Conference on Intelligent Robots and Systems, pages 2869-2876, 2023. [pdf].
Convex hull asymptotic shape evolution. M. Arnold, Y. Baryshnikov, and S. M. LaValle. In Proc. Workshop on the Algorithmic Foundations of Robotics, 2012. [pdf].
Space-filling trees: A new perspective on motion planning via incremental search. J. Kuffner and S. M. LaValle. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2011. [pdf].
Motion planning: The essentials. S. M. LaValle. IEEE Robotics and Automation Society Magazine, 18(1):79-89, 2011. [pdf].
Motion planning for highly constrained spaces. A. Yershova and S. M. LaValle. Technical Report UIUCDCS-R-2008-2975, Department of Computer Science, University of Illinois, 2008. [pdf].
Improving motion planning algorithms by efficient nearest-neighbor searching. A. Yershova and S. M. LaValle. IEEE Transactions on Robotics, 23(1):151-157, February 2007. [pdf].
Chapter 5: Sampling-Based Motion Planning, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].
Chapter 14: Sampling-Based Planning Under Differential Constraints, Planning Algorithms. S. M. LaValle. Cambridge University Press, Cambridge, U.K., 2006. [pdf] [Entire Book].
Adaptive tuning of the sampling domain for dynamic-domain RRTs. L. Jaillet, A. Yershova, S. M. LaValle, and T. Simeon. In Proceedings IEEE International Conference on Intelligent Robots and Systems, 2005. [pdf].
Dynamic-domain RRTs: Efficient exploration by controlling the sampling domain. A. Yershova, L. Jaillet, T. Simeon, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2005. [pdf].
Steps toward derandomizing RRTs. S. R. Lindemann and S. M. LaValle. In IEEE Fourth International Workshop on Robot Motion and Control, 2004. [pdf].
Improving the performance of sampling-based planners by using a symmetry-exploiting gap reduction algorithm. P. Cheng, E. Frazzoli, and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2004. [pdf].
Deterministic sampling methods for spheres and SO(3). A. Yershova and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2004. [pdf].
Incrementally reducing dispersion by increasing Voronoi bias in RRTs. S. R. Lindemann and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, 2004. [pdf].
Current issues in sampling-based motion planning. S. R. Lindemann and S. M. LaValle. In P. Dario and R. Chatila, editors, Robotics Research: The Eleventh International Symposium, pages 36-54. Springer-Verlag, Berlin, 2005. [pdf].
On the relationship between classical grid search and probabilistic roadmaps. S. M. LaValle and M. S. Branicky. In J.-D. Boissonat, J. Burdick, K. Y. Goldberg, and S. A. Hutchinson, editors, Algorithmic Foundations of Robotics. Springer-Verlag, Berlin, 2003. [pdf].
Incremental low-discrepancy lattice methods for motion planning. S. R. Lindemann and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 2920-2927, 2003. [pdf].
From dynamic programming to RRTs: Algorithmic design of feasible trajectories. S. M. LaValle. In A. Bicchi, H. I. Christensen, and D. Prattichizzo, editors, Control Problems in Robotics, pages 19-37. Springer-Verlag, Berlin, 2002. [pdf].
Efficient nearest neighbor searching for motion planning. A. Atramentov and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 632-637, 2002. [pdf].
Resolution complete rapidly-exploring random trees. P. Cheng and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 267-272, 2002. [pdf].
Randomized kinodynamic planning. S. M. LaValle and J. J. Kuffner. The International Journal of Robotics Research, 20(5):378-400, May 2001. [pdf].
RRT-based trajectory design for autonomous automobiles and spacecraft. P. Cheng, Z. Shen, and S. M. LaValle. Archives of Control Sciences, 11(3-4):167-194, 2001. [pdf].
Reducing metric sensitivity in randomized trajectory design. P. Cheng and S. M. LaValle. In Proceedings IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 43-48, 2001. [pdf].
Randomized path planning for linkages with closed kinematic chains. J. Yakey, S. M. LaValle, and L. E. Kavraki. IEEE Transactions on Robotics and Automation, 17(6):951-958, December 2001. [pdf].
Rapidly-exploring random trees: Progress and prospects. S. M. LaValle and J. J. Kuffner. In B. R. Donald, K. M. Lynch, and D. Rus, editors, Algorithmic and Computational Robotics: New Directions, pages 293-308. A K Peters, Wellesley, MA, 2001. [pdf].
Using randomization to find and optimize feasible trajectories for nonlinear systems. P. Cheng, Z. Shen, and S. M. LaValle. In Proceedings Annual Allerton Conference on Communications, Control, Computing, pages 926-935, 2000. [pdf].
RRT-connect: An efficient approach to single-query path planning. J. J. Kuffner and S. M. LaValle. In Proceedings IEEE International Conference on Robotics and Automation, pages 995-1001, 2000. [pdf].
Randomized kinodynamic planning. S. M. LaValle and J. J. Kuffner. In Proceedings IEEE International Conference on Robotics and Automation, pages 473-479, 1999. [pdf].
Rapidly-exploring random trees: A new tool for path planning. S. M. LaValle. TR 98-11, Computer Science Dept., Iowa State University, October 1998, [pdf].