李泓坤

（西安工业大学，陕西西安，710021）

0 引言

自动导引小车 (Automated Guided Vehicle，AGV)属于轮式移动机器人，其以自动导引装置为核心构件，可以按照既定的导航路线平稳行驶[1]。在数控车间等领域内，AGV主要被用作配送物料，整体表现出了操作门槛低、构造简单的特点。但是其在实践应用中也面临着一些挑战，最为棘手的就是AGV路径规划问题。

AGV路径规划直接关系到AGV的行进效率。路径寻优算法是路径规划的核心，依据理论的不同，AGV路径规划技术可分为基于采样的图搜索算法、基于节点的搜索算法、基于模型的方法、基于生物启发式算法等方法。粒子群算法、模拟退火算法、遗传算法等都是典型的启发式算法。生物启发式算法相较于传统路径规划算法，减少了对数学模型的依赖，全局寻优能力强，在AGV规划研究中已经得到大量的实际应用。

灰狼优化 (grey wolf optimization， GWO)[2]算法作为一种生物启发算法，具有结构简单、需要设置的参数少和在实验编码中易实现等优点。然而，过去普遍采用GWO算法应对AGV的路径规划问题，此算法与生俱来的一些缺陷难以保证机器人的运动效率，会造成碰撞的可能，这些缺陷主要是易陷入局部极值、全局勘探与局部开发失调、初始种群过于单一等。

本课题结合GWO算法的上述缺陷，提出了一种改进灰狼优化算法（IGWO），在求解AGV全局路径规划问题时，通过改良，使得灰狼优化算法能够更好地适应数控车间环境，并基于此给出稳定的路径寻优结果，这样就能确保AGV始终选择最佳路径行驶，从而保证导航的准确性，并避免碰撞。

1 灰狼算法

GWO算法属于新型群体智能优化算法，其基本原理是对灰狼群体在自然界内生存时所存在的捕猎行为和社会等级机制进行模拟，对于此算法而言，灰狼种群内任意灰狼都是一个可能的候选解，群体中包含的的最优解、次最优解、第三最优解分别用α，β，δ表示，其他候选的解都用ω表示。然后我们用D 表示灰狼种群的大小，用D 表示搜索空间，那么就代表第D维空间内第i只灰狼的位置。灰狼群体通过式（1）逐渐接近并包围猎物：

2 改进灰狼算法

2.1 基于混沌的种群初始化方法

skew tent映射是一种由简单的确定性系统产生的随机性序列，混沌映射被用于生成混沌序列。在优化领域，混沌映射可以用于替代伪随机数生成器，生成0到1之间的混沌数。经过实验证明，利用混沌序列进行种群初始化、选择、交叉和变异等操作会影响算法的整个过程，而且常常能取得比伪随机数更好的效果。

本文先初始化处理了目标种群，具体是基于skew tent映射得到混沌序列实现的，这样就可以确保解空间的信息被初始群众个体充分利用，同时确保最终解的完整性，其函数式如下所示[3]：

当φ∈(0,1)且x∈[0,1]时，系统处于混沌状态。

2.2 IGWO算法步骤

结合如上分析，得出下表1所示的高效灰狼优化算法（简称IGWO）的详细步骤。

算法 1 IGWO 算法begin算法参数设置：N-种群大小；t -距离控制参数a的初始值；a max -最大迭代次数；ainitial-距离控制参数a的终止值。基于skew tent混沌初始化得到final灰狼种群对群体内所有个体的适应度进行求解，{X i N i , 1,2, ,= …}{f X i N( )i , 1,2,,= …}，然后对最

