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

1. 问题背景与定义 (Problem Formulation)

核心问题：
针对未知的离散时间动态系统（$x_{k+1} = f(x_k)$），仅利用采样的状态轨迹数据，在有限时间范围内估计系统的可达集（Reachable Set）。

挑战：
现有的数据驱动可达集估计方法通常面临三个未被同时解决的实践挑战：

1. 紧度与可靠性的权衡： 难以在缩小集合体积（紧度）和保证未来轨迹包含率（可靠性）之间进行可调节的平衡。
2. 对抗扰动鲁棒性： 现有方法通常假设采样数据是绝对真实的，缺乏对数据中存在噪声或对抗性扰动的鲁棒性。
3. 分布偏移下的保证： 当部署时的数据分布与训练分布发生偏移（Distribution Shift）时，缺乏基于 Wasserstein 距离的优雅退化保证。

数学定义：

• 系统： $x_{k+1} = f(x_k)$，其中 $f$ 未知且包含不确定性。
• 数据： 拥有 $N$ 条独立采样的状态轨迹 $x^{(i)} = (x^{(i)}_k)_{k \in \mathcal{T}}$，来自未知分布 $\mathcal{P}$。
• 目标： 学习一族集合 $\mathcal{R}^*_k$，使得未来新轨迹 $x$ 以高概率满足 $x_k \in \mathcal{R}^*_k$ 对所有 $k \in \mathcal{T}$ 成立。

---

2. 方法论 (Methodology)

本文提出了一种基于场景优化（Scenario Optimization）的松弛框架，结合了对抗鲁棒性和分布鲁棒性。

2.1 可调节的松弛场景程序 (Tunable Relaxed Scenario Program)

作者提出了一个带有松弛变量 $\xi_i$ 的优化问题 $\mathcal{P}_{N,\rho}$：
$$\begin{aligned} \min_{\theta, \xi \ge 0} \quad & \sum_{k \in \mathcal{T}} S(\mathcal{R}_k(\theta_k)) + \rho \sum_{i \in \mathcal{N}} \xi_i \\ \text{s.t.} \quad & g(x^{(i)}, \theta) \le \xi_i, \quad \forall i \in \mathcal{N} \end{aligned}$$

• $\theta$：定义可达集几何形状（如中心、半径、矩阵）的决策变量。
• $S(\cdot)$：集合大小的代理指标（如体积、半径）。
• $\xi_i$：松弛变量，允许部分采样轨迹“违反”约束。
• $\rho$：惩罚参数。
  • 作用：调节集合大小与轨迹包含率之间的权衡。$\rho$ 越大，越强调拟合观测轨迹（减小 $\xi_i$），导致集合变大；$\rho$ 越小，集合越小，但可能忽略异常值。

2.2 对抗鲁棒可达集 (Adversarially Robust Reachable Sets)

考虑到采样轨迹可能受到有界对抗扰动（$\tilde{x} \in \mathcal{A}_{x}$，其中 $\mathcal{A}_{x}$ 是以 $x$ 为中心、半径为 $R$ 的球体），将上述问题扩展为 $\hat{\mathcal{P}}_{N,\rho,A}$：

• 约束条件变为：对于每个采样轨迹 $x^{(i)}$ 及其所有可能的扰动 $\tilde{x}^{(i)} \in \mathcal{A}_{x^{(i)}}$，必须满足 $g(\tilde{x}^{(i)}, \theta) \le \xi_i$。
• 通过多面体近似（Polytopic approximation）将无限约束转化为有限约束，保持问题的凸性。
• 理论保证：基于对抗场景优化理论，定义了对抗复杂度 $s^*_A$，并推导了未来轨迹被排除在集合之外的概率界限（Theorem 1）。

2.3 分布鲁棒性 (Distributional Robustness)

针对部署时分布发生偏移的情况（即真实分布 $\tilde{\mathcal{P}}$ 位于名义分布 $\mathcal{P}$ 的 1-Wasserstein 球内），推导了**分布外（Out-of-Distribution, OOD）**的违规概率界限（Theorem 2）：
$$V_{\tilde{\mu}, \mathcal{P}}(\mathcal{R}^*_N) \le \epsilon(s^*_A) + \frac{\tilde{\mu}}{R}$$

