Importance Sampling for Statistical Certification of Viable Initial Sets
This work addresses the challenge of reliable certification for control systems, offering a simulation-based method that is incremental over existing model-based approaches.
The paper tackles the problem of certifying viable initial sets for control systems by estimating violation probabilities under high-fidelity models, using importance sampling to improve sample efficiency and providing finite-sample guarantees with empirical Bernstein inequalities. It demonstrates improved convergence on an Adaptive Cruise Control benchmark.
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 effectiveness of the proposed approach on two systems and show improved convergence of the resulting bounds on an Adaptive Cruise Control benchmark.