⚡ electrical engineering

Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions

该论文提出了一种算法，通过计算哈密顿 - 雅可比可达性值函数的可靠上下界，解决了传统网格方法因离散化误差而无法保证安全验证集合（如向后可达集和避障集）近似精度的问题，并辅以网格细化策略以获得更紧致的界限。

原作者： Ihab Tabbara, Eliya Badr, Hussein Sibai

发布于 2026-03-31

📖 1 分钟阅读☕ 轻松阅读

原作者： Ihab Tabbara, Eliya Badr, Hussein Sibai

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

这篇论文主要解决了一个关于**“如何确保机器人或自动驾驶汽车在复杂环境中绝对安全”**的数学难题。

为了让你轻松理解，我们可以把这篇论文的核心思想想象成**“在迷雾中绘制一张绝对安全的藏宝图”**。

1. 背景：迷雾中的探险家

想象你是一位探险家（也就是那个控制系统，比如自动驾驶汽车），你的目标是到达一个宝藏点（目标区域，Target Set），但你必须避开沿途所有的陷阱（失败区域，Failure Set，比如悬崖或障碍物）。

传统方法的问题：以前的方法就像是在一张粗糙的网格地图上计算路线。他们把连续的世界切分成一个个小方块（网格），然后在方块的中心点计算。
- 隐患：因为地图太粗糙，他们可能会犯错。比如，某个方块的中心点是安全的，但方块的边缘其实已经掉进陷阱了。传统方法算出来的“安全区”可能看起来很大，但实际上包含了危险（这叫“过拟合”或“假安全”）。或者反过来，把一些其实能到达宝藏的地方误判为去不了（这叫“漏算”）。
- 后果：在自动驾驶或手术机器人这种性命攸关的领域，这种“看起来安全但实际危险”的误判是绝对不能接受的。

2. 核心创新：给地图加上“安全边框”

这篇论文提出了一种新算法，它的核心思想不是只画一条线，而是给每个小方块都画上“安全边框”。

想象一下，我们不再只关心方块的中心，而是给每个方块都套上两个“护盾”：

上界（Upper Bound）：这是一个**“最乐观”的估计。如果连这个最乐观的估计都显示“去不了宝藏”，那这个方块100% 是去不了的**（绝对安全区，即无法到达目标）。
下界（Lower Bound）：这是一个**“最悲观”的估计。如果连这个最悲观的估计都显示“能到达宝藏”，那这个方块100% 是能到达的**（绝对安全区，即可以安全到达目标）。

关键点在于：

如果“最乐观”和“最悲观”的结论一致，我们就100% 确定这个方块是安全的还是危险的。
如果它们打架了（一个说能，一个说不能），说明这个方块太模糊了，我们需要把它切得更细（细化网格），直到我们能看清真相为止。

3. 两个聪明的“作弊”技巧

为了让这个计算既快又准，作者用了两个很聪明的策略：

技巧一：见好就收（提前停止计算）

通常，这种数学计算需要算到“完全收敛”（算到结果不再变化）才停止，但这非常慢，就像非要等到水完全烧开才关火。

论文的做法：作者发现，即使提前关火（提前停止计算），只要加上一个小小的**“修正系数”（就像给没烧开的汤加一点保温剂），依然能保证结果是绝对安全**的。
比喻：就像你切菜，不需要切得完美无缺，只要切得足够厚，保证每一片都包含你想切的部位，并且多切掉一点点边缘，你就永远不会切到手指。

技巧二：智能聚焦（哪里模糊切哪里）

传统的网格是均匀切分的，不管哪里都切得很细，这很浪费算力。

论文的做法：算法会像侦探一样，只盯着那些“最乐观”和“最悲观”结论打架的模糊区域。
比喻：就像你在画素描，远处的山随便涂涂就行（粗网格），但眼睛和嘴巴这种关键部位，就反复擦除、重画，直到细节清晰（细网格）。这样既省时间，又保证了关键地方的精准度。

4. 实际效果：更安全的自动驾驶

作者在两个案例中测试了这个方法：

双宾车（Dubins Car）：一种只能向前开、不能横向移动的简化汽车模型。
3D 躲避（3D Evasion）：飞机在空中躲避碰撞的场景。

结果令人印象深刻：

