动态不确定环境下一种移动 机器人路径规划方法

王 帅

（煤炭科学研究总院沈阳研究院，辽宁 抚顺 113001）

1 引言

动态不确定环境下的路径规划是移动机器人研究的一个重要问题，一直是一个没能妥善解决的难题。所谓动态不确定环境，是指移动机器人只能通过传感器探测其周围有限范围内的环境信息，或者虽然有前验的全局环境信息，但环境中的障碍物是动态变化的。在这种不确定环境下，移动机器人的路径规划大都采用局部路径规划方法，又称动态或在线路径规划。

局部路径规划方法主要有：人工势场法[1]、遗传算法[2]和模糊逻辑算法[3]等。人工势场法结构简单，存在局部极小值问题和抖动问题。遗传算法使用点群进行寻优，在种群数目有限，计算量不大的情况下可以满足实时性的要求。模糊逻辑算法的实时性很好，但是人的经验不一定完备，当输入量增多时，推理规则或模糊表会急剧膨胀。此外还有适用于环境信息完全未知时的滚动窗口法[4]，有效地解决了动态障碍物环境下的机器人运动过程中的避障问题，该方法对障碍物的大小和形状有一定限制。

环境是动态变化的，路径规划方法一定要有学习的能力才能适应环境变化，提高移动机器人的自适应性和智能性。强化学习[5]是一种无监督的在线学习方法，由于其不需要知道环境精确模型，具有实时性和自适应性，因而适应解决动态环境下的移动机器人路径规划问题。采用强化学习算法中的Sarsa学习算法来实现移动机器人在动态未知环境下的路径规划。Sarsa算法适应动态环境下的学习，但其学习速度较慢，基于上述考虑，在Sarsa算法的基础上，引入信度分配函数，提出了信度分配Sarsa算法（Credit Assignment Sarsa，CAS），提高算法的学习速度和自适应能力，可以在动态不确定环境下快速有效地实现路径规划。

2 信度分配Sarsa(CAS)学习算法

2.1 Sarsa学习算法

Sarsa算法是Rummery和Niranjan在1994年提出的[6]，最初被称为改进的Q-learning算法，它仍然采用Q值迭代，Sarsa算法通过反复的实验去学习状态动作对的值函数，一步Sarsa算法可用下式表示

Sarsa与Q-learning的最大差别在于Q-learning采用的是值函数的最大值进行迭代，而Sarsa采用的是实际的Q值进行迭代，此外，Sarsa学习在每个学习步，智能体依据当前Q值确定下一状态时的动作，而Q-learning依据修改后的Q值确定动作，因此Sarsa是一种在策略TD学习。

2.2 信度分配Sarsa(CAS)学习算法

为了提高智能体强化学习的效率和速度，在Sarsa算法中引入信度分配函数[7]，信度分配函用来在各行动规则之间分配报酬，在此算法中，在智能体每次学习中把强化信号分配到为达到某些状态所采取的每一步行动上，根据到目标的距离不同，而分配不同的报酬，信度分配函数的原理如图1所示。

图1 信度分配函数示意图

引入信度分配函数后的Sarsa算法（CAS）的Q值更新规则如下：

当智能体在某一时间段T内经历多步动作后，智能体获得强化信号为R，通过下式来重新修改Q值表：

可以保证此学习算法的收敛。

3 基于CAS学习算法的路径规划

采用CAS算法实现在动态环境下的移动机器人路径规划。强化信号是对学习系统性能的一种评价，用于改善系统的性能。在动态环境下的路径规划的学习中，其目的就是使移动机器人避开动静态障碍物，并以尽可能少的步数到达目标点。CAS算法的核心就是利用Sarsa算法适应动态环境下学习的特性，并引入信度分配函数把强化信号分配给机器人为达到某些状态所采取的每一步行动上，根据到目标的距离不同分配不同的强化信号，来修改Q值，进而修改动作选择策略，实现路径规划。将移动机器人的行为分为4种：到达目标点，漫游寻找目标点，动态障碍物避障，静态障碍物避障。在学习过程中，考虑动作对这4种行为的影响，使这4种行为互相协调融合。

