Formal Verification of Robustness and Resilience of Learning-Enabled State Estimation Systems
2010.08311
0
0
🔮
Abstract
This paper presents a formal verification guided approach for a principled design and implementation of robust and resilient learning-enabled systems. We focus on learning-enabled state estimation systems (LE-SESs), which have been widely used in robotics applications to determine the current state (e.g., location, speed, direction, etc.) of a complex system. The LE-SESs are networked systems, composed of a set of connected components including: Bayes filters for state estimation, and neural networks for processing sensory input. We study LE-SESs from the perspective of formal verification, which determines the satisfiabilty of a system model against the specified properties. Over LE-SESs, we investigate two key properties -- robustness and resilience -- and provide their formal definitions. To enable formal verification, we reduce the LE-SESs to a novel class of labelled transition systems, named {PO}^2-LTS in the paper, and formally express the properties as constrained optimisation objectives. We prove that the verification problems are NP-complete. Based on {PO}^2-LTS and the optimisation objectives, practical verification algorithms are developed to check the satisfiability of the properties on the LE-SESs. As a major case study, we interrogate a real-world dynamic tracking system which uses a single Kalman Filter (KF) -- a special case of Bayes filter -- to localise and track a ground vehicle. Its perception system, based on convolutional neural networks, processes a high-resolution Wide Area Motion Imagery (WAMI) data stream. Experimental results show that our algorithms can not only verify the properties of the WAMI tracking system but also provide representative examples, the latter of which inspired us to take an enhanced LE-SESs design where runtime monitors or joint-KFs are required. Experimental results confirm the improvement in the robustness of the enhanced design.
Create account to get full access
The paper presents a formal verification approach for designing and implementing robust and resilient learning-enabled systems. It focuses on learning-enabled state estimation systems (LE-SESs), which are used in robotics applications to determine the current state (e.g., location, speed, direction) of a complex system. LE-SESs are networked systems composed of connected components, including Bayes filters for state estimation and neural networks for processing sensory input.
The paper investigates two key properties of LE-SESs: robustness and resilience, providing formal definitions for these properties. To enable formal verification, the LE-SESs are reduced to a novel class of labelled transition systems called {PO}^2-LTS. The properties are formally expressed as constrained optimization objectives. The verification problems are proven to be NP-complete.
Based on {PO}^2-LTS and the optimization objectives, practical verification algorithms are developed to check the satisfiability of the properties on LE-SESs. As a major case study, a real-world dynamic tracking system using a single Kalman Filter (KF) and convolutional neural networks to process Wide Area Motion Imagery (WAMI) data is investigated.
Experimental results show that the algorithms can verify the properties of the WAMI tracking system and provide representative examples. These examples inspired an enhanced LE-SESs design with runtime monitors or joint-KFs, improving the system's robustness, as confirmed by experimental results.
This summary was produced with help from an AI and may contain inaccuracies - check out the links to read the original source documents!
Related Papers
👨🏫
Neuromorphic Robust Estimation of Nonlinear Dynamical Systems Applied to Satellite Rendezvous
Reza Ahmadvand, Sarah Safura Sharif, Yaser Mike Banad
0
0
State estimation of nonlinear dynamical systems has long aimed to balance accuracy, computational efficiency, robustness, and reliability. The rapid evolution of various industries has amplified the demand for estimation frameworks that satisfy all these factors. This study introduces a neuromorphic approach for robust filtering of nonlinear dynamical systems: SNN-EMSIF (spiking neural network-extended modified sliding innovation filter). SNN-EMSIF combines the computational efficiency and scalability of SNNs with the robustness of EMSIF, an estimation framework designed for nonlinear systems with zero-mean Gaussian noise. Notably, the weight matrices are designed according to the system model, eliminating the need for a learning process. The framework's efficacy is evaluated through comprehensive Monte Carlo simulations, comparing SNN-EMSIF with EKF and EMSIF. Additionally, it is compared with SNN-EKF in the presence of modeling uncertainties and neuron loss, using RMSEs as a metric. The results demonstrate the superior accuracy and robustness of SNN-EMSIF. Further analysis of runtimes and spiking patterns reveals an impressive reduction of 85% in emitted spikes compared to possible spikes, highlighting the computational efficiency of SNN-EMSIF. This framework offers a promising solution for robust estimation in nonlinear dynamical systems, opening new avenues for efficient and reliable estimation in various industries that can benefit from neuromorphic computing.
5/15/2024
🧠
Learning-Based Verification of Stochastic Dynamical Systems with Neural Network Policies
Thom Badings, Wietze Koops, Sebastian Junges, Nils Jansen
0
0
We consider the verification of neural network policies for reach-avoid control tasks in stochastic dynamical systems. We use a verification procedure that trains another neural network, which acts as a certificate proving that the policy satisfies the task. For reach-avoid tasks, it suffices to show that this certificate network is a reach-avoid supermartingale (RASM). As our main contribution, we significantly accelerate algorithmic approaches for verifying that a neural network is indeed a RASM. The main bottleneck of these approaches is the discretization of the state space of the dynamical system. The following two key contributions allow us to use a coarser discretization than existing approaches. First, we present a novel and fast method to compute tight upper bounds on Lipschitz constants of neural networks based on weighted norms. We further improve these bounds on Lipschitz constants based on the characteristics of the certificate network. Second, we integrate an efficient local refinement scheme that dynamically refines the state space discretization where necessary. Our empirical evaluation shows the effectiveness of our approach for verifying neural network policies in several benchmarks and trained with different reinforcement learning algorithms.
6/4/2024
🚀
Learning-Based Optimal Control with Performance Guarantees for Unknown Systems with Latent States
Robert Lefringhausen, Supitsana Srithasan, Armin Lederer, Sandra Hirche
0
0
As control engineering methods are applied to increasingly complex systems, data-driven approaches for system identification appear as a promising alternative to physics-based modeling. While the Bayesian approaches prevalent for safety-critical applications usually rely on the availability of state measurements, the states of a complex system are often not directly measurable. It may then be necessary to jointly estimate the dynamics and the latent state, making the quantification of uncertainties and the design of controllers with formal performance guarantees considerably more challenging. This paper proposes a novel method for the computation of an optimal input trajectory for unknown nonlinear systems with latent states based on a combination of particle Markov chain Monte Carlo methods and scenario theory. Probabilistic performance guarantees are derived for the resulting input trajectory, and an approach to validate the performance of arbitrary control laws is presented. The effectiveness of the proposed method is demonstrated in a numerical simulation.
4/17/2024
OptiState: State Estimation of Legged Robots using Gated Networks with Transformer-based Vision and Kalman Filtering
Alexander Schperberg, Yusuke Tanaka, Saviz Mowlavi, Feng Xu, Bharathan Balaji, Dennis Hong
0
0
State estimation for legged robots is challenging due to their highly dynamic motion and limitations imposed by sensor accuracy. By integrating Kalman filtering, optimization, and learning-based modalities, we propose a hybrid solution that combines proprioception and exteroceptive information for estimating the state of the robot's trunk. Leveraging joint encoder and IMU measurements, our Kalman filter is enhanced through a single-rigid body model that incorporates ground reaction force control outputs from convex Model Predictive Control optimization. The estimation is further refined through Gated Recurrent Units, which also considers semantic insights and robot height from a Vision Transformer autoencoder applied on depth images. This framework not only furnishes accurate robot state estimates, including uncertainty evaluations, but can minimize the nonlinear errors that arise from sensor measurements and model simplifications through learning. The proposed methodology is evaluated in hardware using a quadruped robot on various terrains, yielding a 65% improvement on the Root Mean Squared Error compared to our VIO SLAM baseline. Code example: https://github.com/AlexS28/OptiState
4/30/2024