徐利锋，杨中柱，黄祖胜，丁维龙

(浙江工业大学 计算机科学与技术学院，杭州 310023)

E-mail：lfxu@zjut.edu.cn

1 引 言

随着通信技术、自动控制技术、传感技术以及人工智能的发展，无人机的功能越来越完善，如何提高无人机的工作效率以及降低无人机的能耗成为了植保无人机领域的研究热点[1，2].无人机航线规划指的是在指定的约束条件下，根据工作目的来设计出一条无人机飞行路径，飞行路径的优劣程度根据具体的工作目的来确定.在军事应用领域，军用无人机能够执行侦查预警、中继通信、战场搜救、跟踪定位等多种任务，设计出更优的无人机飞行路径能够有效的躲避雷达侦测并提高任务成功率[3，4].在民事应用方面，无人机得到了非常广泛的应用[5].例如在物流行业中用无人机来进行自主配送，能够有效降低物流运输的人工成本，根据配送点的位置信息设计出较好的无人机航线能够有效的提高物流运输效率.在农业领域，用植保无人机进行喷雾作业具有效率高、速度快等优点，并且无人机能够在没有跑道的小型区域内垂直起降，能够很方便的在各种地形上进行喷洒作业[6-8].

目前大多数植保无人机需要工作人员用遥控来手动操作，这种方式过分依赖于操作人员的技术，在实际应用中并不能获得很好的效果[9-11].通过遥控驾驶方式来控制无人机的移动会对操作人员产生较大的负荷，并且遥控驾驶方式对于时间延迟以及飞行控制等方面具有较高的要求[12].彭孝东等[13]基于GPS坐标采集无限传输系统，通过手动操作的方式进行了无人机喷洒试验，结果表明人工操作的无人机飞行路径与理论设计的无人机航线偏离严重，通过手动操作的方式无人机很难做到精准作业.随着卫星定位技术的发展，以GPS(Global Positioning System，全球定位系统)导航为主并且能够根据目标区域自动生成无人机作业航线的自主飞行作业模式成为了目前植保无人机的主要发展趋势，对于无人机航线设计的研究显得尤为必要.

植保无人机航线设计属于全覆盖路径规划的范畴，根据航线设计的时间点将全覆盖航线规划算法分为两种[14]：1)根据已有的环境信息包括目标区域形状、大小以及区域内部障碍物的分布情况等，在无人机起飞前设计出一条无人机飞行航线，让无人机沿着设计出的航线飞行，这种方法称为离线式航线规划方法；2)另外一种是在无人机飞行过程中，通过传感器来对目标区域实时扫描，根据扫描结果来实时计算无人机飞行路径，这种方法称为在线式航线规划方法.徐博等[15,16]针对植保施药多个作业区域的情况，提出了一种基于遗传算法的植保无人机航线设计方法，将航线长度、多余覆盖以及重复覆盖作为评价无人机航线优劣的标准；另外其针对不规则区域提出了一种基于作业方向的不规则区域作业航线规划算法，该算法可以根据指定的作业方向快速规划出无人机作业航线.在植保无人机实际作业过程中，受到目标作业区域过大、无人机载药量和续航时间有限等因素的影响，无人机需要多次返航才能完成对目标区域的喷洒作业，针对该实际情况，王宇等[17，18]提出了一种基于栅格法和引力搜索算法的植保无人机路径规划方法，将无人机作业所耗费的时间作为评价路径优劣的标准，实现了对返航点数量及位置的寻优.Gabriely[19]提出了一种基于生成树(Spanning Tree Coverage，STC)的在线式航线规划算法Spiral-STC，通过传感器获取周边环境信息并生成局部地图，通过对局部地图进行栅格划分来获得有效栅格以及障碍栅格.该方法能够保证所有有效栅格均被覆盖，并且不存在重复覆盖的情况，但是由于设计出的航线转弯次数过多而导致增大了能耗成本，另外由于栅格划分的不精确导致出现了遗漏覆盖的情况.Gonzalez[20]等提出了一种改进的Spiral-STC算法，在原始的Spiral-STC算法基础上增加了外环航线，能够有效地提高航线的覆盖率，Choi[21]在此基础上加入了新的地图坐标分配方法，通过分析传感器的历史坐标数据进行分析进而重新分配坐标，能够有效地降低航线的转弯次数.

