Scaling Mixed-Integer Programming for Certification of Neural Network Controllers Using Bounds Tightening
Authors:
- 16 December 2024
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1645-1650
Abstract
Neural networks offer a computationally efficient approximation of model predictive control, but they lack guarantees on the resulting controlled system’s properties. Formal certification of neural networks is crucial for ensuring safety, particularly in safety-critical domains such as autonomous vehicles. One approach to formally certify properties of neural networks is to solve a mixed-integer program based on the network. This approach suffers from scalability issues due to the complexity of solving the resulting mixed-integer programs. Nevertheless, these issues can be (partially) mitigated via bound-tightening techniques prior to forming the mixed-integer program, which results in tighter formulations and faster optimization. This paper presents bound-tightening techniques in the context of neural network explicit control policies. Bound tightening is particularly important when considering problems spanning multiple time steps of a controlled system, as the bounds must be propagated through the problem depth. Several strategies for bound tightening are evaluated in terms of both computational complexity and tightness of the bounds.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Bound Tightening Using Rolling-Horizon Decomposition for Neural Network Verification2024
- Stability Verification of Neural Network Controllers Using Mixed-Integer ProgrammingIEEE Transactions on Automatic Control, 2023
- Reliably-Stabilizing Piecewise-Affine Neural Network ControllersIEEE Transactions on Automatic Control, 2022
- Stability and feasibility of neural network-based controllers via output range analysis2020
- Efficient Representation and Approximation of Model Predictive Control Laws via Deep LearningIEEE Transactions on Cybernetics, 2020
- Strong mixed-integer programming formulations for trained neural networksMathematical Programming, 2020
- Reluplex: An Efficient SMT Solver for Verifying Deep Neural Networks2017
- A Survey on Explicit Model Predictive Control2009
- Evaluation of piecewise affine control via binary search treeAutomatica, 2003
- A receding-horizon regulator for nonlinear systems and a neural approximationAutomatica, 1995