⚡ electrical engineering

Scalable Verification of Neural Control Barrier Functions Using Linear Bound Propagation

本文提出了一种基于线性界传播和 McCormick 松弛的扩展框架，通过计算神经网络梯度的线性上下界并采用自适应细化策略，实现了对任意控制仿射系统下大规模神经控制屏障函数（CBF）的高效可扩展验证。

原作者： Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

发布于 2026-04-15

📖 1 分钟阅读☕ 轻松阅读

原作者： Nikolaus Vertovec, Frederik Baymler Mathiesen, Thom Badings, Luca Laurenti, Alessandro Abate

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

这篇文章介绍了一种让人工智能（AI）控制机器人或自动驾驶汽车时更安全、更可靠的新方法。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成**“给 AI 司机颁发驾照前的终极路考”**。

1. 背景：AI 司机和它的“安全护盾”

想象一下，你正在训练一个 AI 来驾驶一辆自动驾驶汽车。

目标：让车在复杂的道路上行驶，绝对不能撞墙或冲出悬崖。
工具：科学家们发明了一种叫**“控制障碍函数”（CBF）的东西。你可以把它想象成 AI 司机脑子里的一个“隐形安全护盾”**。只要这个护盾存在，AI 就知道：“嘿，往那边开是安全的，往这边开会撞车，所以我要避开。”
新趋势：以前这个“护盾”是人工设计的，像简单的几何图形。现在，大家用**神经网络（Deep Learning）**来训练这个护盾，让它变得更聪明、更灵活，能应对各种奇怪的路况。

2. 问题：怎么证明这个“护盾”真的管用？

虽然神经网络很聪明，但它是个“黑盒子”。我们训练好了它，但怎么100% 确定它在所有情况下都不会失效呢？

旧方法（SMT 求解器）：以前的验证方法就像是一个极其较真的老教授。他会拿着放大镜，把每一个可能的路况（比如车速、角度、天气）都列出来，用复杂的数学公式一个个去算。
- 缺点：如果神经网络稍微大一点（比如层数多一点），这个“老教授”就算到宇宙毁灭也算不完。这限制了 AI 只能做简单的任务，不能处理复杂的现实世界。
瓶颈：验证过程太慢、太贵，导致我们不敢用太强大的 AI 模型。

3. 解决方案：用“直线”去“框住”曲线

这篇论文的作者们想出了一个聪明的办法：不再试图去算清每一个复杂的曲线，而是用“直线”去近似它。

核心比喻：用乐高积木拼出复杂的形状

想象你要验证一个由弯曲的橡皮筋（代表神经网络的复杂非线性逻辑）组成的形状是否安全。

旧方法：试图精确测量每一根橡皮筋的每一个微小弯曲。太难了！
新方法（线性边界传播 LBP）：
1. 画框框：作者们发明了一种技术，能在橡皮筋的周围画出一个**“直线框”**（上界和下界）。只要橡皮筋在这个框里，我们就知道它大概在哪里。
2. 不仅看形状，还看“坡度”：对于安全来说，不仅要知道 AI 在哪里，还要知道它**“想往哪边跑”（也就是梯度/导数）。作者们把这个技术升级了，不仅能框住形状，还能框住“变化的趋势”**。
3. 混合技巧（McCormick 松弛）：当两个复杂的因素（比如车速和转向角度）混在一起时，他们用了另一种数学技巧（就像把复杂的混合液体装进几个简单的方形盒子里），确保不会漏掉任何危险情况。

结果：原本需要算一辈子的复杂曲线，现在变成了几个简单的直线方程。计算机算起来飞快！

4. 进阶技巧：哪里不放心，就“切”哪里

有时候，用一个大框框住整个区域，可能会太“宽泛”（太保守），导致明明安全的地方也被误判为不安全。

自适应切分（Refinement）：作者们设计了一个**“智能切分策略”**。
- 想象你在切蛋糕。如果整块蛋糕看起来没问题，你就放过它。
- 但如果某一块蛋糕看起来有点“模糊”（验证结果不确定），你就把它切成两半（沿着最长的边切），然后分别检查这两小块。
- 这样，只有在真正复杂、危险的地方，系统才会花时间去精细计算；在安全的地方，它就一笔带过。
- 而且，这个过程可以并行处理（就像让很多个切蛋糕的人同时工作），利用显卡（GPU）的速度，效率极高。

