Learning based supervisor synthesis of POMDP for PCTL specifications

Abstract

Partially Observable Markov Decision Process (POMDP) has been widely used in the robotics to model uncertainties from sensors, actuators and the environment. However, such comprehensiveness makes the planning in POMDP generally very difficult. Existing work often searches for an optimal control policy with respect to predefined reward functions, which may require a large memory and is computationally expensive. We propose to use formal methods and learn a Deterministic Finite Automaton (DFA) as a supervisor to regulate the behavior of a Partially Observable Markov Decision Process (POMDP), such that it satisfies the given specification in Probabilistic Computation Tree Logic (PCTL). For such a purpose, we modify the L* learning algorithm and define oracles for membership queries and conjectures. We further show that the termination and correctness of the design algorithm are guaranteed. A simple example is used for illustration.