Permissive Finite-State Controllers of POMDPs using Parameter Synthesis
For researchers in formal verification and planning, this provides a new theoretical connection that leverages existing pMC tools for POMDP controller synthesis, though the performance is only comparable to existing methods.
The paper establishes an equivalence between computing finite-state controllers for POMDPs and parameter synthesis for parametric Markov chains, enabling the use of pMC tools for correct-by-construction FSC synthesis. Experimental results show performance comparable to existing POMDP solvers.
We study finite-state controllers (FSCs) for partially observable Markov decision processes (POMDPs) that are provably correct with respect to given specifications. The key insight is that computing (randomised) FSCs on POMDPs is equivalent to - and computationally as hard as - synthesis for parametric Markov chains (pMCs). This correspondence allows to use tools for parameter synthesis in pMCs to compute correct-by-construction FSCs on POMDPs for a variety of specifications. Our experimental evaluation shows comparable performance to well-known POMDP solvers.