5. 实验结果：更强大、更快速

作者们在各种测试中（比如无人机避障、倒立摆小车等）验证了这种方法：

速度：比以前的方法快了几百倍甚至更多。
规模：以前只能验证很小的神经网络，现在可以验证大得多的网络。这意味着我们可以用更聪明、更复杂的 AI 来控制机器人，而不用担心它“发疯”。
通用性：不管 AI 用的是哪种激活函数（就像不管橡皮筋是什么材质的），这个方法都管用。

总结

这篇论文就像是为AI 安全验证领域带来了一场**“工业革命”**。

以前：验证 AI 安全像是在手工雕刻，慢、贵、只能做小东西。
现在：作者们发明了一种**“流水线模具”**（线性边界传播 + 智能切分），能快速、批量地验证巨大的 AI 模型是否安全。

这让未来的自动驾驶汽车、机器人和无人机能够使用更强大的 AI 大脑，同时我们也能放心地把它们交给它们去处理复杂的任务，因为我们有了一套快速、可靠的“安检系统”来确保它们不会出事故。

论文技术总结：基于线性界传播的可扩展神经控制障碍函数验证

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

背景：控制障碍函数（Control Barrier Functions, CBFs）是确保非线性动力学控制系统安全性的关键工具。近年来，利用神经网络（NN）表示 CBF（即 Neural CBFs）因其强大的表达能力和适应性而备受关注，能够处理复杂的非线性动力学和非凸安全集。
核心挑战：训练好的神经网络是否确实是一个有效的 CBF，需要进行后验验证（Post-hoc Verification）。这是目前的主要计算瓶颈。
- 现有方法的局限性：
  - 基于**可满足性模理论（SMT）**求解器（如 dReal）的方法在处理非线性实数算术时计算成本极高，难以扩展到大型网络或高维状态空间。
  - 基于混合整数规划（MIP）或分支定界的方法通常受限于激活函数的类型（如仅适用于 ReLU），难以处理任意非线性激活函数（如 Tanh, Sigmoid），而后者对于学习复杂的 CBF 至关重要。
问题陈述：给定非线性仿射控制系统 $\dot{x} = f(x) + g(x)u$ 、安全集 $S$ 和一个候选的神经网络 CBF $B_\theta$ ，如何高效、可扩展地验证 $B_\theta$ 是否满足 CBF 条件（即其超水平集是控制不变集），同时支持任意非线性激活函数和大型网络架构。

2. 方法论 (Methodology)

本文提出了一种基于**线性界传播（Linear Bound Propagation, LBP）和McCormick 松弛（McCormick Relaxation）**的新型验证框架。该方法的核心思想是将非线性的 CBF 验证条件转化为保守的线性约束，从而避免昂贵的 SMT 求解。

2.1 线性界传播的扩展 (Extended LBP)

传统 LBP：通常用于计算神经网络输出 $B_\theta(x)$ 在给定输入域 $\Delta$ 上的上下界。
本文创新：将 LBP 扩展以计算**网络梯度（雅可比矩阵 $\frac{\partial B_\theta}{\partial x}$ $\frac{\partial B _{θ}}{\partial x}$ ）**的线性上下界。
- 利用链式法则将梯度表示为各层雅可比矩阵的乘积。
- 引入McCormick 松弛处理层间乘积产生的双线性项（bilinear terms）。
- 通过递归地结合前向传播的激活函数界和反向传播的梯度界，构建出关于输入 $x$ 的仿射上下界：
  $\underline{\Pi}x + \underline{\pi} \leq \frac{\partial B_\theta(x)}{\partial x} \leq \overline{\Pi}x + \overline{\pi}$
- 该方法支持任意半可微激活函数，无需额外的前向传递，且可并行化。

2.2 动力学系统的线性化

