Importance Sampling for Statistical Certification of Viable Initial Sets

Abstract

We study the problem of statistically certifying viable initial sets (VISs)---sets of initial conditions whose trajectories satisfy a given control specification. While VISs can be obtained from model-based methods, these methods typically rely on simplified models. We propose a simulation-based framework to certify VISs by estimating the probability of specification violations under a high-fidelity or black-box model. Since detecting these violations may be challenging due to their scarcity, we propose a sample-efficient framework that leverages importance sampling to target high-risk regions. We derive an empirical Bernstein inequality for weighted random variables, enabling finite-sample guarantees for importance sampling estimators. We demonstrate the proposed approach on two systems and show improved convergence of the resulting bounds on an adaptive cruise control benchmark.