含障碍物多田块下旋翼无人机作业返航补给规划研究

黄小毛 唐 灿 TANG Lie 罗承铭 李文成 张 垒

(1.华中农业大学工学院， 武汉 430070； 2.农业农村部长江中下游农业装备重点实验室， 武汉 430070；3.爱荷华州立大学农业与生物系统工程系， 埃姆斯 IA 50011)

0 引言

无人机尤其是电动多旋翼无人机在农业应用过程中，面临着续航能力差、载重能力受限和人工遥控操作难度大[1]等实际问题，生产中“炸机”现象时有发生。因此，配备高精度定位系统、开发可靠的自主飞行作业控制系统，并综合考虑电力能源等消耗品的按需多次自动补给问题，是一项急需解决的重要任务。

作业路径是GPS导航机器轨迹控制时的跟踪目标，在很大程度上决定着机器的作业质量、效率和总消耗，因此作业路径的规划和优化具有重要意义。目前，针对遥感、巡查、测绘无人机的路径规划研究较多[2-7]。这些用途的无人机作业时一般离地高度较大，几乎没有障碍物，对地面区域的覆盖要求没有农用无人机精细，因此上述方法在农用无人机路径规划时具有一定借鉴意义，但并不完全适用。

农机领域针对地面机具的作业路径研究起步较早[8]，既有针对矩形[9]、一般凸多边形[10]等规则田块边界条件下的单机作业路径研究，也有针对凹多边形田块边界[11-12]甚至多机协同[13]和多田块间[14]作业路径规划的研究。但地面机具通过性能、转弯方式以及安全要求等方面差异明显，这些研究成果对于农用无人机作业路径规划同样只是具有借鉴意义。

专门针对农用无人机的路径规划研究起步较晚，但发展迅速。MOON等[15]针对喷粉无人直升机，提出基于田块分区处理操作的路径规划方法。VALENTE等[16]提出一种基于“和谐搜索”(Harmony search)的启发式搜索算法，求解遍历网格的最优次序。DENG等[17]针对大面积区域多无人机协同作业问题，提出一种区域分割方法，并采用轮廓偏置路径进行覆盖作业。国内徐东甫等[18]、刘浩蓬等[19]将简单四边形边界的规划路径分别应用到赤眼蜂投放和喷雾试验中。王宇等[20]提出一种基于栅格模型的路径规划算法。彭孝东等[21]针对固定翼无人机作业过程中的转弯方式进行了详细的讨论。徐博等[22-23]对五边形边界单田块的无人机作业路径提出了具体算法，研究了多田块路径调度优化，并基于最小能耗对单一大面积矩形边界田块中的架次进行了研究。李继宇等[24]基于能量利用率最大化原则，通过增加补给点的方式，对边界形状简单且单一的田块的补给过程进行了研究。此外，针对绕障碍物定向穿越问题，RADMANESH等[25]基于栅格化地图，研究比较了类似于地面机器的3种无人机绕障路径在线生成算法。

与此同时，以大疆、极飞为代表的中国企业不断推出自动化程度更高、作业性能更加优越、功能更加多样化的农用无人机商用平台，使得无人机农业应用的场景更加多样化、操作过程更加简单化。因此，对作业路径的要求也越来越高。

农用无人机路径规划研究正向复杂边界田块条件(边界形状、障碍物、高度差、多田块)、按需补给调度、多机协同等方向发展。本文针对具有自主飞行功能的旋翼农用无人机在同一区域内相邻多田块间的作业任务规划问题，从无人机应用过程中遇到的续航、负重等实际问题出发，考虑种肥药液和电力能源等消耗品的按需多次补给问题，提出并实现一套含障碍物多田块条件下单机多架次作业的农用旋翼无人机自主飞行作业的路径规划算法。

1 作业路径规划优化原理

1.1 优化目标模型

