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

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

τ 中 (第 7–9 τ 是空集, 表示
¯ U 2 两块, 其中一块包含
¯ U 2 加入临时集合
¯ U 1 和
¯ U 1 和
分割成 ¯ u 中所有反例点, 将 行). 若
现在没有待求解的初始区域的划分块, 返回的 CPBC 即为一组 PAC 障碍证书 (第 10、11 行). 否则, 将 i 自增, τ 赋
值给 π (i) (第 12–14 行), 然后对 π (i) 中每个划分块进行新一轮的遍历. 若 i 的值为 100, 则停止循环, 表示无法证明在
至少 1−β 的置信度下, 该系统在至少 1−ε 的概率下满足安全性质.
算法 1. 组合式 PAC 障碍证书生成算法 CPBC.
(i)
,
输入: 连续动力系统 C = ( f,X 0 ,Ω,X) , 非安全集 X u , 安全需求阈值参数 ε , 置信度水平参数 β , 大数 M π = {X 0 } ,
( )
2 1
τ = {} CPBC = {} i = 1 L = 100 K ⩾ ln +m+1 ;
,
,
,
,
ε β
输出: 一组 PAC 障碍证书 CPBC.
1. while i < L do
2. for π (i) 中每一个划分块 ¯ U
3. 采样 ¯ U 中 K 个点得到样本点集 ¯ u
4. 通过基于大 M 法的混合整数规划方法计算 PAC 障碍证书 B
5. if ¯ u 中每个样本点 x 都满足 B(x) ⩽ 0
B 加入 CPBC
6. 将
7. else
8. 将 ¯ U 划分为 ¯ U 1 和 ¯ U 2 , 分别包含 ¯ u 中所有反例点和非反例点
¯ τ
9. 将 ¯ U 1 U 2 加入
,
τ 是空集
10. if
11. return CPBC
12. else
13. i = i+1
(i)
14. π = τ

5.2 用例展示
本节通过一个具体的三维例子来展示在给定一个连续动力系统 C = ( f,X 0 ,Ω,X) 和相应的非安全区域 X u ⊆ X
的情况下, 如何得到该系统的组合式 PAC 障碍证书.
例 3 [37] : 给定一个连续动力系统

   
 ˙x 1   − x 2 
   
   
   
   ,

 ˙x 2  =  − x 3
   
   
   3 
˙ x 3 −x 1 −2x 2 − x 3 + x 1
3 X 0 = {x ∈ R : 0 ⩽ x 1 , x 2 , x 3 ⩽ 1} , 非安全区域为
3
已知系统的状态空间为 X = {x ∈ R : −2 ⩽ x 1 , x 2 , x 3 ⩽ 2} , 初始区域为
X u = {x ∈ R : 1.5 ⩽ x 1 ⩽ 2,0 ⩽ x 2 , x 3 ⩽ 1} Ω 为均匀分布.
3
,
B(x,c) = c 0 +c 1 x 1 +c 2 x 2 +c 3 x 3 , 由命题 1 i = 0,1,2,3 . 设置安全需求阈值参数
设置障碍证书 可知 c i = c i1 −c i2 ,
4
ε = 0.1 , 置信度水平参数 β = 10 −12 , 大数 M = 10 . 由定理 6 可知从初始区域中随机采样的样本数 K ⩾ 732.624 , 取
(i)
,
K = 733 y ∈ {0,1} 为二进制变量, i = 1,2,...,K .
在 X 0 上有线性不等式约束:

∧
(i)
(i)
(i)
B(x ,c)− My ⩽ 0, x ∈ X 0 .
i=1,2,...,K
X u 上通过定理 2 B(x)−ς ⩾ 0 区间化得:
在 将不等式

c 0 +1.75c 1 +0.5c 2 +0.5c 3 +c 1 [−0.25,0.25]+c 2 [−0.5,0.5]+c 3 [−0.5,0.5]−ς ⩾ 0.