Identification of Unexpected Decisions in Partially Observable
  Monte-Carlo Planning: a Rule-Based Approach
  Partially Observable Monte-Carlo Planning (POMCP) is a powerful online
algorithm able to generate approximate policies for large Partially Observable
Markov Decision Processes. The online nature of this method supports
scalability by avoiding complete policy representation. The lack of an explicit
representation however hinders interpretability. In this work, we propose a
methodology based on Satisfiability Modulo Theory (SMT) for analyzing POMCP
policies by inspecting their traces, namely sequences of
belief-action-observation triplets generated by the algorithm. The proposed
method explores local properties of policy behavior to identify unexpected
decisions. We propose an iterative process of trace analysis consisting of
three main steps, i) the definition of a question by means of a parametric
logical formula describing (probabilistic) relationships between beliefs and
actions, ii) the generation of an answer by computing the parameters of the
logical formula that maximize the number of satisfied clauses (solving a
MAX-SMT problem), iii) the analysis of the generated logical formula and the
related decision boundaries for identifying unexpected decisions made by POMCP
with respect to the original question. We evaluate our approach on Tiger, a
standard benchmark for POMDPs, and a real-world problem related to mobile robot
navigation. Results show that the approach can exploit human knowledge on the
domain, outperforming state-of-the-art anomaly detection methods in identifying
unexpected decisions. An improvement of the Area Under Curve up to 47\% has
been achieved in our tests.
