农用无人机多机多田块作业路径规划算法

唐灿，宗望远,2，黄小毛,2，罗承铭,2，李文成,2，王绍帅

1.华中农业大学工学院，武汉 430070； 2.农业农村部长江中下游农业装备重点实验室，武汉 430070

近年来，无人机逐渐发展成为一种常见的农业生产机械[1]，可以实现遥感[2]、植保[3]、播撒[4]等多种农业作业任务。相较于单个无人机作业，多机协同作业可显著提高作业效率，减少具体田块的作业处理时间[5-6]，是大面积多区域作业时的一项重要形式[7]。

路径规划问题是近些年无人机领域的研究热点。由于实际作业工况多种多样，对单机单田块区域、多田块区域、含障碍物区域、按需补给以及多机协同等都有相关研究。比如单架无人机作业路径规划方面，Valente等[8]提出一种基于“和谐搜索”(harmony search)的启发式搜索算法去求解单机作业情况下的遍历网格的最优次序，王宇等[9]提出一种基于栅格模型的路径规划算法，黄小毛等[10-11]提出基于多边形扫描填充线快速求解的无人机路径规划算法，严炜等[12]提出一种基于差分量子退火算法的农用无人机路径规划方法。

多机协同作业时，主要考虑待作业任务的划分，为使得任务尽可能均衡，一般采用“等面积法”划分待作业区域后再分别规划航线[13-14]。此外，Barrientos等[15]将待作业区域进行网格化处理，并提出一种基于任务协商机制的作业路径规划算法，Nigam等[16]提出一种适用于矩形区域的区域划分与分配算法。由于载荷及续航问题，对于多田块区域，单航次往往无法满足作业要求，因此，需要考虑中途返航至补给点进行电量以及农资的补给。徐博等[17]基于最小能耗对单一大面积矩形边界田块中的补给架次进行了研究。李继宇等[18]基于能量利用率最大化原则，对边界形状简单且单一的田块补给过程进行了研究。

随着电动旋翼农用无人机应用日益广泛，对含障碍物大面积多田块区域的作业任务需求日益增多。本研究在笔者所在课题组前期工作基础上，针对含障碍物多田块条件下，综合考虑电量以及农资补给，提出一套基于Google OR-Tools[19]的农用无人机多机协同作业路径静态规划算法，旨在为多田块条件下的多机协同作业路径规划优化提供参考。

1 材料与方法

多台农用无人机协同作业路径规划的任务是先计算出完全覆盖田块多边形区域的基础作业航线，再分配给多台无人机并合理安排多次补给续航方案。本研究计算时忽略无人机在工作时可能发生的碰撞问题以及天气、风速等外部环境影响和因作业进程而变化的实际载荷对动力的动态影响。

1.1 算法总体流程

以最小转移路径长度为作业优化目标，基于多边形扫描填充算法[10-11]计算出水平航向条件的初始覆盖作业航线，将田块边界障碍物进行安全边界相交性测试[10-11]，并分别针对各田块采用凸多边形“最小跨度法”[10-11]以及非凸多边形“步进旋转法”[10-11]优化作业航向。再基于Google OR-Tools组合优化开源软件工具包，综合考虑消耗品按需返航后的补给与续作问题，进行航线调度次序及作业航次的规划。

以田块及障碍物的边界和飞行作业参数为输入，以作业路径为输出，整个算法的流程如图1所示。

图1 算法流程图Fig.1 Algorithm flow chart

1.2 航线调度优化

建立航线调度目标模型，参照旅行商问题(traveling salesman problem,TSP)，将初始作业航线的每个端点简化为1个“城市”。为保证航线上每个点均可被遍历且无人机可以从航线的一端飞向另一端，在构建TSP距离矩阵时将位于同一航线上的2个城市点间的名义距离设为0，而将实际距离均分到该航线与其他航线间的转移路径上。假设有m台无人机，n条作业航线(加上起降点，共对应2n+1座城市)，集合A={1，2，…，2n}、B={0,1，2，…，2n}、C={1，2，…，m}，每台无人机中有rk次不包含补给点的危险转移过程[10-11]，sk次包含补给点的危险转移过程，h0为作业高度，h为安全高度，则该问题的数学模型可描述如下：

(1)

i,j∈B,k∈C

(2)

(3)

(4)

(5)