优个体、次最优个体、第三最优个体α、β、δ进行记录，用X β表示其对应位置。)d o f o r i=1 t o N d o f o r j=1 t o D d o对距离控制参数a的值进行求解。代入公式（2）和（3）对参数A和C的值进行求解。代入公式（6）完成个体位置的更新。e n d f o r e n d f o r对群体内所有个体的适应度进行求解，w h i l e(t＜t m a x{f X i N( )i , 1,2, ,= …}然后对最优个体、次最优个体、第三最优个体α、β、δ进行记录，用X β表示其对应位置t=t+1;e n d w h i l e e n d

2.3 路径寻优约束条件与适应度函数

选择最优路径的期间，假设机器人的某条行驶路线便是任意灰狼捕猎期间位置更新时对应的坐标集，IGWO算法按照优化策略，在路径集合当中选出一条与约束条件高度匹配的路径，约束条件如下。

(1)路径连续性条件

移动路径不能有迂回状况，即节点的纵向坐标或是横向坐标，相对于下一个节点两者只能有一个是在单调递增，假设机器人由当前节点(x1, y1)移动到下一节点(x2, y2)应至少满足(x2＞x1)或(y2＞y1)。

(2)环境边界与障碍物约束条件

移动路径必须限定在固定图幅边界的栅格区域内，且移动路径节点及节点间的连线禁止穿过障碍物栅格。

(3)目标路径最短条件

在满足约束条件(1)、(2)下的诸多栅格位置中，第j( j = 1 ,2,...Ny)行栅格应选横坐标最小值i( 1 ＜ i＜Nx)作为最终路径节点(xi, yi)，以达到路径最短条件，即IGWO算法规划结果中适应度函数须取最小值。

数控车间环境在路径寻优过程中，以对角线距离作为适应度函数。

3 AGV运行环境建模

本文采用栅格地图表示法[5]表示数控车间环境，将数控车间中 AGV 运行环境视为由多栅格组成的矩形，且每个栅格大小相同。考虑到数控车间下机床对AGV运行路径的影响，对机床栅格进行膨胀处理。后续验证采用八方向搜索节点方法，即AGV可到达相邻位置的8个节点。

通过以上研究，基于数字仿真软件测试平台构建了一个37×23数控车间栅格地图。其中黑色为机床位置，红色为AGV充电位置，绿色为车间仓库位置。

4 仿真实验结果与分析

本文以计算机作为仿真实验平台，其CPU型号为Intel(R) Core(TM) i5-10200H，内存为 16GB，处理器主频为 2.4 GHz，操作系统为 Windows 10，采用 MATLAB R2021b 软件进行仿真操作。

下表1列出了本次实验的算法参数，以应用路径规划时对比算法所需搜索空间和对比算法所在原文献为依据对种群大小、最大迭代次数进行设置，以保证所得结果的准确性与客观性。

表1 仿真实验中的算法参数设置

4.1 路径规划仿真

为了验证本文提出的IGWO算法有效性，通过对栅格地图设置不同的AGV初始位置，物料转送位置和最终停车位置，从寻优效率、路径长度等优化性能方面横向对比的GWO算法和IGWO算法的仿真试验结果，实验次数为30。

PSO算法没无法在全局内搜索最优路径，而且路径寻优收敛效率较低，期间还出现了搜索停滞的现象（陷入局部极值导致）。在迭代前期，GA算法有着十分可观的收敛速度，但与其他启发式算法相比，其也出现了局部收敛的问题，而且比较频繁；SA算法也有着理想的收敛速度，全局路径规划表现较好，但仍存在多次实验所得最优路径值不稳定等问题；GWO算法不但在初始阶段拥有理想的收敛速度之外，中后期搜索还协调了局部开发。由此可见，本文提出的IGWO算法有效弥补了传统GWO算法优化方面的缺陷，具有十分理想的搜索能力和收敛能力。

从表2得出：相较于传统GWO算法，本文提出的IGWO算法平均路径长度更短且得到稳定性更强的结果，算法同时具有理想的收敛速度，因此寻优耗时也变相缩短了。

表2 环境1中30次实验的算法性能对比

5 结论

本文对灰狼算法进行改进，以求解数控车间AGV全局路径规划问题，基于路径规划仿真实验结果，得到几点结论，具体如下：

（1）本文提出的IGWO算法通过引入Tent混沌映射来保证灰狼种群初始化的均匀性，这样就能很好地克服传统GWO算法初始群众分布不均的问题，同时还能使得算法在路径寻优初期的收敛速度得以提升，在路径寻优期间，此算法在综合勘探和避障方面的表现十分出色，一定程度上弥补了传统GWO算法全局算法与局部开发不协调的缺陷，使得算法在路径寻优最后阶段能较为准确地锁定全局最优解。

（2）全局路径规划仿真实验表明，在数控车间场景下，IGWO算法计算所得的路径有效、合理。相对比于传统GWO算法、GA算法、SA算法、PSO算法，本文IGWO算法在路径寻优能力、收敛效率、寻优结果稳定性等方面具有一定的优越性。

（3）本文提出的IGWO算法相较于传统启发式算法具有结构简单、计算复杂度较小、全局搜索能力较强等优势。本文所提的各项改进策略可为其他启发式群智能算法的优化改进以求解全局路径规划问题提供参考。