基于区域扩张策略的势场强化学习算法路径规划研究

阳 杰，张 凯

（西安工程大学电子信息学院，西安710600）

1 引 言

近年，国内外学者对解决智能体路径规划方面进行了广泛的研究[1]。在早期研究中，常用的路径规划算法有栅格法、引力-排斥力势场法、几何构造法、约束条件下的图解法、基于时间窗动态窗口法[2]等。随着研究深入与人工智能的产生，产生了多种智能路径规划算法，如基于遗传因子的遗传算法[3]、基于粒子适应度的粒子群算法[4]、基于信息素的蚁群算法[5]等，然而传统的路径规划方法在解决规划寻优上都稍有不足。在解决复杂的环境路径规划时，基本智能路径规划算法易于陷入局部最优解，无法避免规划出现局部最优解，得到结果只是次优解；传统的人工智能算法在解决复杂环境路径规划寻优问题时，处理优化的数据量庞大，需要通过反复迭代，不断从初始位置进行探索才能得到最佳的路径。

强化学习算法是根据执行动作，将环境状态改变反馈给智能体奖励值，来提高探索寻优的路径规划能力。它通过对环境探索的不断试错来寻找目标点，通过对所有到达目标点路径优化处理得到最优路径，对未知环境具有较好的效果，具有广阔的应用前景，但在针对复杂度较高的未知环境求解时，经典Q 值的获得仍然很困难。针对算法规划寻优问题，研究者提出了多种初始化Q 值函数以及增加环境先验知识的方法来加快路径规划收敛速度，例如神经网络初始化训练Q 值法、基于模糊规则初始Q 值计算法[6]、基于人工势场法初始化状态信息[7-9]等。基本的人工势场法实施简单，能快速求解问题，但在大规模复杂未知障碍物环境中势场力多，对之一一分析计算合力，会令工作量大增。

针对Q-learning 算法收敛慢、易陷入局部最优、凹型障碍物探索能力差等问题，在此提出基于人工势场与Metropolis 准则的先验知识信息以及区域扩展的Q 学习算法，旨在增强Q 学习算法对初始环境状态探索感知能力，避免智能体在路径探索中陷入凹形等障碍物环境而发生机器人锁死等情况，并通过仿真实验，验证改进算法在解的质量和收敛速度上的表现情况。

2 栅格法建立仓储环境模型

在理想状态下进行路径规划不必考虑规划路面是否是平坦，智能体也无需考虑具体行走姿态。为了能够使用DL 算法，需要首先基于这个空间抽象定义出DL 算法中的环境，机器人在某一单元格需要动作决策时，由强化学习算法提供状态决策[10]。

为便于研究，把复杂三维空间简单化降维并离散化成一个二维栅格地图，再将智能体质点化，以一个质点代表机器人。在栅格地图一般分为可行区域部分和障碍物部分，以0 和1 区分不同栅格。在栅格地图中0 表示障碍物栅格，智能体不可行驶；1表示智能体可通行栅格。为了智能体路径规划研究的方便，将连续的状态环境空间离散化处理，建立栅格化地图模型。进一步地，建立仓储栅格地图环境模型，如图1 所示。在此环境模型中仿真验证本文法，为算法在实际环境的应用提供辅助参考。

图1 仓储栅格地图环境模型

在这一栅格环境中，机器人在某一个位置预测的下一步动作栅格节点共8 个，以每个机器人所在的栅格坐标点为准，机器人行驶方向如图2 所示。

图2 机器人运动范围

图1 中，机器人坐标（1，1）是第一个栅格，栅格序号为1。按照从左到右，从下到上排序，可得序号7的栅格坐标是（7，1）；也可以由栅格坐标为（7，1）得到栅格序号是7。

3 算法解析

3.1 Q-learning 算法

