基于改进灰狼优化算法的三维路径规划

音凌一，向凤红

（昆明理工大学 信息工程与自动化学院，云南 昆明 650000）

路径规划是指，在给定的环境中，根据指定的评价标准，规划出一条从起点到目标点的可行路径，并保证移动机器人在不会碰撞障碍物的前提下优化路径[1]。路径规划已在众多领域得到应用，包括移动机器人[2]、水下机器人[3]以及自动引导车[4]（Automated Guided Vehicle，AGV）等。然而，目前研究路径规划的算法大多数都是建立在二维环境中，忽略了三维环境的求解，因此，对三维环境中的路径规划进行研究是非常有必要的。

灰狼优化算法（Grey Wolf Optimization，GWO）是一种模拟灰狼捕猎行为而得到的新型群智能优化算法，较其他群智能算法相比，具有调整参数少、易于实现以及有较强的全局搜索能力等优点[5]，已经在调度问题[6]、求解约束优化问题[7]、高维优化问题[8]以及路径规划问题[9]等方面得到成功的应用。刘长安[10]等通过设计基于贪婪思想初始化策略和动静态加权的位置更新公式，改进灰狼优化算法，并成功应用在三维路径规划问题上；姚鹏[11]等将流

0 引 言

体扰动算法和灰狼优化算法相结合，在三维路径规划中具有良好的效果；DEWANGAN[12]等将灰狼优化算法运用在多机器人三维路径规划中，并与粒子群优化算法、鲸鱼优化算法及正余弦优化算法进行对比，表明灰狼优化算法有着最优的性能。

基于以上研究，本文提出一种基于改进灰狼优化 算 法（Improved Gray Wolf Optimization，IGWO）的移动机器人三维路径规划。首先，为提高灰狼优化算法的性能，改进初始化种群的方法，利用超立方体抽样提高初始种群的质量，提出相对位置的概念，利用个体的相对位置动态调整前三狼的比重；其次，为降低三维空间的复杂度，提出降维-升维的地图处理方法，通过将三维环境降维达到简化地图的目的；最后，融合人工势场法，获得对未知动态障碍物避障的能力。仿真结果证明，相比于遗传算法、粒子群算法及灰狼算法，改进的灰狼算法进行路径规划时所需间更短、路径更优且节点更少。

1 改进灰狼优化算法

1.1 灰狼优化算法原理

在灰狼种群中，种群内部一般分为4个等级：第1级是α狼，领导整个种群的个体；第2级是β狼，主要辅助α狼进行决策；第3级是δ狼，执行侦查和放哨等任务；第4级是ω狼，是最底层的灰狼，服从前三级狼的指挥。灰狼优化算法就是对灰狼种群按等级制度进行捕猎行为的数学模拟，具体的数学描述如下。

1.1.1 包围猎物

包围猎物行为可表示为：

式中：t是当前的迭代次数，A和C是协同向量系数；Xp(t)是猎物的位置向量；X是灰狼的位置 向量。

向量A和C的计算式如下：

式中：a在迭代过程中从2线性减少到0，r1和r2是 [0，1]中的随机向量。

1.1.2 狩 猎

狩猎行为的数学表示为：

式中：Xα、Xβ和Xδ分别是最优解、次优解和第三优解的位置，Dα、Dβ和Dδ分别是灰狼个体到α狼、β狼和δ狼的距离。

1.1.3 搜寻和攻击猎物

灰狼群体主要依靠α狼、β狼和δ狼的位置信息来进行捕猎，在数学描述中主要根据向量A来控制灰狼是搜寻猎物还是攻击猎物。当|A|＜1，强迫灰狼攻击猎物；当|A|＞1，迫使灰狼远离猎物，扩大搜索范围，去寻找下一个猎物。

1.2 改进灰狼优化算法

1.2.1 拉丁超立方抽样

