Anytime Motion Planning using the RRT*

By Sertac Karaman, Matthew R. Walter, Alejandro Perez, Emilio Frazzoli, Seth J. Teller. IEEE International Conference on Robotics and Automation, 2011

917 citations recorded by the source corpus.

The Rapidly-exploring Random Tree (RRT) algorithm, based on incremental sampling, efficiently computes motion plans. Although the RRT algorithm quickly produces candidate feasible solutions, it tends to converge to a solution that is far from optimal. Practical applications favor “anytime” algorithms that quickly identify an initial feasible plan, then, given more computation time available during plan execution, improve the plan toward an optimal solution. This paper describes an anytime algorithm based on the RRT* which (like the RRT) finds an initial feasible solution quickly, but (unlike the RRT) almost surely converges to an optimal solution. We present two key extensions to the RRT*, committed trajectories and branch-and-bound tree adaptation, that together enable the algorithm to make more efficient use of computation time online, resulting in an anytime algorithm for real-time implementation. We evaluate the method using a series of Monte Carlo runs in a high-fidelity simulation environment, and compare the operation of the RRT and RRT* methods. We also demonstrate experimental results for an outdoor wheeled

Subfields: Automotive Engineering, Biomedical Engineering, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/54d0fc859a6d9df491f4cec2ba994ab8275cbc44

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Automotive Engineering

In Biomedical Engineering

In Computer Vision and Pattern Recognition

Citations in the corpus

Asymptotically optimal sampling-based kinodynamic planning (2014, background): “Anytime (Karaman et al., 2011) and lazy (Alterovitz et al., 2011) variants of RRT∗ have also been proposed.”
Sampling-Based Robot Motion Planning: A Review (2014, methodology): “To overcome the slow convergence rate an Anytime framework for RRT* was implemented on an autonomous forklift [202].”
Heuristic approaches in robot path planning: A survey (2016, background): “RRT has received a considerable amount of attention, because of its computational efficiency and effectiveness and its ability to find a feasible motion plan relatively quickly, even in high-dimensional space [30,31].”
Computing Systems for Autonomous Driving: State of the Art and Challenges (2020, background): “As an extension of RRT, RRT* [141], [142] tries to search the optimal paths satisfying real-time constraints.”
Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions (2016, methodology): “, it finds a solution, if one exists, provided with infinite run time [4, 8].”
Learning Sampling Distributions for Robot Motion Planning (2017, positive): “tric motion planning problems. These approaches, which reject samples if they could not improve the current best solution, are herein referred to as informed sampling approaches (Gammell et al. 2014, Karaman et al. 2011). In the case of geometric motion planning problems with Euclidean cost, informe”
Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic (2014, methodology): “[16] use graph pruning to implement an anytime version of RRT* that improves solutions during execution.”
Variational End-to-End Navigation and Localization (2018, methodology): “As opposed to traditional methods for autonomous driving which typically rely on distinct algorithms for localization and mapping [7], [8], [9], planning [10], [11], [12], and control [13], [14], end-to-end algorithms attempt to collapse the problem (directly from raw sensory data to output control ”
Sampling-based robotic information gathering algorithms (2014, background): “utilize branch and bound techniques to trim the search tree (Karaman et al., 2011).”
Sampling-based algorithms for optimal motion planning (2011, methodology): “The RRT∗ algorithm was used for anytime motion planning in Karaman et al. (2011), where it was also demonstrated experimentally on a full-size robotic fork truck.”
Comparison of Trajectory Optimization Algorithms for High-Speed Quadrotor Flight Near Obstacles (2018, methodology): “The waypoints could be manually determined or generated by a sampling-based planner, such as RRT* [9], as shown by [1], [2] and [10].”