在作业区域中，由于地形、输电设备以及其余人为因素的限制，形成了障碍区域.单元分解法[22]是含障碍区域航线设计方法中的一种常用方法，其基本思想是对含障碍区域进行分解，将其分解为多个不含障碍的子区域，然后设计出合理的子区域连接顺序，每个子区域内部用牛耕法[23]来完成.梯形分解法[24]是一种典型的单元分解法，其基本思想如下：用一条虚拟的扫描线对工作区域进行扫描，扫描线与工作区域内部的障碍物存在着相离、相切、相交三种状态，根据扫描线以及障碍物的边界，将工作区域分解为多个子区域，并且每个子区域都是梯形.在梯形分解法中将工作区域分解为子区域时，是用一条扫描线对工作区域进行扫描，扫描线的方向没有改变，因此该算法具有一定的局限性.Huang等[25]针对该问题提出了一种能够让扫描线的方向进行变化的线扫分割法(Line-sweep Decomposition)，在扫描工作区域时对每个子区域使用不同方向的扫描线，最后通过最小高度和(MSA，Minimal Sum of Altitudes)来将扫描后的子区域合并，减少子区域数量.基于上述方法所设计出的无人机航线，往往存在着转弯次数过多的问题，不仅增加了无人机作业的能耗，而且降低了无人机作业的效率.

本文以减少无人机航线转弯次数、提高无人机作业效率为目的，针对含障碍工作区域进行了无人机航线规划方法研究，提出了一种新的植保无人机航线规划算法.基于栅格法来对目标区域进行路径点采样，用路径点来表示目标区域的特征信息，并结合混合粒子群算法来对路径点进行排序，用路径点的排列来表示无人机飞行路径，设计出一条能够有效规避障碍物并对工作区域完成全覆盖的航线.

2 路径点采样

栅格法[26]是一种常用的描述环境信息的方法，栅格法将目标区域用多个正方形网格单元来表示，每个网格单元具有一个属性值来表示该网格单元内是否包含障碍物，不包含障碍物的网格称为有效网格，包含障碍物的网格称为无效网格.在对环境地图进行网格化时，若网格单元过大，那么可能出现某个网格内只存在一小块障碍区域而导致该网格被标记为无效网格，划分后的网格对环境信息描述的准确度较低.对于在线式航线规划方法，栅格划分精度过低会将非障碍区域标记为障碍区域，而栅格划分精度过高会增大计算量，由于在线式航线规划方法对于实时性的要求较高，因此栅格划分精度不能过高.而在离线式航线规划方法中主要是在环境信息已知的条件下对有效网格进行排序，并且在无人机工作前进行航线设计，通过计算机进行处理计算能够有效的解决因栅格法划分精度过高所带来的计算成本增加的问题.本文对于无人机航线规划研究属于离线式，在离线式航线规划方法中栅格划分精度越高越好，若栅格单元的边长小于无人机喷幅宽度，那么无人机按照设计出的航线进行喷雾作业时会出现重复覆盖的情况，因此在本次研究中我们将网格单元的边长设置为无人机的喷幅宽度.

如图1所示，用栅格法来表示环境信息时，绘制出目标区域边界的最小外接矩形，并将矩形的长和宽调整为栅格边长的整数倍.包含作业区域同时不包含障碍区域的栅格称为有效栅格，不包含作业区域也不包含障碍区域的栅格称为无效栅格，包含障碍区域的栅格称为障碍栅格，其中障碍栅格也属于无效栅格.在设计无人机航线时按照一定的顺序连接所有有效栅格，让航线避开无效栅格，完成对整个工作区域的覆盖.

图1 栅格化示意图Fig.1 Schematic illustration of gridding

用栅格法来表示环境信息时，部分栅格中同时包含工作区域以及障碍区域，或者同时包含了工作区域以及工作区域边界外部区域，在栅格法中将这些栅格全部设置为无效栅格，进行航线规划时无人机航线并不经过这些栅格，降低了无人机航线的覆盖率.

图2 路径点采样示意图Fig.2 Schematic illustration of path point sampling

如图2所示，本文用路径点来代替栅格，对工作区域进行栅格化后，在每个栅格单元的中心点设置一个路径点，并将包含在障碍物边界内部的路径点以及工作区域边界外部的路径点设置为无效路径点，包含在工作区域边界内部以及障碍物边界外部的路径点设置为有效路径点.无人机飞行路径可以用路径点的排列顺序来表示，将无人机航线规划转化为对路径点的排序.

3 基于混合粒子群算法的路径点自动排序算法