对系统动力学函数 $f(x)$ 和 $g(x)$ 使用一阶泰勒展开（Certified First-Order Taylor Expansion）。
利用拉格朗日余项界（Lagrange error bound）计算误差项的上下界，将非线性动力学转化为带有误差界的线性形式。

2.3 CBF 条件的线性代理 (Linear Surrogate)

将 CBF 的核心条件（李导数条件）：
$L_f B + \sup_{u \in U} [L_g B \cdot u] + \alpha(B) \geq 0$
中的每一项（梯度、动力学、控制输入项）替换为上述推导出的线性上下界。
利用 McCormick 松弛处理梯度与动力学项的乘积，构建一个保守的线性公式 $\phi_{linear}$ 。
逻辑：如果 $\phi_{linear}$ 在某个区域满足，则原始非线性条件 $\phi$ 必然满足。

2.4 自适应细化策略 (Adaptive Refinement)

由于线性界在大域上过于保守（Conservative），可能导致验证失败（即无法证明满足，也无法证明不满足）。
策略：
- 放弃传统的超矩形（Hyperrectangular）划分，采用**单纯形网格（Simplicial Mesh）**划分状态空间。
- 对于验证结果不确定的区域，沿其最长边进行分割（Splitting）。
- 这种策略能更有效地适应 CBF 条件中多变量耦合的非线性特性，减少保守性。
并行化：利用 GPU 对多个单纯形区域进行批处理（Batching），并行计算线性界和 SAT 求解，显著提升效率。

3. 主要贡献 (Key Contributions)

新型验证方法：提出了结合 LBP 和 McCormick 松弛的验证框架，无需 SMT 求解器即可验证任意激活函数的神经 CBF，显著降低了计算复杂度。
梯度界传播技术：首次将 LBP 扩展用于计算神经网络梯度的线性界，解决了连续时间动力学中李导数验证的关键难题。
自适应单纯形细化：开发了可并行化的自适应细化策略，通过单纯形分割而非超矩形分割，有效降低了线性松弛带来的保守性。
可扩展性验证：实验证明该方法能处理比现有 SMT 方法大得多的神经网络（如包含数十万区域的复杂场景），且支持控制输入项的显式验证。

4. 实验结果 (Results)

基准测试：在多个标准基准（如 Darboux, Barrier 2-4）和两个新基准（2D-Control, Cart-Pole）上进行了测试。
性能对比：
- 与基于 SMT 求解器（dReal）的方法相比，本文方法在验证时间上实现了数量级的提升（例如，Barrier 2 耗时 1.66s vs 635s；Darboux 耗时 144s vs 超时）。
- 能够成功验证包含 64x64 甚至更大隐藏层神经网络的 CBF，而 SMT 方法在处理类似规模网络时往往超时或无法完成。
- 在 Cart-Pole 等包含控制输入项的复杂场景中，验证了 100% 的安全区域。
资源利用：利用 GPU 并行计算，能够高效处理数百万个细分区域（如 Cart-Pole 案例中细分了 300 多万个区域）。

5. 意义与展望 (Significance)

突破规模限制：解决了神经 CBF 验证中的“可扩展性”瓶颈，使得在真实世界复杂系统中使用大型、高表达能力的神经网络作为安全屏障成为可能。
通用性：不局限于 ReLU 激活函数，支持 Tanh、Sigmoid 等更平滑的非线性函数，这通常能产生更优的控制不变集。
工程应用：该方法生成的验证结果可直接用于安全过滤器（Safety Filters）和“学习 - 验证”（Learner-Verifier）框架中，为自动驾驶、机器人操作等安全关键系统的部署提供了理论保障。
未来工作：计划将框架扩展至可达性（Reachability）和避障（Avoidance）等更复杂的规范验证，而不仅仅是不变性（Invariance）。

总结：该论文通过引入线性界传播和 McCormick 松弛，成功将神经 CBF 的验证问题从昂贵的非线性算术求解转化为高效的线性约束检查，并结合自适应单纯形网格细化，实现了在大规模网络和复杂动力学系统上的可扩展验证，是安全关键控制系统领域的一项重要进展。