无人机路径规划优化的总体目标是以最小的作业投入消耗(时间、能源、农资)实现待作业田块的无差别全覆盖作业。这可看成为一个多目标优化问题，由最小重漏面积、最小总路径长度、最小作业时长等子目标组成，但各子目标对总目标的权重无法准确量化。优化时要考虑很多的约束条件，比如田块的边界及障碍物、飞机的作业参数(工作幅宽、作业和跳转时的速度和加减速度、喷播速率、总容积、总电量等)。数学模型为

minF(x)=
(Sl(x),Sc(x),L(x),T(x),E(x),W(x))

(1)

式中x——某一具体的路径规划方案

F(x)——多目标优化总函数

Sl(x)——漏作面积,m2

Sc(x)——重作面积,m2

L(x)——作业路径总长度,m

T(x)——作业时间,min

E(x)——能源消耗量,min

W(x)——农资消耗量,L

在这些优化目标中，由于旋翼无人机作业时不与地表接触，可任意方向移动不需要转弯空间，且配备厘米级高精度定位传感器等，因此自主飞行作业模式下理论上作业重漏面积可忽略不计。而作业时间T(x)、能源消耗量E(x)、农资消耗量W(x)均与作业路径总长度L(x)存在一定的依存关系，按照运动学方程及消耗模型，该多目标优化问题最后可统一转化为以最小路径总长度为优化函数的单目标优化问题进行求解。

为简化计算过程，作以下假设：忽略自然风和旋翼气流造成的影响，不考虑药液或种肥的漂移；田块无起伏、田块间无高度差，或起伏量、高度差相对于作业高度在可接受范围内(仿地飞行模式下)；补给点与起降点位置重合；机器能按照规划顺利完成工作，不考虑机器故障等实际作业过程中不可预知的潜在动态变化因素。

1.2 数据定义及算法流程

从确保作业安全、操作方便和便于程序代码编制的角度考虑数据定义和表征方法。以多边形表征田块边界，外边界以逆时针方向、内边界以顺时针方向依次存储各顶点，每一田块为一多边形数组。这里的“边界”，虽然通常一般主要指田块的边界，但实际上也是障碍物的边界，即：外边界以内、内边界以外的区域是作物种植区；同时，外边界以外或内边界以内的区域可认为是障碍物区。也就是说在获取作物种植区的边界时，可以忽略外边界以外的障碍物(设定外边界以外区域，除起降补给点外，其他区域全是障碍物)，但要注意将外边界以内的障碍物以内边界形式表征出来。此外，统一所有障碍物高度为同一最大高度。

将机器简化为其几何中心上的一点，作业路径即为无人机移动时机器中心的轨迹线，以点数组按照先后顺序存储。下文各图中有效作业路径(即航线)用实线表示，转移等辅助过程中的轨迹(即无效作业路径)用虚线表示；垂直起降轨迹用小圆圈表示。

算法设计时，采用两步优化法进行。即“先路径、后航次”，以最短路径总长度为优化目标，先规划作业方向和航线顺序获得初始作业路径，再考虑作业消耗品(油电、农资)按需补给，规划作业航次获得最终的路径轨迹。以田块及障碍物边界和作业参数为输入，以作业路径为输出，整个算法的流程如图1所示。

图1 旋翼无人机多田块下作业路径规划算法流程图Fig.1 Flow chart of path planning algorithm for autonomous drone in multiple fields

1.3 边界分组与田块识别

田块以及障碍物的边界一般通过人工手持GPS直接打点或在GIS系统中鼠标打点获得，打点、存储的顺序可能具有随意性，不一定完全符合1.2节中的规定。因此经纬度球面坐标系转换成直角坐标系后，首先需要对表征边界的多边形按照相关性进行分组，从数据结构上建立田块区域的概念。

采用多边形表征田块区域时具有以下规律：每个田块有且只有一个外边界，可能没有也可能有多个相离的内边界，且内边界一定包含在外边界内部；每个边界都是一个简单多边形(除相邻边外，其他各边之间互不相交)，可以是凸多边形也可以是凹多边形；每2个田块的外边界之间以及属于同一田块的两内边界之间均为相离关系(既不相交也不相互包含)。