组合优化问题[27](Combinatorial Optimization Problem，COP)指的是在给定的约束条件下，根据预期目的从目标问题的可行解集中寻找最优解的问题，路径点的排列问题也是一种组合优化问题.在目标问题的规模较小时可以用穷举法来获取目标问题的最优解，但是随着问题规模的扩大，算法运行所消耗的时间也在不断增加，出现了组合爆炸问题.启发式优化算法的出现为解决组合优化问题提供了一种新的思路，能够有效解决组合爆炸问题.

3.1 混合粒子群算法

粒子群优化算法(Particle Swarm Optimization，PSO)是一种仿生智能优化算法，PSO模拟了自然界中鸟群的觅食过程[28].在鸟群寻找食物的过程中存在着分散搜寻以及群体搜寻两种情况，分散搜寻指的是鸟群中的单个个体沿着不同的方向去寻找食物，当某个个体寻找到食物的位置时会向整个群体中的其余个体传递食物位置信息，然后整个群体会朝向食物位置移动.研究表明在自然界生物的觅食过程中，个体之间互相学习的种群能够比个体之间相互竞争的种群更加快速地寻找到食物[29].在粒子群优化算法中，种群中的每个粒子表示优化问题的可行解，而食物位置代表着该优化问题的最优解.整个种群为了找到食物位置而不断在解空间中进行探索，在探索过程中所有个体通过自身的寻找经验以及种群中其余个体的寻找经验来不断移动.在算法优化过程中，单个粒子通过自身的历史最优值(pbest)以及种群历史最优值(gbest)来调整粒子的位置以及速度，根据实际的优化问题来确定适应度函数并且通过适应度函数来判定最优值.粒子的更新公式如下：

xi(t+1)=xi(t)+vi(t+1)

(1)

vi(t+1)=ωvi(t)+c1r1(pbesti(t)-xi(t))+
c2r2(gbest(t)-xi(t))

(2)

r1和r2是随机数，其取值范围为[0，1].c1和c2为学习因子，c1表示该个体向其自身历史最优值的学习能力，c2表示该个体向种群历史最优值的学习能力，c1和c2的取值范围为[0，2].这里ω为惯性权重因子，惯性权重表示粒子的速度受到粒子惯性的影响程度.

粒子群算法使用粒子的个体信息、个体历史最优值以及种群历史最优值来对粒子的属性进行更新.对于本文所描述的路径点排列优化问题，粒子的位置表示一条路径，而粒子的速度难以表示，因此本文使用混合粒子群算法[30]来对目标优化问题进行求解.式(2)中的ωvi(t)项视为遗传算法中的变异操作，c1r1(pbesti(t)-xi(t))项视为当前个体与个体历史最优值进行交叉操作，c2r2(gbest(t)-xi(t))视为当前个体与种群历史最优值进行交叉操作.对当前个体进行变异操作以及交叉操作后，得到新个体的适应度值可能会低于原有个体的适应度值，若新个体优于原有个体，那么接受新个体，否则舍弃.

3.2 变异操作和交叉操作

假设有效路径点总数为n，由路径C1变异到路径C2，常用的变异策略有以下几种：

1)在路径C1={P1，…，Pi-1，Pi，Pi+1，…，Pj-1，Pj，Pj+1，…，Pn}中随机选择两个路径点Pi和Pj，在路径C1中交换Pi和Pj，得到的新路径即为C2={P1，…，Pi-1，Pj，Pi+1，…，Pj-1，Pi，Pj+1，…，Pn}.

2)在路径C1={ P1，…，Pi-1，Pi，Pi+1，…，Pj-1，Pj，Pj+1，…，Pn}中随机选择一段子路径C0={ Pi，Pi+1，…，Pj-1，Pj}，将C0反转并插入原有位置，得到的新路径即为C2={P1，…，Pi-1，Pj，Pj-1，…，Pi+1，Pi，Pj+1，…，Pn}.

3)在路径C1={P1，…，Pi-1，Pi，Pi+1，…，Pn}随机选择一个路径点Pi，交换Pi和Pi+1，得到的新路径即为C2={P1，…，Pi-1，Pi+1，Pi，…，Pn}.

在无人机航线规划问题中，无人机航线需要覆盖整个工作区域，并且需要尽量减少对工作区域的重复覆盖.结合实际优化问题，本文提出了一种新的变异策略，具体步骤如下：

Step1.对于路径C={P1，...，Pi-1，Pi，Pi+1，...，Pn}，随机选择一个路径点Pi，若点Pi与点Pi+1在工作区域中为不相邻的两个路径点，那么进入Step 2，否则重复Step 1；