按照上述模型，可在基础航线数据上建立该问题的距离矩阵，并通过算法进行求解。穷举搜索所有航线调度方式可得到最小转移路径，但计算效率较低。本研究采用Google OR-Tools开源工具包中的智能算法，在规定时间内找出尽可能最优的解。解决路径问题时，OR-Tools提供2种解算器，本研究采用其中最常用的解算器CP-SAT。OR-Tools使用最先进的算法缩小搜索集范围，以便找到最佳(或接近最佳)的解决方案[19]，解算器包含了14种初始解构造策略算法(first solution strategy)和5种优化搜索策略算法(local search options)。前者负责构造初始解，包括节约算法(savings)、扫描算法(sweep)、最近插入法(best insertion)、克里斯托菲德斯算法(Christofides)等经典求解算法；后者对初始解进一步优化，包含改良贪心算法(greedy descent)、引导式本地搜索算法(guided local search)、模拟退火算法(simulated annealing)、禁忌搜索算法(tabu search)与目标禁忌搜索算法(objective tabu search)。二者组合起来将形成70种组合策略算法，因篇幅有限，列举其中4种组合策略如表1所示。

表1 4种航线调度组合策略 Table 1 Four combined strategies for route scheduling

1.3 按需多次补给

无人机具有最大起飞质量限制，作业时携带的种肥药液等农业物资也会消耗大量的动力，而电池或燃油容量与其质量成正比。因此，每个航次携带农资的最大质量和电池的容量会受到限制，一般会有一个经济值。本研究暂不考虑农资消耗过程对续航能力的动态影响，设每台无人机最大农资载荷为Q，每个航次的最大续航里程为Lmax。航线作业时会消耗一定量的农资，消耗量与航线对应的单位距离或覆盖面积成正比。求解时，将每条航线需要消耗的农资量均摊到2个航线端点“城市”上。设每个航线端点的农资需求量为qi(i=1,2,…,2n)，yki为无人机k到访端点i，本航次已完成其中u条航线的遍历任务，D为对应的端点序号集合，则农资消耗约束条件为：

(7)

(8)

当动力与农资的累积消耗量其中任意一种超过限制时，执行补给操作，即返回至补给点将动力与农资完全重置。补给完成后，将剩余航线进行重新排序，直至找到新的返航点或完成所有航线的遍历作业[11]。

采用OR-Tools中的CVRP(capacitated vehicle routing problem,具有能力约束的车辆路径问题)求解算法，进行航线任务分配及补给方案的求解。

2 结果与分析

前述算法过程基于Python 3.8语言在PyCharm平台上编码实现，在AMD Ryzen 7 4800,1.8 GHz CPU、16 GB 1 600 MHz内存、Windows 10操作系统环境下，分别对4组人工假想和实际多田块边界在多组不同工作参数条件下进行2次试验，以测试算法稳定性、计算效率和优化效果。

田块边界用蓝色多边形表示，每台无人机航线分别用红色、蓝色、黑色等不同颜色线段表示，转移路径用绿色虚线段表示，无人机的补给返航点用与航线颜色相同的圆圈标记，每个航次起始处加数字标记，其中危险转移过程对应航点处加黑色三角形标记。

表2 测试算例田块参数 Table 2 Field parameters for case studies

设无人机台数为3。实际田块边界利用Omap获取并以KML文件格式导出；假想田块边界利用CAD绘制并以DXF格式导入。计算过程中，先基于多边形扫描填充算法计算出水平航向条件的初始覆盖作业航线，再采用凸多边形“最小跨度法”与非凸多边形“步进旋转法”(取步距角Δθ=0.5°)优化作业航向；后基于OR-Tools求解出田块最优航线调度次序并将航线分配给3台无人机，最后按照无人机性能建立能量与物资消耗模型，调用OR-Tools优化作业航次，计算过程中对每个潜在转移过程均进行安全判断并对危险转移过程进行处理。

算法中统一设定作业高度2 m(实际作业中，为保证绝对安全，要求航线间转移时不同飞机必须采用不同的转移高度，此处作简化处理)，安全转移高度6 m，安全边界距离1 m。参考文献[11]中作业参数，设定无人机速度为3 m/s，电力或燃油续航能力4 000 m，单次航行所需农资为12 L，变量喷播模式下单位面积喷播量为18 L/hm2。同时为避免OR-Tools出现因过分追求最优解使得求解时间过长的情况，设置该环节最大求解时长为30 s。

