基于跳点搜索-遗传算法的自主移动机器人路径规划

田雅琴，胡梦辉，刘文涛，侯寅智

（太原科技大学 机械工程学院，山西 太原 030024）

机器人在军事领域中的应用越来越广泛。在军事活动中，机器人快速、高效地完成任务的第1步在于确定任务路线即路径规划。在具有若干障碍物的复杂环境下，自主移动机器人路径规划的核心是在起点与终点之间规划一条综合性能（如规划速度、路径长度、能量损耗等）最优的路径[1]。综合考虑复杂三维地形和动态障碍物环境等诸多因素下的路径规划是目前研究的新方向[2]。算法的优劣性在路径规划中起着关键作用。现有的算法包括传统算法和智能算法，其中常用的路径规划算法有遗传算法[3-8]、人工势场法[9-11]、蚁群算法[12]、灰狼算法[13]、跳点搜索（jump point search, JPS）算法[14]和A*算法[15]等。无论是传统算法还是智能算法都存在着自身缺陷，但可以通过融合算法弥补各算法的不足而使其呈现更优异的性能。

遗传算法是一种智能搜索算法。它以生物进化为原型，相较于传统的路径规划算法具有较好的全局搜索能力和收敛性，但局部搜索能力差。其具有良好的可扩展性，易与其他算法结合，因此是融合算法中常用的一种算法。杨博等[16]采用中间插值法，通过改进交叉算子、变异算子和适应度函数来优化遗传算法，避免了早熟现象发生，但是未考虑动态障碍物环境下算法的适应性。陈亮等[17]将遗传算法与鲸鱼算法相结合，使得融合算法能在短时间内完成进化，但是当规划空间规模较大时仍存在迭代次数较大的问题。徐兴等[18]提出了基于灾变策略的遗传算法，相对于传统遗传算法，可避免早熟现象且缩短寻优时间。Zhou 等[19]研究后发现，面对现实复杂地形和环境，采用单一的遗传算法因受到算法本身的限制而不能得到理想的结果。

遗传算法借用达尔文进化理论以算法的形式表现出来就是遗传算法的运行过程。遗传算法在计算种群适应度函数时具有较大的计算量，导致算法执行处理时间较长，搜索效率低下[20]。JPS 算法实际上是通过改进A*寻路算法而发展起来的一种新型启发式算法，其相对于A*寻路算法具有更高的搜索效率，但其规划路径的质量易受到周围障碍物影响[21]。

基于遗传算法效率低、运行时间长和JPS算法整体搜索能力易受周围障碍物影响，为了满足战时需求，作者提出一种以快速性、准确性、稳定性为目标的优化算法——跳点搜索-遗传（jump point search-genetic，JPSG）算法。该算法兼顾了遗传算法全局搜索能力和JPS 算法较强的局部搜索能力，可以在自主移动机器人的路径规划中突破局部最优解，提高求解速度，寻优准确率，以及增强该融合算法对动态环境的适应能力。

本研究采用栅格法对自主移动机器人在静态和动态环境下的路径规划进行分析，进而验证JPSG算法在静态环境下的可行性和在动态环境下的良好适应性。

1 栅格建模

首先对环境建模作如下假设：

1）在环境空间中分布着有限个静态障碍物和动态障碍物，每个障碍物大小相等且不考虑高度因素，但需考虑动态障碍物的移动速度大小和方向；

2）自主移动机器人仅仅考虑移动方向，不考虑移动速度大小；

3）用黑白网格区分障碍物和自由移动空间，连续坐标代表移动路径，不重复连续相邻坐标的距离之和代表路径长度。

设自主移动机器人的运动环境空间为A。将机器人移动步长默认为单位长度，并确定其运动空间为30×30的栅格矩阵（即30×30方格图），如图1所示。由图可知，自主移动机器人在非规则边界区域的移动方向共有8个。

图1 30 × 30的栅格矩阵示意图Fig.1 Schematic diagram of 30×30 grid matrix

栅格矩阵中存在若干静态障碍物和动态障碍物。对于任意位置的栅格都有唯一的坐标(x,y)和序号与之相对应，在30×30 的栅格环境中栅格序号s和坐标(x,y)的关系为：

式中：fix为向零舍入运算，mod为求余运算，G为障碍物矩阵。