传统GWO算法通常采用随机生成的数据作为初始种群来求解问题，这种方法建立的初始种群，因为其随机性，无法保证种群的多样性以及种群的均匀分布。现有的大多数改进是采用Logistic映射来进行种群初始化，但具有在[0，0.1]和[0.9，1]区域取值概率较高及映射遍历不均匀的缺点。拉丁超立方抽样用于初始化种群，可以保证全空间填充和抽样重叠的优点。为保持种群的多样性，使初始种群在迭代开始，尽可能地均匀分布在解空间内。因此本文采用拉丁超立方抽样进行种群的初始化。具体过程如下。

（1）确定抽样规模H。

（2）将每维变量xi的定义域区间[xli,xui]划分成H个相等的小区间这样就将原来的一个超立方体划分成H n个小超立方体。

（3）产生一个H×n的矩阵A，A的每一列都是数列1，2，…，H的一个随机全排列。

（4）A的每行对应一个被选中的小超立方体，在每个被选中的小超立方体内随机产生一个样本。

图1是利用超立方体抽样进行种群初始化的结果，可以明显看出，个体在解空间中是均匀分布的，同时不存在重复的个体，说明利用超立方体抽样进行初始化种群是有效的。

图1 超立方体抽样种群初始化结果

1.2.2 动态权重

为加快算法的收敛速度，本文提出一种根据距离比自适应调节的位置更新公式。在迭代过程中，计算所有灰狼个体分别与α狼、β狼、δ狼之间的距离dji和平均距离dj(j=α、β、δ)，再计算出前三狼平均距离的平均值da。用距离dji与da的比值dji_site来表示个体与前三狼相对位置的远近。利用每个迭代中个体距离α、β和δ狼相对位置的不同，来自适应调节位置更新公式中α、β和δ狼的比重。相关计算式如下：

式中：dji是第i只灰狼与j狼的距离，Xi是第i只灰狼的位置，Xj是前三狼的位置，dj是前三狼当前迭代的平均距离，dji_site是第i只狼与j狼的相对距离，f1、f2和f3分别是所有灰狼个体与前三狼相对距离的求和。

2 环境建模

2.1 栅格法三维建模

利用栅格法进行三维建模，首先需将障碍物进行膨胀处理，使不规则形状的障碍物膨胀成规则形状，然后再对有限的范围空间进行分割，使整个范围分割成n个立方体，其中障碍物栅格赋值为1，自由栅格赋值为0，每个自由栅格的中点为路径的节点。由此可知，在等大空间中，n的值越大，立方体越小，环境的分辨率越高；n的值越小，立方体越大，环境的分辨率越低。但n值越大，地图分辨率越高，算法求解路径规划的效率也就越低；n值越小，地图分辨率越低，算法的求解精度越低。所以对地图进行预处理，在保证求解精度的同时，提高求解效率，是很有必要的。

2.2 降维和升维

为了在保证求解精度的同时，降低地图的复杂度，提高求解效率，本文提出一种降维-升维的三维建模方法，具体步骤如下。

（1）建立1 000×1 000×250大小的三维坐标系，设置起点（50，950，120）和终点（950，50，10）， 将障碍物膨胀成规则形状，其中黑色栅格是障碍物栅格，白色栅格是自由栅格。

（2）从上方俯视整个三维地图，将整个三维地图投射到XOY平面上，其中起点为（50，950），终点为（950，50）。

对每个障碍再次进行膨胀处理，膨胀的距离是离最近的障碍物距离的一半。

（4）将膨胀后的顶点作为特征点，对两两特征点的可视性进行判断，建立邻接矩阵C，在邻接矩阵C中进行求解，输出路径L{P1,P2,P3,…,Pn}。

（5）判断P1与其他节点的连线是否经过障碍物，若存在节点Pk与P1的连线不经过障碍物，删除P1与Pk之间的节点；若不存在Pk点，则对P2点进行判断。重复以上操作直到Pn-1点。

计算起点到终点的高度差，按照每个节点之间距离的比值来分配三维空间中移动机器人上升的 高度。

