改进Deep Q Network的路径规划算法

山东交通学院信息科学与电气工程学院(人工智能学院) 张洪博

随着计算机技术、人工智能理论、即时定位与地图构建（Simultaneous Localization And Mapping，SLAM）等技术的不断成熟与发展，机器人技术的研究已经发展到一个崭新的阶段。路径规划作为机器人运动不可或缺的一部分，近些年国内外专家对其研究的热情持续高涨，它已经成为移动机器人趋向人工智能化阶段的核心技术。路径规划的目的是让机器人在规定的区域内找到一条从起点到终点的无碰撞安全路径，并让这条路径尽可能的短。机器人在运动过程中，能够实时模拟出所在的环境。通过控制自身运动状态，探测障碍物并计算安全路径，最后成功到达任务地点。因此，一个性能良好的路径规划算法对移动机器人非常重要。移动机器人目前在许多领域都有着广泛地应用，比如家庭扫地、物流分拣等。尤其在一些环境比较恶劣的情况下，使用移动机器人可以有效地避免对人身安全的危害。

移动机器人路径规划始于20世纪60年代末期，早期的迪杰斯特拉算法，后续的A*算法、人工势场法、粒子群算法、RRT算法等都是经典之作。但传统的路径规划算法自身的收敛速度较慢、计算复杂度较高及适用性较差，所以将深度强化学习方法引入到路径规划中。DQN算法作为深度强化学习的一种，本文在其基础上，改进样本训练方法，提高路径规划的效率、准确性以及实时性。

1 算法介绍

1.1 DQN算法

DQN算法作为深度强化学习的代表之一，不仅在Atari游戏中被测试出有很好的效果，在路径规划中也表现优异。该算法在Qlearning算法的基础上，结合了卷积神经网络来拟合动作值函数。通过经验回放（Experience Replay）打破数据间的关联性，从而解决数据的非静态分布问题，并使用目标网络和当前网络共同解决模型稳定性问题。相比较于其他模型，DQN具有较强的通用性，可用于解决不同类型的问题。DQN算法的网络结构如图1所示。

图1中，DQN中存在两个结构完全相同但是参数却不同的网络，即目标网络和当前网络。当前网络使用的是最新的参数，而目标网络所用的参数是N步之前的。Q(s,a;θ)表示当前网络的输出，用来评估当前的状态-动作对；Q(s′,a′;θ－)表示目标网络的输出。根据公式(1)可以解出TargetQ，并根据公式(2)更新当前网络的参数。每经过一定次数的迭代，将当前网络的参数复制给目标网络。这样就完成了一次学习过程。

图1 DQN算法结构图

1.2 本文算法

DQN算法在进行样本数据采集的时候，没有对样本数据进行优良区分。在训练的时候，所有的样本都有相同的概率被随机抽取到。然而，每个样本对训练的贡献度是不一样的。本文对原DQN算法进行了改进，重点关注机器人当前位置的相邻位置，设计如图2所示的矩阵，对训练样本进行相似度筛选。

图2 筛选矩阵

首先对当前点的周边情况进行计算，返回一个代表周边障碍物情况的3×3矩阵，1代表障碍物，0代表空白，如图3所示。

图3 障碍物矩阵

对两个矩阵进行哈达马积运算，然后求和，由此得到一个数值。通过实验验证得到，当表示周边障碍物的矩阵改变时，最后求出的结果也会改变，这说明设计的矩阵可以用来计算训练样本的相似性。通过此方法，将相似度高的样本数据剔除，减少冗余样本，保留样本的多样性。

2 实验过程

2.1 实验设置

本实验采用栅格地图进行仿真，其中栅格地图的大小为25×25。在每一张测试地图里设定起始点和目标点，然后随机生成设定数量的障碍物。如图4所示。

图4 仿真环境

将每一张栅格地图作为输入输送到神经网络，分别利用DQN算法和改进后的DQN算法进行测试。如果能从起点走到终点，并且不与障碍物发生碰撞，则把找到的路径画出。否则即为失败，不显示图像。

2.2 实验结果

实验使用随机生成的20张25×25的栅格地图。蓝色方块代表当前位置，绿色方块代表终点位置，白色为可以通过的路径。在地图中随机生成40个代表障碍物的黑色方块，从起始点无碰撞走到目标点即为成功。图5和图6分别为DQN算法的测试地图和测试结果，图7和图8分别为改进DQN算法的测试地图和测试结果。

图7 改进DQN算法的测试地图

图8 改进DQN算法的测试结果

DQN算法的测试地图如图5所示。

图5 DQN算法的测试地图

DQN算法的测试结果如图6所示。

图6 DQN算法的测试结果

对DQN算法使用栅格地图进行测试，经过训练，获得了稳定的路径规划能力。在20张测试地图中，成功到达目标点的有16张，成功率达到80%。

改进DQN算法的测试地图如图7所示。

改进DQN算法的测试结果如图8所示。

在实验中，DQN算法对路径规划的成功率达到了80%，改进的DQN算法成功率更是达到95%。相比较而言，改进后的DQN算法比原始DQN算法提高了15%的成功率，效果更好。

结论：本文针对原DQN算法存在样本训练效率低下，样本冗余等问题，提出了一种改进的DQN算法。本文算法通过使用设计的矩阵对数据样本的训练方式进行优化，剔除相似度高的数据样本，获得高质量的样本数据。通过测试，本文算法提高了训练模型的准确度，在规划路径方面有明显地提升。