Contraction-Guided Adaptive Partitioning for Reachability Analysis of Neural Network Controlled Systems
This work addresses the challenge of efficient and accurate reachability analysis for neural network controlled systems, which is crucial for safety-critical applications like autonomous vehicles, but it appears incremental as it builds on existing interval-valued reachability and neural network verification techniques.
The paper tackles the problem of improving interval-valued robust reachable set estimates for nonlinear feedback loops with neural network controllers and disturbances by introducing a contraction-guided adaptive partitioning algorithm. The result is a sizable improvement in accuracy, achieving better reachable set estimation in a fraction of the runtime compared to state-of-the-art methods.
In this paper, we present a contraction-guided adaptive partitioning algorithm for improving interval-valued robust reachable set estimates in a nonlinear feedback loop with a neural network controller and disturbances. Based on an estimate of the contraction rate of over-approximated intervals, the algorithm chooses when and where to partition. Then, by leveraging a decoupling of the neural network verification step and reachability partitioning layers, the algorithm can provide accuracy improvements for little computational cost. This approach is applicable with any sufficiently accurate open-loop interval-valued reachability estimation technique and any method for bounding the input-output behavior of a neural network. Using contraction-based robustness analysis, we provide guarantees of the algorithm's performance with mixed monotone reachability. Finally, we demonstrate the algorithm's performance through several numerical simulations and compare it with existing methods in the literature. In particular, we report a sizable improvement in the accuracy of reachable set estimation in a fraction of the runtime as compared to state-of-the-art methods.