分组算法的核心思想是建立多边形包含关系矩阵[26]，根据被包含次数区分内边界和外边界，然后将每个外边界及所包含的内边界构建成独立的田块区域。如图2所示待作业场景中，边界B1、B2和B4不被任何边界包含，判定为外边界，而其他各边界被包含一次故被判定为内边界；外边界B1、B2和B4分别与其包含的内边界组成3个独立田块F1、F2和F3。

图2 多边形分组算法示意图Fig.2 Schematic of polygons grouping algorithm

1.4 有效作业路径的生成

有效作业路径是机器移动过程中同步进行具体某种作业操作(喷播)的路径，即作业实施过程中遵循的设定轨迹，对无人机来说俗称“航线”。旋翼无人机以作业幅宽w实现对待作业田块所有区域的全覆盖，要求类似于计算机图形学中的多边形填充问题，在数控型腔铣、3D打印等领域也有类似应用。其基本思路是用一组间距为w的平行直线族去覆盖多边形区域，然后用多边形去裁剪各条直线，获得的线段集合即为航线集合。该求解过程的最常用算法是活性边表法，是计算机图形学中的经典算法[26]，在此不作赘述。

1.5 作业方向与航线调度次序优化

计算航线时，所使用平行直线族所在的方向即是无人机的作业方向，而所获得线段在集合中的存储顺序即为航线的调度次序。作业方向与航线调度次序共同决定着航线间衔接转移路径总长度。

在优化作业方向时，包括多田块方向一致性原则(All in one direction, AOD)和单田块方向最优原则(Different direction for different field, DDDF)；而航线调度次序优化时，又有各田块集中调度作业原则(Field by field, FBF)和允许跨田块穿插调度作业行原则(Swath by swath, SBS)。因此实际操作时存在4种情况，如图3所示。

图3 4种不同航向及调度优化策略组合Fig.3 Four different optimization combinations of orientation and ordering strategy

设定某一优化原则后，在求解作业方向时，有两种具体处理方案(步进旋转法和最小跨度法)。前者通过枚举法，比较所有可能作业方向下的作业路径总长度后取最小者，通常取步距角0.5°，计算过程复杂、耗时但稳定并适用于各种形状田块。后者首先计算包含所有边界点点集的凸包多边形，然后确定该多边形的最小跨度方向，并以此作为最优作业方向。最小跨度法计算过程简单，但结果对于凸多边形的单田块情形是准确的，对于凹多边形、孔洞多边形田块以及多个田块的情形，计算结果一般并非为最优方向。

优化航线调度次序时，若将每一条航线视为一个城市，这将是一个典型的TSP旅行商问题，属于NP-hard。采用传统的贪婪算法进行求解，虽然不一定得到最优解，但能在确保算法高效、稳定、可靠的前提下得到可以接受的可行解。实际算法设计及编码过程中，需充分考虑上述4种不同的优化策略组合，对不同方向、不同田块条件下产生的航线进行分级分类的处理。

航线间转移时，若转移线段与田块边界之间存在非完全包含关系(即存在位于田块外部的线上点，如图4所示)，则无人机转移过程中会跳出到田块边界的外部。因田块边界外部可能存在高于作业高度的障碍物(尤其在田块间转移时)，为确保安全，需找出此种情形下的转移线段并进行必要处理。

图4 安全边界相交性测试示意图Fig.4 Schematic of intersection test of safety boundary

采用“安全边界相交性测试法”来判别某条候选转移路径线段Ji与田块边界多边形组{Bi}是否属于非包含关系。具体做法如下：根据障碍物情况，人为设立安全距离d和安全高度h(大于所有障碍物的高度)；将田块边界多边形组{Bi}向外偏置d(外边界扩大、内边界缩小)，得到偏置后多边形组{B′i}；判断转移线段Ji与多边形组{B′i}的相交性，若相交，则视为“危险转移过程”。

