Page 225 - 《软件学报》2025年第8期

3648 软件学报 2025 年第 36 卷第 8 期

式既能保证抽象动作在仿真真实系统行为时高度接近, 又能避免由于错误选择粒度而导致模型不稳定和预测误
差. 这一原则对于使用抽象 MDP 模型解决实际问题尤其重要, 在需要进行准确控制和决策的复杂系统中具有重
要理论价值和实践意义.

4.3 构建场景的抽象 MDP
本节重点讨论在随机环境中构建该场景的马尔可夫决策过程 [29] , 图 6 展示了该方法的具体步骤.

动作 A=(a 0 , a 1 , a 2 ,..., a n−1 ) ਫ਼ࣥ Traces=(s 0 , a 0 , s 1 , a 1 ,..., s n ) ሑ෿ S=(s 0 , s 1 , s 2 ,..., s n )

基于因果语义的特征区间化抽象
y 构建抽象迁移空间
基于区间盒的动作抽象
S I =(s 0 I , s 1 I , s 2 I ,..., s n I )
x 基于时空语义的 (ε,d)-抽象
a 1 0.7
s 0 s 1
1
a 2
0.3
抽象动作 A=(a 0 , a 1 , a 2 ,..., a n−1 ) 0.9 0.1 抽象状态 S=(s 0 , s 1 , s 2 ,..., s n )
1 s 2 1
s 3
抽象 MDP
图 6 抽象 MDP 的构建过程示意图

抽象主要包括 3 个步骤: 基于因果时空语义的状态抽象、基于区间盒的动作抽象以及迁移空间构建. 通过运
用算法 1 和算法 2, 状态抽象对状态空间进行压缩, 以捕捉其关键特征. 根据第 4.2 节内容, 动作抽象将真实世界中
的连续多样的动作离散化为不同区间, 每个区间代表一组相似的动作. 本节将描述迁移空间的构建过程.
ˆ T : ˆ S × ˆ A → ˆ S , 抽象迁移空间是一组具体状态之
使用抽象状态空间 ˆ S 和抽象动作空间 ˆ A, 构建抽象迁移空间
′ ′ ˆ s ˆ s 之
′
间实际迁移的集合. 特别地, 如果存在具体状态 s ∈ ˆs 和 s ∈ ˆs 之间的实际迁移, 则相应地建立起抽象状态 和
′
′ ˆ s 是抽象状态. 抽象迁移共享相同的起始状态和目标状态, 通过迁
ˆ s
间的抽象迁移, 其中 s 和 s 是具体状态, 而 和
ˆ s
′
移概率函数来表示抽象模型. 具体而言, η(ˆs,ˆa,ˆs ) 表示在当前状态 和当前动作 的条件下访问 ˆ s 的概率, 且
ˆ a
′
∑
η(ˆs,ˆa,ˆs ) = 1. 迁移概率定义如下:
′

ˆ s ′ ∈ ˆ S
{ }

′ ′
(ˆs,ˆa,ˆs ) ∈ ˆ T|ˆs ∈ ˆ S ,ˆa ∈ ˆ A,ˆs ∈ ˆ S
′
η(ˆs,ˆa,ˆs ) = { (10)
}

(ˆs,ˆa,_) ∈ ˆ T|ˆs ∈ ˆ S ,ˆa ∈ ˆ A
ˆ s 的具体迁移数量除以从抽象状态 出发
¯ s
′
换言之, 迁移概率是通过从抽象状态 ¯ s 经过执行动作 ˆ a 到抽象状态
的所有实际迁移数量来计算的.
迁移过程如算法 3 所示, 首先初始化抽象迁移空间 ˆ T 为 0, 并设置一个布尔变量 refined 为假, 表示迁移空间的
构建尚未完成. 随后, 算法进入一个循环过程, 持续对迁移概率进行估计和验证, 直到满足精确度要求. 在每一次循
环中, 算法遍历所有抽象状态和动作的组合 ( ˆ s, ˆa), 对于每一组合, 则进一步遍历所有可能的目标抽象状态 , 并根
ˆ s 0
据公式 (10) 计算它们之间的迁移概率 ˆ p. 这一计算步骤是基于预定义的迁移事件集合 ˆ T 和当前的抽象状态与动作
来执行的. 接着, 再利用霍夫丁不等式计算当前迁移概率估计误差 error 的同时与预设偏差阈值 ε 进行比较. 如果
得到误差小于阈值 ε 的结果, 则说明当前迁移概率估计已足够准确, 并将该迁移概率及其相应状态和动作组合添
ˆ T , 并将 标记为真以指示达到了所需精确度水平. 当所有抽象状态和动作组合均经过上
加至抽象迁移空间 refined
述检验与添加操作, 并无更多组合需要进一步优化时, 循环结束并输出所构建抽象迁移空间.
算法 3. 迁移空间构建算法.
ˆ T ε;
输入: 抽象状态集合 ˆ S , 抽象动作集合 ˆ A, 迁移事件集合 , 偏差阈值