刘思嘉，童向荣

（烟台大学计算机与控制工程学院，山东烟台 264005）

0 引言

路径规划问题是人工智能领域热点问题，该问题涉及许多领域，包括：移动机器人导航、飞行器航迹规划、游戏自动导航以及车辆交通导航等。如今，城市交通路径规划在提升交通系统运行效率方面正发挥着越来越重要的作用。结合城市交通特点，可以总结出城市交通路径规划问题的规范化定义：将指定某一车辆作为智能体，目的是让智能体从规定范围内的状态找到一条从起始状态到目标状态的一条无障碍路径。其中如何提高路径规划算法的效率成为亟待解决的问题，路径规划算法使用高效的规划算法来为智能体车辆选择合理的导航路径，从而减少车辆在城市道路上运行的时间，提升城市道路的运行通畅度。

目前，路径规划问题已经得到许多学者的关注，有一些成功的研究成果，具体可以分为全局规划和局部规划。全局规划的算法包括A*算法［1］以及它的各种改进版本等，这些算法已经在离线静态环境中表现出优异的效果。对于动态环境，Yu 等［2］提出了一种在动态图中识别K-最短路径的分布式算法（KShortest Path in Dynamic Graph，KSP-DG），能够在动态道路网环境找到多条最短路径。但是这些算法过于依赖环境数据，需要在大量数据支持下才能完成路径规划，而且在未知环境下的效果较差，无法应用在环境变化的情况下。局部规划包括神经网络法［3］、遗传算法［4］以及强化学习算法等。其中强化学习算法由于无需环境的先验知识，已经得到了广泛的应用。

通过将强化学习算法应用到路径规划算法中，能够有效帮助车辆的行驶路径规划，同时对道路未来通行状态的变化加以考虑，从而能够进一步提高选路算法的合理性，对于缓解城市交通拥堵有着重要的现实意义。因此提出了一种在道路交通网环境下基于强化学习的车辆路径规划算法，采用将基于模型的算法和模型无关的算法相结合的Dyna 框架［5］可以提高规划的速度，同时较为经典的Sarsa 算法［5］作为选路策略可以提高算法的安全性。

与现有其他算法相比，基于强化学习的路径规划算法有如下特点：1）大部分的路径规划环境是未知的，需要算法建立到模型上再进行路径搜索，而模型无关算法可以在未知环境工作，算法具有自适应能力；2）一些路径规划算法能够找到最优路线，但是可能会经过较多的时间，这可能造成资源浪费，强化学习算法能够找到一条相对较快且较优的路线，同时提高路径规划的安全性；3）强化学习是一个不断尝试的过程，通过不断与环境交互来找到最优策略，这样产生的策略对于智能车来说一定是可以完成的，不会因为路径太复杂导致无法执行。仿真实验表明：相对于经典的路径规划算法，基于强化学习的路径规划算法能够真实地模拟智能车辆的实际行驶状态，有效减少环境中车辆行驶时间开销，提高城市交通运行效率。

1 相关工作

在解决路径规划问题的强化学习算法中，Q 学习（QLearning）算法［6］是较为常用的一种算法。乔俊飞等［7］把BP神经网络引入Q-学习算法中应用在移动机器人中，能够实现对未知环境的路径规划。Wang等［8］将Q-learning算法与Sarsa算法结合，提出了一种反向的Q-学习算法。Gosavi［9］提出了一种基于Q 学习和神经网络规划器的路径规划方法，实验证明了该方法在全局信息已知环境中的有效性。Sarsa 算法［5］是在Q-学习算法的基础上提出的一种模型无关的强化学习方法，基于Sarsa 的路径规划算法也得到了一定的研究。王军红等［11］提出了一种基于信用分配的Sarsa算法，引入信用分配的概念分配强化信号并修改动作选择策略，实验表明该算法可以解决动态环境下的路径规划问题。Sarsa 算法与其他方法结合也取得了一定的研究成果，例如k均值聚类算法（kmeans clustering algorithm，k-means）［12］、图搜索算法［13］及神经网络算法［14］等。这些文献中的算法能够完成路径规划的基本要求，但是收敛速度较慢，需要耗费大量的时间。