如图4所示，对于田块F0的某条候选转移路径PiPj，因为线段PiPj与外边界B0偏置后多边形B′0存在交点C1和C2，故该转移过程视为危险转移过程。对于此类转移过程，为确保绝对安全，实际操作时，飞机先从Pi点从作业高度h0拉升至安全高度h，转移至Pj点后再下降至作业高度继续作业。计算转移路线长度时在原计算值上加上高度调整量2(h-h0)。上述过程中涉及到多边形偏置算法、多边形与线段间求交算法，也是计算机图形学中经典问题[26]，限于篇幅问题，不赘述。

1.6 按需多次补给方案

因载质量及续航时间限制，无人机田间作业时往往需要执行多个架(航)次，中间进行能源及药肥种等农资消耗品的补给填装。分为动力消耗补给(Refuel or recharge)和农资消耗补给(Refill)两种，前者要求对所有飞行过程中能源累积消耗值与初始值差值和最低允许值进行比较，确定返航点；后者则主要考虑有效作业段的物资累积消耗值与初始值之间的差值是否为零来确定返航点。

就植保无人机而言，单次电池的续航能力一般在10～25 min之间，飞行速度2～10 m/s，换算成距离在1 200～15 000 m之间，实际还受自然风、起降次数、悬停时间和飞手操作熟练程度等因素的影响。而药箱一般在8～16 L之间，平均10～12 L，根据不同的作物、病虫害类型及危害程度，单位面积喷播量设置不同。有两种参数设置方式，一种为恒速喷播模式，农资消耗量与作业时间成正比，单位是mL/s；另一种是变量/随速喷播模式，农资消耗量与作业距离或面积成正比，单位是mL/hm2。不同的消耗品初始值及消耗速度，决定了需要补给时的返航点一般也不同，但不管哪一种消耗品需要补给，都必须立即做出响应，否则会导致安全事故或作业遗漏。

如图5所示，在通过前述作业方向及航线调度次序优化后获得的初步作业路径中，作业航线与航线间转移路径是相间排列的。若用P0表示起降补给点，n条作业航线用{P1→P2，P3→P4,…，P2i+1→P2i+2,…，P2n-1→P2n}表示,则对应的跳转路径为n+1条，且可表示为{P0→P1,P2→P3,…，P2i→P2i+1,…，P2n→P0}。可以看到，初步作业路径中，除起降点外，还包含2n个航点，从当前航点编号的奇偶性可以判断出飞行器的下一动作是航线间转移还是沿航线作业。

图5 按需补给返航点示意图Fig.5 Schematic of return point to refill and recharge on demand

补给方案生成时，从P0点出发，依次遍历作业航线及转移路径，计算到达某个航点的累计里程(包括从该点返回至补给点的距离及危险转移过程中的高度调整距离)及农资消耗量，当二者之一达到返航补给条件时，考虑返航。

对于第i条作业航线P2i+1→P2i+2(i=0,1,2,…，n-1)而言，若长度为Li,则在变量/随速喷播模式(喷播量与实际作业距离或面积成正比)下，单位面积喷播量为q，则消耗的农资量为

Qi=LiWq

(2)

对于第i条航线间跳转路径P2i→P2i+1(i=0,1,2,…，n)而言，长度为L′i，因喷播系统关闭，故农资消耗量为0。若为危险转移过程，里程加上高度调整值2(h-h0)或2h-h0(包含补给点时)。

对于包含n条初始作业航线的模型而言，航点数为2n，按次序飞行作业至航点j的累计里程及农资消耗量分别用L0～j和Q0～j表示，从j点返航回至补给点的里程用Lj→0表示，经过m次危险转移过程，则

(3)

(4)

若用Lmax和Qmax分别表示最大续航里程和农资容积，则当累计耗时量及农资消耗量满足条件

L0～j+Lj→0+2h-h0≥Lmax≥
L0～j-1+Lj-1→0+2h-h0

(5)

Q0～j≥Qmax≥Q0～j-1

(6)

即安排返航，也称之为“按需返航”。

