Distributionally Robust Abstraction and Strategy Synthesis with Formal Guarantees

Abstract

There is growing interest to control cyber-physical systems under complex specifications while retaining formal performance guarantees. In this thesis we present a framework for formal control of uncertain systems under complex specifications. We consider dynamical systems with random disturbances, whose probability distribution is unknown. When it comes to the specifications, we focus on those given as syntactically co-safe linear temporal logic (scLTL) formulas. Such formulas resemble natural language, and allow us to reason over complex behaviours of the system.

We follow an abstraction-based approach: we abstract the original system to a finite-state Markov model, in which the state discretization error as well as the distributional ambiguity, are embedded as uncertainties. To do so we make use of tools from optimal transport and ambiguity sets of probability distributions. After that, we synthesize a strategy for the abstraction and obtain probabilistic guarantees that the abstraction satisfies the specifications. Finally, we correctly refine the strategy to one that the original system can follow, and prove that the guarantees we obtained for the abstraction also hold for the original system.

We propose two approaches to obtain the abstraction. First, we propose a data-driven approach to abstract the system into an interval Markov decision process (IMDP) when samples from the unknown distribution is available. Then we use already existing algorithms to synthesize a strategy for the IMDP. Secondly, we propose an approach to abstract the original system into a robust Markov decision process (robust MDP). This second approach is applicable to more general uncertainty models besides the data-driven one, and reduces conservatism of the abstraction. Furthermore, we propose an algorithm to synthesize robust strategies for robust MDPs, which also renders the guarantees that the abstraction satisfies the specifications. Finally, we demonstrate the usefulness of our proposed approaches through several case studies that involve both linear and nonlinear systems.