POMDPにおけるほぼ確実な到達可能性の強制
Enforcing Almost-Sure Reachability in POMDPs
部分観測マルコフ決定過程(POMDP)で、悪状態を避けつつ目標状態へほぼ確実に到達する方策を合成するための勝利領域を計算する2つのアルゴリズム(SATベース反復法と決定図ベース法)を提案し、有効性を実証した。
著者: Sebastian Junges, Nils Jansen, Sanjit A. Seshia
分類: cs.AI, cs.RO, cs.SY, eess.SY
原文アブストラクト
Partially-Observable Markov Decision Processes (POMDPs) are a well-known stochastic model for sequential decision making under limited information. We consider the EXPTIME-hard problem of synthesising policies that almost-surely reach some goal state without ever visiting a bad state. In particular, we are interested in computing the winning region, that is, the set of system configurations from which a policy exists that satisfies the reachability specification. A direct application of such a winning region is the safe exploration of POMDPs by, for instance, restricting the behavior of a reinforcement learning agent to the region. We present two algorithms: A novel SAT-based iterative approach and a decision-diagram based alternative. The empirical evaluation demonstrates the feasibility and efficacy of the approaches.