相比现有的工具，他们的方法算得更快，而且算出来的安全区域更大、更准。
现有的工具可能会因为网格太粗，把一些危险的地方误判为安全（比如把悬崖边缘当成平地），而他们的算法绝不会犯这种错。它要么告诉你“这里绝对安全”，要么告诉你“这里绝对危险”，要么告诉你“这里太模糊了，我再切细一点看看”，但绝不会给你模棱两可的假安全。

总结

这篇论文就像是为自动驾驶和机器人安全系统发明了一套**“带放大镜的绘图仪”**。

它不再盲目地相信粗糙的地图，而是通过上下界夹逼和智能细化，确保每一个被标记为“安全”的地方，真的是安全的；每一个被标记为“危险”的地方，真的是危险的。这就像给未来的自动驾驶汽车穿上了一层数学上的“防弹衣”，让它们在复杂的现实世界中，既能大胆前行，又万无一失。

这是一份关于论文《Computing Sound Lower and Upper Bounds on Hamilton-Jacobi Reach-Avoid Value Functions》（计算哈密顿 - 雅可比可达 - 避障值函数的可靠上下界）的详细技术总结。

1. 问题背景与挑战 (Problem Statement)

核心问题：在非线性控制系统的安全验证和控制综合中，哈密顿 - 雅可比（Hamilton-Jacobi, HJ）可达性分析是一个基础工具。它用于计算向后可达集（BRS）（即无论采取何种控制都无法避免进入失败状态的状态集）和可达 - 避障集（RAS）（即存在控制策略能安全到达目标集并避开失败集的状态集）。
现有方法的局限性：
- 传统的 HJ 分析方法通常在离散化的网格上数值求解 HJ 偏微分方程（PDE）。
- 缺乏严格保证：这些方法通常不显式处理离散化误差。因此，它们无法保证计算出的集合是 BRS 的可靠上近似（即不会漏报不安全状态）或 RAS 的可靠下近似（即不会误报安全状态）。
- 收敛性问题：许多方法假设值迭代（Value Iteration）收敛到不动点，但在实际计算中往往提前终止，这引入了额外的近似误差，且现有方法未对此进行修正以保证结果的可靠性。
目标：开发一种算法，能够计算 HJ 值函数的可靠上下界，从而在考虑离散化误差和值迭代提前终止的情况下，严格保证 BRS 的上近似和 RAS 的下近似。

2. 方法论 (Methodology)

论文提出了一套完整的框架，包含离散化抽象、值函数界限计算、提前终止修正以及自适应网格细化。

A. 离散化抽象 (Discrete Abstractions)

将连续状态空间 $X$ 划分为有限网格单元（Cells）。
构建一个非确定性转移关系 $\Delta$ ：对于网格中的每个单元 $s$ 和离散控制动作 $a$ ，计算系统从该单元出发在一步内能到达的所有状态的上近似（Over-approximation）。
利用系统的 Lipschitz 连续性常数，通过模拟中心点轨迹并构建半径为 $L_f \times \text{cell\_radius}$ 的球体（或超立方体）来保证覆盖所有可能的连续状态转移。

B. 值函数的上下界计算 (Value Function Bounds)

定义界限：针对每个网格单元，利用 Lipschitz 常数 $L_l$ 和 $L_r$ 计算失败函数 $l(x)$ 和奖励函数 $r(x)$ 在该单元内的上下界（ $l(s), \bar{l}(s)$ 和 $r(s), \bar{r}(s)$ ）。
定义离散值函数：
- 上界值函数 $\bar{V}_\gamma(s)$ ：对应于最坏情况下的可达 - 避障度量（保守估计安全）。
- 下界值函数 $\underline{V}_\gamma(s)$ ：对应于最好情况下的可达 - 避障度量（保守估计不安全）。
贝尔曼算子：定义了针对这两个值函数的离散贝尔曼算子，证明了它们是压缩映射，存在唯一不动点。
理论保证：证明了对于连续状态空间中的任意状态 $x$ （属于单元 $s$ ），其真实值函数 $V_\gamma(x)$ 满足： $\underline{V}_\gamma(s) \le V_\gamma(x) \le \bar{V}_\gamma(s)$ 。

C. 值迭代提前终止的修正 (Early Stopping Correction)

