Steven M. LaValle

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. All of our RRT papers appear below.


Papers on Rapidly Exploring Random Trees

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

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. In Proceedings IEEE Conference on Robot Motion and Control, 2009. [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].

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

Rapidly-exploring random trees: Progress and prospects. S. M. LaValle and J. J. Kuffner. In Proceedings Workshop on the Algorithmic Foundations of Robotics, 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].