Safe-Planner:単一結果決定化で強循環方策を計算する再計画器
Safe-Planner: A Single-Outcome Replanner for Computing Strong Cyclic Policies in Fully Observable Non-Deterministic Domains
非決定論的計画問題において、全結果決定化ではなく単一結果決定化と順序付けヒューリスティクスを用いることで、誤解を招く弱計画の生成を避け強解に直結する計画を立てる再計画器を提案し、ロボットタスクで有効性を示した。
著者: Vahid Mokhtari, Ajay Suresha Sathya, Nikolaos Tsiogkas, Wilm Decre
分類: cs.AI, cs.RO
原文アブストラクト
Replanners are efficient methods for solving non-deterministic planning problems. Despite showing good scalability, existing replanners often fail to solve problems involving a large number of misleading plans, i.e., weak plans that do not lead to strong solutions, however, due to their minimal lengths, are likely to be found at every replanning iteration. The poor performance of replanners in such problems is due to their all-outcome determinization. That is, when compiling from non-deterministic to classical, they include all compiled classical operators in a single deterministic domain which leads replanners to continually generate misleading plans. We introduce an offline replanner, called Safe-Planner (SP), that relies on a single-outcome determinization to compile a non-deterministic domain to a set of classical domains, and ordering heuristics for ranking the obtained classical domains. The proposed single-outcome determinization and the heuristics allow for alternating between different classical domains. We show experimentally that this approach can allow SP to avoid generating misleading plans but to generate weak plans that directly lead to strong solutions. The experiments show that SP outperforms state-of-the-art non-deterministic solvers by solving a broader range of problems. We also validate the practical utility of SP in real-world non-deterministic robotic tasks.