强化学习主要由智能体、环境、状态、动作、奖励值组成，其基本结构模型如图3 所示。Q-learning 是强化学习算法中基于价值的算法。Q 是智能体在状态s(s∈S)下，通过动作a(a∈A)获得奖励值的收益期望函数，环境会对据Agent 的动作反馈，给予相应的回报r。算法的主要思想是基于环境状态信息S与智能体动作A 构建一个表格来存储Q 值，将其称为Q 值表，智能体的动作选择根据Q 值表，使得优化选择出收益最大的动作。

图3 强化学习结构模型

Q-learning 算法将值函数V(s)进一步细分为了“状态-动作”对的值函数Q(s,a)，即原本状态s 上的值函数V(s)被分为了s 状态上各个动作a 对应的值函数Q(s,a)。Q 值更新公式如下式所示：

式中，r 为智能体从状态s 下采取动作a 使得环境状态转变到s'后获得的奖赏值；γ 为折扣因子；Q(s,a)为状态s 下动作a 对应的Q 值；Q(s',a)为状态s'下动作a 对应的Q 值；α 为学习效率。Q-learning 算法的优势在于将值函数进行了细分，评价策略更加容易，更易学出最优策略。缺点是Agent 的动作空间必须离散且维数不能过高，否则容易陷入维数灾难,在解决仓储物流大规模路径规划问题时显得乏力。

3.2 Metropolis 准则的区域扩张策略

为了避免探索的盲目性以及找到最优路径后的重复学习，此处作如下改进:

1）在路径规划过程中，智能体碰到障碍物时,不需要重新返回到起始点再进行迭代搜索, 而是在碰到障碍物之前的地方进行搜索，寻找其它方向的可行路径。

2）依照ε-greedy 贪婪策略探索，找到目标后，根据模拟Metropolis 准则退出此次探索过程，将目标位置作为探索初始位置，对目标周围区域探索。随着探索的继续，目标区域先验知识增加，探索区域随之增大。

3）探索结束的自主学习条件的依据，根据目标周围区域探索，判断出周围位置距目标点的距离是否到达最优值。当前规划步数与前一步中步数相等时结束此次探索学习。

利用反向探索，可摆脱陷入局部最优解，将目标点作为探索初始点可以增加周围区域最小规划，加快算法收敛，避免了盲目的重复探索，提高整体搜索到决策的效率。

在传统的智能算法中，并不采取区域探索学习，而是人为加入结束条件，进行反复迭代规划出一条到多条初始点到目标点的路径，学习效率一般。改进方法增加了智能体环境先验知识，使智能体能够自主结束学习，避免重复探索学习，节省了学习时间。改进后的算法描述如下:

Step1: 初始化;

Step2: 以初始位置为探索点，规划探索目标点位置所在；

Step3: 探索如果碰到障碍物，不返回初始位置值，而是探索初始点在碰到障碍物前的位点，直到寻到目标点，结束此次探索转入下次探索；

Step4: 以探索到目标点为中心探索策略，设置探索半径大小为ρ，根据ε-greedy 贪婪策略从A(S)选择一个动作a，如果a 的探索半径大于ρ，则转到step5，否则转到step6；

Step5: 根据A(S)重新随机选择一个动作a'；

Step6: 执行动作a, 得到下一个状态s'；

Step7: 如果步数越界, 总步数加1, 回到初始目标位置, 降温，转到step4;

Step8: 如果到达目标,总幕数加1，成功步数加1，总步数加1，δ 加1, r 赋最大值, 更新Q, 回到初始位置，降温，转到step4;

Step9: 根据状态s'的最大Q 值更新状态s 的Q 值, 返回step2;

Step10: 如满足结束条件，结束，否则返回step2。

3.3 人工势场强化学习

传统的Q-learning 算法在环境初始化时，智能体就算法而言对环境状态信息完全不熟知。在算法初始的所有状态下，动作值函数V(s)构成的Q 值表基本是一致的，故就智能体而言，动作a 的选择产生都是随机的，状态的概率也是均匀分布的，且概率值相同。传统Q 学习在解决智能体路径规划探索时，设定的总是智能体在搜索到目标点或机器人碰撞到障碍物时，算法才会给予一个回报奖励值r，从而更新状态动作Q 值表，而对于有凹形陷阱障碍物的环境，智能体容易被凹形区域干扰，传统的奖励值获得方式算法效率低下，需反复不断迭代，尤其对复杂度较大的未知环境会出现大量无效迭代，搜索空间重复而无用，不仅浪费资源，也降低算法效率[11-12]。

