状態コスト空間における実行可能キノダイナミック計画による漸近的最適計画
Asymptotically Optimal Planning by Feasible Kinodynamic Planning in State-Cost Space
任意の最適キノダイナミック計画問題を状態コスト空間での実行可能計画問題の系列に変換し、実行可能計画器をサブルーチンとして漸近的最適計画器を構成するメタアルゴリズムを提案した論文。
著者: Kris Hauser, Yilun Zhou
分類: cs.RO
原文アブストラクト
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.
