⚡ electrical engineering

Time-Varying Reach-Avoid Control Certificates for Stochastic Systems

本文提出了一种针对离散时间连续空间随机系统的时变与时间不变可达 - 避障控制证书框架，并通过和式平方（SOS）优化实现了控制器验证与联合合成，从而在有限或无限时域内最大化目标达成概率并规避不安全区域。

原作者： Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

发布于 2026-03-30

📖 1 分钟阅读☕ 轻松阅读

原作者： Rayan Mazouz, Luca Laurenti, Morteza Lahijanian

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文主要解决了一个让自动驾驶汽车、机器人或无人机在充满不确定性的现实世界中安全行驶并达成目标的大难题。

为了让你轻松理解，我们可以把这篇论文的核心思想想象成**“给自动驾驶汽车设计一套智能的‘安全导航与保险’系统”**。

1. 核心挑战：在迷雾中开车

想象一下，你正在开一辆自动驾驶汽车，但路上有迷雾（随机干扰，比如突发的侧风、路面打滑），而且路况是连续变化的（连续空间，不是只有几个固定的路口）。
你的任务有两个：

到达目的地（Reach）：必须安全地开到终点。
避开危险（Avoid）：绝对不能撞墙或掉进坑里（不安全区域）。

以前的方法要么是把路切成一个个小格子（离散化），但这在复杂路况下计算量太大，算不过来；要么是用复杂的神经网络去“猜”怎么开，但很难保证 100% 安全，因为没法证明它不会出错。

2. 论文的创新：两张“魔法地图”

这篇论文提出了一种新的数学工具，叫做**“时变与不变到达 - 避开证书” (Time-Varying/Invariant Reach-Avoid Certificates)**。

你可以把它想象成给汽车配了两张不同的**“魔法地图”**，用来证明“无论迷雾多大，我都能安全到达”。

方案 A：静态地图（时不变证书）

比喻：这是一张固定的、通用的安全说明书。
特点：它不管你现在是刚出发还是快到了，都告诉你：“只要你在安全区，你就离危险很远；只要你在终点，你就很安全。”
优点：计算简单，像查字典一样快。
缺点：因为它是“一刀切”的，为了保险起见，它可能会把很多本来能走的路也划为“危险区”，导致它给出的安全保证比较保守（比如它说你有 50% 的概率安全，但实际可能有 90%）。

方案 B：动态地图（时变证书）—— 这是本文的亮点

比喻：这是一套随时间变化的“实时导航策略”。
特点：它知道你在第 1 秒、第 10 秒、第 100 秒分别该怎么做。
- 刚出发时，它告诉你：“现在离终点还远，只要别撞墙就行。”
- 快到了，它告诉你：“现在必须精准控制，稍微偏一点就进终点了。”
优点：因为它考虑了时间的变化，所以能给出更精确、更紧的安全保证（比如它能证明你有 95% 的概率安全）。
缺点：计算稍微复杂一点，因为它要算很多个时间点的策略。

3. 如何制造这些地图？（SOS 优化）

以前要画这种地图，需要解非常复杂的数学题，甚至解不出来。
这篇论文引入了一个叫**“和式平方” (Sum-of-Squares, SOS)** 的数学技巧。

比喻：这就像把复杂的“迷宫解题”变成了**“搭积木”**。
以前：你需要凭直觉在迷雾里乱撞，看能不能找到路。
现在：SOS 技术把问题转化成了一个标准的**“凸优化”问题**（就像解一个超级复杂的线性方程组）。计算机可以非常高效、确定性地算出这张“魔法地图”是否存在。如果算出来了，就数学上保证了系统是安全的。

4. 不仅能“证明”，还能“设计”

这篇论文最厉害的地方在于，它不仅能量验证（Verification）现有的控制器是否安全，还能直接设计（Synthesis）出最好的控制器。

比喻：以前的工具只能告诉你“这辆车开得稳不稳”；现在的工具能直接帮你在图纸上画出这辆车的最佳驾驶方案，并保证这辆车在迷雾中一定能开到终点且不掉坑里。

5. 实验结果：真的好用吗？

作者用了很多例子来测试，比如：

一维小车：简单的直线运动。
二维收缩地图：像在一个旋转的房间里找出口。
3D 飞机模型：模拟飞机在气流中飞行。
房间温度控制：模拟空调在温度波动下保持舒适。

结果发现：

