基于IGWO-A*算法的无人机农田喷洒航迹规划

李 靖，杨 帆

（河北工业大学 电子信息工程学院，天津 300401）

随着智慧农业的发展，计算机视觉已经在农业领域取得了良好的成绩。如KOUNALAKIS等[1]在阔叶杂草的奶牛场中实现了杂草自动识别系统。张芳等[2]提出一种用于黄瓜叶部病虫害的识别系统。李少轩[3]开发了人机交互式干旱事件应急应对服务系统。此外，深度学习(deep learning，DL)技术的日益成熟，它在我国农业领域有了广大的发展应用[4]，且随着样本数量的增加，DL技术的农作物、病虫害等分类识别更加广泛及精准。但在识别后如何自动化处理的途径研究相对较少。无人机渐渐的从军用走向民用领域，可以将无人机作业策略引入农业领域。无人机航迹规划是无人机作业领域研究的基础，为其作业效果提供基础保障。OUYANG等[5]提出了一种面向任务的无人机航迹规划，根据作战任务将无人机航路分为固定航路和突防航路，在军事领域根据其作战任务能取得良好效果。ZHENG等[6]针对应急管理领域提出了一种用于快速图像拼接的无人机航迹规划数学模型，给定的模型考虑了3种不同的方法，覆盖了大部分无人机飞行任务的情况。LI等[7]以飞行时间和飞行安全因素为基础，建立目标函数，利用模糊技术对威胁等级进行评估，运用粒子群优化算法(partile swarm optimization，PSO)搜索策略进行无人机航迹规划。刘文兵等[8]对多任务目标聚类，在类内运用了2-opt算子改进遗传算法进行无人机航迹路径规划。目前，群智能优化算法[9]在无人机航迹规划领域较为流行，但群智能优化算法易陷入局部最优解的情况未能从根本上解决，且已有二维空间无人机航迹规划算法较少的考虑了障碍物空间对航迹的影响。针对上述问题，在农田喷洒作业领域提出了一种改进灰狼优化算法 （improve grey wolf optimizer，IGWO）与A*算法相结合的无人机航迹规划算法。IGWO算法引入K-Means聚类算法初始化种群以加强种群多样性，引入非线性收敛因子以平衡全局搜索与局部开发能力，引入PSO算法位置更新调整以避免陷入局部最优问题。通过IGWO算法对标记的多喷洒任务点进行无障碍遍历航迹规划，随后运用A*算法对障碍物路线航迹局部避障调整。

1 理论依据

1.1 灰狼优化算法

灰狼优化算法（grey wolf optimizer，GWO）[10]是模拟灰狼群体捕猎行为的群智能优化算法。灰狼拥有严格的金字塔层级结构，从顶层到底层包含四种狼，分别是 alpha(α)狼、beta(β)狼、delta(δ)狼和 omega(ω)狼。 α 狼是首领狼，β狼服从α狼领导，δ狼服从α狼和β狼，其余狼称为ω狼处于最底层。GWO算法数学建模中，每只灰狼代表种群中1个候选解，将最优解视为α狼，第二和第三最佳候选解视为β狼和δ狼，其余的候选解视为ω狼。灰狼围捕猎物的数学模型描述为：

式中：t为当前迭代次数；tmax为最大迭代次数；A和C为系数向量；Xp为猎物的位置向量；X为灰狼的位置向量；r1和r2的大小为[0，1]之间的随机数，a为收敛因子随着迭代次数的增加从2线性减小到0。

灰狼追踪猎物位置的数学模型描述为：

式中：C1、C2与 C3为随机向量；Xα、Xβ和 Xδ为 α狼、β狼和 δ狼的位置；X 为当前狼的位置。

1.2 改进的灰狼优化算法

1.2.1 K-Means聚类初始化种群 K-Means聚类算法[11]是通过距离度量数据相似性，数据间距离越小相似性越高，则可以归为同类。大量随机生成样本点后运用K-Means算法挑选k个精英个体（k个聚类中心）初始化种群。 假设随机生成 n 个样本点为 P={P1，P2，…，Pn}，需要聚类分成 k 类 C={C1，C2，…Ck}，聚类中心为 μ={μ1，μ2，…μk}，则可以计算样本点与各聚类中心的距离dist(Pi，uj)，将该样本点划分到距离最近的类（Pi∈μnearst），再根据类中样本点重新计算聚类中心，重复上述操作，直到满足迭代次数或最小化损失函数为止，将生成的各聚类中心（精英个体）用于初始化种群。其中，聚类中心更新公式为：

图1中随机生成500个样本点，设置种群数量k为30，运用K-Means聚类将500个样本点聚类分成30类，通过公式（7）计算出每类的聚类中心，将30个聚类中心用于初始化种群。由图1b可知500个样本点生成的30个种群精英个体，具有空间分布相对均匀的效果，增强了种群的多样性，避免算法开始时就陷入局部最优。

