改进Q-learning算法在路径规划中的应用

1、软件与算法改进Q-learning算法在路径规划中的应用千承辉，马天录，刘凯，张宇轩(吉林大学 仪器科学与电气工程学院，长春 130012)摘 要：Q-learning算法是环境未知条件下的有效强化学习算法，该算法在路径规划中被广泛应用。针对Q-learning算法在离散状态下存在运行效率低、学习速度慢等问题，提出一种改进的Q-learning算法，在栅格环境下进行仿真实验，并成功地应用在多障碍物环境下移动机器人路径规划，结果证明了算法的可行性。改进Q-learning算法可以以更快的速度收敛、学习次数明显减少、效率最大可提高20%。同时该算法框架对解决同类问题具有较强的通用性。关键词：路径规

2、划；改进Q-learning算法；强化学习；栅格法；机器人中图分类号：TP391 文献标志码：AApplication of improved Q-learning algorithm in path planningQIAN Cheng-hui，MA Tian-lu，LIU Kai，ZHANG Yu-xuan(College of Instrumentation and Electrical Engineering, Jilin University, Changchun 130012, Chia)Abstract: Q-learning algorithm is an effective

3、reinforcement learning algorithm under the condition of unknown environment, which is widely used in path planning. Aiming at the problem of low efficiency and slow learning in discrete state of Q-learning algorithm, an improved Q-learning algorithm is proposed to simulate in grid environment. It ha

4、s been successfully applied to the path planning of a mobile robot in a multi barrier environment, and the results prove the feasibility of the algorithm. The improved Q-learning algorithm can converge faster, reduce the number of learning, and increase the efficiency by 20%. At the same time, the f

5、ramework of the algorithm has strong generality for solving the same kind of problems.Key words：path planning ; improved Q-learning algorithm; reinforcement learning; grid method; robot 收稿日期：2018年 月 日. 基金项目：吉林省重点科技攻关计划项目（20170204052GX）.大学生创新创业训练项目（2016A65288）. 作者简介：千承辉（1975年），女，高工，博士. 研究方向：智能仪器与微弱信号

6、采集技术. E-mail:qianch0 引言移动机器人可以在人类不可到达或危险未知的地方完成任务，已经成功的运用在很多领域，在移动机器人研究领域中路径规划是一个关键的问题1。路径规划问题已经有很多方法可以借鉴，如蚁群算法、人工磁场法、神经网络法等2-4。本文采用改进的Q-learning算法进行最优路径规划，即指在可以满足预先设定的条件的同时，从起点出发沿最短路径不经过障碍物到达终点。Q-learning算法是环境未知条件下的有效强化学习算法，它的迭代是一个试错和探索的过程，其收敛的一个条件要求对每个可能的状态动作对都多次尝试，最终学到最优的控制策略。Q-learning算法因其不需要建立环

7、境的模型、算法简单、易于使用，已在非线性控制、机器人规划、人工智能问题求解、组合优化和调度制等领域中得到应用。针对不同的应用方向很多人提出了改进的方法5-6，改进后算法的学习效率都得到了一定的提高，但其改进的方法比较繁琐。Q-learning算法应用于路径规划时，存在着学习利率低、收敛速度慢等缺点，且相关研究大多停留在理论层面，缺少对实际问题的解决和实践。本文对Q-learning算法做出改进，并将其应用在多障碍物环境下移动机器人的路径规划，使其在短时间内以最优路径从起点移动到终点。验证了改进算法的高效性，为Q-learning算法的改进提供了新的思路。1 建立环境模型1.1 栅格法建模栅格法

8、简单有效，对障碍物的适应能力强，可减少建模的复杂性，便于计算机存储与处理，也可以直观进行视觉判断，已被广泛用于环境建模方法中7-8。本文通过建立一个n×m的栅格，结合二维直角坐标系来确定栅格位置，并对每个栅格从左至右，从上到下依次标明序号。如图1建立一个3×4的栅格。图1 3×4栅格1.2 问题描述本文利用摄像头采集环境信息、识别障碍物、根据获取的实际信息采用栅格法建立环境模型、设定起点与终点、采用Q-learning算法进行路径规划、根据规划结果控制机器人行走，如图2所示。采集环境信息栅格法建模设定起点终点规划路径执行行走命令图2 整体设计框图如图3所示，a图为

