计算机专业Q-learning算法在路径规划中的应用.doc

改进Q-learning算法在路径规划中的应用 摘 要：Q-learning算法是环境未知条件下的有效强化学习算法，该算法在路径规划中被广泛应用。针对Q-learning算法在离散状态下存在运行效率低、学习速度慢等问题，提出一种改进的Q-learning算法，在栅格环境下进行仿真实验，并成功地应用在多障碍物环境下移动机器人路径规划，结果证明了算法的可行性。改进Q-learning算法可以以更快的速度收敛、学习次数明显减少、效率最大可提高20%。同时该算法框架对解决同类问题具有较强的通用性。 关键词：路径规划；改进Q-learning算法；强化学习；栅格法；机器人 中图分类号：TP391 文献标志码：A Application of improved Q-learning algorithm in path planning Abstract: Q-learning algorithm is an effective 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 has 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 framework 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年），女，高工，博士. 研究方向：智能仪器与微弱信号采集技术. E-mail:qianch@ 0 引言 移动机器人可以在人类不可到达或危险未知的地方完成任务，已经成功的运用在很多领域，在移动机器人研究领域中路径规划是一个关键的问题[1]。路径规划问题已经有很多方法可以借鉴，如蚁群算法、人工磁场法、神经网络法等[2-4]。本文采用改进的Q-learning算法进行最优路径规划，即指在可以满足 预先设定的条件的同时，从起点出发沿最短路径不经过障碍物到达终点。 Q-learning算法是环境未知条件下的有效强化学 习算法，它的迭代是一个试错和探索的过程，其收敛的一个条件要求对每个可能的状态动作对都多次尝试，最终学到最优的控制策略。Q-learning算法因其不需要建立环境的模型、算法简单、易于使用，已在非线性控制、机器人规划、人工智能问题求解、组合优化和调度制等领域中得到应用。针对不同的应用方向很多人提出了改进的方法[5-6]，改进后算法的学习效率都得到了一定的提高，但其改进的方法比较繁琐。 Q-learning算法应用于路径规划时，存在着学习利率低、收敛速度慢等缺点，且相关研究大多停留在理论层面，缺少对实际问题的解决和实践。本文对Q-learning算法做出改进，并将其应用在多障碍物环境下移动机器人的路径规划，使其在短时间内以最优路径从起点移动到终点。验证了改进算法的高效性，为Q-learning算法的改进提供了新的思路。 1 建立环境模型 1.1 栅格法建模 栅格法简单有效，对障碍物的适应能力强，可减少建模的复杂性，便于计算机存储与处理，也可以直观进行视觉判断，已被广泛用于环境建模方法中[7-8]。本文通过建立一个n×m的栅格，结合二维直角坐标系来确定栅格位置，并对每个栅格从左至右，从上到下依次标明序号。如图1建立一个3×4的栅格。 图1 3×4栅格 1.2 问题描述 本文利用摄像头采集环境信息、识别障碍物、根据获取的实际信息采用栅格法建立环境模型、设定起点与终点、采用Q-learning算法进行路径规划、根据规划结果控制机器人行走，如图2所示。 采 集 环 境 信 息 栅格法建模 设定起点终点 规划路径 执行行走命令 图2 整体设计框图 如图3所示，a图为摄像头获取的图像，b为MATLAB处理后的图像。从处理后的图像已经能够清楚的知道障碍物的位置坐标，由于采集回来的图像像素点过多，如果以像素点为单位进行计算势必会增加运算量，同时机器人体积较大，对单个像素点计算也没有意义。因此，本文对MATLAB处理后的图像分块化处理。 设机器人最大尺寸可占m个像素点，对图像以m个像素为单位进行分块： (1) (2) 其中，x，y分别为分块处理 后每一块对应的坐标，r，c分比为获取实际环境图片的横向、纵向像素点数，公式(2)所求为x，y的最大值，ceil为向上取整函数，为1则为障碍栅格，用黑色表示，为0则为自由栅格，用白色表示，分块结果如图4所示。 (a) 实际图像 (b) 处理后图像 图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的立即回报加上以后遵循最优策略的值。 (3) 其中，γ∈（0,1）称为折算因子，r(s,a)为状态s执行动作a得到的奖励。这个Q函数的定义提供了Q-learning算法的基础[11]。为了描述此算法，实际Q函数的估计使用符号来指代。在此算法通过一个大表表示其估计值，其中对每个状态－动作对有一表项。状态－动作对〈s,a〉的表项中存储了(s,a)的值，即对实际的但未知的Q(s,a)值的当前估计。此表可被初始为随机值。重复地观察其当前的状态s，选择某动作a，执行此动作，然后观察结果回报以及新状态。然后遵循每个这样的转换更新(s,a)的规则： (4) 此训练法使用智能体对新状态s'的当前值来计算其对前一状态s的(s,a)的值。上述是对于确定性马尔可夫决策过程的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)的更新规则如下： (5) 其中, γ∈（0,1）称为折算因子, α称为深度学习因子，Q(s',a' )为下一步状态－动作对〈s',a' 〉对应的Q值，Q(s'',a'' )为下两步状态－动作对〈s'',a'' 〉对应的Q值。 α的取值范围为（0.5,0.1），此处引入的深度学习因子α的作用在于保证Q值的收敛。更新的学习规则利用深度学习因子α对第一步获得回报和第二步获得的回报进行了权衡，由于机器人即将执行的仅由周围的环境决定，所以我们规定α>0.5是为了保证第一步的回报权重较大。否则将会出现因第二步无障碍而忽略第一步障碍的情况。当α=1时，更新规则仅由第一步决定，和经典Q-learning算法的更新规则一致。 对比公式4和公式5，改进后的Q-learning算法进行了深度的学习，Q-learning算法是一个试错的过程，由于机器人搜索范围有限所以在原始Q-learning算法中仅进行了一步的探索，但是获取了环境的所有信息，我们可以在软件中进行深层的探索。就路径规划问题而言我们最终的目的是找到一条合适道路走到我们想要的终点，改进后的Q-learning算法探索地更远，可以提前发现终点，尽早的更新(s,a)的值。同时，根据这种改进方法，我们也可以改进Q-learning算法使其参考第三步、四步作为更新Q值的参考。 4 实验结果与分析 4.1 仿真实验结果 为了验证算法性能，本文在同一环境中分别对Q-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列举了在不同参数条件下算法改进前后需要的学习次数。折算因子γ越大时，学习次数越多；深度学习因子α越大时，改进算法学习次数越多，但改进后的算法收敛速度加快。 我们用MATLAB随机生成一个20×20的栅格环境，设定实验条件：γ=0.4，α=0.6，学习结果如图8所示，Q-learning算法学习次数为60次，改进Q-learning算法学习次数为50次。经过大量的仿真实验可以证明改进Q-learning算法对复杂环境有较强的适应能力，在复杂的环境中可以准确快速的规划路径。 表1 不同参数下算法改进前后对比 折算因子 深度学习 因子 α 改进前 学习次数 改进后 学习次数 改进后提高的效率 0.2 0.6 50 40 20.0% 0.2 0.7 50 43 14.0% 0.2 0.8 50 44 12.0% 0.2 0.9 50 46 8.0% 0.5 0.6 65 56 13.8% 0.5 0.7 65 57 12.3% 0.5 0.5 0.8 0.8 0.8 0.8 0.8 0.9 0.6 0.7 0.8 0.9 65 65 117 117