Asymptotically optimal sampling-based kinodynamic planning

By Yanbo Li, Zakary Littlefield, Kostas E. Bekris. Int. J. Robotics Res., 2014

308 citations recorded by the source corpus.

Sampling-based algorithms are viewed as practical solutions for high-dimensional motion planning. Recent progress has taken advantage of random geometric graph theory to show how asymptotic optimality can also be achieved with these methods. Achieving this desirable property for systems with dynamics requires solving a two-point boundary value problem (BVP) in the state space of the underlying dynamical system. It is difficult, however, if not impractical, to generate a BVP solver for a variety of important dynamical models of robots or physically simulated ones. Thus, an open challenge was whether it was even possible to achieve optimality guarantees when planning for systems without access to a BVP solver. This work resolves the above question and describes how to achieve asymptotic optimality for kinodynamic planning using incremental sampling-based planners by introducing a new rigorous framework. Two new methods, STABLE_SPARSE_RRT (SST) and SST*, result from this analysis, which are asymptotically near-optimal and optimal, respectively. The techniques are shown to converge fast to high-quality paths, while they maintain only a sparse set of samples, which makes them computationally efficient. The good performance of the planners is confirmed by experimental results using dynamical systems benchmarks, as well as physically simulated robots.

Subfields: Aerospace Engineering, Computer Graphics and Computer-Aided Design, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/0417d0b262457872310ca8c0f58c36c5806c9d61

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

1. Kostas E. Bekris
2. Zhepei Wang
3. Fei Gao
4. Abdeslam Boularias
5. Chao Xu
6. Xiaoxia Zhou

In Computer Vision and Pattern Recognition

1. Kostas E. Bekris
2. Shaojun Zhu
3. Fei Gao
4. Abdeslam Boularias
5. Chao Xu
6. Andrew Kimmel
7. Dacheng Tao

Citations in the corpus

• Geometrically Constrained Trajectory Optimization for Multicopters (2021, background): “There are also algorithms (Janson et al. 2015; Li et al. 2016; Gammell et al. 2018) that further explore either the efficiency or the applicability of randomized motion planning.”
• Fast Model Identification via Physics Engines for Data-Efficient Policy Search (2017, background): “It can also help the real-world applicability of motion planners that reason over dynamics and operate with physics engines [Bekris and Kavraki, 2008; Li et al., 2016; Littlefield et al., 2017].”