9、摄像头获取的图像，b为MATLAB处理后的图像。从处理后的图像已经能够清楚的知道障碍物的位置坐标，由于采集回来的图像像素点过多，如果以像素点为单位进行计算势必会增加运算量，同时机器人体积较大，对单个像素点计算也没有意义。因此，本文对MATLAB处理后的图像分块化处理。设机器人最大尺寸可占m个像素点，对图像以m个像素为单位进行分块： 其中，x，y分别为分块处理 后每一块对应的坐标，r，c分比为获取实际环境图片的横向、纵向像素点数，公式(2)所求为x，y的最大值，ceil为向上取整函数，为1则为障碍栅格，用黑色表示，为0则为自由栅格，用白色表示，分块结果如图4所示。 (a) 实际图像 (b) 处理

10、后图像图3 获取、处理后图像图4 分块处理后的栅格图由于机器人的搜索范围有限，为了简化运算，本文规定机器人当前的状态只能选择上、下、左、右操作。而对于边、角的特殊位置可选择的操作更少，如图5。(a) 中间位置 (b)边位置 (c)角位置图5 机器人位置信息2 Q-learning算法基本原理本文的环境可被建模为一个确定性马尔可夫决策过程，在此条件下Q-learning算法的基本原理如下9-10：设定学习每个状态动作对s,a的评价值为Q(s,a)。评价函数Q(s,a)定义为：它的值是从状态s开始到执行a作为第一个动作时的最大折算累积回报。即Q(s,a)的值从状态s执行动作a的立即回报加上以后遵循

11、最优策略的值。 其中，（0,1）称为折算因子，r(s,a)为状态s执行动作a得到的奖励。这个Q函数的定义提供了Q-learning算法的基础11。为了描述此算法，实际Q函数的估计使用符号来指代。在此算法通过一个大表表示其估计值，其中对每个状态动作对有一表项。状态动作对s,a的表项中存储了(s,a)的值，即对实际的但未知的Q(s,a)值的当前估计。此表可被初始为随机值。重复地观察其当前的状态s，选择某动作a，执行此动作，然后观察结果回报以及新状态。然后遵循每个这样的转换更新(s,a)的规则： 此训练法使用智能体对新状态s'的当前值来计算其对前一状态s的(s,a)的值。上述是对于确定性马尔

12、可夫决策过程的Q-learning算法的描述6。使用此算法，估计的在极限时收敛到实际Q函数，只要系统可被建模为一个确定性马尔可夫决策过程，回报函数r有界，并且动作的选择可使每个状态动作对被无限频繁的访问。图6 Q-learning算法与环境交互模型3 改进Q-learning算法的路径规划公式4定义的函数说明了在一个确定性马尔可夫决策过程模型中Q值的更新过程，当前(s,a)值由奖励值r(s,a)、所有下一状态动作对s',a' 对应的Q值的最大值和折算因子的大小决定。本文改进的Q-learning算法中(s,a)的更新规则如下： 其中, （0,1）称为折算因子, 称为深度学习因子

13、，Q(s',a' )为下一步状态动作对s',a' 对应的Q值，Q(s'',a'' )为下两步状态动作对s'',a'' 对应的Q值。的取值范围为（0.5,0.1），此处引入的深度学习因子的作用在于保证Q值的收敛。更新的学习规则利用深度学习因子对第一步获得回报和第二步获得的回报进行了权衡，由于机器人即将执行的仅由周围的环境决定，所以我们规定>0.5是为了保证第一步的回报权重较大。否则将会出现因第二步无障碍而忽略第一步障碍的情况。当=1时，更新规则仅由第一步决定，和经典Q-learning算法的更新

14、规则一致。对比公式4和公式5，改进后的Q-learning算法进行了深度的学习，Q-learning算法是一个试错的过程，由于机器人搜索范围有限所以在原始Q-learning算法中仅进行了一步的探索，但是获取了环境的所有信息，我们可以在软件中进行深层的探索。就路径规划问题而言我们最终的目的是找到一条合适道路走到我们想要的终点，改进后的Q-learning算法探索地更远，可以提前发现终点，尽早的更新(s,a)的值。同时，根据这种改进方法，我们也可以改进Q-learning算法使其参考第三步、四步作为更新Q值的参考。4 实验结果与分析4.1 仿真实验结果为了验证算法性能，本文在同一环境中分别对Q-

