基于深度Q学习的移动机器人路径规划

刘志荣， 姜树海， 袁雯雯， 史晨辉

(1.南京林业大学 机械电子工程学院，江苏 南京 210037；2.南京林业大学 智能控制与机器人技术研究所，江苏 南京 210037)

路径规划是移动机器人导航的重要组成部分，其目标是在复杂环境下能够寻找一条从起点到终点的无碰撞路径。路径规划的核心是算法设计，根据训练方法的不同，算法可分为监督学习、无监督学习和强化学习。监督学习和无监督学习以大量的样本数据为基础，这使得机器人在先验知识匮乏的情况下很难通过监督学习和无监督学习进行良好的路径规划。强化学习是一种不需先验知识、与环境直接进行试错迭代获取反馈信息来优化策略的人工智能算法，因而广泛应用于复杂环境下的移动机器人路径规划中[1-2]。根据求解方法不同，强化学习算法分为直接策略搜索法和值函数法。直接策略搜索法将策略参数化表示，通过优化指标进行梯度上升，最后得到最优或者局部最优策略，可解决连续动作空间的问题[3]，主要应用于机器人的控制方面[4]，但在离散动作空间问题上并不能很好地评估单个策略，易于收敛到局部最小值。值函数法根据状态转移概率是否已知又分为基于模型的强化学习算法和与模型无关的强化学习算法两类。基于模型的强化学习算法进行路径规划时需要知道环境特征，依据环境特征构建环境模型，因此只适用于简单的结构化环境中的路径规划。与模型无关的强化学习算法，无需构建环境模型就可应用于复杂环境下的机器人路径规划中。Q-learning是典型的与模型无关的强化学习算法，无需知道模型就可以保证收敛，是目前应用于机器人路径规划中最有效的强化学习算法，在状态空间较小的情况下能够获得很好的路径规划[5]，但Q-learning通过构建Q值表选择最优策略，在维数很大时会导致维数灾难[6]，因此很难推广到大状态空间中。

深度Q学习(Deep Q-Learning Network，DQN)算法是在深度学习发展的基础上而兴起的新的算法，它统一了深度学习的感知能力和强化学习的决策能力，是一种更接近人类思维方式的人工智能方法。近几年来，在游戏等方面利用DQN探索原始图像进行实时决策已经超越人类的表现[7]。同时，深度强化学习在控制系统决策方面有良好的表现，广泛应用于机器人的各种任务，如机器人的运动、抓取、操作[8]、控制[9]、自动驾驶[10]等方面。Pfeiffer等人[11]利用深度学习模型将激光传感器测距结果和目标位置映射为移动机器人的控制命令。Lei Tai等人[12]在未创建地图的基础上利用DQN实现了移动机器人的导航，之后他们[13]又构建深度卷积神经网络框架，以RGB-D传感器图片为输入信息，输出为机器人的下一步动作，该思想将强化学习算法上升到了新的高度。感知能力与决策能力是衡量智能的两大指标，强化学习的弱感知能力致使机器人难以直接通过学习高维状态输入去控制输出决策，而深度学习可用网络结构来映射Q值表，从而解决Q-learning的维数灾难问题。本文在分析Q-learning进行路径规划的优点和不足的基础上，将深度学习框架融于Q-learning中，构建记忆回放矩阵和两层网络结构，提高DQN收敛性，使其能够在复杂状态环境下进行良好的路径规划。

1 Q-learning算法

Q-learning是一种典型的与模型无关的强化学习算法，由Watkins[6]在1989年提出。Q-learning算法首先建立一张Q值表，然后通过机器人与环境交互，得到奖赏函数值，通过不断迭代修改Q值表，使选择正奖赏的动作的概率不断增加，随着不断与环境交互，更改动作策略集，使机器人的动作最终趋于最优动作集。Q-learning采用状态-动作对Q(s,a)迭代方式来获得最优策略。算法在每一次迭代时需要考察每一个状态-动作对Q(s,a)的值。Q-learning算法的基本形式为

Q(st,at)=Q(st,at)+α[rt+γmaxaQ(st+1,a)-Q(st,at)]

(1)

式中，st为t时刻移动机器人的状态，在状态st下执行动作at，移动机器人状态变为st+1，同时得到奖励值rt;rt是对状态st+1的评估，表示机器人由当前状态执行动作到下一个状态所获得的奖励值；动作a∈A，A为动作空间；状态st,st+1∈S,S为状态空间；α为学习率，α越大Q值收敛越快，但越容易产生振荡；maxaQ(st+1,a)表示从动作集A中选择一个动作A使得Q(st+1,a)的取值最大；γ为折扣因子，表示未来奖励对当前动作的影响程度[14]。

将式(1)变形成

