Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning
|Title||Sparse Methods for Efficient Asymptotically Optimal Kinodynamic Planning|
|Publication Type||Conference Paper|
|Year of Publication||2014|
|Authors||Li, Y, Littlefield, Z, Bekris, KE|
|Conference Name||Workshop on the Algorithmic Foundations of Robotics (WAFR)|
|Conference Location||Istanbul, 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.