基于改进Q-learning算法的移动机器人局部路径规划
时间：2023-04-16 10:25:04 来源：柠檬阅读网 本文已影响 人 
张耀玉，李彩虹，张国胜，李永迪，梁振英
(山东理工大学 计算机科学与技术学院, 山东 淄博 255049)
随着科学技术的快速发展，移动机器人的应用越来越广泛。在移动机器人的研究中，机器人避障并且规划有效路径是至关重要的问题[1]。移动机器人的路径规划分为全局路径规划[2]和局部路径规划[3]。全局路径规划是在静态已知环境信息下，寻找一条从起点到目标点的无碰撞最优路径。局部路径规划是在未知或部分已知环境信息下，在移动过程中利用传感器等检测环境信息进行实时路径规划。
当前有效避障的路径规划方法有很多，传统方法主要有A*算法[4]、Dijkstra算法[5]、模糊控制法[6]、遗传算法[7]、人工势场法[8]和神经网络[9]等。而智能算法的应用在很大程度上解决了传统算法效率低下、操作复杂等缺点。Q-learning算法是Watikins提出的一种强化学习算法[10]，在移动机器人路径规划领域中应用广泛，具有不依赖环境先验模型的特点；
缺点是算法收敛速度较慢，在训练次数不够多时找不到最优路径。因此，高乐等[11]在Q-learning算法的基础上增加了一层学习过程，对环境进行了深度学习，提高了算法的收敛速度。毛国君等[12]引入了动态搜索因子ε，根据环境的反馈来动态调整贪婪因子ε，当探索路径失败时，增大ε使下一次探索的随机性增大；
反之，则通过减少ε来增加目的性，该方法有效地减少了迭代搜索的代价，能够找到更优的路径。Oh等[13]采用基于模糊规则的Q-learning算法指定Q值，然后与传统的Q-learning算法相融合来加速算法的学习效率，以更少的迭代次数获得良好的结果。Lillicrap等[14]以神经网络来拟合Q-learning中的Q(s,a)，然后采用经验回放和目标网络的方法来改善Q-learning算法收敛稳定性。
本文针对传统的Q-learning算法存在的学习速度慢、效率低等问题，提出一种改进的IQ-learning算法，实现移动机器人的局部路径规划。在传统Q-learning算法的基础上，增加对角线运动奖励值，减少算法在初始阶段盲目搜索问题，减少规划路径的长度，提高路径的规划效率，使移动机器人在更短时间内找到一条从起点到目标点的较优路径。
强化学习是从环境状态到动作映射的学习，使动作从环境中获得的奖励最大，其工作原理如图1所示。强化学习基于马尔可夫决策过程(Markov decisions process, MDP)[15]。马尔可夫属性是指系统的状态只与当前状态有关，而与更早之前的状态无关。
图1 强化学习工作原理
Q-learning算法是强化学习算法之一，是基于Q值迭代的无模型算法。通过不断迭代，对每个可能的状态动作进行多次尝试，最终学到最优的控制策略[16]。迭代过程中不断对Q值更新，Q值的更新公式为
newQ(s,a)=(1-α)Q(s,a)+α(R(s,a)+
γmaxQ"(s",a")),
(1)
式中：s和s"分别代表当前状态和下一个状态；
a代表s到s"的有效动作；
Q(s,a)代表当前状态s和动作a的Q值；
R(s,a)是指当前状态s和动作a的奖励；
maxQ"(s",a")代表下一个状态下所有动作中最大的Q值；
α表示学习率，α越大，Q值收敛越快，但也越容易产生振荡，本文α取0.6。根据式(1)，Q-learning算法在某个状态下采取贪心策略对所有可能路径进行探索，每前进一步都在寻找当前状态下的局部最优解。
本文所设计的IQ-learning算法在Q-learning算法基础上，在奖惩函数中添加对角线运动奖励值，使得移动机器人在路径规划时减少盲目搜索，提高算法的学习效率。
2.1 栅格地图设计
本文基于栅格地图构造机器人的运行环境。运行环境为20×20的八连通栅格地图，结合二维直角坐标系确定栅格位置，并对每个栅格从下到上、从左到右依次标明序号，行和列的交叉位置代表地图信息中的一个环境状态。在栅格地图中设置移动机器人的运行环境，包括障碍物、起点和目标点，如图2所示。对于移动机器人来说，这些障碍物的位置信息未知，机器人在学习过程中根据执行动作后得到的奖惩值来确定障碍物的位置信息。
图2 栅格地图
2.2 状态-动作的表示
设定移动机器人的起点和目标点后，将移动机器人看作一个质点，机器人在运行环境中的每个坐标表示一个状态，记为st，坐标记为Φ(i,j)。根据栅格地图的维数，共有Xlim×Ylim个状态,其中lim∈[1,20]，lim为整数。所有状态组成的状态集S为
S={st|st=Φ(i,j),i∈Xlim,j∈Ylim}。
(2)
一般情况下，移动机器人的探索为上、下、左、右4个动作。为提高算法探索效率，增加对角线方向的探索行为，即以该质点为中心，定义移动机器人可以执行8个方向上的动作，记为ai(i=1～8)：上、下、左、右、右上、右下、左上和左下，机器人可以按照以上8个动作移动，平移一格的步长为1，对角线移动一格的步长约为1.4，如图3所示。动作集合A记为
图3 动作空间
A={ai,i=1～8}。
(3)
机器人选择不同的动作执行后，状态会发生不同的改变，分别执行8个动作时所对应的状态变换见表1。
表1 状态-动作关系表
2.3 Q表的设计
建立一个二维表，用来存储Q值，其中行表示每种状态s，列代表每种状态的动作a，Q值是某一状态下执行某种动作获得的奖励。根据移动机器人Xlim×Ylim个状态、8个动作建立的Q表为
(4)
Q表建立后将其初始化，经过训练不断迭代更新，根据最终的Q表进行最优路径的选择。
2.4 奖惩函数的设计
奖惩函数R的设置对移动机器人的行动具有导向作用。为提高算法寻找最优路径的效率，本文增加对角线移动的奖励值，奖惩函数的设计为
(5)
2.5 动作策略的选择
动作策略采取ε-greedy改进的贪心策略，在移动机器人做决策时，有ε的概率随机选择未知的一个动作，剩下的1-ε的概率选择已有动作中价值最大的动作，公式为
π(a|s)=
(6)
式中：ε是小于1且很小的正数；
a表示机器人的动作；
s表示机器人的状态；
A(s)表示机器人处于某个状态下可以选择的动作集合。这种策略可以均衡利用与探索，采用回报值最大的动作值为利用，其他非最优的动作值有一定概率继续探索。
2.6 IQ-learning算法的训练过程
基于栅格地图设计IQ-learning算法，完成移动机器人局部路径规划任务，算法学习步骤如下：
1) 清空二维环境地图，给定移动机器人起点、目标点和障碍物信息。建立Pmat线性表，用来存储从起点到目标点的历史最佳状态-动作对；
Q表存储当前学到的从起点到目标点的最佳状态-动作对；
len记录当前最短路径长度；
min_total_steps记录历史最短路径的长度。
初始化奖惩函数，学习次数i=0，最大学习次数Nmax=80。初始化Pmat线性表及历史最短路径长度min_total_steps=Nmax。
2)设置迭代计数器初始值count=0，len=Nmax，清空Q表。
3)根据式(6)动作选择策略选择一个动作a执行，执行完动作a后，机器人状态转为st +1，count++。若此时机器人已到达目标点，则转到步骤6)；
否则转到步骤4)。
4)根据式(5)奖惩函数计算当前状态的奖惩值。若机器人收到奖励则转到步骤5)；
若机器人收到惩罚，则机器人退回上一个状态s=st并转到步骤3)继续探索。
5)按照式(1)更新Q值，并转到步骤3)继续探索。
6)记录迭代次数count值、当前最短路径长度len，更新Q表，且i++。
7)更新Pmat表与min_total_steps的值。若学习次数i 本文将分别在离散型障碍物、一字型障碍物、U型障碍物和混合型障碍物环境下，对所设计的IQ-learning算法的规划路径进行仿真，测试算法的可行性。在所设计的栅格地图中设置移动机器人的起点和目标点，根据不同的环境设置不同的障碍物，在同一环境下对比Q-learning算法和IQ-learning算法训练80次得到的最短路径。 IQ-learning算法在离散型障碍物环境下的训练过程如图4所示，图中蓝色圆点代表算法在探索路径的过程中走过的栅格位置。由图4可以看出，随着算法训练次数的增多，学习到的规划路径越来越好，路径长度逐渐收敛到最短。 图4 离散型障碍物环境下的训练过程 Q-learning算法和IQ-learning算法训练80次得到的最短路径如图5所示，由图5可以看出,Q-learning算法训练得到的路径在坐标(7,8)处存在步数浪费的现象，此时路径长度为20.8； 图5 离散型障碍物环境下的路径规划 移动机器人在一字形障碍物环境下规划路径时容易陷入对称冗余状态。IQ-learning算法在一字型障碍物环境下的训练过程如图6所示。从图6可以看出，随着算法训练次数的增多，机器人逐渐走出对称冗余状态，并从中选择了最短路径。 图6 一字型障碍物环境下的训练过程 Q-learning算法和IQ-learning算法训练80次得到的最短路径如图7所示，由图7可以看出，Q-learning算法存在多处步数浪费现象，算法训练得到的路径长度为26.4； 图7 一字型障碍物环境下的路径规划 移动机器人在U型障碍物环境下规划路径时，因为传感器信息感知的局限性，机器人容易陷入死锁状态，而找不到最优路径。IQ-learning算法在U型障碍物环境下的训练过程如图8所示。从图8可以看出，随着算法训练次数的增多，机器人不再进入U型区域，规划的路径长度也越来越短。 图8 U型障碍物环境下的训练过程 Q-learning算法和IQ-learning算法训练80次得到的移动机器人最短路径如图9所示。由图9可以看出，Q-learning算法学习80次得到的训练路径较长，在坐标(3,5)和(9,10)处有步数浪费现象，此时路径长度为27； 图9 U型障碍物环境下的路径规划 混合障碍物环境包括离散障碍物、一字型障碍物和近似U型障碍物。IQ-learning算法在混合型障碍物环境下的训练过程如图10所示。从图10可以看出，随着算法训练次数的增多，机器人能够摆脱U型和一字型障碍物的阻碍，路径逐渐收敛，最后学习到更短的路径。 图10 混合型障碍物环境下的训练过程 Q-learning算法和IQ-learning算法训练80次得到的移动机器人最短路径如图11所示。由图11可以看出，Q-learning算法经过80次学习得到的最短可行路径在坐标(14,13)处，有明显的步数浪费，规划的路径较长，此时路径长度为23.6； 图11 混合型障碍物环境下的路径规划 经过以上仿真验证，本文提出的IQ-learning算法能够减少移动机器人在局部路径规划中的路径长度，不进入死锁或陷阱区域。在不同环境下两种算法的路径长度对比见表2。 表2 不同环境下的路径长度 实验中，Q-learning算法和IQ-learning算法都经过80次学习得到最短路径。在混合型障碍物环境下，记录了Q-leaning算法和IQ-learning算法的路径长度变化趋势，如图12所示，由图12可以看出Q-learning算法在训练40次后路径长度趋于收敛，而IQ-learning算法在训练20次后，路径长度明显下降并趋于收敛。IQ-learning算法相较于Q-learning算法能在更少的训练次数内找到较优的路径，加快了收敛速度。 图12 路径长度变化趋势对比 本文基于栅格地图环境对Q-learning算法进行改进，加入对角线运动奖励值，使得移动机器人在规划路径中能够以更少的训练次数得到更优的路径。通过改进后的IQ-learning算法和Q-learning算法在同一障碍物环境和同样训练次数下的仿真实验结果对比，IQ-learning算法训练得到的路径长度更短，其收敛速度也有所提高，验证了IQ-learning算法的可行性。 然而随着移动机器人所处环境状态越来越复杂，使用Q值表存储状态-动作值函数的缺点越来越明显，会引起维数灾难。下一步的研究工作是利用函数近似逼近来替代Q值表，增强算法的可行性和通用性。3.1 离散型障碍物环境下的路径规划仿真
而IQ-learning学习80次得到的机器人规划路径更短，此时路径长度为19.4。
3.2 一字型障碍物环境下的路径规划仿真
IQ-learning算法训练得到的路径更短，其路径长度为22.8。
3.3 U型障碍物环境下的路径规划仿真
而IQ-learning算法学习80次后得到的路径更优，此时路径长度为24.8，路径长度明显减少。
3.4 混合型障碍物环境下的路径规划仿真
IQ-learning算法学习80次得到的路径更短，此时训练得到路径长度为22.8。
