Page 175 - 《软件学报》2021年第11期

陈子璇 等:一种基于广义异步值迭代的规划网络模型 3501

曼误差为该状态在这轮值迭代前后状态值之差的绝对值,即在一个 MDP 模型已知的环境中,经过第 n 轮值迭代
之后,状态 s 的贝尔曼误差 BE n (s)为
( , ) | |a =
BE n ( ) |s = Vs − n ( ) max [ ( , )R s a + γ ∑ s′ Tr ′ ( | , ) ( )]| |s s a Vs′ n = Vs − n ( ) max Qs V n be ( )s − V n af ( ) |s (5)
n
a
a
其中,V n be ( )s 表示状态 s 在第 n 轮值迭代之前的状态值,V n af 表示状态 s 经过了第 n 轮值迭代之后的状态值.
因此,对于 GAVIN 中节点优先级的第 1 种定义方式,在第 n 轮异步值迭代中,当前节点 s 的优先级 I n (s)为
I n (s)=BE n (s) (6)
上述优先级的定义形式基于如下观察:在两轮值迭代之间,有一些节点的状态值会发生显著的变化,因此与
这些节点相连接的节点的状态值同样也可能会发生较大的变化.这就意味着:随着值迭代过程的进行,节点的状
态值的显著变化会给整个状态空间上与其相连通的节点的状态值带来不同程度的影响.根据贝尔曼误差的定
义,节点的状态值的变化越大,贝尔曼误差也就越大,即表明节点的贝尔曼误差可被用于定义优先级——对于那
些有着更大贝尔曼误差的节点,在值更新过程中,应赋予它们更高的优先级来优先更新它们的状态值.
第 2 种定义与第 1 种定义略微不同,第 2 种形式中使用转移概率和贝尔曼误差的乘积来定义优先级.对于
这种定义方式,在第 n 轮异步值迭代过程中,当前节点 s 的优先级 I n (s)为
I n (s)=TBE n (s)=Tr(s|s′,a′)⋅BE n (s′) (7)
其中,TBE n (s)表示第 n 轮异步值迭代过程中,节点 s 上转移概率与贝尔曼误差的乘积.s′是当前节点 s 的前继节点
(predecessor node),即能与当前节点之间发生状态转移的节点.s 是节点 s′经过第 n 轮异步值迭代之后能转移到
的节点,Tr(s|s′,a′)是智能体在节点 s′执行动作 a′转移到节点 s 的概率.由于在公式(7)的定义中考虑的是两个节点
之间转移概率的数值大小而非图形中节点的组成结构,因此利用 Tr(s|s′,a′)而非 P s′,s 来表示节点 s′到节点 s 的转
移概率.由于非规则图形的结构特性,相互之间能发生状态转移的节点必是相连的节点,所以只要 Tr(s|s′,a′)≠0,s′
必为 s 的前继节点.
第 1 种优先级定义方式中并没有考虑当前节点与其前继节点之间的转移模型,而在第 2 种定义方式中,为
了能更为突出节点之间的连接性,我们引入了“转移”的概念.第 2 种定义方式的主要思想与第 1 种定义方式的思
想类似,具体为:若状态空间中某些节点(如节点 s′)的状态值在值迭代前后的变化越大,那么那些能与其发生状
态转移的节点(如节点 s)的状态值发生的变化也会越大.这就意味着:随着迭代过程的执行,节点 s 的状态值的变
化会对与其之间有着较大转移概率 Tr(s|s′,a′)的前继节点 s′的状态值带来较大的影响.因此,在值更新过程中,应
该赋予这些节点 s 较高的优先级来优先更新它们的状态值.在 GAVIN 中,无论是利用第 1 种方式还是第 2 种方
式来定义节点的优先级,只要节点的状态值随着迭代的进行发生了变化,那么该节点的优先级也会随之改变.
在定义了节点的优先级之后,就可根据优先级来选择每轮异步值迭代中要进行值更新的节点.为了能合理
地选择节点,本文根据各节点的优先级定义了一个阈值,并在每轮迭代开始前选择那些优先级大于阈值的节点

进行更新.本文使用所有节点贝尔曼误差的平均值作为阈值,也就是说,第 n 轮异步值迭代过程开始前,阈值 T n
的定义为
1
T = ∑ I n () s (8)
n
|| ν s ν∈
其中,ν表示一张非规则图形的整个节点空间,s 表示图中的任一节点,|ν|表示图中的节点总数.
由公式(8)可知,该阈值在不同轮次的异步值迭代中的大小也会不同.这就使得在每轮异步值迭代中,所选节
点的个数会根据当前环境自适应地变化.此外,使用所有节点贝尔曼误差的平均值作为阈值,能够使得那些具有
相对较高优先级(如优先级高于 T n )的节点与那些具有相对较低优先级(如优先级低于 T n )的节点更具区分性.
根据节点的优先级和阈值,选择第 n 轮异步值迭代过程中要进行值更新的节点的过程可形式化为
S = f ν T n (9)
E
(; )
ν
n
E
其中,f ν 为节点选择函数, S 表示被选择出来以执行值更新的节点集合.在选择好要进行值更新的节点后,即可
n
执行 GAVIN 中的异步值迭代过程.GAVIN 中的第 n 轮异步值迭代的过程可被形式化为
Q ()a 1 (S n E ) = ( )a (S n E )( + P R γV n ) (10)
n+