改进强化学习算法应用于移动机器人路径规划

王科银，石 振，杨正才，杨亚会，王思山

1.湖北汽车工业学院 汽车工程学院，湖北 十堰442002

2.汽车动力传动与电子控制湖北省重点实验室（湖北汽车工业学院），湖北 十堰442002

3.湖北汽车工业学院 汽车工程师学院，湖北 十堰442002

随着科技的发展，移动机器人越来越多地走进人们的日常生活。移动机器人的路径规划问题也越来越受到重视。路径规划技术能够在参照某一指标的条件下，帮助机器人避开障碍物规划出一条从起点到目标点的最优运动路线。根据路径规划过程中对环境知识的已知程度，路径规划可以分为全局路径规划和局部路径规划[1-2]。其中应用较为广泛的全局路径规划算法有A*算法[3]、dijkstra算法[4]、可视图法[5]、自由空间法[6]等；局部路径规划算法有人工势场算法[7]、遗传算法[8]、神经网络算法[9]、强化学习算法[10]等。强化学习算法是一种适应性比较强的算法，可以在完全未知的环境中通过不断试错寻找最优路径，这也使得强化学习算法在移动机器人路径规划领域获得越来越多的关注。

在移动机器人路径规划领域应用最为广泛的强化学习算法是Q-learning算法。传统的Q-learning算法存在以下问题：（1）在初始化的过程中将所有的Q值设置成0或者是随机值，这使得智能体在起始阶段只能是盲目搜索，导致算法出现过多的无效迭代；（2）在动作选择时采用ε-贪婪策略，太大的ε值会使智能体更多地探索环境不容易收敛，太小ε值会导致智能体对环境探索不够而找到次优解，难以平衡探索和利用之间的关系[11]。

针对上述问题，很多学者提出了各种Q-learning的改进算法。宋勇等人[12]引入人工势场，利用先验知识确定每点的势能值，根据势能值初始化Q值，提高了算法初始阶段的学习效率。董培方等人[13]联合人工势场和环境陷阱搜索作为先验知识初始化Q值，得到更快的收敛速度和更优的规划路径。Wen等人[14]基于模糊规则初始化Q值，加快了算法的收敛速度。徐晓苏等人[15]在引入人工势场初始化Q值的基础上，增加移动机器人的搜索步长和方向因素，缩短了路径规划时间，提高了路径的平滑度。上述对Q-learning算法的改进都是根据一定规则对Q值初始化，这在一定程度上提高了算法性能，但是缺乏对智能体动作选择策略的研究。针对当前研究现状的不足本文提出一种改进的Q-learning算法，在Q值初始化的过程中引入改进人工势场的引力场函数，使得越靠近目标位置状态值越大从而智能体在起始阶段就能朝着目标位置进行搜索，减少算法起始阶段的无效迭代；在动作选择上改进ε-贪婪策略，根据算法的收敛程度动态调整贪婪因子，更好地平衡探索和利用之间的关系，进一步加快算法收敛速度，并且保证算法的收敛稳定性。

1 相关理论

1.1 Q-learning算法

Q-learning是一种离线的时序差分强化学习算法[16]。智能体根据某一策略对状态-动作对(s,a)进行k次采样，得到状态动作值函数估计值Q(s,a)，当进行下一次采样时，可获得奖励值R(s,a)并进入下一个状态s′，智能体直接选择状态s′所对应的最大状态动作值Q(s′,a′)来更新上一个状态s的Q(s,a)，更新公式如下：

其中，(s,a)为当前状态-动作对，(s′,a′)为下一时刻的状态-动作对，R(s,a)为状态s下执行动作a的即时奖励，α为学习率，通常设置a为小于1的正数，γ为折扣因子，折扣因子的取值范围是0~1。

在Q-learning的应用中，通常采用ε-贪婪策略来选择下一状态的动作，其表示在智能体选择下一动作时以ε(ε<1)的概率随机在动作空间中选择动作，以1-ε的概率选择最优动作。

1.2 改进人工势场法

人工势场包括引力场和斥力场，其中目标点对移动机器人产生引力，引导机器人朝着目标点运动，越靠近目标点引力越大。障碍物对机器人产生斥力，避免与之发生碰撞。移动机器人运动路径上的每一点所受的合力等于该点所受目标点的引力和障碍物的斥力之和，在合力的作用下移动机器人从起始位置出发，避开障碍物到达目标位置。因为本文的研究基于未知环境，障碍物位置无法确定，所以只考虑引入引力场，提出如下引力场函数：

其中，ζ是大于0的尺度因子，用来调节引力大小， ||d为当前位置与目标点所在位置的距离，η为正常数，防止目标点处引力值出现无穷大。

该方法构造的人工势场，整个势能场从起点到目标点呈现单调递增趋势，目标点具有最大势能值且不为无穷大。

2 改进Q-learning算法

2.1 Q值初始化

传统的Q-learning算法把所有Q值初始化为0或者是随机数值，在算法初期智能体只能是随机地选择动作，从而产生巨大的无效迭代。通过1.2节中改进的引力场函数初始化状态值，通过状态动作值函数和状态值函数关系式（3）对Q值初始化。通过该方法初始化的Q值使得智能体在初始阶段就能以更大的概率向目标点方向移动，减少了算法初期的大量无效迭代，加快算法收敛。