首先尝试通过初步试验，对比测试70种不同组合策略对不考虑补给时的调度优化算法效果。因篇幅有限，而测试结果表明进一步优化搜索策略算法中引导式本地搜索算法优化效果最好，禁忌搜索算法优化效果最差；同时克里斯托菲德斯算法(Christofides)是旅行商问题中近似比最好的结果，扫描算法(sweep)也是车辆路径问题中较为常用的方法，因此只截取由以上4种算法所组成的4种组合策略优化结果，如表3所示。

从表3可以看出，“Christofides算法×引导式本地搜索算法(C×G)”组合下的计算结果，无论在路径总长度还是算法耗时上，都与“sweep算法×引导式本地搜索算法(S×G)”大致相当；“Christofides算法×禁忌搜索算法(C×T)”组合下的计算结果与“sweep算法×禁忌搜索算法(S×T)”也是基本一致。而当比较“Christofides算法×引导式本地搜索算法(C×G)”和“Christofides算法×禁忌搜索算法(C×T)”组合下的计算结果时，出现了相对较大的差异，同样的趋势出现在“sweep算法×引导式本地搜索算法(S×G)”和“sweep算法×禁忌搜索算法(S×T)”组合下的计算结果。这说明，不同的初始解构造策略对结果影响不大，结果上的差异主要由进一步的优化搜索策略算法的不同而引起并决定。

表3 多机作业4种不同航线调度组合策略算法下初始路径规划(不考虑补给)测试结果 Table 3 Results of initial path planning under four different route scheduling combination strategies algorithm for multi UAVs operation without replenishment

进一步固定初始解构造策略为常用的Christofides，对比测试5种优化搜索策略算法对考虑补给情况下的路径优化效果，并且与文献[13-14]中等面积划分算法进行对比，结果如表4所示。表4中，5种优化搜索策略算法的转移路径总长度的数据，相同条件下相比较最好的结果用**注释，最差的结果用*注释；优化结果分别对比等面积划分算法结果，计算出优化提升效果。

从表4可知，5种进一步的优化搜索策略算法的效果各不相同。从优化结果上看，对转移路径总长度的优化效果，引导式本地搜索算法(G)最好，8个算例中有7个是最优的，禁忌搜索算法(T)和目标禁忌搜索算法(OTS)最差，各获得3个算例的最差结果，其次是模拟退火算法(SA)和改良贪心算法(GD)获得1个算例的最差结果。造成这种差异的主要原因除了算法本身的设计差异外，可能还在于设置了30 s求解时间的限制。也就是说部分算法能够在该时长内快速逼近最优解，而其他算法可能需要更多的寻优时间。

将各算例的OR-Tools优化结果，与等面积划分法的算法结果进行对比时，发现最优结果对转移路径总长度的优化效果为30.92%～47.10%，而最差优化效果也能够达到24.86%～43.96%。这说明，基于OR-Tools优化效果显著，非常有必要。同时，从算法耗时上看，改良贪心算法的耗时最短，其他算法的耗时相当，为70～552 s，但基本在路径离线规划优化操作的可接受范围之内。

表4 多机作业5种优化搜索策略算法对考虑补给情况下的优化结果 Table 4 Results of five optimizing search strategy algorithms for multi-UAVs considering replenishment

表5中给出了相同初始解构造策略算法下5种进一步优化搜索策略算法的最优和最差结果与等面积划分优化算法的结果的相关图例，可见算法所得基础航线对田块区域的覆盖效果良好，基本看不出重漏作业区域。

表5 5种优化搜索策略算法中最好及最差优化结果和等面积划分算法结果截图 Table 5 Screenshots of the optimal and worst results in 5 optimizing search strategy algorithms

续表5 Continued Table 5

3 讨 论

本研究针对含障碍物多田块条件下的农用无人机路径规划问题，研究了多机协同全覆盖路径规划优化算法。同时考虑消耗品按需返航后的补给与续作问题，基于Google OR-Tools组合优化开源软件工具包，对不同的调度搜索策略进行了对比试验研究。利用4组假想与实际含障碍物多田块进行仿真试验测试，首先测试了Google OR -Tools组合策略算法在不考虑补给时的优化效果和计算效率，结果表明 OR-Tools初始解构造策略对最终结果影响不大，结果上的差异主要由进一步的优化搜索策略算法的不同而引起并决定。然后将本研究设计的算法与无人机沿航向方向等面积划分算法相比较，结果表明算法运行稳定可靠，优化效果明显，相比于等面积划分算法，航线间转移路径总长度下降了24.86%～47.10%，算法耗时70～552 s，在路径离线规划优化操作的可接受范围之内，满足无人机路径离线规划优化的算法耗时要求和优化目标。