Step2.在剩余路径点集合C-{Pi}中随机选择一个点Pj，若点Pj与点Pj+1在工作区域中为不相邻的两个路径点，那么进入Step 3，否则重复Step 2；

Step3.在路径C中交换点Pi和点Pj，得到的新路径即为变异后的路径.

对于两条路径C1和C2，常用的交叉方法有以下几种：

1)在C2中随机选择一条局部路径C0，将C1中与C0相同的路径点删除，然后将C0添加到C1末尾，得到的新路径即为交叉路径.

2)在C2中随机选择一条局部路径C0，将C0添加到C1中的对应位置并将C1中与C0重复的路径点删除，得到的新路径即为交叉路径.

3)在C2中随机选择一条局部路径C0，将C0随机添加到C1中的任意位置并将C1中与C0重复的路径点删除，得到的新路径即为交叉路径.

3.3 路径点排序优化算法

在文献[25]中提出了无人机在转弯时会经历“减速-转弯-加速”过程，与直线飞行相比，转弯过程会带来更大的能量消耗，因此无人机航线的转弯次数越少越好，本文将无人机航线转弯次数作为评价无人机航线优劣的标准.算法的适应度函数如下：

(3)

C表示任意一条路径，T为该路径的转弯次数.

算法具体步骤如下：

1)初始化.假设有效路径点总数为n，那么初始路径用1-n的随机排列表示，粒子的位置代表一条路径.根据指定的种群大小m初始化种群，获得m条初始路径(C1，C2，…，Cm).

2)计算种群最优值以及每个粒子的个体历史最优值.根据适应度函数计算出所有粒子的适应度值，将适应度值最大的粒子所表示的路径设置为种群最优值Cpbest，初始时刻第i个粒子的个体历史最优值Cgbesti与其初始值Ci相同.

6)终止.若算法未达到最大迭代次数，那么返回第3步继续运行.若算法达到最大迭代次数，那么算法停止，输出最优路径Cpbest.

4 仿真实验

本次仿真实验环境为Windows10操作系统，编程语言使用Java程序设计语言，硬件平台为Intel(R) Core(TM) i7-6700HQ @ 2.60 GHz，内存为16 GB.

本次实验在单障碍工作区域以及多障碍工作区域内进行了无人机航线设计，并与文献[31]中提出的基于Reeb图的欧拉回路航线设计方法进行了对比，文献[31]基于牛耕单元分解法对含障碍工作区域进行了子区域划分，用Reeb图来表示子区域，将子区域衔接问题转化为Reeb图边的遍历问题，通过匈牙利0-1指派法实现了Reeb图奇度节点的最小权匹配，并基于改进的Fleury欧拉回路算法来确定最佳的子区域衔接顺序，最终实现对含障碍作业区域的无人机航线规划.

4.1 单障碍工作区域航线设计

本研究在实验中设计了三个不同位点(位点1、2、3)的单障碍，并运用前述算法进行工作区域航线设计.

图3 单障碍(位点1)工作区域无人机航线设计结果Fig.3 Result of UAV route planning on target area with single barrier(position No.1)

如图3所示，对于一块80 m*80 m的工作区域，边界顶点坐标分别为(0，0)，(80，0)，(80，80)，(0，80)，其内部存在一块不规则的凹多边形障碍物区域，障碍物边界各个顶点坐标分别为(4.5，23)，(7，16.5)，(13，15.5)，(18，10)，(24.5，11.5)，(24，22.5)，(13.5，24.5)，设定无人机喷幅宽度为5 m，最终航线设计结果如图3(a)所示.从图中可以看出按照本文所提出的方法设计出的无人机航线避开了工作区域内部的障碍物，并且航线不存在交叉的情况，说明无人机按照该航线进行喷雾作业时没有出现重复覆盖的现象，航线转弯次数为36次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图3(b)所示，航线转弯次数为60次，可以看出本文所提出的方法能够设计出一条转弯次数更少的无人机航线.

图4 单障碍(位点2)工作区域无人机航线设计结果Fig.4 Result of UAV route planning on target area with single barrier(position No.2)

如图4所示，工作区域大小为80m*80m，障碍物顶点坐标分别为(10，50)，(6，49)，(4.5，41.5)，(7，31.5)，(11，30)，(16.5，33)，(14.5，48)，无人机喷幅宽度为5m，航线规划结果如图4(a)所示，航线转弯次数为34次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图4(b)所示，航线转弯次数为60次.