在复杂、高维（比如 3D 飞机）的情况下，“动态地图”（时变证书） 完胜。它能用更简单的数学公式（低阶多项式）算出比旧方法（静态地图）高得多的安全概率。
旧方法在复杂情况下经常算不出结果（失败），或者给出的安全概率低得没用（比如只保证 10% 安全，实际有 90%）。
新方法成功让飞机和机器人在充满噪音的环境中，以极高的概率（90% 以上）安全完成任务。

总结

这篇论文就像给自动驾驶和机器人领域提供了一套**“数学上的安全保险”。
它不再依赖“猜”或者“暴力计算”，而是用一种聪明的数学方法（SOS），既能证明系统安全，又能自动设计出最优的控制策略。特别是它提出的“随时间变化的策略”**，让机器人在复杂多变的环境中，能更聪明、更自信地完成任务，同时保证绝对的安全底线。

一句话概括：这就好比给自动驾驶汽车装上了一个**“能预测未来每一秒风险并实时调整路线的超级大脑”，并且这个大脑的每一个决策都有数学铁证**支持，确保万无一失。

这是一份关于论文《Time-Varying Reach-Avoid Control Certificates for Stochastic Systems》（随机系统的时变到达 - 避障控制证书）的详细技术总结。

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

核心问题：
如何在具有连续状态空间和连续动作空间的离散时间随机系统中，验证并合成控制器，以满足**到达 - 避障（Reach-Avoid）**属性？

到达 - 避障属性：要求系统轨迹从初始集 $X_0$ 出发，在有限或无限时间范围内，以高概率到达目标集 $X_r$ ，同时在整个过程中始终保持在安全集 $X_s$ 内（即不进入不安全集 $X_u$ ）。
挑战：
1. 随机性与非线性：系统受随机扰动影响，且动力学通常是非线性的，导致精确计算到达概率极其困难。
2. 连续空间：传统的基于离散化（如马尔可夫决策过程近似）的方法在高维空间中面临“维数灾难”，计算不可行。
3. 现有方法的局限性：
  - 基于有限抽象的方法计算复杂度高。
  - 现有的连续域证书方法（如基于鞅的方法）通常仅限于无限时域，且在转化为凸优化问题时过于保守（Conservative），或者依赖难以验证的深度神经网络。
  - 现有方法往往难以同时处理时变（Time-Varying）和时不变（Time-Invariant）场景，且缺乏联合优化控制器和证书的有效凸框架。

目标：
提出一种基于证书（Certificate-based）的框架，能够：

为给定的控制器提供到达 - 避障概率的下界保证（验证问题）。
联合合成最优反馈控制器和对应的证书，以最大化到达概率（控制综合问题）。
适用于有限时域和无限时域，且能处理连续状态和动作空间。

2. 方法论 (Methodology)

本文提出了一种基于**动态规划（Dynamic Programming, DP）原理和和式平方（Sum-of-Squares, SOS）**优化的统一框架。

2.1 核心概念：到达 - 避障证书

作者定义了两类实值函数（证书） $R(x)$ ，用于下界估计到达概率：

时变证书 (Time-Varying Certificate)： $R(x, k)$ $R (x, k)$ ，依赖于时间步 $k$ $k$ 。适用于有限时域和无限时域。
- 通过引入松弛变量（slack variables） $\alpha_i, \beta_i$ ，放宽了传统值函数在目标集（值为1）和不安全集（值为0）的硬约束，使其更适合连续函数的优化。
- 利用 DP 原理，建立证书与真实概率值函数之间的不等式关系，证明证书值减去松弛项之和即为概率下界。
时不变证书 (Time-Invariant Certificate)： $R(x)$ $R (x)$ ，不显式依赖时间。
- 适用于稳态分析。
- 证明了现有的基于鞅（Martingale）的证书是本文时不变证书的一个特例。

2.2 优化框架：SOS 凸优化

为了将上述函数优化问题转化为可计算的凸优化问题，作者采用了以下策略：

多项式参数化：将证书 $R(x)$ 和控制器 $\pi(x)$ 限制为多项式函数。
SOS 松弛：利用 SOS 多项式理论，将“非负性”约束转化为半定规划（SDP）约束。
- 利用 Putinar 正性定理（Positivstellensatz）处理半代数集（Safe, Unsafe, Target sets）上的约束。
- 将期望算子 $E[\cdot]$ 转化为多项式系数的线性约束（利用矩矩阵 Moment Matrix）。
联合合成 (Joint Synthesis)：
- 针对控制合成问题（Problem 2），这是一个非凸的 Min-Max 问题（最小化控制器参数，最大化最坏情况下的状态）。
- 利用对偶理论和 SOS 松弛，将非凸的 Min-Max 问题转化为一个单一的凸 SOS 优化问题，从而能够同时求解最优控制器和证书。

