张婷宇　郑宝娟

摘 要 采用滚动Q学习的方法解决大规模环境下机器人视野域范围有限，同时有效改善因 Q 学习的状态空间增大而产生的维数灾难等问题。仿真实验结果表明，应用该算法机器人可在复杂的未知环境中快速地规划出一条从起点到终点的优化避障路径， 效果令人满意。

关键词 路径规划 滚动学习 Q学习 智能算法

中图分类号：TP242文献标识码：A

0引言

目前，大多数自主移动机器人均是在高度结构化的环境中执行预先规定的动作序列，但在新的环境下或遇到意外情况时，却不能很好地完成指定任务，其主要原因是当机器人面对非结构化且存在不确定性的实际环境时没有主动学习和自适应的能力。自适应路径规划可以部分解决这一问题，即机器人在与环境的不断交互过程中，规划出一条从指定的起始点到目标点，并且满足一定优化标准的、安全避障的路径。该算法是机器人应用研究的一个重要方面，属于NP-hard问题。针对上述研究现状及不足，本文提出了滚动Q学习机器人路径规划算法，以滚动学习算法来解决Q学习可能发生的维数灾难问题。

1基于滚动的 Q 学习算法

算法的基本思想是充分利用机器人实时探测到的局部环境信息，以滚动方式分別在各个规模较小的视野域内进行 Q 学习，并得到一条该视野域内的局部最优路径。机器人沿该路径前进一段距离后 （该距离长度记为 ），在新的视野域内重新获取动作-状态对进行 Q 学习， 并规划当前路径。这样，在一条条局部最优路径的导航下，机器人最终沿着一条全局优化的避碰路径到达终点。

在视野域内障碍物较少时，机器人走1/3长的局部路径后才在新的视野域内继续规划新路径;在障碍较多时，每走2步再重新规划新路径;只有在障碍物很多时，机器人走1步后即重新规划。 的取值很难有一个严格的最优界定，它只能是根据实验结果抽象出比较保守的值，其取值原则是必须能保证各个局部路径叠加后仍能使全局路径最优或近似最优。此外，算法得到的路径是否近似最优，会受到视野域尺寸大小的影响。若将视野域半径设置过小，则机器人获得的环境信息将过于局部化，规划过程容易陷入局部最小;若将视野域半径设置过大，则又使状态-动作对大增，降低算法的收敛速度。因此本实验中对于算法中的视野域半径参数是根据大量实验的经验来设定的。大量的实验结果表明，一般视野域半径范围取整个工作环境半径的 1/10 左右为适。

Step 1：设置起点gstart和终点gend，并初始化工作环境WS，机器人的视野半径r，以及保守阈值n1和n2;

Step 2：若机器人在当前视野域内探测到gend，则用新算法规划出一条从机器人当前位置到gend的优化路径，规划算法终止;

Step 3：产生gsub，机器人以PR为出发点，gsub为终点，用滚动Q学习算法规划出一条局部优化路径，并记录下该路径长度local_pathlen;

Step 4：计算Pobstacle、 ，机器人沿局部规划路径行进;

Step 5：根据机器人当前位置PR和视野半径r更新视野域，并对视野域内环境作栅格化处理，转至Step 2。

2仿真实验

通过仿真实验来验证本文提出算法的有效性和先进性。实验环境为 Windows XP， Intel（R） Core（TM）2Duo CPU T6400 2.00 GHz， 2G 内存，编译工具为VC++6.0。

为了验证在较大规模环境下全局滚动 Q 学习算法的效果，在 50 ？50 的未知环境下做了大量的实验，效果令人满意。以半径为r = 5的机器人为例，即 实时地进行动态调整。根据大量实验总结的经验，设置 n1= 0.3，n2= 0.7。在第1个视野域内，机器人用滚动算法规划出一条局部路径记为 l1，并计算出 Pobstacle= 0.25 < n1，所以机器人将 设为l1长度的1 /3 （即 = 3）;然后沿l1前进3步后，再根据新的 视野域重新映射子目标并规划路径，重新计算 ;重复上述过程;直到探测到 gend并规划完最后一段路径为止。

3结论

在未知环境下采用标准的Q学习算法进行机器人路径规划时，由于缺乏对环境的先验知识，使得算法速度缓慢，特别是随着环境规模增大，学习状态空间增大，甚至会发生维数灾难。为此，本文提出了滚动Q学习算法，该算法在未知较大规模环境下进行滚动学习，采取这些措施后，大幅提高了算法的收敛速度和环境适应能力。仿真实验结果表明该算法的效果令人满意，具有算法简单、速度快、环境适应性强等特点。特别是当机器人对复杂环境中障碍物信息一无所知以及环境规模较大时，更能体现该算法的优越性。该算法具有自学习和自适应能力，是一种很有发展前景的算法。

参考文献

[1] Ahuh，D，J&J.H.Park.Path planning and navigationfor autonomous mobile robot[C].IEEE 28th the AnnualConf of the Industrial Electronics Society. Seville： IEEEPress，2002：1538-1542.

[2] Vladimiro Miranda， Nuno Fonseca. EPSO-evolutionaryparticle swarm optimization， a new algorithm withapplication in power systems[C]. Transmission andDistributionConf and Exhibition.Yokohama，2002：745-750.

[3] 宋清昆，胡子婴.基于经验知识的 Q-学习算法[J].自动化技术与应用，2006，25（11）：10-12.