Asymptotically Optimal Planning by Feasible Kinodynamic Planning in State-Cost Space
This work addresses optimal planning in robotics and AI by providing a general method that avoids reliance on steering functions or numerical solvers, making it applicable to a wide range of problems, though it builds incrementally on existing feasible planning techniques.
The paper tackles the problem of optimal kinodynamic planning by showing that any optimal planning problem can be transformed into a series of feasible planning problems in state-cost space, leading to asymptotically optimal solutions. It presents a meta-algorithm proven to be asymptotically optimal, with derived formulas for expected running time and suboptimality, and demonstrates superior or comparable performance on benchmarks using EST and RRT subroutines.
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.