15、learning算法和改进Q-learning算法进行实验。实验条件：设定折算因子=0.2，深度学习因子=0.6，障碍环境为20×20栅格，学习结果如图7所示。由实验结果我们可以看出Q-learning算法和改进Q-learning算法路径规划结果一致，在上述条件下当Q值不在变化时，Q-learning算法学习次数为50次，改进Q-learning算法的学习次数为40次，效率明显提高。图7 学习结果4.2 对比分析为了更好的说明改进算法的普遍通用性，表1列举了在不同参数条件下算法改进前后需要的学习次数。折算因子越大时，学习次数越多；深度学习因子越大时，改进算法学习次数越多，但改进后的

16、算法收敛速度加快。我们用MATLAB随机生成一个20×20的栅格环境，设定实验条件：=0.4，=0.6，学习结果如图8所示，Q-learning算法学习次数为60次，改进Q-learning算法学习次数为50次。经过大量的仿真实验可以证明改进Q-learning算法对复杂环境有较强的适应能力，在复杂的环境中可以准确快速的规划路径。表1 不同参数下算法改进前后对比折算因子深度学习因子 改进前学习次数改进后学习次数改进后提高的效率0.20.6504020.0%0.20.7504314.0%0.20.8504412.0%0.20.950468.0%0.50.6655613.8%0.50.7

17、655712.3%656511711711711760621081101131137.9%4.6%7.7%6.0%3.4%3.4%图8 学习结果5 结束语本文从实际问题出发，采集实际环境信息作为研究的出发点，对Q-learning算法进行了改进。使用栅格法建立环境模型，简化了运算，分别采用Q-learning算法和改进Q-learning算法对多障碍物环境下移动机器人进行路径规划，对比结果发现改进算法收敛速度加快，对于复杂环境具有较强的适应能力，当栅格维数更多时，改进后提高的效率将会更高，同时改进算法也可以用于其他Q-le

18、arning算法解决的问题，具有一定的通用性。参考文献1 Wei Ru-ming. Research and Implementation of Path Planning for Mobile Robot Based on Reinforcement LearningD.South China University of Technology,2015韦如明. 基于强化学习的移动机器人路径规划研究与实现D. 华南理工大学, 2015.2You Xiao-ming, Liu sheng, Lv Jin-qiu.Ant colony algorithm based on dynamic sear

19、ch strategy and its application on path planning of robotJ. Control and Decision,2017,32(3):552-556.游晓明, 刘升, 吕金秋. 一种动态搜索策略的蚁群算法及其在机器人路径规划中的应用J. 控制与决策, 2017, 32(3):552-556.3Huang Li-xin,Geng Yi-cai.Robot Path Panning Based on Dynamic Potential Field Method.Computer Measurement & Control, 2017, 25

20、(2):164-166. 黄立新, 耿以才. 基于动态人工势场法移动机器人路径规划研究J. 计算机测量与控制, 2017, 25(2):164-166.4Deng Y, Yang G W, Cui X M, et al. Application of Improved Back Propagation Neural Network in Mowing Robots Path PlanningJ. Applied Mechanics & Materials, 2014, 602-605(602-605):916-919.5Chu Jian-hua.Improvement and Appl

21、ications for Q-learning Reinforcement Learning AlgorithmsD.Beijing University of Chemical Technology,2009.褚建华. Q-learning强化学习算法改进及其应用研究D. 北京化工大学, 2009.6Hu Zi-ying.The Study and Improvement of Q-learning Algorithm Based on Agent SystemD.Harbin University Of Science And Technology,2007.胡子婴. 基于智能体系统的Q-学习算法的研究与改进D. 哈尔滨理工大学, 2007.7Yu Hong-bin,Li Xiao-an.Fast Path Planning Based on Grid Model of RobotJ. Microelectronics & Computer, 2005, 22(6):98-100.于红斌, 李孝安. 基于栅格法的机器人快速路径规划J. 微电子学与