当按照公式(5)条件返航时，若j为奇数，则从上一航线的末端点(即j-1)处返航；若j为偶数，则采用插值法在航线中间某点Pnew返航，则L0～new+Lnew→0+2h-h0=Lmax。

当按照公式(6)条件返航时，若j为奇数，则从上一航线的末端点(即j-1)处返航；若j为偶数，则采用插值法在航线中间点Pnew返航，则Q0～new=Qmax。

将中间点Pnew用参数表达式(即Pnew=λPj-1+(1-λ)Pj,λ∈[0,1])表示后代入上面等式，即可求出该点坐标，求解时可利用迭代法快速解算。

返航至补给点后，在补给点进行物资补给时，有两种处置方式：按需重置(Reset on demand,ROD)，只将达到使用极限的物资进行再次加载重置，未达到使用极限的物资不作处理，也称之为“按需补给”；完全重置(All reset,AR)，只要是返回至补给点，即将所有物资全部重置，包括未使用完毕的电池或燃油、种肥药等农资消耗品，也称之为“完全补给”。

此外，对剩余航线的遍历作业(续航、续作)也有两种处置方案：按照原计划从返航点继续作业，直至找到新的返航点或完成所有航线的遍历作业，称之为断点续作(Go back to breakpoint and continue，GBC)；对剩余航线进行重新排序，按新次序安排作业，直至找到新的返航点或完成所有航线的遍历作业，称之为重排续作(Go on with new order,GNO)。两种方案均可采用递归算法进行求解。因此形成表1所示4种补给续航组合策略。

表1 4种补给续航组合策略Tab.1 Four different combinations of refill-recharge and go-on strategies

2 实例仿真计算

上述全部算法过程在Visual C++ 6.0平台上编码实现，在Intel(R) Core(TM)i7-3370 @3.4 GHz CPU、8 GB 1 600 MHz内存、Windows 7操作系统环境下，分别对4组典型场景算例在多组不同工作参数条件(田块属性及补给点位置如表2所示)下进行算法稳定性和计算效率测试试验。

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

算例1、2田块均为假想边界(算例2田块边界来自文献[25])，算例3为田块中带孔洞的假想边界，算例4田块边界来自开源地面站软件MissionPlanner中Google Earth环境下的实际田块。计算过程中，算法对导入的边界自动进行分组，识别区分不同田块并逐一处理，对于单一边界且为凸多边形的田块采用“最小跨度法”优化航向，其他的情形则采用“步进旋转法”(步距角0.5°)优化航向。采用贪婪算法进行航线调度次序优化。计算过程中对每一潜在转移过程均进行安全判断并对危险转移

过程进行处理。统一设定作业高度2 m，安全转移高度6 m，安全边界距离1 m。路径总长度通过线段长度求和得到，算法耗时通过GetTickCount()函数获取算法运行前后的系统时间后再求差得到，且测试时包括界面显示更新相关操作。

每个作业场景下进行2组试验测试。试验1测试不同场景田块算例在不同作业参数下，在不考虑作业补给条件下，4种不同作业方向及航线调度优化策略对作业路径总长度的优化效果，测试结果相关数据如表3所示。转移路径优化效果S=(S1-S2)/S1×100%，S1、S2分别为较差的优化结果和较好的优化结果，在表3中对应的数据用*和** 标识，而对应的路径截图如表4所示。

表3 4种不同作业航向及航线调度组合策略下初始路径规划测试结果Tab.3 Test results of 4 different strategies for route orientation and order

表4 较好及较差航向及航线调度优化组合策略对应的初始路径截图Tab.4 Screen shots of initial route with optimal and worst combination of orientation and order strategies

