近最適なタスク・動作計画のための許容可能な抽象化
Admissible Abstractions for Near-optimal Task and Motion Planning
エンジェリック意味論に基づく抽象化の許容条件を定義し、連続状態の動作計画で具体計画コストの上下界を導出して探索を高速化。10^13状態の問題で別途タスクプランナなしに近最適解を発見した。
著者: William Vega-Brown, Nicholas Roy
分類: cs.AI, cs.RO
原文アブストラクト
We define an admissibility condition for abstractions expressed using angelic semantics and show that these conditions allow us to accelerate planning while preserving the ability to find the optimal motion plan. We then derive admissible abstractions for two motion planning domains with continuous state. We extract upper and lower bounds on the cost of concrete motion plans using local metric and topological properties of the problem domain. These bounds guide the search for a plan while maintaining performance guarantees. We show that abstraction can dramatically reduce the complexity of search relative to a direct motion planner. Using our abstractions, we find near-optimal motion plans in planning problems involving $10^{13}$ states without using a separate task planner.
