Abstract
This workLittlefield, ZakarydescribesBekris, KostasSTABLE SPARSE RRT (SST), an algorithmLi, Yanbo that (a) provably provides asymptotic (near-)optimality for kinodynamic planningKinodynamic planning without access to a steering function, (b) maintains only a sparse set of samples, (c) converges fast to high-quality paths and (d) achieves competitive running time to RRT, which provides only probabilistic completeness. SST addresses the limitation of RRT∗\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$^*$$\end{document}, which requires a steering function for asymptotic optimalityAsymptotic optimality. This issue has motivated recent variations of RRT∗\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$$^*$$\end{document}, which either work for a limiting set of systems or exhibit increased computational cost. This paper provides formal arguments for the properties of the proposed algorithm. To the best of the authors’ knowledge, this is the first sparse data structureSparse data structures that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of benchmarks, including physically simulated ones, confirm the argued properties of the approach.