在1991 年，强化学习的先驱Sutton 等［5］提出了Dyna 框架，这个框架通过加入与模拟环境交互得到的经验，能够有效提升算法的收敛速度。Dyna 框架通常与Q-学习算法结合使用。朱美强［15］通过将流形学习中拉普拉斯特征映射方法与Dyna-Q 算法结合起来用于解决路径规划的问题，实验证明取得较好的结果。史豪斌等［16］提出一种基于Dyna-Q 的旋翼无人机视觉伺服智能控制方法调节伺服增益以提高其自适应性。但是，Q-学习算法存在一个问题是过于追求奖励最大化导致智能体在有障碍的地图中陷入危险次数过多。

2 理论基础

算法理论涉及经典的马尔可夫决策过程（Markov Decision Process，MDP），由四元组来描述，其中：

S代表着状态集合，指的是城市中的位置；

A代表智能体能够采取的动作集合，智能体汽车在栅格内可执行4个动作，分别为上、下、左、右；

P代表着状态转移概率矩阵，表示智能体汽车选择上下左右的概率；

R代表着奖励函数，智能体在模拟地图中移动时，未碰撞障碍物时奖励值为0，碰撞到障碍物时奖励值为-1，移动到目标点时奖励值为2。

马尔可夫决策过程为强化学习问题提供了基本的理论框架，现存环境中几乎所有的强化学习问题都可以使用MDP 去建模。

2.1 模型无关的强化学习算法

Sarsa 算法是一种使用时序差分求解强化学习控制问题的方法，与Q-学习算法相同，它采用Q-表的方式储存动作值函数，决策部分采用贪婪策略（epsilon-greedy）选择动作。Sarsa 算法属于在线学习算法，它会先执行动作再更新，其基本更新规则如式（1）所示：

其中：S为当前状态，A为当前状态选择的动作，S′为下一个状态，A′为下一个状态选择的动作，R为奖励值，γ为折扣因子，α为学习因子，Q为q值的集合。在仿真实验中，学习率α=0.01，折扣因子γ=0.9。

从更新函数可以看出，相较于Q-学习算法，Sarsa 算法是一种更为保守的算法，它更在乎每一步的决策，它对错误和陷阱更加敏感。在城市交通路径规划中，智能车对碰撞更加敏感，那么系统需要一个更加安全的算法来指导智能车的移动。Sarsa 算法是一个兼顾安全与速度的无模型强化学习算法，它更加符合城市交通环境，所以选择使用Sarsa算法作为基础算法指导智能体的路径规划。

2.2 基于Dyna框架的强化学习算法

在模型无关的强化学习算法中，智能体能使用从环境中产生的经验中直接学习到策略；而在基于模型的强化学习中，智能体使用模拟产生的模拟经验规划出新的策略；在Dyna框架中，智能体利用与环境交互产生的直接经验来学习一个模型，同时利用模型生成模拟经验，使用真实经验和模拟经验同时作用于智能体，帮助智能体去学习和规划出合适的策略。

Dyna框架如图1所示。

图1 Dyna框架Fig.1 Dyna framework

从图1 可以看出，Dyna 框架表示一个规划的过程。在智能体每次寻找路径过程中，Dyna 框架都会通过获得的模拟经验和完善模型来指导智能体的选择，这样可以使智能体在运行过程中不断地思考，更快地选择最优路径。相比其他算法，收敛速度有一定的优势。在城市交通路径规划中，将车辆作为智能体，车辆能够移动的位置作为状态空间，车辆选择的每个动作作为动作空间。在车辆选择到达目标位置的路径的过程中，车辆首先在状态空间中根据奖励函数的值选择下一个状态，同时在系统中构建关于环境的地图。车辆继续与真实环境交互获得直接经验，车辆也与构建的模型交互获得模拟经验帮助智能车提前规划路径。在两者共同作用下，车辆能够避免选择较差的路径，提升车辆路径规划的速度。

3 基于Dyna框架的Sarsa算法

