サンプリングベース経路計画は有限計算後ほぼ最適である
Sampling-based Roadmap Planners are Probably Near-Optimal after Finite Computation
PRM*などの漸近最適なロードマップ型計画法が、有限回の反復後にも最適経路長に対して一定の誤差範囲に収まる確率的保証を初めて形式的に証明し、シミュレーションで評価した論文。
著者: Andrew Dobson, George V. Moustakides, Kostas E. Bekris
分類: cs.RO
原文アブストラクト
Sampling-based motion planners have proven to be efficient solutions to a variety of high-dimensional, geometrically complex motion planning problems with applications in several domains. The traditional view of these approaches is that they solve challenges efficiently by giving up formal guarantees and instead attain asymptotic properties in terms of completeness and optimality. Recent work has argued based on Monte Carlo experiments that these approaches also exhibit desirable probabilistic properties in terms of completeness and optimality after finite computation. The current paper formalizes these guarantees. It proves a formal bound on the probability that solutions returned by asymptotically optimal roadmap-based methods (e.g., PRM*) are within a bound of the optimal path length I* with clearance {\epsilon} after a finite iteration n. This bound has the form P(|In - I* | {\leq} {\delta}I*) {\leq} Psuccess, where {\delta} is an error term for the length a path in the PRM* graph, In. This bound is proven for general dimension Euclidean spaces and evaluated in simulation. A discussion on how this bound can be used in practice, as well as bounds for sparse roadmaps are also provided.
