非決定計画領域におけるLTLf最善努力戦略の合成
LTLf Best-Effort Synthesis in Nondeterministic Planning Domains
完全観測可能な非決定領域で有限トレース線形時相論理の目標に対する最善努力戦略を、ゲーム理論的手法で効率的に合成する方法を提案した。
著者: Giuseppe De Giacomo, Gianmarco Parretti, Shufang Zhu
分類: cs.AI, cs.FL, cs.GT, cs.RO
原文アブストラクト
We study best-effort strategies (aka plans) in fully observable nondeterministic domains (FOND) for goals expressed in Linear Temporal Logic on Finite Traces (LTLf). The notion of best-effort strategy has been introduced to also deal with the scenario when no agent strategy exists that fulfills the goal against every possible nondeterministic environment reaction. Such strategies fulfill the goal if possible, and do their best to do so otherwise. We present a game-theoretic technique for synthesizing best-effort strategies that exploit the specificity of nondeterministic planning domains. We formally show its correctness and demonstrate its effectiveness experimentally, exhibiting a much greater scalability with respect to a direct best-effort synthesis approach based on re-expressing the planning domain as generic environment specifications.
関連論文
- 記号LTLfにおけるベストエフォート合成計画・合成