试验2在试验1基础上进一步测试返航补给规划算法的稳定性及计算效率。因各田块集中调度FBF原则可能会在补给规划时被破坏掉，且由表3可知，AOD×SBS几乎是最优的作业方向及调度组合策略，因此统一选择在该方向及调度策略下，进一步设置补给相关试验条件(电力或燃油续航能力4 000 m，农资消耗品一次加载12 L，随速变量喷播模式下单位面积喷播量18 L/hm2)，测试在4种不同补给及续作组合策略方式下的补给次数和转移路径的差别，结果如表5所示。进一步将其中的较好结果及较差结果对应的补给路径截图在表6中(不同颜色区域表示不同的航次)进行对比展示。

表5 按需返航后4种不同补给续作组合策略下航次(最终路径)规划测试结果Tab.5 Test results of final fights and route by four different combinations of refuel-refill and go-on strategies

表6 较好及较差补给续作优化组合策略对应的最终路径截图Tab.6 Screenshots of final flight route with optimal and worst combination of refuel-refill and go-on strategies

3 讨论

针对含障碍物多田块中单一旋翼无人机不考虑补给及考虑补给条件下的路径规划问题，所设计的算法分别对多组不同面积、田块数目、边界数目和节点数目的假想田块、实际田块在不同作业幅宽条件下进行了无差别测试，优化计算结果稳定、具有可重复性。

从表3可以看出，算法耗时随田块边界复杂程度而增加，随作业幅宽增加而减小，测试算例耗时从78 ms到105 161 ms不等。这其中对于潜在转移过程的安全性判断耗费了大量时间。同一工作幅宽条件下，有效工作路径总长度相当，因为该数值与工作幅宽的乘积与田块面积相当。对于转移路径的优化，较好结果相对于较差结果的提升效果从10.25%到33.81%不等，AOD×SBS几乎具有绝对的优化效果，但不是绝对最优组合策略。在时间允许情况下，建议用户对这4种航向及调度组合策略进行逐一测试并优选。

考虑消耗品补给时，算法同样具有很好的稳定性和计算效率。测试中，算法耗时从21 170 ms到106 393 ms不等，影响因素与不考虑补给时相当，数值上略有增加，主要由补给算法模块引起。4种不同补给续航组合策略条件下的优化效果中，补给次数的最好优化效果从15次降到10次，补给次数少的转移路径长度小，转移路径长度的较好结果相对于较差结果的优化幅度从14.00%到26.27%不等，总体来说同条件下完全重置+重排续作的组合策略的表现较优，但并不绝对，因此实际操作时建议对4种不同补给续航组合策略进行现场优选。

实际作业过程中，飞行器的耗电量或耗油量除了与飞行时间有关，还与飞行高度、加减速、喷播量、风速甚至各传感器信号强弱程度等很多因素有关，飞行距离只是其中消耗能源占比最大的一个。因此实际使用时续航能力采用距离来衡量和设置时，应多次试验近似确定，同时为确保安全，最好设置一个安全系数。

算例中的补给点都是事先人工随机确定的。事实上补给点的数量和位置至关重要，如何合理地设置数量和位置，需要进一步深入研究。

实际田块中障碍物的具体表现形式(边界形状、高度和位置)具有多样性，文中做法仅考虑了田块内部障碍物的边界形状和位置多样性，其他都进行了简单化处理：以最大障碍物高度作为所有障碍物高度来进行安全转移时的高度调整；忽略田块外部障碍物的具体边界形状及位置(除起降补给点，认为外边界以外都是障碍物)。这种处理方式也是目前大多商用无人机对障碍物的通行处理做法。虽可以确保飞行安全，但有可能增加转移路径中不必要的高度调整值，增加时间及能源消耗，这也是需要细化深入研究的内容。

4 结论

(1)针对同一区域内相邻多田块无人机作业任务规划问题，从无人机应用过程中遇到的续航、负重等实际问题出发，考虑种肥药液和电力能源等消耗品的按需多次补给，提出并实现一套含障碍物复杂多田块条件下单机多架次作业的农用旋翼无人机自主飞行作业的路径规划算法。

(2)针对假想田块及实际田块的算例仿真测试结果表明，提出的规划算法运行稳定可靠、效率高、优化效果明显，可满足农用无人机单机作业时的相关要求。