<inline-formula><tex-math notation="LaTeX">$\mathsf{HyHooVer}$</tex-math></inline-formula>: Verification and Parameter Synthesis in Stochastic Systems With Hybrid State Space Using Optimistic Optimization

Abstract

This article presents a new method for model-free verification of a general class of control systems with unknown nonlinear dynamics, where the state space has both a continuum-based and a discrete component. Specifically, we focus on finding what choices of initial states or parameters maximize a given probabilistic objective function over all choices of initial states or parameters from such hybrid state space, without having exact knowledge of the system dynamics. We introduce the notion of set initialized Markov chains to represent such systems. Our method utilizes generalized techniques from multi-armed bandit theory on the continuum, in an attempt to make an efficient use of the available sampling budget. We introduce a new algorithm called the Hybrid Hierarchical Optimistic Optimization (HyHOO) algorithm, which is designed to address the problem outlined in this paper. The algorithm combines elements of the existing Hierarchical Optimistic Optimization (HOO) bandit algorithm with carefully chosen parameters to create a fresh perspective on the problem. By viewing the problem as a multi-armed bandit problem, we are able to provide theoretical regret bounds on sample efficiency of our tool, $\mathsf{HyHooVer}$. This is achieved by making assumptions about the smoothness of the underlying system. The results of experiments in formal verification and parameter synthesis of variety of scenarios, indicate that the proposed method is effective and efficient when applied to realistic-sized problems and it performs well compared to other methods, specifically PlasmaLab, BoTorch, and the baseline HOO algorithm. Specifically, it demonstrates better efficiency when employed on models with large state space and when the objective function has sharp slopes in comparison with other tools.

Keywords

• Autonomous systems
• black-box optimization
• monte-carlo tree search
• multi-armed bandits
• safety verification