Statistical Reachability Analysis of Stochastic Cyber-Physical Systems Under Distribution Shift

Navid Hashemi, Lars Lindemann, Jyotirmoy V. Deshmukh

TL;DR

This paper tackles the challenge of ensuring safety in cyber-physical systems when their behavior might change after deployment (distribution shift). They propose a novel data-driven approach that uses surrogate models and robust conformal inference to provide probabilistic safety guarantees even when the system's dynamics are unknown and its behavior drifts.

What Problem Does This Paper Address?

Ensuring the safety of cyber-physical systems (CPS) is paramount, especially in safety-critical applications. A common technique for this is reachability analysis, which determines the set of all possible states a system can reach within a given time. However, traditional methods often require a precise, symbolic model of the system's dynamics. Many real-world CPS, particularly those with complex, nonlinear, or hybrid components (like those using machine learning), lack such explicit models. Instead, we might only have access to a "digital twin" – a simulator that can generate example trajectories.

A major hurdle arises when the system's behavior in the real world (deployment) deviates from the behavior learned from the simulator. This "sim-to-real" gap, or distribution shift, can invalidate safety guarantees derived solely from the simulator. This paper addresses the problem of performing reachability analysis for stochastic CPS where the dynamics are unknown and the deployed system's behavior might shift from the training data distribution. The goal is to provide probabilistic safety guarantees that hold even under this distribution shift.

Methods

The paper proposes a three-step approach:

  1. Learning a Deterministic Surrogate Model: Instead of directly analyzing the complex, unknown dynamics, the authors train a neural network (NN) surrogate model. This model learns to predict K-step trajectories from a given initial state, using data sampled from the simulator. A key innovation here is using a quantile loss function during training, rather than the standard mean squared error. This helps reduce conservatism in the resulting safety guarantees, as it focuses on the distribution of prediction errors rather than just their average.
  2. Reachability Analysis on the Surrogate Model: Once the surrogate model is trained, standard reachability analysis techniques are applied to it. This generates a "surrogate flowpipe" – an approximation of the reachable states based on the learned model.
  3. Robust Conformal Inference for Distribution Shift: To account for the potential distribution shift between the simulator and the deployed system, the paper employs robust conformal inference. This statistical technique quantifies the uncertainty in the surrogate model's predictions. Crucially, it's adapted to be "robust" to distribution shifts, meaning it can provide valid guarantees even if the deployed system's trajectories come from a slightly different distribution than the training data. They introduce a novel way to compute the nonconformity score by taking the maximum of weighted residuals, which normalizes errors and further reduces conservatism.

Datasets

The paper uses simulated data for training and evaluation. Specific datasets mentioned include:

  • Simulated trajectories from a non-linear system: Used in Experiment 1 to compare MSE and quantile loss training.
  • 12-Dimensional Quadcopter Model: A benchmark system from [17] used for experiments. Data is generated with additive Gaussian noise and a specific ODE model.
  • Time-reversed van Der Pol Oscillator (TRVDP) Dynamics: A known unstable system used for experiments. Data is generated from its SDE model with additive Gaussian noise.

The paper does not introduce new benchmark datasets but rather uses existing models and generates data from them.

Key Insights and Ideas

  • Quantile Loss for Reduced Conservatism: Training surrogate models with a quantile loss function, rather than MSE, leads to tighter and less conservative reachability guarantees. This is because it directly optimizes for the distribution of prediction errors, which is more relevant for probabilistic guarantees.
  • Robust Conformal Inference is Crucial for Distribution Shift: Standard conformal inference assumes the test data comes from the same distribution as the training data. Robust conformal inference, as adapted in this paper, is essential for maintaining safety guarantees when this assumption is violated due to distribution shifts.
  • Data Efficiency: The proposed method achieves high confidence guarantees with significantly fewer calibration data points compared to prior work, making it more practical.
  • Unified Nonconformity Score: Using a trajectory-wise maximum of weighted residuals as the nonconformity score simplifies the application of robust conformal inference, avoiding component-wise analysis that can lead to conservatism.

Key Results

  • Tighter Flowpipes: Experiments demonstrate that the proposed quantile loss training method results in significantly tighter probabilistic flowpipes compared to using MSE loss. Figure 1 visually illustrates this for a 2D system.
  • Valid Guarantees under Distribution Shift: The method successfully provides probabilistic safety guarantees (e.g., 95% confidence) for systems experiencing distribution shifts, as shown in experiments with the quadcopter and TRVDP dynamics. Table 1 and Figure 4 quantify these results, showing that neglecting distribution shift leads to violated guarantees.
  • Improved Data Efficiency: For a 99.99% confidence level on a quadcopter model, the proposed method requires only 2x10^4 calibration data points, whereas a prior method [10] needs 24x10^6.
  • Scalability: The approach is demonstrated on high-dimensional systems (12D quadcopter) and unstable systems (TRVDP), showcasing its applicability.

Limitations and Future Work

  • Approximation of Distribution Shift: The paper assumes that the distribution shift can be characterized by an f-divergence ball of a known radius τ. In practice, estimating τ accurately can be challenging.
  • Computational Cost: While the method is data-efficient, reachability analysis on high-dimensional systems can still be computationally intensive. The use of techniques like set partitioning in the NNV toolbox helps mitigate this.
  • Future Work: The authors suggest exploring more sophisticated methods for estimating the distribution shift radius τ and investigating the application of their framework to systems with continuous-time dynamics. They also mention the potential for further improvements in training surrogate models and the use of more advanced reachability analysis tools.

Summary updated

Abstract

Reachability analysis is a popular method to give safety guarantees for stochastic cyber-physical systems (SCPSs) that takes in a symbolic description of the system dynamics and uses set-propagation methods to compute an overapproximation of the set of reachable states over a bounded time horizon. In this paper, we investigate the problem of performing reachability analysis for an SCPS that does not have a symbolic description of the dynamics, but instead is described using a digital twin model that can be simulated to generate system trajectories. An important challenge is that the simulator implicitly models a probability distribution over the set of trajectories of the SCPS; however, it is typical to have a sim2real gap, i.e., the actual distribution of the trajectories in a deployment setting may be shifted from the distribution assumed by the simulator. We thus propose a statistical reachability analysis technique that, given a user-provided threshold $1-ε$, provides a set that guarantees that any reachable state during deployment lies in this set with probability not smaller than this threshold. Our method is based on three main steps: (1) learning a deterministic surrogate model from sampled trajectories, (2) conducting reachability analysis over the surrogate model, and (3) employing {\em robust conformal inference} using an additional set of sampled trajectories to quantify the surrogate model's distribution shift with respect to the deployed SCPS. To counter conservatism in reachable sets, we propose a novel method to train surrogate models that minimizes a quantile loss term (instead of the usual mean squared loss), and a new method that provides tighter guarantees using conformal inference using a normalized surrogate error. We demonstrate the effectiveness of our technique on various case studies.
BibTeX
@article{hashemi2024statistical,
  author = {Navid Hashemi and Lars Lindemann and Jyotirmoy V. Deshmukh},
  title = {{Statistical Reachability Analysis of Stochastic Cyber-Physical Systems Under Distribution Shift}},
  journal = {IEEE TCAD},
  year = {2024},
  doi = {10.1109/tcad.2024.3438072},
}
Figure