コスト下界を用いた漸近最適動作計画
Asymptotically-Optimal Motion Planning using Lower Bounds on Cost
サンプリングベース動作計画において、コストの下界推定を利用して衝突判定の呼び出しを削減し、漸近最適性を保ちながら効率的に低コスト経路を生成するMPLBアルゴリズムを提案した論文。
著者: Oren Salzman, Dan Halperin
分類: cs.RO
原文アブストラクト
Many path-finding algorithms on graphs such as A* are sped up by using a heuristic function that gives lower bounds on the cost to reach the goal. Aiming to apply similar techniques to speed up sampling-based motion-planning algorithms, we use effective lower bounds on the cost between configurations to tightly estimate the cost-to-go. We then use these estimates in an anytime asymptotically-optimal algorithm which we call Motion Planning using Lower Bounds (MPLB). MPLB is based on the Fast Marching Trees (FMT*) algorithm recently presented by Janson and Pavone. An advantage of our approach is that in many cases (especially as the number of samples grows) the weight of collision detection in the computation is almost negligible with respect to nearest-neighbor calls. We prove that MPLB performs no more collision-detection calls than an anytime version of FMT*. Additionally, we demonstrate in simulations that for certain scenarios, the algorithmic tools presented here enable efficiently producing low-cost paths while spending only a small fraction of the running time on collision detection.