2.3 两种形式的对比

时不变形式：计算复杂度低（与时间步数无关），但为了获得紧致的下界，通常需要高次多项式，导致决策变量爆炸。
时变形式：计算复杂度随时间步数线性增加，但可以使用低次多项式获得更紧致的下界，特别适合高维系统。

3. 主要贡献 (Key Contributions)

统一的证书公式：
- 提出了适用于离散时间、连续空间随机系统的时变和时不变到达 - 避障证书。
- 覆盖了有限时域和无限时域场景，并提供了严格的概率下界保证。
- 通过引入松弛变量 $\alpha, \beta$ ，解决了传统方法中连续函数难以精确满足边界条件（0 或 1）的问题，使优化问题可行且保守性更低。
基于 SOS 的凸优化框架：
- 建立了基于 SOS 的凸优化问题，用于验证给定控制器的性能。
- 提出了联合合成最优反馈控制器和证书的新方法，避免了深度学习中难以验证的问题，且无需对状态/动作空间进行离散化。
理论分析与比较：
- 证明了现有文献中的鞅证书是本文框架的特例。
- 分析了时变与时不变证书在计算复杂度（ $O((H+1)^3)$ vs $O(1)$ ）和紧致度之间的权衡。
广泛的实验验证：
- 在多个基准系统（1D/2D/3D 线性系统、收缩映射、飞机模型、房间温度控制）上进行了验证。
- 与现有最先进方法（如 [8] 和 [19]）进行了对比，证明了本文方法在概率下界紧致度和计算可行性上的优势。

4. 实验结果 (Results)

实验在 Julia 语言环境下，使用 SumOfSquares.jl 和 JuMP 包进行求解。

与 [8] (时间不变，无限时域) 的对比：
- 在 1D 线性系统中，本文方法在多项式次数为 8 时获得的概率下界（0.76）远高于对比方法（0.16）。
- 在 2D 收缩映射中，当初始集较难时，对比方法甚至无法找到可行解（FAILED），而本文方法成功给出了高概率下界（>0.9）。
- 结论：引入松弛变量 $\alpha$ 显著提高了 SOS 优化的可行性和性能。
与 [19] (有限时域) 的对比：
- 在相同设置下，本文的时不变和时变形式均提供了更紧致的概率下界。
- 特别是时变形式，在较低的多项式次数下就能达到接近 1.0 的概率下界，而对比方法需要更高次数且效果较差。
验证与合成性能：
- 验证：SOS 计算出的下界与蒙特卡洛模拟（Monte Carlo）的实证概率非常接近。例如，在 3D 飞机模型中，时变证书仅需 6 次多项式即可给出 0.98 的下界，而时不变证书需要 24 次多项式才能得到非平凡结果。
- 控制合成：联合合成的线性反馈控制器显著提高了系统的到达概率。
  - 例如，在 2D 收缩映射案例 2 中，无控制时到达概率仅为 0.19，合成控制器后提升至 0.95。
  - 时变证书在合成控制器时，能用更低的多项式次数（如 degree 2 或 4）达到与时不变高次多项式（degree 24）相当甚至更好的性能。
计算效率权衡：
- 时变证书的计算时间随时间步长 $H$ 增加，但通常比时不变证书在达到同等精度时所需的计算量更小（因为避免了高次多项式带来的变量爆炸）。
- 在高维系统（如 3D 房间温度）中，时变方法表现出更好的可扩展性。

5. 意义与影响 (Significance)

理论突破：填补了连续空间随机系统到达 - 避障分析中，时变与时不变证书统一框架的空白，并建立了与动态规划的紧密联系。
工程实用性：提供了一种无需离散化、可验证且计算可行（基于凸优化）的方法，用于设计安全关键的随机系统控制器。这对于自动驾驶、机器人导航等需要严格安全保证的领域至关重要。
解决“维数灾难”的新思路：通过时变证书允许使用低次多项式，有效缓解了高维系统中高次多项式带来的计算不可行问题，为高维随机系统的形式化验证和控制开辟了新途径。
超越深度学习：相比于依赖神经网络的近似方法，本文提供的基于 SOS 的证书具有严格的数学保证，且合成过程是确定性的凸优化，避免了黑盒模型的不确定性。

总结：该论文提出了一种强大的、基于凸优化的形式化方法，能够有效地处理随机系统中的复杂安全与目标达成问题，特别是在高维连续空间场景下，展示了优于现有方法的性能和可扩展性。