由栅格的坐标(x,y)结合障碍物矩阵判断该位置是否为障碍物。

2 JPSG算法原理

JPSG算法是利用JPS算法高效率地搜索出一条局部最优路径来减少遗传算法的迭代次数，提高整体种群质量。采用JPSG算法可以有效解决遗传算法早期盲目搜索造成的收敛时间长、最优解不稳定的问题，能在较少的已知数据下保障最优解。随着迭代次数增加，最优解越早出现，则对提高遗传算法的稳定性越有好处。

2.1 改进遗传算法

改进遗传算法主要通过采用自适应交叉概率、变异概率和改进适应度函数计算方法来加快算法的收敛速度。

2.1.1 选择算子

轮盘赌法的选择方式是根据概率且将概率大小与适应度相关联，从而使有较高适应度的个体具有更大优势。表示为：

式中：pi为轮盘赌法中的种群个体的概率值；fi为种群个体的适应度值；j为种群数量，j=1, 2, …,M。

2.1.2 交叉算子

交叉算子的主要作用是产生新的个体。交叉概率越大，新个体产生速度越快，同时种群中最优个体被破坏的概率越大；交叉概率越小，遗传算法的收敛速度越慢。表示为：

式中：pc为交叉概率，pmax、pmin分别为本次迭代中种群的最大、最小路径长度。

由式(4)可知：若当前种群的最大路径长度与最小路径长度的比值变大时，交叉概率随之变大。通过不断交叉使种群路径长度加速向当前迭代种群最优路径长度靠拢；当交叉概率较小时，可以避免种群中最优路径长度被破坏。

2.1.3 变异算子

变异运算是使遗传算法突破局部最优解的重要方法。变异概率太小，则产生新个体的几率较小，且容易出现早熟现象；变异概率太大，则随机概率较大。表示为：

式中：pm为变异概率，xs、ys分别为起点的横坐标和纵坐标，xg、yg分别为终点的横坐标和纵坐标。

若迭代时迭代种群内最大路径长度与起点与终点之间的距离相差较大，则当变异概率逐渐增大时，变异后得出更优的路径长度，而不至于使种群路径长度陷入局部最优路径长度。当变异概率减小时，不会破坏当前种群内路径长度的稳定性。

2.1.4 插入算子

根据式(6)可以判断路径中相邻栅格节点间是否连续。根据式(2)中G值是否为0，来判断每相邻两步之间是否需要重新插入节点。表示为：

式中：abs 为绝对值函数，max 为取最大值函数，floor为向下取整函数，xnow、ynow分别为当前节点的横坐标和纵坐标，xnext、ynext分别为下一节点的横坐标和纵坐标，xinsert、yinsert分别为插入点的横坐标和纵坐标。

2.1.5 适应度函数

个体i的适应度表示个体在种群生存的优势程度，用于区分个体的优劣。

式中：Fi为路径长度，F为起点与终点之间的距离，ε为在区间服从均匀分布的随机数，m为最优跳点个数。

原适应度值仅仅由路径长度的倒数决定，当路径长度相近并接近最优解时，适应度值相差不大而难以区分，改进后以Fi与F的差值作为分母。当2个路径长度接近时能较好区分出更优路径长度而加速收敛。

2.2 JPS算法

通过式(11)所示当前节点与上一节点之间的距离关系来判断当前方向是直行还是沿对角线方向。跳点搜索算法的优点是可以兼顾当前节点和上一节点的位置，即根据上下节点的位置关系判断下一步前进方向，同时为当前节点识别出自然邻居和强制性邻居。

式中：xpre、ypre分别为上一节点的横坐标和纵坐标。

自然邻居定义为当前节点沿对角线方向上的下一个节点、水平方向上的下一个水平节点和垂直方向上的下一个垂直节点。若当前节点的邻居节点中有障碍物，且从上一节点经过当前节点到达下一节点的距离比不经过当前节点到达下一节点的距离小，则称下一节点为强制邻居，如图2和图3所示。

图2 斜线强制邻居示意图Fig.2 Schematic diagram of oblique line forced neighbors

图3 直线强制邻居示意图Fig.3 Schematic diagram of linear forced neighbors

2.2.1 跳点评估函数

通过搜索规则对跳点进行评估，选择出最优跳点以组成最优路径。评估函数如下：

