オンラインPOMDP計画における任意時点での決定論的最適性保証
Online POMDP Planning with Anytime Deterministic Optimality Guarantees
離散POMDPにおいて近似解と最適解の決定論的な関係を導出し、既存のオンライン木探索アルゴリズムに決定論的保証を付与する手法を提案した。
著者: Moran Barenboim, Vadim Indelman
分類: cs.AI, cs.RO
原文アブストラクト
Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framework for formulating decision-making problems under such conditions. However, finding an optimal solution for a POMDP is generally intractable. In recent years, there has been a significant progress of scaling approximate solvers from small to moderately sized problems, using online tree search solvers. Often, such approximate solvers are limited to probabilistic or asymptotic guarantees towards the optimal solution. In this paper, we derive a deterministic relationship for discrete POMDPs between an approximated and the optimal solution. We show that at any time, we can derive bounds that relate between the existing solution and the optimal one. We show that our derivations provide an avenue for a new set of algorithms and can be attached to existing algorithms that have a certain structure to provide them with deterministic guarantees with marginal computational overhead. In return, not only do we certify the solution quality, but we demonstrate that making a decision based on the deterministic guarantee may result in superior performance compared to the original algorithm without the deterministic certification.