图5 单障碍(位点3)工作区域无人机航线设计结果Fig.5 Result of UAV route planning on target area with single barrier(position No.3)

如图5所示，工作区域大小为80m*80m，障碍物顶点坐标分别为(37，46)，(33.5，33.5)，(56，34)，(53，46)，无人机喷幅宽度为5m，航线规划结果如图5(a)所示，航线转弯次数为27次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图5(b)所示，航线转弯次数为60次.

图6 包含两块障碍物的工作区域航线设计结果Fig.6 Result of UAV route planning on target area with two barriers

4.2 多障碍工作区域航线设计

实验中模拟了包含多个障碍物的工作区域，如图6所示，工作区域大小为80m*80m，其内部存在两块不规则的凸多边形障碍物区域，左下角障碍物顶点坐标分别为(10，30)，(5，28)，(7，12)，(14，8)，(16，13)，(12，20)，(14，28)，右上角障碍物顶点坐标分别为(54，66)，(58，54)，(73，56)，(76，64)，航线规划结果如图6(a)所示.当目标工作区域内部存在多块障碍物时，本文提出的方法仍然能够设计出一条规避所有障碍物的航线，并且保证了无人机按照指定航线进行作业时不会出现重复覆盖现象，航线转弯次数为39次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图6(b)所示，航线转弯次数为42次.

如图7所示，图中的目标区域中在图6所示的工作区域的基础上添加了一块新的障碍物，图中共有三块障碍物，新加的障碍物顶点坐标分别为(54.5，21)，(57.5，15)，(53.5，9)，(66，11)，(64，18)，航线规划结果如图7(a)所示.图7(a)中的航线绕开了新增加的障碍物，航线转弯次数为46次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图7(b)所示，航线转弯次数为88次.

图 7 包含三块障碍物的工作区域航线设计结果Fig.7 Result of UAV route planning on target area with three barriers

如图8所示，工作区域大小为80m*80m，其内部存在两块不规则的凸多边形障碍物区域，左下角障碍物顶点坐标分别为(5，70)，(6，55)，(14，55)，(15，68)，上方障碍物顶点坐标分别为(64，46)，(66，31)，(74，31)，(75，45)，航线规划结果如图8(a)所示，转弯次数为44次.在相同条件下采用文献[31]中提出的方法所得到的无人机航线如图8(b)所示，航线转弯次数为90次.

图8 包含两块障碍物的工作区域航线设计结果Fig.8 Result of UAV route planning on target area with two barriers

在本次仿真实验中，设计了多种不同的工作区域，包括含单个障碍物的工作区域以及包含多个障碍物的工作区域，每个工作区域内部障碍物的大小、形状以及位置均不相同.应用本文所提出的植保无人机航线设计算法，在多种不同的工作区域内均能设计出一条对目标区域完成全覆盖的无人机航线.对比以上所有实验结果，可以发现与文献[31]提出的含障碍区域无人机航线规划方法相比，本文所提出的方法设计出的无人机航线的转弯次数大幅降低，实验结果表明对于含障碍物的工作区域本文所提出的方法能够设计出更优的无人机航线.

5 结论与展望

本文提出了一种针对含障碍工作区域的植保无人机航线设计方法，基于栅格法对目标工作区域进行路径点采样，获得所有有效路径点，并结合混合粒子群算法来对路径点进行排序，设计出一条能够有效规避障碍物并对工作区域完成全覆盖的航线.实验结果表明本文提出的无人机航线设计方法能够应用在多种含障碍工作区域内，目标区域包含单个或者多个障碍物时均能获得良好的效果，能够有效减少无人机航线的转弯次数，降低无人机飞行时的能耗.

本文提出的植保无人机航线设计方法适用于平原等地面高度变化较小的地区，设计无人机航线时在二维环境地图中进行.在未来的研究工作中，考虑到部分地面高度变化较大的工作环境，需要在三维空间中进行无人机航线设计.在进行无人机航线设计时没有考虑航线终点的问题，根据本文所提出的无人机航线规划方法所设计出的无人机飞行路径，其终点在工作区域中心部位，无人机在完成作业后需要返航，仍然会增加无人机的耗能，在未来的研究工作中需要考虑到航线起点和终点的问题，减少无人机停止作业后返航所来带的能量消耗.考虑到无人机定位控制精度的问题以及自然环境中风的作用，无人机实际飞行路线与理论规划路径之间存在一定的偏移，影响了无人机作业结果，在后续的研究工作中需要对上述因素进行详细分析，进一步完善无人机航线设计方法.