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

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

large. This work applies the idea of asynchronous update to further study GVIN. By defining the priority of each state and performing
asynchronous VI, a planning network is proposed, it is called generalized asynchronous value iteration network (GAVIN). In unknown
tasks with irregular graph structure, compared with GVIN, GAVIN has a more efficient and effective planning process. Furthermore, this
work improves the reinforcement learning algorithm and the graph convolutional operator in GVIN, and their effectiveness are verified by
path planning experiments in irregular graphs and real maps.
Key words: deep learning; reinforcement learning; imitation learning; planning; asynchronous update

近几年,随着深度学习在人工智能领域的流行,神经网络模型已被广泛应用于强化学习(reinforcement
learning,简称 RL)和模仿学习(imitation learning,简称 IL)等机器学习任务中,并取得了很多成果 [1−8] .在这些任务
的解决方案中,策略通常用神经网络来表示.然而,由于网络中缺少明确的规划模块和相应的规划运算,这种网
[9]
络形式的策略本质上是反应式的 .由于反应式策略无法理解动作的目标导向性,因此采用这种策略的智能体
(agent)通常只能学会解决在训练集中出现过的任务,而较难泛化到解决其训练集之外的未知任务 [10] ,从而在实
际应用中会遇到很大的挑战.
为了解决这个挑战,Tamar 等人 [10] 提出了一种嵌有值迭代模块的可微的规划网络——值迭代网络(value
iteration network,简称 VIN).该网络可利用 IL 或 RL 算法进行端到端的训练,使得网络在未知任务中能执行规划
运算,从而生成具有较好泛化能力的策略.VIN 中,值迭代模块的关键创新之处在于:它以一种堆叠式的卷积神经
[9]
网络 来模拟值迭代过程 [11] ,使得智能体可以顺利学习到当前任务中的动态信息,进而利用规划方法得到有效
的且具有泛化能力的策略.然而,由于其值迭代模块中的卷积算子在内部结构上具有局限性,目前 VIN 的应用领
域仅限于具有规则结构的任务,即内部构成为一维顺序结构或是二维栅格结构的任务.在自动驾驶汽车的路径
规划、网页中信息采集/导航等内部构成为非规则结构的任务中,智能体会无法准确地学习到非规则环境的动
态信息,从而无法进行有效的规划.因此,Niu 等人 [12] 提出了一种基于 VIN 的广义值迭代网络(generalized value
iteration network,简称 GVIN)来消除这种局限性.GVIN 通过两个方面改进了 VIN:(1) 它利用一种适用于非规则
图形的图形卷积算子来近似表示状态转移矩阵,以模拟值迭代过程.该卷积算子泛化了 VIN 中所使用的二维图
形卷积算子,使得其能够不受规则图形结构的限制,从而作用于具有非规则结构的任务中.(2) 它提出了一种 n
步 Q 学习算法 [13] 的改进算法——情节式 Q 学习算法(episodic Q-learning),使得规划网络在利用 RL 算法训练时
的稳定性有了进一步的提升.由于 GVIN 成功地将 VIN 的应用范围扩大至具有非规则图形结构的任务中,所以
称它为“广义的(generalized)”.
然而,VIN 和 GVIN 中均存在着一个相同的问题——这两个网络中所模拟的值迭代过程均为同步执行的,
即无论每个状态的重要性如何,整个状态空间中所有状态的值函数在每一轮值迭代过程中都会被更新.这意味
着网络并没有根据状态的重要性来合理分配每个状态所需的规划时间,那么当状态空间较大时,规划过程可能
会长时间陷入无意义的值更新中,导致网络整体规划性能的下降 [14] .
基于这两个规划网络中应用范围更为广泛的 GVIN 模型,本文提出了一种改进的异步规划网络模型,即广
义异步值迭代网络(generalized asynchronous value iteration network,简称 GAVIN).为了实现 GAVIN,本文依据异
步更新 [15,16] 的思想,提出了一种适用于 GVIN 的异步更新方法——基于状态的异步更新方法,并将其进一步地
应用于 GVIN 的值迭代过程中.该方法的主要思想是:在每轮值迭代过程开始之前,为状态空间上的每个状态定
义其优先级,其后根据状态优先级来异步更新状态值,即使得状态空间上某些状态处的值被更新之前,那些在规
划过程中相对更为重要的状态的值已被多次更新,从而合理地分配规划过程中智能体在每个状态上所需的规
划时间.需要指出的是:文献[15,16]中所提出的异步更新方法仅适用于具有规则结构的规划任务,而基于状态的
异步更新方法不仅适用于具有规则结构的任务,还能更好地应用于求解具有非规则结构的任务.此外,GAVIN 中
的异步更新过程会根据当前环境的变化来自适应地选择需要更新的状态集合,且该集合的大小并非为固定值,
这也与文献[15,16]中的方法有所不同.
与 GVIN 相同,GAVIN 使得智能体能够在具有非规则图形结构的未知任务中自我学习环境的动态信息并
规划出最优策略.此外,通过使用基于状态的异步更新方法,GAVIN 有效地解决了原网络模型规划过程中存在的