Search and explore: symbiotic policy synthesis in POMDPs

Formal Methods in System Design, vol. 68

Abstract

Abstract This paper marries two state-of-the-art controller synthesis methods for partially observable Markov decision processes (POMDPs), a prominent model in sequential decision making under uncertainty. A central issue is to find a POMDP controller—that solely decides based on the observations seen so far—to achieve a total expected reward objective. As finding optimal controllers is undecidable, we concentrate on synthesising good finite-state controllers (FSCs). We do so by tightly integrating two modern, orthogonal methods for POMDP controller synthesis: a belief-based and an inductive approach. The former method obtains an FSC from a finite fragment of the so-called belief MDP, an MDP that keeps track of the probabilities of equally observable POMDP states. The latter is an inductive search technique over a set of FSCs, e.g., controllers with a fixed memory size. The key result of this paper is a symbiotic anytime algorithm that tightly integrates both approaches such that each profits from the controllers constructed by the other. Experimental results indicate a substantial improvement in the value of the controllers while significantly reducing the synthesis time and memory footprint.

Authors 6

1. Roman Andriushchenko

   Brno University of Technology

   Affiliation as printed

   Brno University of Technology, Brno, Czech Republic

2. Alexander Bork Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

3. Milan Češka corresponding

   Brno University of Technology

   Affiliation as printed

   Brno University of Technology, Brno, Czech Republic

4. Sebastian Junges

   Radboud University Nijmegen

   Affiliation as printed

   Radboud University, Nijmegen, The Netherlands

5. Joost-Pieter Katoen Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University, Aachen, Germany

6. Filip Macák

   Brno University of Technology

   Affiliation as printed

   Brno University of Technology, Brno, Czech Republic