其中，P(s′|s,a)为当前状态s和动作a确定的情况下转移到状态s′的概率，V(s′)为下一状态的状态值函数，对于本研究初始化Q值时，V(s′)=Uatt。

2.2 贪婪因子动态调整

如何平衡强化学习当中探索和利用之间的关系是强化学习算法实际应用的难点之一。探索是指智能体在选择动作时，不遵循已经学习到的策略，而是运用其他可能不太好的策略扩大对环境的搜索范围，减小出现局部最优的可能性；利用是指智能体在选择下一步动作时根据已经学习到的策略选择当前最优动作。ε-贪婪策略在一定程度上平衡了探索和利用，但是智能体每次都以ε的概率在动作集中随机选择动作，不好的动作也以同样的概率被选择，由此会导致整个过程收敛速度慢，即使在最后收敛也会因为以ε的概率随机选择动作使得结果存在一定的波动。针对该问题，本文提出一种改进的ε-贪婪策略。

e为自然对数的底，当自变量t大于0时，tanh(t)的取值范围为（0，1）；stdn为连续n次迭代次数的步数标准差；T为系数，与模拟退火算法[17]中的温度值作用相反，T越大随机性越小；εmax和εmin分别为所设置的探索率的最大值和最小值。

在强化学习算法起始阶段，因为算法不收敛stdn较大，智能体以εmax的概率随机选择动作；随着算法的进行stdn减小，使得ε在(εmin,εmax)范围内取值，stdn越大表明迭代次数之间的步数差别越大，环境越需要探索，ε的取值就越大；stdn较小时，表明算法趋于收敛，ε稳定在εmin。由以上分析可以看出，该方法设计的贪婪因子动态调整策略，使得前期以更大的概率对环境进行探索，随着算法的进行，逐渐趋于利用，能够更好地平衡探索和利用之间的矛盾。

3 仿真实验与结果分析

3.1 实验环境

利用Python的Tkinter标准化库，搭建如图1所示的20×20的格栅地图作为仿真环境，每个小格栅的尺寸是20×20像素。其中方块代表障碍物，白色格栅为无障碍区域。格栅地图中的每一格代表一个状态，共400个状态。起点设置在（10，10）的坐标位置，即状态（1，1），终点设置在状态（18，14）。

图1 路径规划仿真环境Fig.1 Simulation enviroment of path planning

3.2 实验参数

在仿真环境中对比以下4种算法：Trad_Q-learning代表传统的Q-learning算法；APF_Q-learning代表引入人工势场法初始化Q值的改进算法；Adj_Q-learning代表使用贪婪因子动态调整策略替代ε-贪婪策略改进算法；Imp_Q-learning代表本文提出的最终改进算法。

4种算法的相同参数设置为：学习率a=0.01，折扣因子γ=0.9，最大迭代次数20 000次。其他设置如表1。

表1 4种算法的设置Table 1 Settings of 4 kinds of algorithms

对于4种算法奖励函数设置为：

贪婪因子动态调整策略参数如下：εmax=0.5,εmin=0.01,T=500,n=10。

3.3 实验结果与分析

图2中（a）~（d）依次表示上述4种算法的收敛情况，当路径长度在小范围内波动时认为算法收敛。表2详细对比了4种算法的性能，收敛条件都设置为连续10次迭代步数标准差小于5，每种算法运行10次取数据平均值。

图2 4种算法收敛回合Fig.2 Convergence episode in 4 kinds of algorithms

表2 4种算法性能比较Table 2 Performences comparison of 4 kinds of algorithms

实验结果表明4种算法在迭代一定次数后都可以规划出最优路径，图1中的蓝色圆点展示了某次实验规划出的最优路径。对比算法APF_Q-learning和算法Trad_Q-learning可知，引入人工势场法初始化Q值可使得算法收敛时间缩短79.2%，迭代次数减少50.0%，但是算法在收敛稳定性上没有提升；对比算法Adj_Q-learning和算法Trad_Q-learning可知，动态调整贪婪因子可使得算法收敛时间缩短62.4%，迭代次数减少40.2%，算法的收敛结果稳定性得到了提升，算法收敛后只有极少数的波动；对比算法Imp_Q-learning和算法Trad_Q-learning可知，本文提出的最终改进算法在初始化Q值时引入人工势场法，在动作选择时动态调整贪婪因子可使得算法收敛时间缩短85.1%，迭代次数减少74.7%，同时算法的收敛结果稳定性也得到了提升。

4 结语

针对未知静态环境下移动机器人的路径规划问题，为了提高强化学习算法的收敛速度和收敛结果稳定性，本文在传统Q-learning算法的基础上引入改进人工势场法初始化Q值，同时在动作选择时动态调整贪婪因子。通过实验表明算法的效率和收敛结果的稳定性都得到大幅提升。但是该算法在应用时需要根据不同的情境设置6个参数，如何设置算法中的参数，使得算法具有更好的适应性是接下来研究的重点。