式中：fcost为当前经过路径长度，fvalue为当前点与终点之间的距离，fjps为评估函数值。

通过路径评估函数可以评判起点、跳点和终点依次连接后的路径是否为最佳路径。跳点搜索如图4所示。图中深灰色和浅灰色栅格为跳点，其中将最优跳点（浅灰色栅格）连接后，可以构成一条由起点到终点的最优路径。

图4 跳点搜索示意图Fig.4 Schematic diagram of jump point search

2.2.2 openlist列表

在openlist列表中储存着下一个跳点信息，根据跳点评估函数计算出各个跳点值的大小，进行排序。openlist列表中存在着函数值相同的跳点，在其中总是优先弹出第1个跳点的位置，导致后面的跳点无法被考虑到是否为最优跳点，因此，将函数值相同的跳点一一弹出，按照所弹出跳点的位置进行路径规划，并根据路径长度选择最优跳点。

3 JPSG算法流程

JPSG算法流程如图5所示。JPS 算法具有高效的局部搜索能力，改进自适应遗传算法具有较好的全局搜索能力。将JPS算法的解析结果融入随机概率，初始化种群以加快迭代速度，同时将JPS算法融入变异算子，随着断点位置不同可得到多种局部最优结果，最后通过对比得到最优路径。

图5 JPSG算法流程图Fig.5 Flow chart of JPSG algorithm

4 路径规划仿真研究

在所建立的栅格矩阵上进行自主移动机器人路径规划仿真。

4.1 基于JPS算法的路径规划

基于传统JPS算法的路径规划结果如图6所示。将算法中openlist 列表进行改进，得到的路径规划结果如图7所示。图6中的路径长度为31.556 3，图7中的路径长度为30.970 5，可见图7中的路径为最优路径。图7中，在栅格坐标（11, 12）处存在2条到下一节点的函数值相同的路径，算法改进后由于openlist列表在（11, 12）处弹出等值点，实现了提前规划最优路径。

图6 基于传统JPS算法的路径规划结果Fig.6 Path planning result based on traditional JPS al‐gorithm

图7 基于改进JPS算法的路径规划结果Fig.7 Path planning result based on improved JPS algo‐rithm

4.2 静态环境下路径规划

分别采用JPSG 算法、改进JPS 算法、改进遗传算法和传统遗传算法进行静态环境下的路径规划，并将规划结果进行对比，来验证JPSG算法的优越性。在相同的静态环境下，采用MATLAB2021b软件运行上述4 种算法。将规划路径的长度、准确率、收敛迭代次数和规划时间等作为参数对算法性能进行评估，其中准确率是指该算法下出现种群最小路径长度的次数与最大迭代次数的比值。在30×30 的栅格矩阵上进行仿真。参数设置如下：M=10 000 个，0.6≤pc≤1.0，0.02≤pm≤0.10，最 大迭代数T=100 次。路径规划仿真结果如图8 所示。采用JPSG 算法、改进JPS 算法、改进遗传算法和传统遗传算法得到的路径规划结果如图8 所示。JPS 算法中没有种群规模和迭代次数，因此将基于JPSG 算法、改进遗传算法和传统遗传算法的规划路径长度进行对比，如图9 所示，算法性能对比如表1 所示。

图8 静态环境下路径规划的仿真结果Fig.8 Simulation results of path planning in static environment

图9 静态环境下规划路径长度的仿真结果Fig.9 Simulation results of path planning length in static environment

表1 静态环境下算法性能对比Table1 Comparison of algorithm performance in static environment

由图8 可知：相对于改进JPS 算法、改进遗传算法和传统遗传算法，JPSG算法具有更好的整体搜索能力，利用JPS算法的快速局部搜索能力可加快收敛速度，且不容易陷入局部最优解；JPS 算法的整体搜索能力易受周围障碍物的影响；遗传算法易陷入局部最优解。

由表1可知：相较于改进遗传算法和传统遗传算法，JPSG 算法的规划路径长度最短，收敛迭代次数最少；准确率分别提高了72%、90%；规划时间分别减小了12%、15%；方差值分别减小了30%、31%，表明JPSG 算法的规划结果更加稳定。可见JPSG 算法融合了2 种算法的优点，能够避免陷入局部循环、加快收敛速度以及具备较高的搜索正确率，使自主移动机器人得到最优的规划路径。此外，基于JPSG 算法分别在20×20 和30×30栅格矩阵上的路径规划结果如图10 所示。将JPSG算法与文献[22]和文献[23]提出的RRT（rapidly-ex‐ploring random tree,快速搜索随机树）算法和改进遗传-鲸鱼融合算法等进行对比，算法性能对比如表2和表3所示。

