Page 15 - 《软件学报》2025年第5期

杨紫萱 等: 基于 PAC 学习的组合式概率障碍证书生成 1915

E(−0.063,−0.974) . 将
个反例点 A(−0.112,−0.993) 、 B(−0.104,−0.928) 、 C(−0.072,−0.922) 、 D(−0.009,−0.963) 、
初始区域划分为上半部分 X 1 和下半部分 X 2 两个区域, 其中 X 2 包含所有反例点. 从 X 1 中随机采样 K 个点, 学习 PAC
B 1 = −8.907+7.287x 1 −10.998x 2 , 如图 K 个点, 学习 PAC 障
障碍证书 1 (b) 中的黑色直线所示. 从 X 2 中随机采样
B 2 = −0.099+3.666x 1 +1.573x 2 , 如图 1 (b) 中的蓝色直线所示.
碍证书

Barrier border Barrier border
2.5 2.5
2.0 2.0
1.5 1.5
1.0 1.0
0.5 0.5
x 2 0 x 2 0
−0.5 −0.5
−1.0 −1.0
−1.5 −1.5
−2.0 −2.0
−2.5 −2.5
−2.5 −2.0 −1.5 −1.0 −0.5 0 0.5 1.0 1.5 2.0 2.5 −2.5 −2.0 −1.5 −1.0 −0.5 0 0.5 1.0 1.5 2.0 2.5
x 1 x 1
(a) 单个障碍证书 (b) 组合式障碍证书
图 1 组合式障碍证书效果图

B 2 (x) ⩽ 0 , 分别可以说明在
将 X 1 和 X 2 中的采样点分别代入 B 1 和 B 2 验证可知满足原始约束条件 B 1 (x) ⩽ 0 和
至少 1−10 −12 的置信度下, 从 X 1 出发的状态在连续演化过程中满足安全性质的概率至少为 0.9, 从 X 2 出发的状态
在连续演化过程中满足安全性质的概率至少为 0.9. B 1 和 B 2 一起将初始区域 X 0 与非安全区域 X u 分隔开. 因此可

以表明在至少 1−10 −12 的置信度条件下, 该动力系统满足安全性的概率至少为 0.9. B 1 和 B 2 称为该系统的一组
PAC 障碍证书, 共同验证系统的概率安全性.
基于以上例子所带来的启发, 本文提出学习一组组合式 PAC 障碍证书的方法, 以解决样本点中可能存在反例
点的问题.
定义 5 (组合式 PAC 障碍证书). 给定一个连续动力系统 C = ( f,X 0 ,Ω,X) 和相应的非安全区域 X u ⊆ X , 若
β ∈ (0,1) 的一组组合式 PAC 障碍证书, 则需满
B 1 ,B 2 ,...,B n 是关于安全需求阈值参数 ε ∈ (0,1) 和置信度水平参数
足下述条件:
CPBC1. ∀x ∈ X u ,B i (x) > 0, i = 1,2,...,n ;
∂B i
∀x ∈ X, λ ∈ R 为一个固定的常数;
CPBC2. (x) f(x)+λB i (x) ⩽ 0, i = 1,2,...,n, 其中
∂x
(j)
(1)
(2)
,
CPBC3. ∀x , x ,..., x (K) ∈ X i , ∧ B i (x ) ⩽ 0 i = 1,...,n 为真, 其中 {X 1 ,...,X n } 是 X 0 的划分, K 是从子块 X i
i i i i
j=1,2,...K
中随机采样的样本数且满足公式 (8).
对于所得到的一组组合式 PAC 障碍证书 B 1 ,B 2 ,...,B n , 只需每个 X i 中 K 个样本点对于 B i ,i = 1,2,...,n 都有能
满足的安全性质. 由于样本数由安全需求阈值参数 ε ∈ (0,1) 和置信度水平参数 β ∈ (0,1) 决定, 并且对于每个 PAC
1−ε . 组合式 PAC 障碍证书的安全概率由以下定理可得.
障碍证书所学习的样本点不同, 因此系统的安全概率为
定理 7 (组合式 PAC 障碍证书概率安全性). 假设 B 1 ,B 2 ,...,B n 为一组组合式 PAC 障碍证书, 满足 CPBC1–3,
则在至少 1−β 的置信度下, 可以说明系统 C = ( f,X 0 ,Ω,X) 在至少 1−ε 的概率下满足安全性质.
如图 2 所示为组合式 PAC 障碍证书的构造框架, 具体流程如下.
(1) X 0 的一个划分; 组合式 PAC i = 1 L = 100 .
(1) 令 π = {X 0 } 是初始区域 障碍证书集合 CPBC = {}; ;
(i) (i) (i) (i) K 个点, 并利用大 法分
(2) 对于 π = {X ,...,X } 中每个子块, n i 为当前 π 中包含的子块个数, 随机采样 M
1 n i
别计算相应子块的 PAC B ,...,B (i) .
(i)
障碍证书
1 n i
X (i) (i) j = 1,2,...,n i , 若均满足则
(3) 令 T = {}; 分别对每个子块 j 中的 K 个样本点检验是否满足条件 B (x) ⩽ 0 ,
j