Reachability Analysis of Neural Feedback Loops using Sparse Polynomial Optimisation
Matthew Newton, Antonis Papachristodoulou · 2022 IEEE 61st Conference on Decision and Control (CDC) · 2022
Neural networks have seen a recent increased use in control feedback systems. However, providing robustness guarantees on these feedback systems has proven challenging and to combat these issues, there is a significant amount of current research. One of the biggest shortcoming of neural networks is how sensitive they are to adversarial inputs. Given that feedback systems are usually subject to external perturbations, this issue surrounding neural networks must be overcome before they can be used in safety-critical applications. One method to tackle this problem is to compute outer-approximations of the reachable sets, through bounding the activation functions in the neural network controller. Our approach is to use these bounds in a sparse polynomial optimisation framework in conjunction with the Positivstellensatz. The sparsity property is able to exploit the natural cascading structure of the neural network to allow for tractable solve times. The Positivstellensatz is able to provide more accurate bounds over similar methods by asserting the emptiness of a semi-algebraic set. We show through examples that our method can provide tighter bounds over similar methods, with reasonable computational time. Our approach is also able to deal with non-linear polynomial dynamics due to the polynomial optimisation framework we use, while other methods need to use alternative work-around solutions to incorporate the non-linearities.