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

3498 Journal of Software 软件学报 Vol.32, No.11, November 2021

规划时间分配不合理的问题,进一步避免了无意义的值更新过程,提高了其在具有非规则结构的任务中的规划
效率及泛化能力.这个改进的规划网络模型能为许多实际应用场景带来益处.例如:它可被应用于自动驾驶领域
中,使得自动驾驶汽车在未知路况中的路径规划过程更为高效且有效.值得注意的是:GAVIN 中的规划算法与传
统的规划算法不同,如 Dijkstra 算法 [17] ,后者在规划过程中需要一个已知的环境模型,而前者旨在通过试错(trial-
and-error)或模仿专家样本的数据来学习一个广义的环境模型,使训练后的网络模型能应用于与训练任务不同
的任意未知任务中.其次,为了进一步提高规划网络中 RL 算法的训练性能,本文将加权双 Q 学习(weighted
double Q-learning) [18] 中所用的加权双估计器(weighted double estimator)思想与情节式 Q 学习相结合,提出了一
种新的 RL 训练算法——情节式加权双 Q 学习(episodic weighted double Q-learning).最后,本文提出一种新的定
义方法来小幅改进 GVIN 中所用的、由基于嵌入信息的核函数所定义的图形卷积算子 [12] ,使得利用这个改进后
的卷积算子的网络在规划过程中能够更为准确地学习到非规则图形的基本结构信息,从而获得更好的规划性
能及泛化能力.
本文的具体实验场景为智能体在非规则图形及真实路况地图中的路径规划问题.在真实路况地图环境中,
每个路口可被形式化为非规则图形中的节点,每条道路可被形式化为非规则图形中的边.在这些实验场景中,每
个节点都具有不同的局部结构,即每个节点所连接的节点数目不同且相连节点之间边的方向也不同.使用具有
非规则图形结构的实验环境验证了 GAVIN 的广义性.实验结果有力地验证了新方法的有效性.与 GVIN 相比,
在利用内部组成结构较为简单的非规则任务训练过后,GAVIN 所表示的策略能够在更复杂且更大规模的未知
测试任务中获得更好的泛化性能.具体地,本文分别利用美国明尼苏达州高速地图(Minnesota highway map)以
及纽约市区街道地图(New York city street map)的真实数据对新方法进行评估,实验结果有力地验证了 GAVIN
在大规模实际应用场景中的适用性和有效性.

1 基础知识及相关工作
本节对本文内容所涉及的基础知识及相关工作进行了介绍.第 1.1 节中介绍了马尔可夫决策过程,第 1.2 节
对 GVIN 模型进行了简要介绍,第 1.3 节介绍了相关的 RL 算法——情节式 Q 学习算法及加权双 Q 学习算法.
1.1 马尔可夫决策过程

许多序贯决策问题都可以用马尔可夫决策过程(Markov decision process,简称 MDP) [19] 来建模.MDP 可表示
为一个五元组(S,A,Tr,R,γ),其中,S 是状态空间,A 是动作空间,Tr(s′|s,a)是状态转换函数,R(s,a)是奖赏函数,γ∈(0,1)
是折扣因子.MDP 中的策略 π是指从状 态空间 S 到动作空间 A 的映射.在策略 π下 ,状态 s 的值为
(, )a = E
π
V π ()s = π [∑ ∞ γ t R ( , ) |s a s = E ]. s 在π下,状态-动作对(s,a)的值为 Qs π [∑ ∞ γ t R ( , ) |s a s = , s a = ] a .智
t= 0 t t 0 t= 0 t t 0 0
*
能体求解 MDP 的目标为:找到最优策略π ,以最大化其期望回报.当 MDP 模型已知时,最优策略可以通过值迭代
(, )a =
过程来获得.值迭代过程中包含两个子过程:V n+1 (s)=max a Q n (s,a), Qs R ( , )s a + γ ∑ Tr ′ ( | , ) ( ).s s a V s′ 通过这
n s′ n
*
*
*
两个过程,随着 n→∞,Q n 可渐近收敛到最优值 Q .由此可得最优策略π (s)=argmax a Q (s,a).
在 RL 问题中,智能体的目的是通过与环境交互,从环境给予的奖赏信号中学习到一个最优策略.即智能体
在未知的环境中,通过不断的试错来进行学习,以找到能够最大化期望累积奖赏的策略 [19] .
在 IL 问题中,智能体的学习过程有所不同,它不是从环境提供的奖赏信号中学习,而是从专家提供的演示数
据中学习.即智能体从一组专家样本中学习其要执行的策略.一般而言,每一个专家样本均包含了一种具体情况
的详细描述以及在这种情况下,智能体应采取的正确动作的规范(标签) [3,19] .
1.2 广义值迭代网络(GVIN)模型
GVIN 是一种嵌有规划模块的可微的规划网络模型,利用这个规划模块,GVIN 能够学习到非规则图形中的
环境动态信息,并利用这些信息进行规划,最终生成具有泛化能力的策略.图 1 为 GVIN 的整体网络结构示意图.
图中左上角为输入到网络进行训练的 8-节点的非规则图形 G.f R 为用于生成图形内部各节点奖赏信号的恒等函
数,该函数的输入信息为经过图形信号{0,1}编码后的非规则图形,其中,只有目标节点的信号值为 1,其他节点的