Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space
Michal Kleinbort, Edgar Granados, Kiril Solovey, Riccardo Bonalli, Kostas E. Bekris, Dan Halperin
Abstract
We present a novel analysis of AO-RRT: a tree-based planner for motion planning with kinodynamic constraints, originally described by Hauser and Zhou (AO-X, 2016). AO-RRT explores the state-cost space and has been shown to efficiently obtain high-quality solutions in practice without relying on the availability of a computationally-intensive two-point boundary-value solver. Our main contribution is an optimality proof for the single-tree version of the algorithm-a variant that was not analyzed before. Our proof only requires a mild and easily-verifiable set of assumptions on the problem and system: Lipschitz-continuity of the cost function and the dynamics. In particular, we prove that for any system satisfying these assumptions, any trajectory having a piecewise-constant control function and positive clearance from the obstacles can be approximated arbitrarily well by a trajectory found by AORRT. We also discuss practical aspects of AORRT and present experimental comparisons of variants of the algorithm.
BibTeX
@inproceedings{icra2020_refinedanalysiso,
title = {Refined Analysis of Asymptotically-Optimal Kinodynamic Planning in the State-Cost Space},
author = {Michal Kleinbort and Edgar Granados and Kiril Solovey and Riccardo Bonalli and Kostas E. Bekris and Dan Halperin},
booktitle = {ICRA 2020},
year = {2020}
}