ReachLipBnB: A branch-and-bound method for reachability analysis of neural autonomous systems using Lipschitz bounds
We propose a novel Branch-and-Bound method for reachability analysis of neural networks in both open-loop and closed-loop settings. Our idea is to first compute accurate bounds on the Lipschitz constant of the neural network in certain directions of interest offline using a convex program. We then use these bounds to obtain an instantaneous but conservative polyhedral approximation of the reachable set using Lipschitz continuity arguments. To reduce conservatism, we incorporate our bounding algorithm within a branching strategy to decrease the over-approximation error within an arbitrary accuracy. We then extend our method to reachability analysis of control systems with neural network controllers. Finally, to capture the shape of the reachable sets as accurately as possible, we use sample trajectories to inform the directions of the reachable set over-approximations using Principal Component Analysis (PCA). We evaluate the performance of the proposed method in several open-loop and closed-loop settings.
Code (1)
Similar Papers 제목 키워드 기반
Provable Bounds on the Hessian of Neural Networks: Derivative-Preserving Reachability Analysis
We propose a novel reachability analysis method tailored for neural networks with differentiable activations. Our idea hinges on a sound abstraction of the neural network map based on first-order Taylor expansion and bou…
Safety Verification for Neural Networks Based on Set-boundary Analysis
Neural networks (NNs) are increasingly applied in safety-critical systems such as autonomous vehicles. However, they are fragile and are often ill-behaved. Consequently, their behaviors should undergo rigorous guarantees…
Autonomous VehiclesReachability-Based Contingency Planning against Multi-Modal Predictions with Branch MPC
This paper presents a novel contingency planning framework that integrates learning-based multi-modal predictions of traffic participants into Branch Model Predictive Control (MPC). Leveraging reachability analysis, we a…
Model Predictive ControlVerifying Safety of Neural Networks from Topological Perspectives
Neural networks (NNs) are increasingly applied in safety-critical systems such as autonomous vehicles. However, they are fragile and are often ill-behaved. Consequently, their behaviors should undergo rigorous guarantees…
Autonomous VehiclesData-Driven Reachability Analysis for Piecewise Affine Systems
Hybrid systems play a crucial role in modeling real-world applications where discrete and continuous dynamics interact, including autonomous vehicles, power systems, and traffic networks. Safety verification for these sy…
Autonomous Vehicles