基于模拟退火策略的强化学习路径规划算法

季野彪，牛龙辉

（西安工程大学电子信息学院，西安710000）

0 引言

随着无人驾驶[1]的兴起，机器人导航技术[2]越来越受到人们的重视。对于机器人导航技术的研究，其核心在于路径规划[3]，即在特定环境下，依据某些规则，规划出一条从起始点到目标点的最优无碰撞路径[4]。强化学习是近年来发展迅速的一种机器学习算法，并在移动机器人路径规划领域取得了较好的应用。强化学习算法中，agent 通过与环境的交互进行试错学习，从而获得奖赏值，最终规划出一条奖赏值最高的最优路径[5]。

传统的Q（λ）学习算法进行路径规划[6]时，agent 每到一个状态，其动作选择策略都会有一个固定的探索因子决定下一个动作是探索环境还是利用环境。对于探索因子的设计往往会影响算法的性能，过大的探索因子会导致agent 对环境知识的利用不够，影响算法收敛速度，过小的探索因子会导致算法陷入局部最优。

本文针对Q（λ）学习算法中探索因子的设计问题，通过加入模拟退火（Simulated Annealing，SA）[7]的思想，提出了基于模拟退火策略的Q（λ）学习算法（SA-Q（λ））。改进的SA-Q（λ）学习算法中探索因子动态变化，学习初期探索因子较高，agent 以较大的概率选择随机动作，以便尽快地了解环境。随着学习幕数的增加，探索因子根据退火规则逐渐减小，agent 以较大的概率选择最优动作。实验表明，改进的SA-Q（λ）学习算法加快了agent 规划出最优路径、提高了算法的收敛速度。

1 强化学习

1.1 简介

强化学习是机器学习的一种类型，通过与环境交互获得反馈，目的是为得到较高的正回报。在学习过程中给定agent 奖赏和惩罚的规则，agent 根据自身的经验不断发现能够获得奖赏的动作，最终学习出一条奖赏值最高的状态——动作链[8]。图1 所示为强化学习过程中agent 与环境的交互过程。首先，agent 获取当前所处状态s，并依据动作选择策略选择动作a；随后，采取动作a，环境状态由s 转移到s'，同时给出奖赏值r；最后，agent 通过奖赏值r 以及值更新公式更新状态-动作值。

标准的强化学习算法框架包含四大要素[9]：

（1）环境模型

环境模型提供了agent 进行学习的环境，并设计了状态和动作之间的映射空间。

（2）策略

策略π 提供了agent 在各个状态选择动作的依据。

（3）奖赏函数

奖赏函数r 为agent 执行一次动作之后，环境对该动作是否有利于达成目标的评价，r 值越大则表明该动作越利于达成目标。

（4）值函数[10]

值函数V 是agent 选择的动作的期望回报，通过对值函数的更新提高回报动作的选择概率，降低其他动作的选择概率，从而获得较大的期望回报。

根据选择不同动作所获得的回报值不同调整策略，使得回报最大化：

图1 强化学习中的智能体-环境交互过程

1.2 Q（λ）学习算法

Q（λ）学习算法是在经典Q 学习算法中加入资格迹，由单步更新变为多步更新。在当前回报较好的情况下，不仅更新当前状态，并为导致到达该状态的某些先前状态分配一些回报，大大提高了算法的收敛时间。

传统的Q 学习算法的Q 值更新公式如下[11]：

式中：Q(s，a)和Q(s'，a')为状态s 和状态s'下执行动作a 和a'对应的Q 值；r 为环境由状态s 经过动作转移到状态s'后给出的立即强化信号，即奖励函数值；α和γ 分别为学习率和折扣因子。

在引入资格迹后，Q（λ）学习算法的Q 值更新公式如下[12]：

式中：E(s，a)为资格迹，资格迹初始值都为0，当agent 经过某个状态时，当前时刻该状态上的资格迹值为1。在执行后续动作时，资格迹E(s，a)中的值依据下式衰减：

式中：λ 为资格迹衰减因子，agent 每执行一次动作，状态s 处的资格迹值就根据上式衰减一次。

Agent 在每一个状态下，都依据贪婪策略选择即将采取的动作，该策略往往会导致算法陷入局部最优，且无法在增加学习周期的情况下跳出局部最优。为避免算法陷入局部最优以及提高算法的收敛速度，本文提出了动态调整探索因子的思想。将Q（λ）学习算法与模拟退火中Metropolis 规则[13]相结合，使得算法学习前期探索因子较大，学习后期探索因子较小，既避免了算法陷入局部最优，又保证了算法的收敛速度，全面提高了算法性能。

2 基于模拟退火的策略的Q（λ）算法

2.1 模拟退火算法