• $\tilde{\mu}$：Wasserstein 距离半径（分布偏移程度）。
• $R$：对抗扰动半径。
• 结论：理论保证会随着分布偏移的增加而线性退化，退化速率取决于偏移量与对抗半径的比值。

2.4 凸重构 (Tractable Convex Reformulations)

为了实际求解，针对三种常见的几何形状推导了具体的凸优化形式：

1. $p$-范数球 (p-norm balls)：基于体积或半径作为目标。
2. 椭球 (Ellipsoids)：基于行列式（体积）或对数行列式作为目标。
3. Zonotopes (Zonotopes)：基于生成矩阵和半宽向量，引入辅助变量处理线性约束。

---

3. 主要贡献 (Key Contributions)

1. 可调节的权衡机制：

   • 不同于以往使用硬约束的场景优化，本文引入松弛变量 $\xi_i$ 和惩罚参数 $\rho$，实现了集合大小与未来轨迹包含率之间的可调节权衡，降低了对异常值的敏感性。

2. 对抗扰动下的后验保证：

   • 利用对抗鲁棒场景优化理论，为受扰动的采样轨迹提供了后验（a posteriori）概率保证。即使数据受到有界对抗攻击，也能保证未来轨迹以高概率落在估计的可达集内。

3. Wasserstein 分布偏移下的退化界限：

   • 首次将达观集估计与 Wasserstein 分布鲁棒性结合，给出了当部署分布发生偏移时，理论保证如何**优雅退化（gracefully degrade）**的显式界限。

4. 多种几何形状的凸重构：

   • 针对 $p$-范数球、椭球和 Zonotopes 三种几何结构，推导了具体的凸优化公式，使得算法在数值上易于计算。

---

4. 实验结果 (Results)

在数值模拟中，作者使用了一个带有非线性项和随机扰动的二阶系统进行了验证：

• 几何形状对比：
  • 比较了 Zonotopes、椭球和欧几里得球。
  • Zonotopes 通常能提供更紧致的集合（更小的体积），但需要更多的采样数据才能达到与其他形状相同的理论保证水平。
  • 椭球和球 在数据量较少时表现更稳健。
• 参数 $\rho$ 的影响：
  • 随着 $\rho$ 增大，松弛变量 $\xi_i$ 被更严厉地惩罚，导致估计的可达集变大，以更好地覆盖观测到的（包括被扰动的）轨迹。
  • 验证了 $\rho$ 作为调节集合大小与泛化性能之间权衡的有效性。
• 理论 vs 实证：
  • 实验显示，经验违规概率（Empirical Violation Probability）始终低于理论界限（Theoretical Bound），验证了理论推导的保守性和有效性。
  • 随着样本量 $N$ 的增加，理论界限和实证结果均显著改善。
• 分布偏移测试：
  • 在测试数据分布发生偏移（均值和方差变化）的情况下，经验违规概率依然保持在理论界限（Theorem 2）之下，证明了方法对分布偏移的鲁棒性。

---

5. 意义与总结 (Significance)

• 理论突破：将场景优化从“黑盒”工具转化为针对可达集估计的定制化框架，填补了数据驱动可达性分析中关于对抗鲁棒性和分布偏移保证的空白。
• 实际应用价值：
  • 为安全关键系统（如自动驾驶、机器人控制）提供了更可靠的验证工具，特别是在数据质量不可靠或环境分布可能变化的场景下。
  • 提供的可调节参数 $\rho$ 允许工程师根据具体应用场景（是更看重控制精度还是安全性）灵活调整策略。
• 未来方向：论文指出，未来的工作可以将 Wasserstein 模糊集直接嵌入训练过程，以显式地保证分布鲁棒性，而不仅仅是依赖对抗训练带来的隐式鲁棒性。

总结而言，该论文提出了一种统一且鲁棒的框架，利用少量采样轨迹，在存在噪声、对抗攻击和分布偏移的情况下，生成具有严格概率保证的可达集估计。