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

高 乐, 马天录, 刘 凯, 张宇轩

(吉林大学 仪器科学与电气工程学院, 长春 130012)

0 引 言

移动机器人可在人类不可到达或危险未知的地方完成任务, 已经成功运用于很多领域。在移动机器人研究领域中路径规划是一个关键的问题[1]。目前路径规划问题已有很多方法可以借鉴, 如蚁群算法、 人工磁场法、 神经网络法等[2-4]。笔者采用Q-Learning算法进行最优路径规划, 即指在可满足预先设定的条件时, 从起点出发沿最短路径不经过障碍物到达终点。

Q-Learning算法是环境未知条件下的有效强化学习算法, 它的迭代是个试错和探索的过程, 其收敛的一个条件是对每个可能的状态动作对都进行多次尝试, 最终学到最优的控制策略。Q-Learning算法因其不需要建立环境的模型而简单易用, 已在非线性控制、 机器人规划、 人工智能问题求解、 组合优化和调度制等领域中得到应用。针对不同的应用方向很多人提出了改进的方法[5,6], 改进后算法的学习效率都得到了一定的提高, 但其改进的方法比较繁琐。

Q-Learning算法应用于路径规划时[7], 存在着学习效率低、 收敛速度慢等缺点, 且相关研究大多停留在理论层面, 缺少对实际问题的解决方案。笔者对Q-Learning算法做出改进, 在原有算法上增加了一层学习过程, 可提早发现障碍物和目标位置, 提前进行决策。并将其应用于多障碍物环境下移动机器人的路径规划, 使其在短时间内以最优路径从起点移动到终点, 并且验证了改进算法的高效性, 为Q-Learning算法的改进提供了新思路。

1 环境建模

1.1 栅格法建模

栅格法简单有效, 对环境的适应能较力强, 可减少建模的复杂性, 便于计算机分析处理, 也可进行直观判断, 已被广泛用于环境建模方法中[8,9]。笔者通过建立一个n×m的栅格, 结合二维直角坐标系确定栅格位置, 并对每个栅格从左至右, 从上到下依次标明序号。一个3×4的栅格如图1所示。

1.2 问题描述

笔者利用摄像头采集环境信息, 识别障碍物； 根据获取的实际信息采用栅格法建立环境模型, 设定起点与终点, 采用Q-Learning算法进行路径规划, 根据规划结果控制机器人行走, 整体设计如图2所示。

图1 3×4栅格 图2 整体设计框图 Fig.1 3×4 grid Fig.2 Overall design block diagram

获取并处理后图像如图3所示, 图3a为摄像头获取的图像, 图3b为Matlab处理后的图像。从处理后的图像已能清楚获取障碍物的位置坐标, 由于采集的图像像素点过多, 如果以像素点为单位进行计算会增加运算量, 同时机器人体积较大, 对单个像素点计算也没有意义。因此, 笔者对Matlab处理后的图像分块处理。

a 实际图像 b 处理后图像图3 获取并处理后图像Fig.3 Images acquired and processed

设机器人最大尺寸可占m个像素点, 对图像以m个像素为单位进行分块

分块处理后每块对应的坐标最大值为

其中r,c分别为获取实际环境图片的横向、 纵向像素点数,J为向上取整函数。block[x][y]为1则为障碍栅格, 用黑色表示； block[x][y]为0则为自由栅格, 用白色表示。分块结果如图4所示。

由于机器人的搜索范围有限, 为了简化运算, 笔者规定机器人当前的状态只能选择上、 下、 左、 右操作, 而对于边、 角的特殊位置可选择的操作更少(见图5)。

图4 分块处理后的栅格图 图5 机器人位置信息 Fig.4 Image divided into block Fig.5 Robot position information

2 Q-learning算法基本原理

笔者的环境可建模为一个确定性马尔可夫决策过程, 以下叙述在此条件下Q-Learning算法的基本原理[10-13]。

设学习每个状态-动作对〈s,a〉的评价值为Q(s,a)。评价函数Q(s,a)定义为： 其值是从状态s开始到执行第1个动作a时的最大折算累积回报。即Q(s,a)的值从状态s执行动作a的立即回报加上之后遵循最优策略的回报值。

图6 Q-Learning算法与环境交互模型Fig.6 The alternation process model of Q-Learning and environment

3 改进Q-Learning算法的路径规划

其中α称为深度学习因子,Q(s′,a′)为下一步状态-动作对〈s′,a′〉对应的Q值,Q(s″,a″)为下两步状态-动作对〈s″,a″〉对应的Q值。

α的取值范围为(0.5,1), 此处引入的深度学习因子α的作用在于保证Q值的收敛。更新的学习规则利用深度学习因子α对第1步获得的回报和第2步获得的回报进行权衡, 由于机器人即将执行动作仅由周围的环境决定, 所以规定α>0.5保证第1步的回报权重较大。否则将会出现因第2步无障碍而忽略第1步障碍的情况。当α=1时, 更新规则仅由第1步决定, 和经典Q-Learning算法的更新规则一致。

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次, 效率明显提高。

4.2 对比分析

为说明改进算法的普遍通用性, 表1列举了在不同参数条件下算法改进前后需要的学习次数。折算因子γ越大, 学习次数越多； 深度学习因子α越大, 改进算法学习次数越多, 但改进后的算法收敛速度加快。

表1 不同参数时算法改进前后对比

用Matlab随机生成一个20×20的栅格环境, 设定实验条件：γ=0.4,α=0.6, 学习结果如图8所示。Q-Learning算法学习次数为60次, 改进Q-Learning算法学习次数为50次。仿真实验证明, 改进Q-Learning算法对复杂环境有较强的适应能力, 在复杂的环境中可准确快速地规划路径。

图7 实际环境下的学习结果 图8 随机环境下的学习结果 Fig.7 Learning results in the actual environment Fig.8 Learning results in random environment

5 结 语

笔者从实际问题出发, 采集实际环境信息作为研究出发点, 对Q-Learning算法进行了改进, 使用栅格法建立环境模型, 简化了运算。分别采用Q-Learning算法和改进Q-Learning算法对多障碍物环境下移动机器人进行路径规划, 对比结果证明改进算法收敛速度加快, 对于复杂环境具有较强的适应能力。当栅格维数更多时, 改进后提高的效率将会更高。同时改进算法也可用于其他Q-Learning算法解决的问题, 具有一定的通用性。