模拟退火算法最早的思想是由N.Metropolis 等人于1953 年提出。1983 年，S.Kirkpatrick 等人成功将退火思想引入到优化组合问题领域[14]。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，通过跳出局部最优的机制达到全局最优[15]。

2.2 模拟退火算法

将模拟退火算法中跳出局部最优的思想引入到Q（λ）算法中的动作选择策略中，设计自适应的动态探索因子，使得agent 学习前期探索到的路径多样性提高，避免在路径规划时陷入局部最优。同时，随着降火过程，探索因子逐渐减小，提高算法的收敛速度。基于模拟退火的动作选择策略具体步骤如下：

（1）agent 在状态st时刻，随机动作为ar，回报值最高的动作为ap；

（2）产生（0，1）之间的随机数δ；

（3）判断δ 与p=e((Q(st，ar)-Q(st，ap))/Tt)之间的大小关系，若δ

（4）判断是否至冷却状态，若至冷却状态，则T=Tmin。

根据上述动作选择策略，将改进的SA-Q(λ)学习算法应用于移动机器人路径规划，具体执行过程如下路径规划步骤如下：

Set initial temperature T，the end temperature Tmin，the rate of fire reduction q

Initialize Q(s，a)arbitrarily，for all s ∈S，a ∈A(s)

Repeat（for each episode）:

E(s，a)=0，for all s ∈S，a ∈A(s)

Initialize s，a

T=T×q

Repeat（for each step of episode）:

Choose a from s using simulated annealing strategy

Take action a，observe r，s'

δ=r+γ maxa'Q(s'，a')-Q(s，a)

E(s，a)←1

For all s ∈S，a ∈A(s):

Q(s，a)←Q(s，a)+αδE(s，a)

E(s，a)←γλE(s.a)

s ←s'

Until s is terminal

Until learning cycles reach set values

每一幕开始之前进行等比降温操作，保证了随着学习幕数的增加，动作选择策略中选择随机动作的概率逐渐减小，保证了算法收敛速度能够有效提高。在温度降至冷却时刻后，动作选择策略中选择随机动作的概率几乎为0，保证了算法能够稳定收敛。

3 实验及结果分析

3.1 实验环境

实验环境为一个20×20 的栅格世界[16]，如图2 所示。每个栅格代表智能体的一种状态。黑色栅格为障碍物，白色栅格为可移动区域。对agent 而言，环境是未知的，且环境中的障碍物与目标都是静态的。Agent的运动方向可分为上、下、左、右，分别代表agent 的四个可选动作。

图2 试验环境

3.2 试验参数的设计

本实验中奖惩函数的设计如下：

智能体在环境中移动，未碰到障碍物时，奖励值为0；碰到障碍物，则获得奖励值-1，到达终点时获得奖励值10。根据需要，本文将模拟退火参数设置为：初始温度T=300，降温速率q=0.95，常温Tmin=10-8。设置每一幕中最大移动步数为40000，智能体到达目标或者步数超过40000，则该幕结束。

本文比较学习算法和学习算法的收敛速度，算法中的学习率、折扣因子及策略设置如表1 所示。

表1 两种学习算法参数设置

3.3 试验及结果分析

由上述仿真环境以及设置的参数对Q(λ)和SA-Q(λ)两种算法进行仿真试验，比较了Q(λ)学习算法与SA-Q(λ)算法的收敛速度。在环境中，设置agent的起始点位置为（0，20），终止点位置为（20，0）。图3所示为算法收敛速度对比图，红色曲线为Q(λ)学习算法收敛曲线，蓝色曲线为本文SA-Q(λ)学习算法收敛曲线。图中可见两种算法在学习初期都花费较多步数才能到达目标点，而在60 幕之后，本文提出的SA-Q(λ)学习算法随着降火策略调整探索因子之后，规划的路径长度明显减小，并且于200 幕后算法收敛。传统的Q(λ)学习算法由于存在0.1 的探索因子，算法在收敛后仍有一定的波动。图4 为SA-Q(λ)算法收敛后规划出的最优路径，路径长度为38，证实为最优路径。

4 结语

本文提出了改进的SA-Q(λ)学习算法，平衡了智能体路径规划中探索与利用的关系，既避免了算法陷入局部最优，也有效提高了算法收敛速度。在20×20的栅格环境中，通过对比Q(λ)和SA-Q(λ)学习算法的收敛速度，得出SA-Q(λ)学习算法在学习初期对环境的探索率高，同时随着降火的过程算法对环境的利用提高的结论。在本文的研究工作中，笔者发现降火过程中降火函数的选取在一定程度上也会对算法收敛速度有很大的影响，在今后的研究中将针对降火函数做改进，进一步提高强化学习算法的收敛速度。

图3 算法收敛对比图

图4 路径效果图