Human-in-the-Loop Synthesis for Partially Observable Markov Decision
  Processes
  We study planning problems where autonomous agents operate inside
environments that are subject to uncertainties and not fully observable.
Partially observable Markov decision processes (POMDPs) are a natural formal
model to capture such problems. Because of the potentially huge or even
infinite belief space in POMDPs, synthesis with safety guarantees is, in
general, computationally intractable. We propose an approach that aims to
circumvent this difficulty: in scenarios that can be partially or fully
simulated in a virtual environment, we actively integrate a human user to
control an agent. While the user repeatedly tries to safely guide the agent in
the simulation, we collect data from the human input. Via behavior cloning, we
translate the data into a strategy for the POMDP. The strategy resolves all
nondeterminism and non-observability of the POMDP, resulting in a discrete-time
Markov chain (MC). The efficient verification of this MC gives quantitative
insights into the quality of the inferred human strategy by proving or
disproving given system specifications. For the case that the quality of the
strategy is not sufficient, we propose a refinement method using
counterexamples presented to the human. Experiments show that by including
humans into the POMDP verification loop we improve the state of the art by
orders of magnitude in terms of scalability.