3.1 学习系统对环境的感知

为了实时而准确获得机器人所处环境的信息，解决静态障碍物和动态障碍物的避障问题，机器人必须通过一定数量的传感器来感知局部环境。假定机器人配置有8个测距传感器，传感器分别探测8个不同的方向，这8个方向平分圆周，同时机器人还有1个可以进行360度感知动态障碍物的图像传感器。根据机器人动态路径规划特点，假定机器人在任何时刻都能通过这些传感器感知8个方向上一定距离之内是否存在动态或静态的障碍物，可以通过传感信息测定机器人与动态和静态障碍物之间的距离、动态障碍物的运动速度和运动方向，并假定机器人与动静态障碍物之间的安全距离为D，当距离小于D时，则会发生碰撞。

3.2 学习系统的状态空间和动作空间

环境状态用动态环境中各物体的位置坐标、速度大小和运动方向等参数来描述。这里机器人所处环境的状态空间可以表示为S={sid ，ad，av，aθ}。

机器人的动作空间为在传感器所指的8个方向上{N，S，W，E，NE，SE，NW，SW}前进一定的距离。

3.3 基于CAS学习算法的路径规划算法流程

step1：任意初始化 (,)Qsa；

step2：初始化环境状态s；

step3：获得此时环境状态 ts；

step4：根据Q值表和贪婪策略，获得机器人在ts时的动作 ta；

step5：执行动作 ta，获得下一个状态 1ts+；

step6：根据Q值表和贪婪策略，选择动作 1ta+；

step8：收到强化信号R，按时间信度分配策略分配强化信号 (,)fRt，重新更新Q值表：

①如果步数过界，总步数加1，回到初始位置，转step9；②如果到达目标点，回到初始位置，成功幕数加1，总步数加1，转step9，否则转step2。

step9：如果学习满足预定的结束条件，学习结束，否则转step2。

机器人在动态未知环境中通过传感器感知局部环境信息，做出判断并执行动作，环境给出即时强化信号，机器人根据强化信号来调整动作。在每个时间段，信度分配函数重新分配奖惩的强化信号给这一时间段内所采取的每一步行动上，因为这每一步动作都对最终结果的产生负有责任。当机器人碰撞到障碍物后不返回初始点，在原地寻找其他可行路径，保证能够寻找到目标点。一个学习周期是由若干个学习步骤组成的序列，当满足：①到达目标②达到预定最大步数两个条件中的任何一个时，结束一个周期的学习，如此反复直到规划出最优路径。

4 仿真实验及结果分析

在仿真试验中，移动机器人工作空间为离散化的栅格，每个栅格代表机器人的一种状态。在其中设置静态和动态的障碍物。系统的任务是从任何一个初始位置开始以尽可能少的步数到达目标位置，并且不能和动静态的障碍物发生碰撞，做如下假设：

（1）移动机器人在二维空间内运动。

（2）机器人可以通过传感器系统探测周围一定范围内的环境。

（3）机器人把除了目标点外所有被观测到的对象当作障碍物。

（4）机器人事先不知道动态障碍物的运动特性。

仿真场景如图2所示，环境为20×20的栅格。仿真场景中的黑色区域为静态障碍物，其中十字型黑色区域为动态随机运动的障碍物，其在一定区域内在前后左右4个方向上随机运动，速度恒定且小于机器人运动速度，即环境是动态的。S点为初始点，G为目标点，其每次走过的轨迹被显示出来，每个栅格对应于机器人走过的每一步。环境中的目标是静态的，对于移动机器人而言，环境（即障碍物、边界以及目标的位置）是未知的。以机器人为中心的二维空间内平均分布8个运动方向，代表它的8个可选动作。

图2 仿真场景