图10 基于JPSG算法的路径规划结果Fig.10 Path planning results based on JPSG algorithm

表2 JPSG算法与文献[22]中算法的性能对比Table 2 Performance comparison between JPSG algorithm and the algorithm in literature [22]

表3 JPSG算法与文献[23]中算法的性能对比Table 3 Performance comparison between JPSG algorithm and the algorithm in literature [23]

由表1 和表2 可知：JPSG 算法和JPS 算法在简单障碍物下搜索效率较高；由表2 得出知改进JPS算法相较于传统RRT算法和RRT-Dijkstra算法具有短时间寻优能力，与Dijkstra 算法相对比具有更高的搜索效率。

由表3 可知，JPSG 算法相较于文献[23]中的遗传算法、改进遗传算法和改进遗传-鲸鱼融合算法在地图规模和障碍物简单的状况下的搜索效率更优。

4.3 动态环境下路径规划仿真

上述仿真是在静态环境下进行的，在实际中机器人所处工作环境大多是动态的，因此在动态环境下分别采用JPSG 算法、改进JPS 算法、改进遗传算法和传统遗传算法进行路径规划仿真与对比，来验证JPSG 算法适应动态环境的优异性。设定机器人的探测半径为，其移动速度为单位时间内的移动步长，时间步长Δt=0.5 s，动态障碍物的移动速度为2/s。当无动态障碍物时，自主移动机器人按照原优化路径行走。由单位时间和动态障碍物的移动速度可以计算出机器人与动态障碍物发生碰撞的时间。利用MATLAB2021b软件运行上述4种算法，得到动态环境下路径规划仿真结果。在静态和动态环境下路径规划仿真结果的对比如图11 所示。其中，当采用JPSG 算法时，机器人遇到第1 和第2 个动态障碍物后的路径规划如图12 所示。图中带有空心箭头的实线代表动态障碍物的运动路径，带有实心箭头的实线代表静态环境下的规划路径，点划线代表动态环境下的规划路线，虚线代表动态障碍物的运动范围，箭头代表运动方向。 将基于JPSG算法、 改进遗传算法和传统遗传算法的规划路径长度进行对比如图13所示，算法性能对比如表4所示。

表4 动态环境下不同算法的性能对比结果Table 4 Performance comparison results of different algorithms in dynamic environments

图11 在静态和动态环境下路径规划仿真结果的对比Fig.11 Comparison of simulation results of path planning in static and dynamic environments

图12 机器人遇到第1，2个动态障碍物后的路径规划示意Fig.12 Schematic of path planning after the robot encounters the first and second dynamic obstacles

图13 动态环境下规划路径长度的仿真结果Fig.13 Simulation results of path planning in dynamic environment

由图11可知：遗传算法对动态环境的适应性较差；在障碍物不断变化的情况下，JPS 算法的整体搜索能力易受周围障碍物影响；JPSG算法对动态环境的适应能力较好，能快速收敛而节省搜索时间。

由表4 可知：相较于改进遗传算法和传统遗传算法，JPSG 算法的规划路径长度最短，收敛迭代次数最少；准确率分别提高了55%、95%；规划时间分别减小了12%、14%；方差值分别减小了50%、51%，表明JPSG 算法的规划结果更加稳定。可见JPSG 算法融合了2 种算法的优点，能够避免陷入局部循环、加快收敛速度以及具备较高的搜索正确率，使自主移动机器人得到最优的规划路径。

5 结 论

通过改进JPS算法的openlist 弹出机制优化了JPS 算法规划路径的准确性，同时采用自适应交叉算子和变异算子改进遗传算法来优化收敛时间，最后将改进JPS 算法和改进自适应遗传算法融合，得到JPSG 算法在静态和动态环境下分别采用JPSG 算法、改进遗传算法、传统遗传算法进行自主移动机器人路径规划，并将各算法下规划的路径进行对比，结果表明JPSG 算法在稳定性、快速性、准确性上具有明显的优势。