Interval Reachability of Nonlinear Dynamical Systems with Neural Network Controllers
This addresses the safety verification problem for neural network controllers in complex nonlinear environments, offering a scalable solution that is incremental in improving computational efficiency.
The paper tackles the problem of verifying safety in nonlinear continuous-time dynamical systems controlled by neural networks, proposing an interval analysis framework that efficiently computes hyper-rectangular over-approximations of reachable sets, with performance demonstrated to match state-of-the-art methods for linear systems.
This paper proposes a computationally efficient framework, based on interval analysis, for rigorous verification of nonlinear continuous-time dynamical systems with neural network controllers. Given a neural network, we use an existing verification algorithm to construct inclusion functions for its input-output behavior. Inspired by mixed monotone theory, we embed the closed-loop dynamics into a larger system using an inclusion function of the neural network and a decomposition function of the open-loop system. This embedding provides a scalable approach for safety analysis of the neural control loop while preserving the nonlinear structure of the system. We show that one can efficiently compute hyper-rectangular over-approximations of the reachable sets using a single trajectory of the embedding system. We design an algorithm to leverage this computational advantage through partitioning strategies, improving our reachable set estimates while balancing its runtime with tunable parameters. We demonstrate the performance of this algorithm through two case studies. First, we demonstrate this method's strength in complex nonlinear environments. Then, we show that our approach matches the performance of the state-of-the art verification algorithm for linear discretized systems.