对于机器人的学习系统来说，学习的目标有3个：成功避开静态障碍物，成功避开动态障碍物，以最少步数到达目标点。因此机器人强化信号包括三个方面：sR={-10,20,-100,0}，对应条件为{接近静态障碍物，远离静态障碍物，与静态障碍物碰撞，其他}；gR={100,0}，对应条件为{到达目标点，漫游寻找目标点}；aR={-10,20,-100,0}，对应条件为{接近动态障碍物，远离动态障碍物，与动态障碍物碰撞，其他}。

在仿真中取α=0.01，γ=0.95，β=0.4，K=2。仿真结果如图3和4示，可以看出Sarsa算法和CAS算法在动态环境下都能学习到无避碰的成功步数最少的路径，Sarsa算法的学习速度较慢，而CAS算法学习速度明显优于Sarsa算法的学习速度。成功步数最后在23步和24步两个值之间交替变化，这体现出动态障碍物对学习算法的影响。如果环境是静态的，最优步数应是23步，由于动态障碍物的随机运动，其在某一时刻会阻挡机器人沿着23步最短路径移动，此时机器人就会寻找到其他的无碰撞的最短路径，这就是步数为24步的路径，这条路径也是当前环境状态下最优的，随着环境的不同可选择的其他路径数目也会不同。

图3 Sarsa算法成功步数曲线

图4 CAS算法成功步数曲线

成功幕数(episode)是指移动机器人从初始位置开始，通过学习成功到达目标点的一个学习周期，成功步数是指每一幕中机器人成功学习的步数，成功步数越少，说明机器人的行动策略越来越优，路径规划的效率也越来越高。随着学习的不断进行，机器人对动态环境逐渐适应，机器人的行动越来越有效率，避障能力越来越高，成功幕数快速增加，每次成功学习步数呈减小趋势，最终学习到最优路径，这个路径能保证机器人从初始点任一时刻出发都能避开动静态的障碍物，并在当前环境下以最少的步数到达目标点。大量仿真实验都表明，当环境变得较为复杂时，CAS算法的规划效果也很好，这说明算法的自适应性较强。

5 结论

本文提出了一种基于信度分配的Sarsa学习算法。通过信度分配函数的引入来有效分配强化信号，进而修正动作选择策略，有效地提高了Sarsa算法的学习效率和速度，节省了学习时间，实现了在动态不确定环境下的移动机器人路径规划，仿真试验说明该方法的有效性和可行性。接下来的主要工作是如何在环境特别复杂、路径规划的学习空间很大情况下，有效提高算法的学习效率和收敛速度。

[1] Khatib O.Real-time obstacle avoidance for manipulators and mobile robot [J].The International Journal of Robotic Research,1986,5(1)：90-98.

[2] M Gemeinder,M Gerke.GA-based Path Planning for Robot System Employing an Active Search Algorithm [J].Applied Soft Computing,2003(3)：149-158.

[3] 庄晓东,孟庆春,殷波等.动态环境中基于模糊概念的机器人路径搜索方法[J].机器人,2001,23(5)：397-399.

[4] 张纯刚,席裕庚.动态未知环境中移动机器人的滚动路径规划及安全性分析[J].控制理论与应用,2003,20 (1)：37-44.

[5] Sutton R S,Barto A G.Reinforcement Learning：An Introduction [M].Cambridge,MA：MIT Press,1998.

[6] Rummery G,Niranjan M.On-line Q-learning using connectionist system.Technical Report CUED/FINFENG/ T-R166,Cambridge University EngineerIng Department,1994.

[7] 吴继伟,萧蕴诗,许维胜.基于信度分配的Agent强化学习算法[J].同济大学学报,2003,31(8)：947-950.

[8] Miyazaki K,Yamamura M,Kobayashi S.On the rationality of profit sharing in reinforcement learning [A].Proc of the 3rd International Conference on Fuzzy Logic Neural Net and Soft computing,1994：285-288.