Optimal kinodynamic motion planning using incremental sampling-based methods

By Sertac Karaman, Emilio Frazzoli. 2010

440 citations recorded by the source corpus.

Sampling-based algorithms such as the Rapidly-exploring Random Tree (RRT) have been recently proposed as an effective approach to computationally hard motion planning problem. However, while the RRT algorithm is known to be able to find a feasible solution quickly, there are no guarantees on the quality of such solution, e.g., with respect to a given cost functional. To address this limitation, the authors recently proposed a new algorithm, called RRT*, which ensures asymptotic optimality, i.e., almost sure convergence of the solution returned by the algorithm to an optimal solution, while maintaining the same properties of the standard RRT algorithm, both in terms of computation of feasible solutions, and of computational complexity. In this paper, the RRT* algorithm is extended to deal with differential constraints. A sufficient condition for asymptotic optimality is provided. It is shown that the RRT* algorithm equipped with any local steering procedure that satisfies this condition converges to an optimal solution almost surely. In particular, simple local steering procedures are provided for a Dubins' vehicle as well as a double integrator. Simulation examples are also provided for these systems comparing the RRT and the RRT* algorithms.

Subfields: Aerospace Engineering, Computer Vision and Pattern Recognition

How researchers see this paper

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

In Aerospace Engineering

In Computer Vision and Pattern Recognition

Citations in the corpus

A Fast Integrated Planning and Control Framework for Autonomous Driving via Imitation Learning (2017, neutral): “Emails: { litingsun, chengpeng2014, wzhan, tomizuka} @berkeley.edu. i) graph-search-based, such as A ∗ (see [4]), ii) sampling-based (e.g., RRT, RRT*, see [5], [6]), iii) interpolating-curve-based [7], [8], and iv) optimization-based [9], [10].”
A Survey of Motion Planning and Control Techniques for Self-Driving Urban Vehicles (2016, background): “Moreover, Karaman and Frazzoli [127] demonstrated that the RRT converges to a suboptimal solution with probability one and designed an asymptotically optimal adaptation of the RRT algorithm, called RRT*.”
Optimal Path Planning using RRT* based Approaches: A Survey and Future Directions (2016, background): “Prior kinodynamic extensions of RRT* such as Kinodynamic-RRT* [62] and LQR-RRT* [63] only satisfy bounded sub optimality and require RRT* to re-propagate the tree partially during each iteration.”
Incremental Sampling-based Algorithms for Optimal Motion Planning (2010, methodology): “However, the proposed algorithms also extend to systems with differential constraints, as shown in [18].”
Survey of Robot 3D Path Planning Algorithms (2016, methodology): “RRT performs well in practice and can guarantee completeness, but it pays almost no attention to the quality of the results, and it is proved that RRT algorithms are not asymptotically optimal [30].”
Polynomial Trajectory Planning for Aggressive Quadrotor Flight in Dense Indoor Environments (2016, methodology): “These algorithms have been most successful for simple Dubins vehicle or double-integrator systems where analytical techniques can be used to steer between two points in state space [13].”
Kinodynamic RRT*: Asymptotically optimal motion planning for robots with linear dynamics (2013, methodology): “systems have therefore focused on simple specific instances of kinodynamic systems [9], or have used approximate solutions to the two-point boundary value problem [5], [18].”
Sampling-Based Robot Motion Planning: A Review (2014, background): “The solution convergence remained an unanswered problem, until it was proven that given infinite runtime RRT will not find an optimal solution [195].”
A Review of Motion Planning Techniques for Automated Vehicles (2016, methodology): “[96] a new approach of this algorithm was developed, named RRT∗ (see [40, Fig.”
Geometrically Constrained Trajectory Optimization for Multicopters (2021, background): “Successful applications of them also exist in kinodynamic planning (or trajectory planning) problems (LaValle and Kuffner Jr 2001; Frazzoli et al. 2002; Karaman and Frazzoli 2010) if a steering function based on system dynamics is provided.”
Heuristic approaches in robot path planning: A survey (2016, background): “The solution convergence remains an unanswered problem; until it is proven that given infinity runtime RRT will not achieve an optimal path [37].”