💻 computer science

Stochastic Barrier Certificates in the Presence of Dynamic Obstacles

本文提出了一种针对含动态障碍的随机离散时间连续空间系统的安全验证方法，通过引入基于贝尔曼最优性原理的时变随机屏障证书，将其构建为凸和式平方规划问题，从而在有限时域内提供了比现有方法更紧确且可扩展的安全概率下界。

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

发布于 2026-04-23

📖 1 分钟阅读☕ 轻松阅读

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

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

这篇文章主要解决了一个非常现实的问题：在一个充满不确定性和移动障碍物的世界里，如何保证一个“调皮”的机器人（或任何自动系统）不会撞车或出事故？

想象一下，你正在玩一个超级复杂的赛车游戏。

你的车（系统）：有点“醉”，方向盘偶尔会自己乱动（随机噪声/不确定性）。
赛道（环境）：不是静止的，路上有其他的车（动态障碍物）在到处乱跑，而且它们跑得很快。
目标：你要保证在规定的时间内，你的车绝对（或者以极高的概率）不会撞到那些乱跑的车，也不会冲出赛道。

传统的“安全证书”方法就像是在玩这个游戏时，只拿一张静态的地图来规划路线。这张地图告诉你：“只要你不进这个圈，你就安全。”
但这有个大问题：那些乱跑的车（障碍物）是动的！静态地图无法捕捉它们下一秒会跑到哪里。为了强行用静态地图，以前的方法要么把地图画得特别大（把时间维度也画进去），导致地图复杂到电脑算不过来；要么为了保险起见，把安全区域画得特别小，导致你的车根本动不了（太保守了）。

这篇论文提出了一种全新的、更聪明的“动态安全证书”方法。我们可以用三个生动的比喻来理解它的核心贡献：

1. 从“死记硬背”到“看剧本演戏” (时间不变 vs. 时间变化)

旧方法（时间不变证书）：
就像是一个死板的教官。他不管现在是第 1 秒还是第 10 秒，都对着你喊同一个口号：“只要你在 A 区，你就安全！”
- 缺点：因为障碍物在动，第 1 秒的 A 区可能第 5 秒就变成禁区了。教官为了保险，只能把 A 区画得特别小，或者把规则定得特别死，导致你的车寸步难行。
新方法（时间变化证书）：
就像是一个聪明的导演，手里拿着一本分镜剧本。
- 第 1 秒：导演说“现在障碍物在左边，你在右边就安全”。
- 第 5 秒：导演说“现在障碍物跑到了中间，你赶紧往右躲”。
- 第 10 秒：导演说“障碍物走了，你可以加速了”。
- 优点：这种方法利用了时间的结构。它知道每一秒的情况都不一样，所以能给出更精准、更宽松（不那么保守）的安全建议。就像导演知道剧情怎么发展，所以能给出最合理的指导，而不是用一条死规则管到底。

2. 从“把世界装进一个巨大的箱子”到“给每一秒发一张通行证” (维度灾难 vs. 动态规划)

旧方法的笨办法：
为了处理移动的障碍物，以前的方法试图把“时间”和“障碍物位置”全部塞进一个巨大的超级状态空间里。
- 比喻：就像为了预测明天天气，你试图把过去 100 年每一天的天气、每一片云的位置全部画在一张巨大的地图上。这张地图太大了，电脑根本算不动（这就是所谓的“维度灾难”）。
新方法的巧办法：
作者利用了贝尔曼最优性原理（听起来很吓人，其实就是“倒着推”的智慧）。
- 比喻：想象你要从终点倒着走回起点。
  - 最后一步（第 H 秒）：只要没撞车，就是安全的。
  - 倒数第二步（第 H-1 秒）：只要下一步能走到安全的地方，现在就是安全的。
  - 以此类推，一直推到第 1 秒。
- 这种方法不需要把整个时间线画在一张图上，而是给每一秒单独发一张“安全通行证”。虽然要发很多张证，但每张证都很简单，电脑算起来非常快，而且非常精准。

3. 数学魔法：把“不可能”变成“容易算” (多项式与 SOS)

你可能会问：“给每一秒都发一张证，还要考虑随机性，这数学题是不是太难解了？”
作者用了一个数学技巧叫平方和（Sum-of-Squares, SOS）。

比喻：这就像是在解一个超级复杂的迷宫。以前的方法试图用蛮力去试每一条路。而作者发现，只要把迷宫的墙壁和路径用一种特殊的“多项式积木”搭出来，这个问题就能变成一个标准的、电脑能瞬间解开的线性方程组。
这意味着，虽然理论很深奥，但实际计算起来非常快且稳定，甚至可以在普通的笔记本电脑上运行。

实验结果：真的好用吗？

作者拿了很多复杂的系统做测试（比如像杜宾车、四旋翼无人机、甚至模拟的捕食者 - 猎物系统），并且让它们在有移动障碍物的环境下运行。

结果：
- 旧方法：要么算不出来（超时），要么给出的安全概率低得可怜（比如只敢保证 20% 安全，实际上可能 90% 都安全）。
- 新方法：给出的安全概率非常接近真实情况（比如 98%），而且计算速度极快。
- 图 2 的模拟：就像是在看赛车回放，新方法画出的“安全边界”紧紧贴着真实的安全区域，既没有浪费空间，也没有漏掉危险。

总结

这篇论文的核心思想就是：不要试图用一张静态的网去捕捉动态的世界，而要像导演一样，根据每一秒的剧本，动态地调整安全策略。

通过这种“时间变化”的视角，结合高效的数学工具，他们让机器人和自动驾驶汽车在面对移动障碍物时，不仅能算得更快，还能走得更自信（在更广阔的空间里安全行驶），而不是因为害怕撞车而畏手畏脚。这对于未来在繁忙城市里自动驾驶、无人机配送等场景至关重要。