构建势场路径规划模型时，要知道智能体起始位置，设置起始坐标s=(x,y)，同时也要知道目标位置，设置目标点坐标g=(a,b)。之后再初始化奖励值函数以及Q 值表，以目标点为中心构建引力势场，以障碍物为中心构建排斥力势场，设定初始化后的V(s)值。

智能体在某一位置时需要对栅格环境行驶的8个栅格逐一探索，若发现障碍物，则进行V(S(t+1))=-A 操作，对该障碍物进行区域外侧探索，确定障碍物环境区域，并针对该区域扩展探索。该区域值函数状态值为负数。

根据智能体动作更新环境状态值函数，并通过值函数按下式更新动作Q 值表：

在初始时刻，智能体从起始位置出发，通过创建的引力势场、排斥力势场，构建初始环境状态信息，状态V(S(t+1))≥0 是可移动探索区域。智能体每一个动作对应Q 值表更新一对状态-动作值。探索到目标位置或者碰到障碍物后，此探索结束，从障碍物前一步或者目标点进行区域扩张探索。

3.4 回报函数设计

综合考虑机器人行驶每一步决策动作而不是寻找到目标点才得到奖励值，在对奖励值设计时，设定为每一步动作都会获得对应奖励值，根据每一步的动作情况不同设计不同的回报函数值。表1 是根据探索动作出现的情况设计的回报函数。靠近目标点获得正奖励值、远离目标获得负奖励值、如果与障碍物发生碰撞获得较大的负奖励值。为了避免机器人与障碍物或其他机器人相撞、对机器人每一个单元格的移动设计最小安全距离。只要机器人与障碍物或其他机器人距离大于最小安全距离dq，则认为两车不会相撞。

表1 函数奖励值设置

4 实验结果及分析

针对强化学习算法特点，在Windows 系统中的MATLAB 1019a 上进行仿真实验。利用路径规划建模常用的栅格法构建环境模型，在E 形、凹形环境下进行仿真，验证本算法有效性并与Q 学习算法进行对比。实验在E 型障碍物、凹型障碍物两种环境下进行，深色星线代表本算法，浅色实线代表Q 学习算法。对E 型栅格环境，设置起点坐标s=(15,6)，终点坐标g=(20,20)。仿真实验结果如图4 所示；

图4 E 型障碍物环境仿真结果

对凹型栅格环境，设置起点坐标s=(1,20)，终点坐标g=(20,1)。仿真实验结果如图5 所示。

图5 凹型障碍物环境仿真结果

为确保验证结果更加准确，在这四种障碍物环境中各运行仿真10 次。对两种算法的对比实验数据进行统计，得到的结果如表2 所示。

表2 两种方法对比实验统计结果

从图4、图5 可以看出，本改进算法的收敛效果明显要优于Q 学习算法，不论是E 型障碍物环境或者凹型障碍物环境都具有较好的收敛效果。在表2中用最优值、平均长度、标准差及最优值次数四个指标来评估两种算法性能的优劣。用路径最优值、平均长度表征本算法在全局搜索最优路径中的能力；用标准差来表征算法多样性：标准差越小，多样性越高。用在十次实验中达到全局最优值次数的概率表征算法的鲁棒性。

5 结 束 语

传统Q 学习算法在智能体路径规划中全局搜索能力差，易陷入局部最优，收敛速度慢，改进算法采用势场强化，以引力与排斥力势场结合对初始环境状态初始化，并引入了更新区域扩张的搜索策略。仿真实验证明，新算法不仅在各种障碍物环境中保证解的质量与收敛速度，在复杂环境中也同样具有良好的准确性与鲁棒性。在此仅针对静态障碍物验证了算法的有效性，在动态环境下的路径规划还有待进一步研究与摸索。