Dyna 学习框架下可以与多种强化学习算法相结合。结合方式为使用基础算法与未知环境进行交互获取真实样本，再使用Dyna 框架对交互中建立的地图模型进行多次规划获取虚拟样本，最终使用真实样本与虚拟样本共同指导智能体的路径规划过程。基础算法选择的是Sarsa 算法。首先Sarsa算法是一种在线学习的算法，它会在状态转换的过程中学习，并且整个学习和行动过程只使用一个策略，同时使用两次ϵ-贪婪的方式选择出Q（S，A）和Q（S′，A′）。相对于其他算法，Sarsa 算法更加谨慎，与Dyna 学习框架的规划过程相结合，既保证了算法的安全性，又能提升算法的运行速度。

Dyna-Sa（Dyna-Sarsa）在城市交通环境的流程如图2所示。

图2 Dyna-Sa框架流程Fig.2 Flowchart of Dyna-Sa framework

3.1 Dyna-Sa算法

将Sarsa 算法与Dyna 框架结合，目的是将Dyna-Sa 算法应用到城市路径规划，具体如下：

研究的问题是单智能体路径规划，智能体为控制的车辆。在实现路径规划的过程中，智能体需要按照一些特定的规则寻找路径，这些特定的规则就是算法，Dyna-Sa 算法作为新规则应用到城市路径规划问题中。在城市路径规划中，随着车辆的运行，其所处的环境也在不断变化，这对于路径规划是很大挑战。Dyna 框架可以很好地解决这个问题，智能体既从模型中获得模拟经验，也从直接交互的环境中获得经验，两种经验能够为智能体选路提供指导，智能体可以快速找到一条安全的路径。

下面给出Dyna-Sa算法步骤：

1）初始化尝试要理解得到的模型Model（s，a）；

2）对于每一轮迭代，先根据当前状态和Q（S，A）用ϵ-贪婪的方式得到新状态S′和奖励R；

3）然后用Sarsa更新价值函数Q（S，A）；

4）用R，S′更新模型Model（s，a）（与真实环境交互完毕后，进行n次模拟）；

5）每次模拟都随机选择一个之前出现过的状态S，并在此基础上随机选择一个动作A；

6）基于模型Model（S，A）得到S′和R；

7）再使用Sarsa更新价值函数：

Q(S，A)=Q(S，A) +α(R+γQ(S′，A′) -Q(S，A))

Dyna-Sa算法基本流程中，外部循环过程直接利用数据经验去构建环境模型，从而更新值函数，内部循环过程使用构建模型去生成新的模拟经验，用来更新值函数，对较于简单的规划过程或者强化学习算法，Dyna-Sa算法呈现出更高的效率。

Dyna-Sa 是保证安全性的一种算法。它的安全性取决于基础算法和框架的配合。基础算法Sarsa 使用了广义策略迭代的思想，会使用下一步的状态S′和根据状态给出的动作A′的Q值来对目标值进行估计。这就会对目标值的选择更加敏感，对于奖励值低的状态，智能体就会选择远离。同时使用Dyna 框架进行不断地模拟运行，在运行过程中能够记录下有风险的行为，智能体能够避免这些路径而选择安全性更高的路径。

在速度方面，Dyna-Sa 使用了Dyna 框架，直接对环境进行建模，算法同时获得模拟经验和直接交互的经验，等同于智能体在未知环境中使用较少的时间尝试了更多的路径。相对于其他算法，能够帮助更快的智能体选择最优路径，最终有效提高了整个算法的收敛速度。

3.2 算法分析

目前，Dyna-Q 算法已经成功应用到一些模拟环境中，这些场景与城市交通环境有一些差异。首先讨论Sarsa 算法和Q-学习算法的不同点，以及选择Sarsa 算法应用到Dyna 框架中的原因。

这两种算法的差异主要体现在更新函数的不同，Sarsa 使用的是利用下次状态所采取的动作对应的Q值来更新Q值，Q-学习使用下次状态的最大Q值来更新。通过分析这两种更新方式，可以得到两种算法的特性：Sarsa 算法会探索更多的可能性，而Q-学习算法则会更倾向于选择最大可能性的选择。在学习效果方面，Q-学习算法具备学习到全局最优的能力，Sarsa 则相对差一些。收敛速度方面，Sarsa 与Q-学习算法有相似的效果。