1. 研究问题 (Problem)

本文旨在解决随机动态系统在动态障碍物环境中的安全性验证问题。具体挑战包括：

不确定性：系统演化受非线性随机动力学和噪声影响。
动态环境：环境中存在随时间演化的障碍物（动态障碍物），导致不安全区域（Unsafe Regions）是时变的。
现有方法的局限性：
- 传统的随机屏障函数（SBF）通常假设静态环境，使用单一的时间不变证书，忽略了安全约束的时间序列结构，导致结果过于保守。
- 现有的处理时变性的方法（如基于插值的方法）通常通过马尔可夫不等式和布尔不等式构建保证，引入了额外的保守性，且由于双线性项的存在，难以转化为凸优化问题，导致可扩展性差。
核心目标：在有限时间视界（Finite Horizon）内，为系统提供经过认证的、紧致的（Tight），即系统在整个过程中保持在安全集内且不与动态障碍物碰撞的概率下界。

2. 方法论 (Methodology)

作者提出了一种基于随机屏障函数（Stochastic Barrier Functions, SBFs）的框架，包含两种主要方法：

A. 时间不变方法 (Time-Invariant Approach)

状态空间增强：将系统状态 $x_k$ 与所有障碍物的配置 $o^j_k$ 堆叠，构建一个增广的“元系统”状态 $z_k = (x_k, o^1_k, \dots, o^{N_o}_k)$ 。
静态化：在增广空间中，障碍物的动态演化被吸收到状态转移中，使得不安全集在增广空间中变为静态。
局限性：虽然可以将问题转化为标准的 SBF 问题，但状态维度的增加导致了“维数灾难”，使得在高维系统中求解变得不可行。

B. 时间变化方法 (Time-Varying Approach) - 核心贡献

**基于动态规划 **(DP)：利用贝尔曼最优性原理，将安全性验证视为一个逆向递归过程。
时变证书：引入随时间步 $k$ $k$ 变化的屏障函数 $B(x, k)$ $B (x, k)$ ，而非单一的全局函数。
- 该函数直接捕捉了安全性的逆向可达性结构（Backward Reachability Structure）。
- 每个时间步的不安全区域 $X_u(k)$ 被显式地纳入约束条件中。
数学形式化：
- 定义了一组随时间变化的 SBF 条件，包括非负性、在初始集上的上界、在不安全集上的下界以及基于期望的递推不等式。
- 证明了安全概率下界为 $1 - (\alpha + \sum \beta_i)$ 。
**凸优化求解 **(SOS)：
- 假设系统动力学和障碍物映射为多项式函数，且集合为半代数集。
- 将屏障函数的合成问题转化为凸的平方和（Sum-of-Squares, SOS）优化问题。
- 利用半定规划（SDP）进行数值求解，确保了计算的可处理性（Tractability）。

3. 主要贡献 (Key Contributions)

统一的 SBF 框架：提出了同时包含时间不变（基于状态增强）和时间变化（基于 DP）的 SBF 证书公式，适用于离散时间随机系统。
基于动态规划的时间变化证书：
- 首次将贝尔曼最优性原理引入随机屏障证书，直接编码了时间演化结构。
- 相比现有方法，显著降低了保守性，提供了更紧致的安全概率下界。
可计算的 SOS 合成：证明了在多项式假设下，时间变化屏障的合成可以转化为凸优化问题，实现了数值稳定的合成。
实证验证：在多个非线性系统（如不稳定系统、振荡器、Dubin 小车、四旋翼无人机）上进行了基准测试，验证了理论保证并展示了优越性。

4. 实验结果 (Results)

作者在 Julia 环境中使用 SumOfSquares.jl 和 JuMP 进行了实验，对比了三种方法：时间不变法、插值法（Interpolation-based）和本文提出的时间变化法。

安全性概率下界（ $P_s$ $P_{s}$ ）：
- 时间变化法在所有基准测试中 consistently（一致地）获得了最高的安全概率下界。
- 在长视界（Large Horizon）和高维系统中，时间不变法和插值法的下界往往退化为 0 或非常保守，而时间变化法仍能保持较高的下界（例如在 Oscillator 和 Quadrotor 实验中，下界接近蒙特卡洛模拟的真实值）。
计算效率与可扩展性：
- 时间不变法：随着视界增加或系统维度提高，需要极高阶的多项式，计算时间急剧增加甚至超时（Time-out）。
- 插值法：在低维短视界下表现尚可，但在复杂动态障碍物场景下，计算时间过长或无法收敛。
- 时间变化法：虽然参数数量随时间步增加，但避免了状态维度的爆炸。在大多数情况下，计算时间可控，且能处理更复杂的动态障碍物场景（如多个移动障碍物）。
蒙特卡洛验证：图 2 显示，时间变化证书计算出的理论下界与蒙特卡洛模拟得到的经验安全概率高度吻合，证明了其非保守性和准确性。

5. 意义与影响 (Significance)

理论突破：解决了动态环境中随机系统安全性验证的保守性问题，通过引入时间变化结构，更准确地捕捉了系统与环境交互的时序特性。
实际应用价值：为自动驾驶、机器人导航等需要在动态不确定环境中运行的系统提供了更可靠、更紧致的安全保证，使得在复杂场景下的安全控制合成成为可能。
方法学创新：展示了如何将动态规划思想与随机屏障函数及 SOS 优化相结合，为处理具有时变约束的随机控制问题提供了一条新的、可扩展的技术路径。

总结：该论文通过引入基于动态规划的时间变化随机屏障证书，成功克服了传统方法在处理动态障碍物时的保守性和可扩展性瓶颈，为随机系统在动态环境中的安全验证提供了目前最紧致的理论保证和高效的计算方案。