问题：在实际计算中，值迭代往往在收敛前停止。
解决方案：
- 对于下界（ $\underline{V}_\gamma$ ）：利用迭代过程中的最小变化量 $\delta_k$ 和折扣因子 $\gamma$ ，引入一个修正项 $\frac{\gamma \delta_k}{1-\gamma}$ 。即使迭代提前停止，加上修正项后的值仍能保证是真实值函数的下界。
- 对于上界（ $\bar{V}_\gamma$ ）：证明了在适当初始化下，迭代过程中的任意中间值都是真实值函数的上界，无需额外修正项（但在 $\gamma=1$ 时需特殊处理）。
结果：算法可以在任意迭代步数停止，并输出具有数学保证的保守界限。

D. 自适应网格细化 (Adaptive Refinement)

未分类单元：如果某个单元的下界 $\le 0$ 且上界 $> 0$ ，则无法确定该单元是安全还是不安全（未分类）。
细化策略：算法自动识别这些未分类单元，将其沿最长边分裂为两个更小的子单元。
迭代过程：在细化后的网格上重新运行值界限计算，直到所有单元被分类或达到最小分辨率限制。这显著提高了边界附近的近似精度。

3. 主要贡献 (Key Contributions)

可靠的界限计算算法：提出了一种算法，能够计算离散时间非线性控制系统的 HJ 值函数的可靠上下界。该方法显式处理了状态空间离散化误差和值迭代提前终止带来的误差。
提前终止的理论保证：在可达 - 避障（Reach-Avoid）问题中，证明了即使值迭代未收敛到不动点，通过引入修正项，算法计算出的界限依然是正确的（Sound）。
自适应细化算法：开发了一种局部细化算法，专门针对界限不够紧（无法分类）的网格单元进行分裂，从而获得更精确的 BRS 上近似和 RAS 下近似。
实验验证：在 Dubins 小车和 3D 规避两个案例研究中验证了算法的有效性，并与现有的 HJ 工具箱（如 HJ Reachability Toolbox）和符号控制工具（ROCS 2.0）进行了对比。

4. 实验结果 (Results)

案例研究：
- Dubins 小车：在二维平面运动模型中，算法成功计算了避障和到达目标的安全区域。
- 3D 规避：在三维飞机规避场景中验证了方法的有效性。
对比分析：
- 与现有 HJ 工具箱对比：传统 HJ 工具箱在低分辨率网格下容易将不安全状态误判为安全（即 RAS 下近似不足），而本文方法始终保证 RAS 的下近似性质。
- 与 ROCS 2.0 对比：在相同的离散化参数下，本文方法计算出的 RAS 更大（更精确），且运行时间更短。即使不进行网格细化，本文方法也能比 ROCS 2.0 计算出更大的安全集。
- 计算效率：虽然网格细化会增加计算量，但迭代时间与网格大小呈近似线性增长。批量细化策略（Batch Refinement）比逐个细化更高效。
避免-only 情况：论文指出，对于纯避障（Avoid-only）问题，必须使用非折扣因子（ $\gamma=1$ ）才能正确分类安全集，因为折扣因子会导致安全状态的值收敛至零，从而无法区分。

5. 意义与影响 (Significance)

安全性保证：该方法填补了现有 HJ 分析在“离散化误差”和“提前终止”方面的理论空白，为安全关键系统（如自动驾驶、手术机器人）提供了形式化验证所需的严格数学保证。
量化评估：不同于传统的二值分类（安全/不安全），该方法提供的是值函数界限，允许量化系统满足规格的程度（Safety Margin），为控制器设计提供了更丰富的信息。
自适应精度：通过局部细化，算法能够在保持计算效率的同时，在状态空间的关键边界区域提供高分辨率的近似，解决了传统均匀网格在精度和计算成本之间的权衡难题。
通用性：框架适用于非线性离散时间系统，且通过修正项处理了迭代收敛问题，具有广泛的适用性。

总结：这篇论文提出了一种严谨的数值方法，通过计算 HJ 值函数的可靠上下界，解决了传统可达性分析中因离散化和提前终止导致的安全性保证缺失问题，并通过自适应细化显著提高了计算精度，为安全关键控制系统的验证提供了强有力的工具。