城市道路复杂，车流量较大，当从车辆出发点到目标点进行路径规划时，需要考虑很多因素。其中一个重要因素是避开车辆拥堵路段，那么对于城市交通环境下的路径规划，最短的路径并不一定是最优的路径。Sarsa 算法和Q-学习算法都能在训练中选择远离拥堵路段的路径。同时需要考虑在车辆运行过程中，在规划路线中发生拥堵的情况。Sarsa 算法能够探索更多可能性，在规划路线路况发生变化时，能够做出较快改变，选择其他畅通路线。

强化学习算法需要在与环境的交互中通过学习策略来获得最大化回报或实现特定目标，与其他路径规划应用场景不同，城市交通路径规划的成本较高，在智能体汽车训练过程中，难免与障碍物发生碰撞。需要选择较为安全的路径规划算法。Sarsa 算法会选择更加保守的策略，在更新Q值的时候已经为未来规划好了动作，能够有效避免碰撞。在算法与框架结合过程中，存在算法不收敛和计算时间过长的情况。对于算法不收敛的情况，需要考虑到基础算法自身特点，与Q-学习算法相比，Sarsa 算法对低奖励值的状态更加敏感，在选择下一步动作时会规避风险，这是一个较为安全的行动策略，但在障碍物较为密集的情况下，智能体较低概率通过奖励值低的状态，导致在局部区域产生死循环，Dyna-Sa 算法无法收敛。通过调整系统参数来避免该情况，提高系统贪婪值使得智能体探索更多未知状态，降低盲目选择高奖励的概率，最终减少算法不收敛的情况。具体参数选择在仿真实验部分详细说明。

计算时间过长原因是规划次数选择不当。增加规划次数有利于增加虚拟经验，更好地帮助智能体选择路径。但过多规划会占用大量系统内存，路径规划目的是更快地选择一条安全的路径到达目标状态。规划次数过多影响系统整体运行速度，这与期望目标产生冲突。在经过多次仿真实验后得出：当规划次数为30 时，算法表现较优。在仿真实验中，由于建立的地图模型规模较小，所以规划次数选择较少的数值。随着模型复杂化，规划次数应当相应增加。

3.3 算法复杂度分析

强化学习算法复杂度与状态空间大小n和智能体训练次数m相关，在Dyna 框架模拟运行的次数可以认为在每次训练次数中，所以Dyna-Sa算法的时间复杂度为O（m（n-1））。

4 仿真实验

实验部分是将提出的算法和城市交通路径规划问题结合起来进行仿真实验，通过与其他几种经典的强化学习路径规划算法的实验结果进行对比，来验证该算法的性能。首先做出如下假设：不考虑智能车与障碍物边界碰撞问题以及交通信号灯等外在因素，仅将道路边界与拥堵车流作为障碍物。在本章中使用两个实验来证明提出算法的有效性。

4.1 仿真环境

本文代码的运行基于Intel Core i7-7700HQ CPU@2.80 GHz 的处理器、NVIDIA GeForce GTX1060 的显卡以及8 GB 内存的硬件环境，使用Windows 10 操作系统搭建软件环境，实验平台是PyCharm，编程语言是Python。

本实验验证算法的地图由栅格法建立。需要选择合适的栅格尺寸，为保证规划精度，同时确保智能体汽车的安全，将栅格尺寸设定为恰好与模拟智能车的外轮廓边长相同。地图中的障碍物固定生成，智能体汽车在栅格内可执行4 个动作，分别为上、下、左、右。

4.2 不同规划步数收敛速度对比

首先使用栅格建立一个的无障碍地图，智能体从初始状态到达目标状态。引入Dyna 框架的目的是将基于模型的强化学习和模型无关的强化学习结合起来。通过实验做出规划步数分别为0、5、50的步数变化曲线，如图3。其中图3中的N表示规划步数，横轴表示智能体的迭代次数，纵轴表示每次迭代智能体从初始状态到目标状态所需步数。

图3 不同规划步数收敛速度对比Fig.3 Convergence speed comparison of different planning steps

