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

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

PBC1. ∀x ∈ X u , B(x) > 0 ;
∂B
∀x ∈ X, λ ∈ R 为一个固定的常数;
PBC2. (x) f(x)+λB(x) ⩽ 0, 其中
∂x
PBC3. 在置信度至少为 1−β 的条件下, P({x ∈ X 0 | B(x) ⩽ 0}) ⩾ 1−ε .
B(x) 满足 X 0 出发的状态在连续演化过
若函数 PBC1–PBC3, 则在至少 1−β 的置信度下, 可以说明从初始区域
程中不会进入非安全区域的概率至少为 1−ε . PAC 学习框架定义了一个学习算法可以产生 PAC 障碍证书的概
ε , 并且安全需求阈值参数可以通过训练数据的规模来控制. 相较
率, 即其安全需求阈值参数小于某个给定的阈值
于传统的穷尽搜索或确定性方法, 该方法能够更高效地计算出具有一定置信度的概率障碍证书, 从而减少计算的
复杂性. PAC 障碍证书满足以下定理.
定理 4. 若 B : R → R 是关于 ε ∈ (0,1) 和 β ∈ (0,1) 的 PAC 障碍证书, 则连续动力系统 C = ( f,X 0 ,Ω,X) 在至少
n
1−β 的置信度下, 满足安全性质的概率大于等于 1−ε .
对于 PAC 障碍证书的求解, 可以将问题转化为在初始区域上通过场景优化方法求解的优化问题. 给定一个连
n λ c 为障碍证
续动力系统 C = ( f,X 0 ,Ω,X) 和相应的非安全区域 X u ⊆ X , 存在一个函数 B(x,c) : R → R 和一个常数 ,
书中每一项的系数, B(x,c) 是关于安全需求阈值参数 ε ∈ (0,1) 和置信度水平参数 β ∈ (0,1) 的 PAC 障碍证书, 如果
满足以下约束条件:

∫


 min B(x,c)dx


 c

 X 0


  ∧

 (i) (i)
  B(x ,c) ⩽ 0,
  x ∈ X 0
 
 

 i=1,2,...,K (5)
 
 


 
 s.t. B(x,c) > 0,

 ∀x ∈ X u
 
 
 
 
 ∂B


 
  (x,c) f(x)+λB(x,c) ⩽ 0, ∀x ∈ X
 
∂x
B(x,c) ⩽ 0 , 即一组状态
通过最小化 B(x,c) 在初始区域上的积分使得从初始区域出发的状态尽可能多地满足
X u .
使得轨迹永远不会进入非安全区域
[5]
定理 5 . 若上述优化问题可行并且存在唯一的最优解 c , 给定安全需求阈值参数 ε ∈ (0,1) 和置信度水平参数
∗
β ∈ (0,1) 的条件下, 随机采样数 K 满足:

( )
2 1
K ⩾ ln +m ,
ε β
其中, m 为优化变量的个数. 则在至少 1−β 的置信度下 P({x ∈ X 0 | B(x) ⩽ 0}) ⩾ 1−ε , 即动力系统 C = ( f,X 0 ,Ω,X) 满
足安全性质的概率至少为 1−ε .

4 组合式概率障碍证书生成方法
本节通过使用场景优化方法和基于微分中值定理的区间线性化方法将 PAC 障碍证书的求解问题转化为基于
大 M 法的混合整数规划问题, 并且提出通过反例制导方法生成一组组合式的 PAC 障碍证书来验证动力系统的概
率安全性.

4.1 基于大 M 法的混合整数规划方法
在约束条件 (5) 中, 通过场景优化方法从初始区域 X 0 中随机采样 K 个样本点, 然而, 这些样本点并不一定能
够全部满足约束条件. 为了确保能够得到一个 PAC 障碍证书, 引入常量 M 作为罚因子, 将优化问题 (5) 转化为一
个混合整数规划问题. 希望不满足约束条件的样本点的数量尽可能少, 即使在某些样本点为反例点的情况下, 依然
∑
α
能够得到优化问题的解. 本文选择障碍证书模板 B(x,c) = c α x . 具体地, 通过引入一个很大的正常数 M 和 K
α∈M
(i)
个二进制变量 y ∈ {0,1},i = 1,2,...,K 来调整原始约束条件 (5). 给定一个连续动力系统 C = ( f,X 0 ,Ω,X) 和相应的
n β 给定
非安全区域 X u ⊆ X , 存在一个函数 B(x,c) : R → R 和一个常数 λ , 在安全需求阈值参数 ε 和置信度水平参数
的情况下, 通过求解以下优化问题来计算 B(x,c) :