经过降维-升维处理后的路径如图2（a）所示，长度为1 331.84 m，算法求解时间为3.23 s；未地图处理的路径如图2（b）所示，路径长度为1 457.13 m，算法求解时间为9.00 s。对比可知，经过降维-升维的处理，路径优化了125.29 m，求解时间优化了5.77 s。说明降维-升维的地图处理方法能有效地加强灰狼优化算法求解路径规划问题的效率，缩短最优路径的长度。

图2 地图处理对比

2.3 局部动态障碍物避障

文献[13]用A*算法与人工势场法融合，证明与人工势场法融合可以使A*算法获得一定的动态避障能力。为使IGWO算法获得动态避障能力，本文把改进灰狼算法全局路径规划的节点作为人工势场法的临时节点，将改进灰狼优化算法与人工势场法相结合，以达到动态避障的目的，最后利用仿真验证融合后的算法的动态避障性能。

3 仿真实验

为证明灰狼势场算法的性能，在Matlab R2018b上进行仿真实验，建立1 000×100×250大小的三维栅格地图，并与遗传算法（Genetic Algorithm，GA）、 粒子群算 法（Particle swarm optimization，PSO）及GWO算法对比。其中，设路径规划起点为（50，950，120），终点为（950，50，10），算法的初始种群N=30，最大迭代次数tmax=100，GA算法中交叉概率为0.8，变异概率为0.1；PSO算法中学习因子c1=c2=2，惯性权值ωini=0.9，ωend=0.4；人工势场法静态和动态障碍物影响范围为15 m。最后，设置未知动态障碍物，进行动态避障仿真实验，以验证灰狼势场法的动态避障能力。

3.1 全局静态环境仿真

各算法在相同地图中求解三维路径规划的结果如图3所示。图3（a）、（b）、（c）、（d）是未经过降维-升维处理地图的求解结果，可以明显看出，IGWO算法的求解结果节点数最少，路径最优，说明对传统GWO算法进行提高种群质量及动态权重的改进，有利于改进算法的求解精度和质量。图3（e）是经过降维-升维处理后IGWO算法的求解结果，对比图3（d）可以明显看出，路径的节点数进一步减少，说明降维-升维处理方法优化了路径长度。

图3 路径规划结果

表1是各算法在1 000×100×250三维地图上运行20次的平均结果，可以看出，IGWO算法的求解结果相比于GA算法、PSO算法和GWO算法，路径长度上优化了208.44 m、91.57 m和58.89 m，节点数减少了10个、8个和16个，仅在求解时间上略差于PSO算法，说明超立方体策略和动态权重提高了算法求解精度和求解速度；降维IGWO算法求解结果相比于GA算法、PSO算法、GWO算法和IGWO算法，求解时间减少了11.57 s、5.12 s、8.88 s 和5.77 s，路径长度优化了333.73 m、216.86 m、184.18 m和125.29 m，节点数减少了19个、17个、25个和9个，说明降维-升维的地图处理方法对算法求解路径规划问题的效率及减少路径长度有着一定积极作用。

表1 20次仿真平均结果

3.2 局部动态环境仿真

在3.1节的三维环境中，增加两个动态障碍物，再用融合算法进行路径规划求解。融合算法的路径规划结果如图4所示。

图4 增加局部动态障碍物后的规划路径

图5（a）和图5（b）分别是路径在动态障碍 物1处的放大和路径在动态障碍物2处的放大，其中黑色的是动态障碍物运动轨迹。可以明显看出与人工势场法的结合，使IGWO算法成功对未知动态障碍物进行避障，表明算法具有动态避障能力。

图5 动态障碍物放大

4 结 语

本文对传统灰狼算法进行改进，提出超立方体抽样初始化种群策略和动态权重，并与传统灰狼算法在求解路径规划问题上进行对比，证明了改进策略能有效地提高灰狼优化算法的收敛精度和收敛速度；采用降维-升维地图处理方法，降低了三维地图的复杂性，提高了灰狼优化算法求解路径规划问题的效率及精度；利用人工势场法，成功地对局部未知的动态障碍物进行避障，使改进的灰狼优化算法拥有一定的动态避障能力。