Sampling-based algorithms for optimal motion planning
By Sertac Karaman, Emilio Frazzoli. 2011
5,606 citations recorded by the source corpus.
During the last decade, sampling-based path planning algorithms, such as probabilistic roadmaps (PRM) and rapidly exploring random trees (RRT), have been shown to work well in practice and possess theoretical guarantees such as probabilistic completeness. However, little effort has been devoted to the formal analysis of the quality of the solution returned by such algorithms, e.g. as a function of the number of samples. The purpose of this paper is to fill this gap, by rigorously analyzing the asymptotic behavior of the cost of the solution returned by stochastic sampling-based algorithms as the number of samples increases. A number of negative results are provided, characterizing existing algorithms, e.g. showing that, under mild technical conditions, the cost of the solution returned by broadly used sampling-based algorithms converges almost surely to a non-optimal value. The main contribution of the paper is the introduction of new algorithms, namely, PRM* and RRT*, which are provably asymptotically optimal, i.e. such that the cost of the returned solution converges almost surely to the optimum. Moreover, it is shown that the computational complexity of the new algorithms is within a constant factor of that of their probabilistically complete (but not asymptotically optimal) counterparts. The analysis in this paper hinges on novel connections between stochastic sampling-based path planning algorithms and the theory of random geometric graphs.
Subfields: Computer Vision and Pattern Recognition, Control and Systems Engineering
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Computer Vision and Pattern Recognition
- Luc Van Gool
- Dacheng Tao
- Jitendra Malik
- Trevor Darrell
- Sergey Levine
- Li Fei-Fei
- Xiaogang Wang
- Andrew Zisserman
In Control and Systems Engineering
- Sergey Levine
- Pieter Abbeel
- Chelsea Finn
- Dieter Fox
- J. Bagnell
- Pierre Sermanet
- Corey Lynch
- Ken Goldberg
Citations in the corpus
- A Survey of Autonomous Driving: Common Practices and Emerging Technologies (2019, methodology): “RRT* [258], an extension of the RRT, provides more optimal paths instead of completely random ones while sacrificing computational efficiency.”
- A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, methodology): “RRG [73] + Dijkstra Exact steering procedure available Probabilistically complete [73] ∗ Asymptotically optimal [73] ∗ O (n log n) [73] h , f , ∗ Yes”
- Human motion trajectory prediction: a survey (2019, methodology): “…algorithms (i.e. Dijkstra (Schrijver 2012), Fast Marching Method (Sethian 1996), optimal sampling-based motion planners (Janson et al. 2018; Karaman and Frazzoli 2011), value iteration (Littman et al. 1995)) scales exponentially with the number of agents, the size of the environment and…”
- Robust Control of Mobility and Communications in Autonomous Robot Teams (2013, methodology): “This path can be determined by a RRT algorithm [38].”
- CHOMP: Covariant Hamiltonian optimization for motion planning (2013, methodology): “The RRT* range (step size) parameter was set equal to that of the RRT (corresponding to a workspace distance of 2 cm).”
- Motion Planning Networks (2018, methodology): “Since we use RRT*, our proposed method inherits the probabilistic completeness of RRTs and RRT* [5] while retaining the computational gains.”
- Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic (2014, methodology): “Karaman and Frazzoli [7] present a lower-bound for this rewiring radius in terms of the measure of the problem space and the number of vertices in the graph.”
- Parallel sampling-based motion planning with superlinear speedup (2012, background): “…planners, such as the Rapidly-exploring Random Tree (RRT) and RRT*, are used in a variety of robotics applications including manipulation, computational biology, and autonomous vehicles to find paths through the robot’s free configuration space from a start location to a goal location [1], [2].”
- Stable Prehensile Pushing: In-Hand Manipulation with Alternating Sticking Contacts (2017, methodology): “Both these routines are directly adopted from RRT∗ architecture originally proposed in [21] and also used in our previous work [2].”
- Mesh Manifold Based Riemannian Motion Planning for Omnidirectional Micro Aerial Vehicles (2021, neutral): “RRT* [7], RRT-Connect [8]), to find obstacle-free paths.”
- Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions (2016, methodology): “Initial complete practical planners such as Road Map (RM), Potential Fields, and Cell Decomposition (CD) techniques are unable to deal with dynamic and complex high dimension problems [1, 7-10].”
- Broadly-Exploring, Local-Policy Trees for Long-Horizon Task Planning (2020, background): “As the temporal distance is not easily quantifiable, we learn to predict it with a temporal distance classifier, ⌧tdc(xi, xj), with K exponential categories corresponding to temporal distance intervals, dk 2 {[0, 1), [1, 2), [2, 4), [4, 8), [8, 16), .”
- Integrated task and motion planning in belief space (2013, methodology): “We are replacing the current RRT implementation with an RRT* (Karaman and Frazzoli, 2011) implementation which should reduce these problems.”
- Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions (2013, neutral): “This latter coefficient differs from, and is indeed less than, the lower bound in our mathematical guarantee of asymptotic optimality for k-nearest FMT*, equation (6) (note that k0,RRT* is also below the theoretical lower bound presented in Karaman and Frazzoli, 2011).”
- Differentiable Gaussian Process Motion Planning (2019, methodology): “Sampling based asymptotically optimal planning methods such as RRT* [22] effective in finding good homotopy classes to serve as an initialization for local trajectory optimizers, but can be slow to converge and produce non-smooth solution paths.”
- Algorithms for collision-free navigation of mobile robots in complex cluttered environments: a survey (2014, background): “Creates a tree of possible actions to connect initial and goal configurations (see, e.g., [64, 121]).”
- Path planning in GPS-denied environments via collective intelligence of distributed sensor networks (2016, background): “Since the estimate of the new way-point is provided relative to the robot, the RRT algorithm also operates in a relative coordinate system in a receding horizon fashion.”