Q(st,at)=(1-α)Q(st,at)+α[rt+γmaxaQ(st+1,a)]

(2)

由式(2)可知，状态st对应的Q值稳定的必要条件为状态st+1对应的maxaQ(st+1,a)恒定，否则上一个状态的Q值会随下一个状态的Q值的改变而变化，因为整体是一个回溯过程，前面所有的动作对应的状态都不能达到稳定值。

假设st+1状态稳定，即Qt+1恒定，为求Q(st,at)的稳定状态，借助式(2)迭代。

一次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1](Q(st,at)简写成Qt)

二次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)[(1-α)Qt+α[rt+γQt+1]]+α[rt+γQt+1]

=(1-α)2Qt+[1-(1-α)2][rt+γQt+1]

(3)

三次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)[(1-α)2Qt+[1-(1-α)2][rt+γQt+1]]+α[rt+γQt+1]

=(1-α)3Qt+[1-(1-α)3][rt+γQt+1]

(4)

以此类推，N次迭代：

Q(st,at)=(1-α)Qt+α[rt+γQt+1]

=(1-α)nQt+(1-α)nQt+[1-(1-α)n][rt+γQt+1]

(5)

因为0<α<1，所以0<(1-α)<1，当n→∞，(1-α)n→0。

Q(st,at)→rt+γQt+1，此时Q(st,at)收敛。

Q-learning借助式(2)更新，最终整个Q值表会达到一个极限ΔQ=rt+γmaxaQ(st+1,a)-Q(st,at)，当Q值不断迭代更新，n→∞时，Q(st,at)将以概率1收敛于最优值，即

Q(st,at)=rt+γmaxaQ(st+1,a)

(6)

由式(6)可知，Q-learning算法前一个状态的收敛依赖于后一个状态，与初值无关，并且无需知道模型就可以保证收敛，是目前应用于机器人路径规划中最有效的强化学习算法。但是Q-learning在复杂的障碍物密集的环境下需要构建庞大的Q值表，然后根据回报值循环更新Q值表的对应值，该方法极其耗时，因此Q-learning很难应用到大状态空间下的移动机器人路径规划。

2 DQN算法实现

2.1 DQN模型结构

DQN是Q-learning的变体算法，它以卷积神经网络为载体，用参数为w的f网络近似代替值函数，公式为

f(s,a,w)≈Q*(s,a)

(7)

f(s,a,w)可以是任何类型的函数，通过函数近似替代，无论状态空间有多大，都可用神经网络的输出表示Q值，这就是用神经网络近似替代Q值的基本思路，具体如图1所示。s为输入状态，如在迷宫环境中，s代表一个小网格的特征，可以用网格对顶角坐标表示，则s=(x1,y1,x2,y2)表示机器人的一个状态，输出F(s,ai,w)(i=1,2,3,4)是一个值，表示当前状态s下动作ai的Q值。因此只要输入状态s，就可以得到所有动作的Q值。通过网络从根本上代替了Q-learning的Q值表，减少了维度灾难的发生。

2.2 DQN特点

对于离散动作状态空间的决策问题，DQN将状态作为输入，输出为每个动作的Q值估计，以此近似值函数。但是神经网络的加入破坏了Q-learning的无条件收敛性[15]。为了解决DQN的收敛性，可以从下面两个方面进行改进。

2.2.1 记忆回放

DQN在与环境互相迭代过程中，前一个状态与下一个状态具有高度相关性，导致神经网络过拟合而无法收敛。在与环境交互过程中，机器人在状态s时执行动作a，得到回报值r并到达下一个状态s′，反复执行这个过程，直到到达目标点。记忆回放的思想是在每次学习过程中，随机抽取记忆库中的一批样本，并对其梯度下降进行学习。通过记忆矩阵中的经验单元(s,a,r,s′)，可以将新的经验单元和老的经验单元随机按批次混合进行更新，从而打断相邻数据样本之间的相关性。并且很多经验单元会不止一次地被用于更新，从而提高样本的利用率。

2.2.2 建立双层网络结构

DQN与传统的利用神经网络逼近值函数方法相比，建立了一个与当前Q网络结构相同、参数不同的Q-target神经网络，即在计算目标Q值使用专门的Q-target网络来计算，而不是直接使用预更新的当前Q网络，以此来减少目标值与当前值的相关性。损失函数公式为

I=(r+γmaxa′Q(s′,a′；w-)-Q(s,a;w))2

(8)

式中,Q(s,a;w)为当前网络的输出，用来评估当前状态动作对的值函数。Q(s′,a′;w-)为Q-target的输出，用来求得目标值函数的Q值。

Q-target网络参数w-由参数w延迟更新获得，即参数w实时更新，经过若干轮迭代后，将当前Q网络的参数赋值给Q-target网络。对参数w进行求导，可得值函数的更新，如式(8)所示。

