Affordable Access

Asymptotically Optimal Planning by Feasible Kinodynamic Planning in State-Cost Space

Authors
Type
Preprint
Publication Date
Submission Date
Identifiers
arXiv ID: 1505.04098
Source
arXiv
License
Yellow
External links

Abstract

This paper presents an equivalence between feasible kinodynamic planning and optimal kinodynamic planning, in that any optimal planning problem can be transformed into a series of feasible planning problems in a state-cost space whose solutions approach the optimum. This transformation gives rise to a meta-algorithm that produces an asymptotically optimal planner, given any feasible kinodynamic planner as a subroutine. The meta-algorithm is proven to be asymptotically optimal, and a formula is derived relating expected running time and solution suboptimality. It is directly applicable to a wide range of optimal planning problems because it does not resort to the use of steering functions or numerical boundary-value problem solvers. On a set of benchmark problems, it is demonstrated to perform, using the EST and RRT algorithms as subroutines, at a superior or comparable level to related planners.

Statistics

Seen <100 times