Data-driven Reachable Set Estimation with Tunable Adversarial and Wasserstein Distributional Guarantees

1. Problem Statement

The paper addresses the challenge of estimating reachable sets for unknown discrete-time dynamical systems using only sampled state trajectories.

• Context: Traditional reachable set estimation relies on known system models. However, modern applications often involve partially known dynamics or complex uncertainties where model-based approaches fail.
• Goal: To learn a family of sets (one for each time step in a finite horizon) that contains future state trajectories with high probability, based solely on $N$ observed trajectories.
• Key Challenges:
  1. Trade-off: Balancing the tightness (size) of the estimated set against the reliability (probability of inclusion) for unseen trajectories.
  2. Adversarial Robustness: Ensuring the sets remain valid even if the observed training data is perturbed by noise or malicious adversaries.
  3. Distributional Shift: Providing guarantees that degrade gracefully when the deployment distribution differs from the training distribution (measured via Wasserstein distance).

2. Methodology

The authors propose a unified framework based on Scenario Optimization with specific extensions for robustness and relaxation.

A. Tunable Relaxation Framework

Instead of treating scenario optimization as a black box with hard constraints, the authors introduce a relaxed scenario program ($P_{N,\rho}$):

• Objective: Minimize a size proxy of the reachable set (e.g., volume, radius) plus a penalty term weighted by $\rho$.
• Constraints: The constraints allow for slack variables ($\xi_i$) for each sampled trajectory.
  • $g(x^{(i)}, \theta) \leq \xi_i$
• Tuning Parameter ($\rho$): This parameter controls the trade-off.
  • High $\rho$: Enforces strict consistency with observed data (larger sets, higher inclusion probability).
  • Low $\rho$: Allows more outliers to be ignored (smaller sets, potentially lower inclusion probability).
• Geometries: The framework supports various convex geometries, including $p$-norm balls, ellipsoids, and zonotopes.

B. Adversarially Robust Formulation

To handle perturbations in the observed data (e.g., sensor noise or adversarial attacks), the method is extended to Adversarially Robust Scenario Optimization:

• Perturbation Model: Each sampled trajectory $x^{(i)}$ is assumed to lie within a bounded set $\mathcal{A}_{x^{(i)}}$ (e.g., a ball of radius $R$).
• Robust Constraints: The optimization ensures that for every trajectory, all possible perturbations within the adversarial set satisfy the reachable set constraints.
• Complexity Measure: The authors define an Adversarial Complexity ($s^*_A$), which counts the number of trajectories that are "active" in defining the boundary of the reachable set under worst-case perturbations.

C. Theoretical Guarantees

The paper derives rigorous probabilistic bounds using recent results in scenario optimization:

1. A Posteriori Probabilistic Guarantees: Theorem 1 provides a bound on the adversarial probability of trajectory exclusion ($V_A$). With confidence $1-\beta$, the probability that a new trajectory (and its perturbations) falls outside the estimated set is bounded by a function of the adversarial complexity $s^*_A$ and the number of samples $N$.
2. Wasserstein Distributional Robustness: Theorem 2 addresses the scenario where the deployment distribution shifts from the training distribution.
   • If the new distribution lies within a 1-Wasserstein ball of radius $\tilde{\mu}$ around the nominal distribution, the violation probability is bounded by:
     $$V_{\tilde{\mu}, P} \leq \epsilon(s^*_A) + \frac{\tilde{\mu}}{R}$$
   • This shows that the theoretical guarantees degrade gracefully (linearly) with the magnitude of the distribution shift relative to the adversarial radius.

D. Tractable Reformulations

To ensure computational feasibility, the authors derive convex reformulations for specific geometries:

• $p$-norm Balls: Reformulated using radius and center variables with $L_p$ norm constraints.
• Ellipsoids: Reformulated using matrix variables, often utilizing the log-determinant of the shape matrix as a size proxy to maintain convexity.
• Zonotopes: Reformulated using generator matrices and scaling factors, introducing auxiliary variables to handle the linear constraints of the zonotope definition.

3. Key Contributions

1. Relaxed Scenario Approach for Reachability: Unlike prior works that use hard constraints or holdout methods, this paper introduces a tunable relaxation ($\rho$) that explicitly balances set size and generalization guarantees.
2. Adversarial Robustness in Reachability: It is the first work to integrate adversarially robust scenario optimization directly into reachable set estimation, providing bounds that account for bounded perturbations in the training data.
3. Wasserstein Distributional Guarantees: The paper provides explicit, non-asymptotic bounds on how the probabilistic guarantees degrade under distribution shifts, linking the degradation rate to the ratio of the Wasserstein radius to the adversarial radius.
4. Geometric Flexibility: The framework is generalized to support $p$-norm balls, ellipsoids, and zonotopes, with specific convex reformulations provided for each.

4. Results and Simulations

The authors validate their theory through numerical simulations on a stochastic nonlinear system:

• Setup: A system with unknown dynamics ($x_{k+1} = Ax_k + B\phi(Cx_k) + w_k$) over a horizon $T=25$, trained on $N=1000$ trajectories.
• Adversarial Robustness:
  • Simulations showed that increasing $\rho$ leads to larger sets that better cover the data, including adversarially perturbed samples.
  • Empirical vs. Theoretical: The empirical probability of trajectory violation was consistently below the theoretical bounds derived in Theorem 1, confirming the validity of the guarantees.
  • Geometry Comparison: Zonotopes provided tighter sets (better size) but required more samples to achieve the same theoretical guarantees compared to ellipsoids or balls.
• Distributional Shift:
  • Tests were conducted where the test data was drawn from a shifted Gaussian distribution (different mean and variance).
  • The empirical out-of-distribution violation probability remained below the theoretical bound derived in Theorem 2, demonstrating the method's robustness to distribution shifts.
• Tuning: The parameter $\rho$ was shown to effectively trade off set size against inclusion probability across all geometries.

5. Significance

This paper bridges the gap between data-driven learning and formal verification in control systems.

• Practicality: It moves beyond "black-box" scenario optimization, offering a tunable mechanism ($\rho$) for engineers to balance safety (set size) and performance (inclusion probability).
• Robustness: By explicitly modeling adversarial perturbations and distribution shifts, the method is more suitable for real-world deployment where data is noisy and operating conditions may drift.
• Theoretical Rigor: The derivation of a posteriori guarantees that hold for unseen data, even under distributional shifts, provides a strong safety certificate for autonomous systems and safety-critical control applications.

In summary, the paper presents a robust, data-driven framework for estimating reachable sets that is mathematically grounded, computationally tractable, and adaptable to various geometric representations and uncertainty models.