wt+1=wt+α[r+γmaxa′Q(s′,a′;w-)-Q(s,a;w)]Q(s,a;w)

(9)

2.3 DQN算法流程

DQN算法流程如下。

① 初始化记忆矩阵D，初始化Q-target网络参数w-和当前网络参数w。

② 将移动机器人的环境信息和摄像头采集的图像数据传递给机器人的多融合传感器，获取环境的特征信息(s,a,r,s′)并将其保存于记忆矩阵D中。

③ 从记忆矩阵B中取出一批样本。

④ 用Q-target网络计算：y=r+γmaxa′Q(s′,a′;w-)。

⑤ 用I=(r+γmaxa′Q(s′,a′;w-)-Q(s,a;w))2来提升参数。

⑥ 每隔N步将参数w复制给参数w-。

3 仿真结果及结果分析

3.1 动作空间的表示

仿真过程中将移动机器人近似为质点，用红色圆圈表示。以移动机器人为中心，定义机器人的动作空间包含前进、后退、左移、右移4个基本动作。程序中用0,1,2,3表示，动作空间矩阵为[0,1,2,3]。采用ε-greedy策略，一方面以1-ε的概率选择Q值最大的动作a，来尽可能利用环境信息，该过程为利用过程。另一方面以小概率ε随机选择动作进行环境探索，以此保证所有的状态空间都有可能被搜索过。所设置的探索分布为

(10)

3.2 奖赏函数的设计

奖赏函数在强化学习过程中具有导向作用，对强化学习所采取动作的好坏做出评价，用标量r表示。强化学习的目的就是使机器人最终获得的总的奖赏值之和最大。所设置的奖赏函数为

(11)

3.3 仿真结果与分析

3.3.1 简单的仿真环境

本实验主要分析传统强化学习的路径规划过程。该仿真环境较为简单。采用Python建立二维网格地图表示环境信息，网格地图将机器人所处环境分解为小栅格。网格模型尺寸为400×400，最小移动单元为20。每个栅格对应机器人的一个状态。状态空间为20×20的网格大小的对顶角坐标(x1,y1,x2,y2)。环境GUI如图2所示。

图2中圆圈代表初始点，圆心坐标为(10,10)；浅灰色方块代表目标点，中心坐标为(350,350)；深灰色方框代表障碍物；白色区域代表安全区域。

图3为机器人在迭代5000次过程中所得到的最短路径轨迹。该轨迹也是机器人从初始点到目标点的最短距离。说明通过机器人与环境的不断交互，强化学习能够让机器人在简单环境中进行良好的路径规划。

图2 仿真环境

图3 Q-learning最短路径图

图4为迭代过程中的回报值变化曲线，由图可知，随着迭代步数的增加，回报值有越来越大的趋势，这说明机器人在与环境迭代过程中，所规划的路径越来越趋于最优路径。图5为迭代过程中的步长，由图可知，随着迭代步数的增加，起始点到终点的规划步长趋于减少，最终收敛于最优步长。

图4 回报值随迭代次数变化曲线图

图5 到达目标点所需步长随迭代次数的变化曲线图

3.3.2 复杂的仿真环境

环境状态很复杂时，简单的Q-learning很难获得好的效果，用同样方法构建图6仿真环境。图7为回报值和到达目标点所需步长随迭代次数变化图，由图可知，迭代30000次时，回报值仍为负数，说明算法并没有很好的学习，到达目标点所需步长值一直大于200，显然算法没有收敛，机器人不能到达目标点。

图6 仿真环境

图7 回报值和到达目标点所需步长随迭代次数变化图

将构建的DQN算法应用到图6仿真环境中，结果机器人能到达终点。图8为机器人在迭代5000次过程中所得到的最短路径轨迹。该轨迹也是机器人从初始点到目标点的最短距离。说明在复杂的环境中，DQN算法没有维数灾难的困恼，能够让机器人进行良好的路径规划。图9为回报值和到达目标点所需步长随迭代次数变化图，从图中可以看出，DQN在迭代1000次附近就开始收敛，相比于Q-learning，不仅收敛速度较快，而且能够在复杂环境中进行良好的路径规划。

图8 DQN最短路径图

图9 回报值和到达目标点所需步长随迭代次数变化图

4 结束语

提出了一种基于深度学习的强化学习算法，以网络输出代替Q值表，解决Q-learning的维数灾难问题，通过构建记忆回放矩阵和两层网络结构打断数据相关性，提高网络收敛性。仿真实验说明该方法的有效性和可行性。本文主要针对静态环境下的复杂路径规划的研究，针对DQN在更复杂的动态环境下的路径规划问题，还有待进一步的研究。