图1 K-Means算法聚类种群初始化（种群数量30）Figure 1 Population initialization of K-Means algorithm clustering(the number of population is 30)

1.2.2 非线性收敛因子 HEIDARI等[12-13]指出A和C是两个随机自适应向量以辅助GWO算法全局搜索和局部开发。由式（3）可知向量C是随机的，因此向量A与全局搜索与局部开发能力息息相关。|A|＞1时灰狼种群增大搜索范围寻找猎物，实现全局搜索；|A|＜1时收缩搜索范围攻击猎物，实现局部开发。由式（2）可知A的取值范围为[-a，a]，A随a变化，且随着迭代次数的增加a线性的从2衰减到0。而算法的收敛并不是线性的过程，在全局搜索阶段需要搜索慢些利于寻找猎物，而找到猎物后收敛快些易于迅速攻击，因此式（4）中a的线性衰减不能满足实际情况，从而引入非线性收敛的余弦收敛因子，即：

式中：Tmax为最大迭代次数；t为当前迭代次数。图2显示了收敛因素a的先慢后快的非线性收敛变化。

图2 收敛因子对比效果Figure 2 Comparison effect of convergence factor

1.2.3 位置更新调整策略 GWO算法的位置更新方程如式（6），其考虑了个体与种群的位置交流信息，但忽略了自身个体经验信息的交流[14]，而PSO算法对个体自身历史最优解具有记忆的能力[15]，因此在IGWO算中引入PSO算法中个体速度更新及位置更新策略，使得灰狼种群个体能够保存自身最优位置信息，则灰狼追踪猎物位置的数学模型可修改描述为：

式中：ω 为惯性系数；c1，c2，c3为学习因子；r1，r2，r3为[0，1]之间的随机数。

1.3 A*路径规划算法

A*算法[16-17]是一种启发式搜索算法，路径规划时对每个搜索位置进行估价，即：

式中：G(n)为起点到第n节点的实际代价，H(n)为第n节点到目标节点的最佳路径的估计代价。搜索过程是通过OPEN表和CLOSED表标识的，OPEN表记录了待搜索节点，CLOSED表记录了已搜索过节点，不断的根据估价函数重排OPEN表寻找最优节点实现搜索过程。

2 无人机农田喷洒航迹规划

无人机农田喷洒航迹规划主要有两个阶段，一是运用改进灰狼优化算法进行多喷洒点的无障碍空间遍历路径求解，以解决多喷洒点先后顺序及喷洒路径，二是运用A*算法对喷洒路径进行修正以避免障碍物碰撞。

2.1 IGWO算法求解无障碍空间航迹路径

假设区域工作环境地图已知，要求无人机能够遍历全部n个喷洒点形成遍历航迹路径，则路径长度为：

式中：||TjTj+1||表示第j到j+1个喷洒点的距离。||TnT1||表示第n喷洒点到起始喷洒点之间的距离。要求出遍历任务点顺序 T={T1，T2，…，Tn}，使路径长度最短 min（L）。 以式（12）作为目标函数，运用IGWO算法求解最优解得出无障碍物空间多喷洒点一次航迹路径，其流程如图3。

2.2 A*算法求解障碍物空间航迹路径

A*算法以图的输入形式进行连接编码矩阵区域搜索，寻找出一条从起点到已搜索区域中所有节点的最短路径。为了降低计算复杂度，A*算法首先将高分辨率地图降低为适用的低分率地图，将降低分辨率地图的每个像素作为节点，每个节点都有许多无障碍物连接线作为边，形成编码矩阵，图4为常用的3种连接编码矩阵（搜索模板），所有可能的移动用1表示，所有不可以的移动用0表示，R代表无人机当前位置。搜索方向越多，搜索路径可能性就越多，搜索精度越高，但计算耗时会越大。图6a为分辨率500×500降低到100×100的地图上进行模板b的路径扩张搜索区域（灰色区域），图6b为避障后从喷洒点(50，50)到喷洒点(400，400)规划出的航迹路线，路径长度为 553．5534m。

图3 IGWO算法求解航迹规划流程图Figure 3 Flow chart of IGWO algorithm to solve the route planning

图4 连接编码矩阵Figure 4 Connection coding matrix

3 试验仿真结果与分析

3.1 IGWO算法无障碍物航迹规划

