SEEV: Synthesis with Efficient Exact Verification for ReLU Neural Barrier Functions
Abstract
Neural Control Barrier Functions (NCBFs) have shown significant promise in enforcing safety constraints on nonlinear autonomous systems. State-of-the-art exact approaches to verifying safety of NCBF-based controllers exploit the piecewise-linear structure of ReLU neural networks, however, such approaches still rely on enumerating all of the activation regions of the network near the safety boundary, thus incurring high computation cost. In this paper, we propose a framework for Synthesis with Efficient Exact Verification (SEEV). Our framework consists of two components, namely (i) an NCBF synthesis algorithm that introduces a novel regularizer to reduce the number of activation regions at the safety boundary, and (ii) a verification algorithm that exploits tight over-approximations of the safety conditions to reduce the cost of verifying each piecewise-linear segment. Our simulations show that SEEV significantly improves verification efficiency while maintaining the CBF quality across various benchmark systems and neural network structures. Our code is available at https://github.com/HongchaoZhang-HZ/SEEV.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- General Cutting Planes for Bound-Propagation-Based Neural Network Verification cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
- General Cutting Planes for Bound-Propagation-Based Neural Network Verification cites Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound
- Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
- Complete Verification via Multi-Neuron Relaxation Guided Branch-and-Bound cites Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers
- Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete Verifiers cites Automatic Perturbation Analysis for Scalable Certified Robustness and Beyond
Cited by top-tier papers1
Builds on8
- Automatic Perturbation Analysis for Scalable Certified Robustness and BeyondKaidi Xu, Zhouxing Shi, Huan Zhang, Yihan Wang et al.NeurIPS 2020 · 415 citations
- Fast and Complete: Enabling Complete Neural Network Verification with Rapid and Massively Parallel Incomplete VerifiersKaidi Xu, Huan Zhang, Shiqi Wang, Yihan Wang et al.ICLR 2021 · 250 citations
- Learning Safe Multi-agent Control with Decentralized Neural Barrier CertificatesZengyi Qin, Kaiqing Zhang, Yuxiao Chen, Jingkai Chen et al.ICLR 2021 · 164 citations
- General Cutting Planes for Bound-Propagation-Based Neural Network VerificationHuan Zhang, Shiqi Wang, Kaidi Xu, Linyi Li et al.NeurIPS 2022 · 154 citations
- Complete Verification via Multi-Neuron Relaxation Guided Branch-and-BoundClaudio Ferrari, Mark Niklas Müller, Nikola Jovanovic, Martin T. VechevICLR 2022 · 117 citations
Related papers
- Exact Verification of ReLU Neural Control Barrier FunctionsHongchao Zhang, Junlin Wu, Yevgeniy Vorobeychik, Andrew ClarkNeurIPS 2023 · 32 citations
- Synthesizing Barrier Certificates of Neural Network Controlled Continuous Systems via ApproximationsMeng Sha, Xin Chen, Yuzhe Ji, Qingye Zhao et al.DAC 2021 · 14 citations
- Neural Barrier Certificates Synthesis of NN-Controlled Continuous Systems via Counterexample-Guided LearningHanrui Zhao, Niuniu Qi, Mengxin Ren, Xia Zeng et al.DAC 2024 · 3 citations
- An Iterative Scheme of Safe Reinforcement Learning for Nonlinear Systems via Barrier Certificate GenerationZhengfeng Yang, Yidan Zhang, Wang Lin, Xia Zeng et al.CAV 2021 · 15 citations
- Unifying Qualitative and Quantitative Safety Verification of DNN-Controlled SystemsDapeng Zhi, Peixin Wang, Si Liu, C.-H. Luke Ong et al.CAV 2024 · 11 citations
