屏障证书的构造:动态规划视角
《Automatica》:On the construction of barrier certificates: A dynamic programming perspective
【字体:
大
中
小
】
时间:2026年08月28日
来源:Automatica 6.2
编辑推荐:
摘要
本文重新审视了有限时域上随机动力系统的形式化验证问题,采用势垒证书方法。该领域现有的大部分工作侧重于安全性属性,其基于c-鞅的概念构建势垒证书。在本工作中,我们首先从动态规划算子的角度,对现有基于鞅的势垒证书条件提出了新的见解。具体而言,我们证明现有条件实质上提供了动
摘要
本文重新审视了有限时域上随机动力系统的形式化验证问题,采用势垒证书方法。该领域现有的大部分工作侧重于安全性属性,其基于c-鞅的概念构建势垒证书。在本工作中,我们首先从动态规划算子的角度,对现有基于鞅的势垒证书条件提出了新的见解。具体而言,我们证明现有条件实质上提供了动态规划解的一个界限,而该解恰好刻画了安全概率。基于这一新视角,我们表明现有方法中的势垒条件在不安全状态上可能过于保守。为解决这一问题,我们提出了一组新的安全势垒证书条件,相较于现有方法具有更低的保守性,从而为安全验证提供 tighter 或相等的概率界限。我们进一步将方法扩展到 reach-avoid 规范,提供了一组新的势垒证书条件。我们还展示了如何利用和式平方(SOS)规划来搜索这些新的势垒证书。最后,我们通过数值算例展示了该方法相较于现有方法的优点,并验证了高维系统 reach-avoid 验证的可行性。
引言
安全性是信息物理系统(CPS)中的主要关注点,尤其是随着它们被更多地整合到关键基础设施中并发展出复杂功能之后。许多CPS在具有不确定性的动态环境中运行,从而导致随机行为。例如,自动驾驶车辆必须满足安全性要求,如在路面条件不确定和交通状况不可预测的情况下避免碰撞。确保此类系统的安全需要严格的验证方法,以考虑随机性和环境变化。近年来,人们对随机动力系统的验证技术兴趣日益增长,旨在提供形式化保证,使系统能够在不确定条件下可靠运行(Belta 和 Sadraddini,2019,Lavaei 等,2022,Yin 等,2024)。
随机系统的安全验证通常通过 Bellman 方程来建模,其中安全概率通过动态规划方法计算,参见 Abate 等(2008)。然而,这些第一性原理方法通常在高维系统中计算不可行。另一种方法是使用抽象模型进行验证。例如,Esmaeil Zadeh Soudjani 和 Abate(2014)采用马尔可夫链抽象来验证随机系统的概率不变性。基于抽象的方法的关键优势是它们能够处理超越安全性的复杂规范(Zhong 等,2023),同时利用针对有限状态系统的成熟算法。然而,它们仍然受到维度灾难的困扰,限制了其在高维设置中的可扩展性。
一种更具计算可行性的安全验证方法是无需抽象的势垒证书方法(Nejati 等,2023,Prajna 等,2007,Salamati 和 Zamani,2022),该方法提供了类似 Lyapunov 的系统行为保证。最初,势垒证书用于界定无限时域上的安全概率(Huang 等,2017,Prajna 等,2007,Wisniewski 和 Bujorianu,2017)。随后,该方法被扩展到有限时域安全验证(Santoyo 等,2021,Steinhardt 和 Tedrake,2012,Xue,2024a),因为对于大多数实际系统而言,无限时域安全性难以实现。最近,势垒证书已被应用于在线性时序逻辑(LTL)规范下验证随机系统(Jagtap 等,2018),以及在分布鲁棒设置下的安全验证,其中精确的随机分布未知,但受限于一个模糊集(Chen 等,2025,Sch?n 等,2024)。
本文贡献:虽然 Abate 等(2008)和 Summers 和 Lygeros(2010)等先驱工作已使用动态规划建模了这些概率的精确计算,但在连续状态空间中直接求解本质上受到维度灾难的困扰。势垒证书框架通过无需状态空间离散化即可高效提供严格的概率界限,从而绕过了这一瓶颈。在本工作中,我们从动态规划(DP)的角度着手解决有限时域上随机系统的形式化验证中势垒证书的构建问题,包括安全性和 reach-avoid 规范。首先,我们重新审视安全验证问题,证明现有的势垒证书条件实际上为 DP 解提供了下界。通过这一 DP 视角,我们进一步揭示了某些现有的势垒证书条件在不安全状态上施加了不必要的保守性。基于这一见解,我们提出了一种新的用于安全验证的势垒证书,通过放宽先前方法中的参数约束来降低保守性。然后,我们将这种基于 DP 的构建扩展到 reach-avoid 规范,这是文献中较少探索的领域。我们表明,我们的方法克服了从安全验证扩展到 reach-avoid 验证的基本挑战。具体而言,虽然标准的基于鞅的证书依赖于单一吸收边界来处理安全性,但在 reach-avoid 场景中,它们难以处理不相交的目标集和不安全集之间的竞争停止时间。我们的动态规划视角通过结构化地将状态空间分解为三案例逻辑,成功地解缠了这些竞争的边界。最后,我们将这些新势垒证书的搜索表述为和式平方(SOS)规划,并通过一个高维 reach-avoid 验证示例以及与现有方法在两个示例上的对比实验来验证其可行性。
相关工作:构建有限时间安全势垒证书最常见的途径依赖于c-鞅的概念,它提供了不安全概率的上界;参见 Jagtap 等,2018,Santoyo 等,2021 以及 Steinhardt 和 Tedrake(2012)。然而,这种标准框架在某些情况下可能过于保守,且无法直接处理 reach-avoid 验证,因为它无法推导出 reach-avoid 概率的下界。我们的工作通过提出相较于现有方法更宽松的势垒证书构建条件来解决这些局限性。更根本地,我们建立了一个统一的动态规划框架用于势垒证书综合,它不仅涵盖安全性和 reach-avoid 规范,而且还能够扩展到更复杂的规范。在 Xue(2024a)中,作者提出了一种基于切换系统的有限时间 reach-avoid 势垒证书。与他们的方案相比,我们的公式实现了更简单的证书结构,并展示了更好的实验性能。我们还注意到,许多现有工作侧重于为随机系统中的无限时域 reach-avoid 规范构建势垒证书(Abate 等,2025,Anand 等,2022,Henzinger 等,2025,Meng 和 Liu,2024,Xue,2024b,Zikelic 等,2023)。相比之下,我们的工作考虑有限时间验证,这需要不同的分析工具。
最后,我们要澄清的是,我们的工作并非首次尝试将势垒证书与动态规划技术联系起来。例如,在 Laurenti 和 Lahijanian(2024)以及 Steinhardt 和 Tedrake(2012)中,作者也通过证明其条件为动态规划计算的不安全概率提供上界来推导安全势垒证书。与这些势垒证书相比,我们的证书更为通用,且通过固定一个参数可以退化为它们的特例。此外,这些工作主要重新证明了也可以从超鞅等其他视角推导出的势垒证书结果。相比之下,通过深入探索势垒证书与动态规划之间的联系,我们识别了现有方法在不安全区域上的保守性,并通过提出一种新的安全势垒证书来解决这一问题。
本文其余部分组织如下。我们在第 2 节中介绍必要的预备知识,并在第 3 节中正式陈述问题。接下来,在第 4 节中,我们从动态规划的角度重新审视现有的基于鞅的安全势垒证书。基于这一新视角,第 5 节介绍了一种具有放宽约束的新型势垒证书用于安全验证,并讨论其在 reach-avoid 规范上的扩展。第 6 节展示了如何利用和式平方规划来综合所提出的势垒证书。最后,我们在第 7 节中通过三个案例研究来展示我们的方法,并在第 8 节中总结全文。
预备知识
符号:我们用 ? 和 ?≥0 分别表示所有实数的集合和所有非负实数的集合。给定一个 Borel 空间 A,?(A) 和 ??(A) 分别表示 A 的 Borel σ-代数以及 A 上所有 Borel 概率测度的集合。转移核是一个映射 t: A × ?(A) → [0,1],使得对任意 a ∈ A,t(a, ·): ?(A) → [0,1] 是 Borel 概率测度,且对任意 B ∈ ?(A),t(·, B): A → [0,1] 是可测的。概率测度 t(a, ·) 也记作 t(·|a)。
问题形式化
在本工作中,我们考虑离散时间随机系统的安全和 reach-avoid 规范的概率验证。具体而言,给定一个自治随机动态系统,我们的目标是确定安全概率(或 reach-avoid 概率)是否高于所需的阈值。该问题正式陈述如下。
问题 1 给定一个自治离散时间随机动力系统 S=(X, X0, W, μ, f, T),安全区域 S∈?(X),目标区域 G∈?(X),以及期望界限 0≤ε≤1,验证是否满足安全概率或 reach-avoid 概率的界限要求。
从动态规划角度重新审视现有的安全势垒证书
由于动态规划的高复杂性,显式计算安全概率通常是一项计算挑战性的任务。为了缓解这种可扩展性挑战并更高效地计算安全概率,势垒证书的概念在文献中被广泛用于安全验证。势垒证书提供了安全概率的下界,因此无需穷举搜索即可实现高效的安全验证。
受动态规划启发的势垒证书构建
基于上述关于现有势垒证书与动态规划技术之间新见解的讨论,在本节中,我们为安全规范提出了一组放宽了现有条件的新型势垒证书条件。此外,我们通过开发一种新的用于 reach-avoid 概率验证的势垒证书,将我们的方法扩展到 reach-avoid 规范的情况。
通过和式平方规划计算势垒证书
到目前为止,我们提出了两种势垒证书:一种用于安全规范,通过移除现有方法的参数条件并仅添加单一条件;另一种用于 reach-avoid 规范,采用类似的构建方式。在本节中,我们将所提出的 DSBC(动态规划安全势垒证书)和 RABC(reach-avoid 势垒证书)的搜索表述为和式平方(SOS)规划(Prajna 等,2002,Sturm,1999)。值得注意的是,SOS 方法本身是一个成熟的、标准的计算工具。
案例研究
在本节中,我们首先使用两个取自 Xue(2024a)的示例将所提出的新型势垒证书与现有方法进行比较。然后,我们进一步验证了我们的方法在高维系统中的可行性。
结论
在本工作中,我们重新审视了使用势垒证书的随机动力系统形式化验证问题。我们首先从动态规划的角度为现有的用于安全规范的基于鞅的势垒证书提供了一种替代证明。基于这一新视角,我们进一步提出了一种新型的势垒证书,它不仅统一了现有的势垒证书,还提供了更宽松的约束。我们表明这样的构建也可以……
余陈于1999年出生于中国广东。他于2022年获得上海交通大学学士学位。他目前在上海交通大学自动化与智能感知学院攻读博士学位。他的研究兴趣位于形式化方法、控制理论、优化和机器人的交叉领域。他的研究专注于开发用于自主系统的可靠控制和规划方法,以在不确定性下完成复杂任务。
Yu Chen | Shaoyuan Li | Xiang Yin
生物通微信公众号
生物通新浪微博
今日动态 |
人才市场 |
新技术专栏 |
中国科学人 |
云展台 |
BioHot |
云讲堂直播 |
会展中心 |
特价专栏 |
技术快讯 |
免费试用
版权所有 生物通
Copyright© eBiotrade.com, All Rights Reserved
联系信箱:
粤ICP备09063491号