图5为GWO算法与IGWO算法在无障碍物空间中求解多个喷洒点的航迹规划路径对比效果，其中种群的数量设置为30，最大迭代次数为800次，当待喷洒点较少时（图5a和图5b 5个喷洒点），GWO算法与IGWO算法航迹规划路径相同，均为2-3-4-5-1-2喷洒点遍历航迹路径，路径长度2552．7062m。而当待喷洒点较多时 （图5c和5d 30个喷洒点），GWO算法与IGWO算法求解无障碍物空间航迹路径分别为6357．799m和6092．4102m，路径缩短265．3888m，路径缩短4．17%。从图6对30个任务点求解适应度曲线的收敛情况可知，IGWO算法第248次迭代时便寻找到了最优遍历路径，而GWO算法在784次迭代才寻找到最优解路径，IGWO算法寻优迭代次数为GWO算法的1/3，效率提升2倍，且IGWO算法的收敛效果要优于GWO算法，说明IGWO算法的模型求解能力更强。

图5GWO算法与IGWO算法无障碍物空间航迹规划对比Figure 5 Route planning for obstacle avoidance of A*algorithm

3.2 A*算法障碍物避障航迹规划

图7 为房屋障碍物田间地图，通过交互式标记出障碍物区域如图7b白色区域，生成障碍物地图掩模板，图7c白色区域为障碍物区域不可通行，黑色区域为自由空间可通行。运用A*算法通过2．2节3种连接编码矩阵模板对障碍物进行避障及航迹规划，路径起点坐标为(250，50)，目标点坐标为(150，200)，其路径规划长度分别为 327．4000，296．6703，287．5984m， 路径规划效果如图7d～f，可以看出连接编码矩阵模板越简单，路径规划效果越差但耗时相对减少，综合考虑路径长度及路径平滑程度，可以得出模板b与模板c是可以被选择的。

3.3 基于IGWO-A*算法的农田喷洒无人机航迹规划

图8a白色实线段为农田区域无障碍物时IGWO算法求解的遍历多喷洒点的航迹规划效果，其遍历顺序为1-8-2-5-4-3-7-6-1，此步为一次航迹规划。当发现规划路径中喷洒点6至喷洒点1的航迹中有障碍物阻碍，如图8b白色方框为障碍物区域，此时在此段航迹中运用A*算法进行喷洒点6坐标为起点，喷洒点1坐标为目标点的避障二次航迹规划，以修正此段航线。图8c和图8d的白色虚线段为A*算法运用模板b和模板c搜索的避障二次修改效果路径，从而形成了农田多喷洒点无人机航迹规划结果。

图6 收敛性能对比Figure 6 Comparison of convergence performance

图7 A*算法求解避障航迹路径Figure 7 A*algorithm to solve the path of obstacle avoidance

图8 基于IGWO-A*算法的农田喷洒无人机航迹规划结果Figure 8 Result of route planning of UAV for farmland spraying based on IGWO-A*algorithm

4 讨论与结论

本研究结果表明，改进灰狼优化算法引入K-Means聚类算法，可以从500种群个体筛选出遍布全局的30个精英个体以初始化种群，可以加强种群的多样性与优越性；引入非线性收敛因子可以实现全局搜索慢些以广泛的搜寻猎物，在找到猎物收敛快些以迅速攻击猎物；引入PSO算法的对于个体自身历史最优信息的记忆能力，可以使得灰狼种群个体能够保存自身最优位置信息。通过上述对传统灰狼优化算法的改进，使得对无人机喷洒作业遍历航迹规划模型求解的能力更强。在本试验模型环境中，IGWO算法需要248次迭代找到最优解遍历路径，而GWO算法需要784次迭代才能找到最优解路径，效率提升2倍。而在航迹规划长度上，本试验环境下对于5个任务点的遍历航迹规划GWO算法与IGWO算法的航迹规划长度相同；而对于30个任务点遍历航迹规划IGWO算法比GWO算法规划路径缩短4．17%，可见，IGWO算法对于大任务量作业任务更具优越性。除此之外，徐博等[18]在植保无人机航迹规划中有深入研究，为了降低无人机总能耗，提出了一种多架次往复遍历式植保无人机的作业路径。又针对多作业区域运用改进二进制编码的遗传算法与TSP模型结合进行了多作业区域植保无人机航线全局规划[19]，对无人机植保作业航迹规划均有一定的成效，但并未考虑无人机低空作业的障碍物碰撞问题。本研究在无人机航迹规划的同时，进行低空障碍物避障路径优化，以更加适应低空任务场景的需求。

综上所述，IGWO算法与A*算法相结合的无人机农田喷洒航迹规划策略，不但可以增强模型的求解能力，缩短航迹规划长度；而且充分考虑了低空作业时障碍物区域避障问题，可以二次航迹路径修正以避免碰撞，有利于无人机农田喷洒作业的实施。本研究并未考虑作业任务点是如何确定的，如若加入机器视觉与深度学习识别过程且样本量足够大时，可以实现喷洒点（如虫害区域、杂草区域等）的自动提取与分类[20-21]，可以提升无人机农田喷洒作业系统的自主性，促进智慧农业的发展。