从实验结果可以看出：随着迭代次数的增加，圆形表示的规划步数为50 的情况收敛速度最快，矩形代表的规划步数为5 的情况次之，星形表示的无规划的情况最慢。最终可以得出结论：智能体使用模型产生的模拟经验越多，状态值函数的更新次数越多，那么它的步数收敛的速度越快。

4.3 模拟地图下的仿真

本章使用栅格构建一个模拟地图，地图尺寸为6×6，如图4～5 所示。其中左上角五角星表示智能车初始状态，右下角圆形表示目标状态，地图中间黑色矩形表示障碍物，白色区域为可移动区域。任务是找到一条路径将智能车从初始状态移动到目标状态。

图4 无障碍地图模型Fig.4 Map model without obstacle

图5 有障碍地图模型Fig.5 Map model with obstacles

4.4 仿真参数选择

使用Q-学习算法、Sarsa 算法和Dyna-Q 算法作为对比实验，与新算法进行比较。所有实验的相关参数如下：算法最大尝试回合设置为100，学习率α，折扣因子γ，贪婪值。其中的学习率、折扣因子和贪婪值需要通过运行实验调整参数获得，实验如下。

首先调整的是强化学习算法的学习率。学习率可以理解为算法的学习效率。当学习率较大时，算法的学习速度快，但是容易导致易损失值爆炸；当学习率较小时，算法的学习速度慢，同时会出现过拟合问题，算法的收敛速度变慢。由于仿真环境较为简单，所以不需要设置动态变化的学习率便可使算法实现最优效果。通过实验可以得到：当学习率小于0.01时，算法收敛速度过慢，影响算法性能；当学习率大于0.01时，梯度可能会在最小值附近来回震荡，甚至导致无法收敛；当学习率等于0.01 时，收敛速度最优，同时无其他副作用。算法的学习率设置为0.01。

然后调整折扣因子寻找最优性能。折扣率能够避免产生状态的无限循环，当折扣率较小时，智能体更加在意短期回报；当折扣率较大时，长期回报变得更重要。通过实验得出当折扣因子为0.9 时能够确保收敛的速度较快，同时不会导致不收敛的方差，更加适合仿真实验地图环境。

由于使用Sarsa算法作为基础算法，其采样的策略和指导的策略都是采用的贪婪策略，这就涉及贪婪值的选取问题。为此，最优贪婪值需要设计实验来获取，保证算法性能，其他参数在贪婪值变化的过程中保持不变。在实验过程中，贪婪度在（0，1）区间取值，一些经典文献将贪婪值划分成3 个区间，分别是（0，0.1］、（0.1，0.2］、（0.2，1）。将3 种不同贪婪度的Dyna-Sa 算法应用到有障碍地图中，进行100 次迭代训练，同时使用收敛速度和碰撞次数作为评价标准。最终可以得到如表1的结果。

从表1 中可以看出贪婪度处于（0.1，0.2］区间时，算法能够表现出最优性能。在贪婪度处于（0，0.1］区间时，算法会选择奖励值最大的状态，所以收敛速度较慢，同时碰撞次数较多，安全性较差。贪婪度处于（0.2，1）区间时，算法表现过于保守，智能体会在某个安全区域内停滞，导致算法无法收敛，同时碰撞次数较多。

最终将学习率设置为0.01，折扣因子设置为0.9，贪婪度值在仿真实验的有障碍地图设置为0.2，在无障碍地图中设置为0.1。

奖励R的设置如式（2）所示：

表1 不同贪婪度下的算法性能Tab.1 Algorithm performance under different greedinesses

仿真地图环境较简单，奖励R的取值对实验结果影响有限，所以选择简单的值便可实现算法功能。智能体在模拟地图中移动时，未碰撞障碍物时奖励值为0，碰撞到障碍物时奖励值为-1，移动到目标点时奖励值为2。

4.5 仿真实验结果及分析

按照前面的参数设置，将4 种算法分别引入地图中进行实验。每个算法进行100 次迭代训练，其中使用Dyna 框架的规划次数为30，就是将智能体与模拟环境进行30次交互来获得虚拟经验。每个算法实验重复10 次，然后取平均值作为实验输出数据。算法性能的评价标准为算法平均运行时间、平均碰撞障碍物次数、达到收敛所需回合和达到收敛所需时间。

