Diagnosing Partially Observable Markov Decision Processes

Abstract:
Albeit an important and versatile model for many practical applications, partially observable Markov Decision Processes (POMDPs) are notoriously hard to analyze. Many interesting properties are either of high complexity or even theoretically undecidable, and while approximative methods often provide good results for, e. g., policy synthesis and the computation of probabilities, other problems remain still unsolved. One such issue is diagnosis – figuring out why a certain specification cannot be met, and what can be done to repair the system. While in deterministic systems like digital circuits, a single execution trace is a sufficient proof of an unsafe system, the situation is less easy in probabilistic systems – typically large sets of traces are required whose joint probability exceeds a maximally tolerable probability. For POMDPs, the restricted observability adds another layer of uncertainty. In this paper we focus on analyzing where the restricted observability needs to be refined in order to satisfy a required safety or performance property. We propose and evaluate different approaches for obtaining such diagnostic information.