Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning

TitleSparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning
Publication TypeConference Paper
Year of Publication2014
AuthorsLi, Y, Littlefield, Z, Bekris, KE
Conference NameWorkshop on the Algorithmic Foundations of Robotics (WAFR)
Date Published08/2014
Conference LocationIstanbul, Turkey

This work describes SST, an algorithm that (a) provides asymptotic (near-)optimality for kinodynamic 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. This algorithm addresses the limitation of RRT*, which requires a steering function for asymptotic optimality. This issue has motivated recent variations of RRT*, 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 structure that provides such desirable guarantees for a wide set of systems under a reasonable set of assumptions. Simulations for a variety of standard benchmarks, including using a physics engine, confirm the argued properties of the approach.