无障碍地图和有障碍地图实验结果如表2～3所示。从表2～3中的数据可以看出，使用Dyna框架的算法的各项数据都要优于未使用框架的算法，这就体现了规划的高效性。在无障碍地图的实验中，Dyna-Q算法和Dyna-Sa算法性能相似。在有障碍地图的实验中，平均碰撞数、达到收敛回合和达到收敛时间方面，Dyna-Sa算法均要优于Dyna-Q算法，但在平均运行总时间方面，Dyna-Sa表现稍差。原因是Dyna-Sa算法是一种风险敏感算法，在学习初期，Dyna-Sa算法因躲避障碍物而放弃较近路径，保证安全性，但会导致时间浪费，Sarsa算法同理。在多次学习后，Dyna-Sa算法得到的经验会指导智能体选择最优路径，所需时间会逐渐缩短。综合表中数据可以得出：Dyna-Sa算法从总体看较优于其他三种算法，在保证安全性的同时，能够在较短时间内找到一条较优路径，满足城市交通路径规划这种特殊环境的要求。

表2 无障碍地图实验结果Tab.2 Experimental results on map without obstacle

表3 有障碍地图实验结果Tab.3 Experimental results on map with obstacles

图6 和图7 分别表示无障碍物和有障碍物环境下算法收敛情况，横轴表示迭代次数，纵轴表示算法每次迭代结束时经过的步数。

图6 无障碍物环境下算法收敛情况Fig.6 Convergence of algorithm in obstacle-free environment

图7 有障碍物环境下算法收敛情况Fig.7 Convergence of algorithm in environment with obstacles

为了更好地展示算法性能，方便读者阅读，将整个迭代过程进行分割。在无障碍环境中，图6（a）部分表示前25回合算法收敛情况，可以得出：所有算法在17 回合后都已经收敛；Dyna-Sa 算法和Dyna-Q 算法收敛速度相似，远优于不使用Dyna 框架的算法。图6（b）部分表示26 回合到100 回合的算法收敛情况，可以得出：所有算法都收敛，没有异常情况出现。图7（a）、（b）、（c）分别表示前30 回合、31～70 回合、71～100 回合有障碍环境算法收敛情况，所有算法都呈现同一趋势：首先步数较少，然后突然升高，最终趋于平稳。原因是在有障碍物的环境中，智能体首先尝试碰撞障碍物获取环境状态，步数较少，然后在躲避障碍物的过程，产生大量的步数，最终产生一条通往目标状态的完整路径，达到收敛状态。Sarsa 算法在整个过程无法收敛；Q-Learning 算法在37回合后能够达到收敛；Dyna-Q 算法和Dyna-Sa 算法分别在24 回合和18 回合达到收敛。Dyna-Sa 是一种风险敏感算法，所以迭代产生平均步数较多。

5 结语

针对城市交通路径规划问题，新算法Dyna-Sa 主要是以Dyna 为框架，使用Sarsa 的更新函数和决策方式，将模型无关和基于模型的算法结合的Dyna 框架向无模型的强化学习算法引入模型，使用学习到的经验来训练模型，同时利用模型来产生模拟的经验，最后与从环境中直接学习的经验两者共同作用于值函数的更新。本文分析了城市交通路径规划的特殊性，比较了Sarsa 算法和经典强化学习算法Q-学习的特点，选择了更为保守并且适合的Sarsa算法与Dyna框架结合。

仿真实验表明智能体规划次数越多，学习到的模拟经验就越多，算法的收敛速度越快。第二个实验将提出的算法与其他3种算法在仿真地图上对比，结果显示Dyna-Sa算法能够有效避免障碍物，提高了路径规划的安全性，同时能够保证快速找到一条符合要求的路径，更加适合应用在城市交通环境中。

未来工作主要是研究算法在动态交通环境中表现，以及在奖励值的设置中增加变量函数来提升算法整体的收敛速度，同时提高车辆路径规划过程中的安全性。