黃小毛 唐 燦 TANG Lie 羅承銘 李文成 張 壘

(1.華中農(nóng)業(yè)大學(xué)工學(xué)院， 武漢 430070； 2.農(nóng)業(yè)農(nóng)村部長江中下游農(nóng)業(yè)裝備重點(diǎn)實(shí)驗(yàn)室， 武漢 430070；3.愛荷華州立大學(xué)農(nóng)業(yè)與生物系統(tǒng)工程系， 埃姆斯 IA 50011)

0 引言

無人機(jī)尤其是電動多旋翼無人機(jī)在農(nóng)業(yè)應(yīng)用過程中，面臨著續(xù)航能力差、載重能力受限和人工遙控操作難度大[1]等實(shí)際問題，生產(chǎn)中“炸機(jī)”現(xiàn)象時(shí)有發(fā)生。因此，配備高精度定位系統(tǒng)、開發(fā)可靠的自主飛行作業(yè)控制系統(tǒng)，并綜合考慮電力能源等消耗品的按需多次自動補(bǔ)給問題，是一項(xiàng)急需解決的重要任務(wù)。

作業(yè)路徑是GPS導(dǎo)航機(jī)器軌跡控制時(shí)的跟蹤目標(biāo)，在很大程度上決定著機(jī)器的作業(yè)質(zhì)量、效率和總消耗，因此作業(yè)路徑的規(guī)劃和優(yōu)化具有重要意義。目前，針對遙感、巡查、測繪無人機(jī)的路徑規(guī)劃研究較多[2-7]。這些用途的無人機(jī)作業(yè)時(shí)一般離地高度較大，幾乎沒有障礙物，對地面區(qū)域的覆蓋要求沒有農(nóng)用無人機(jī)精細(xì)，因此上述方法在農(nóng)用無人機(jī)路徑規(guī)劃時(shí)具有一定借鑒意義，但并不完全適用。

農(nóng)機(jī)領(lǐng)域針對地面機(jī)具的作業(yè)路徑研究起步較早[8]，既有針對矩形[9]、一般凸多邊形[10]等規(guī)則田塊邊界條件下的單機(jī)作業(yè)路徑研究，也有針對凹多邊形田塊邊界[11-12]甚至多機(jī)協(xié)同[13]和多田塊間[14]作業(yè)路徑規(guī)劃的研究。但地面機(jī)具通過性能、轉(zhuǎn)彎方式以及安全要求等方面差異明顯，這些研究成果對于農(nóng)用無人機(jī)作業(yè)路徑規(guī)劃同樣只是具有借鑒意義。

專門針對農(nóng)用無人機(jī)的路徑規(guī)劃研究起步較晚，但發(fā)展迅速。MOON等[15]針對噴粉無人直升機(jī)，提出基于田塊分區(qū)處理操作的路徑規(guī)劃方法。VALENTE等[16]提出一種基于“和諧搜索”(Harmony search)的啟發(fā)式搜索算法，求解遍歷網(wǎng)格的最優(yōu)次序。DENG等[17]針對大面積區(qū)域多無人機(jī)協(xié)同作業(yè)問題，提出一種區(qū)域分割方法，并采用輪廓偏置路徑進(jìn)行覆蓋作業(yè)。國內(nèi)徐東甫等[18]、劉浩蓬等[19]將簡單四邊形邊界的規(guī)劃路徑分別應(yīng)用到赤眼蜂投放和噴霧試驗(yàn)中。王宇等[20]提出一種基于柵格模型的路徑規(guī)劃算法。彭孝東等[21]針對固定翼無人機(jī)作業(yè)過程中的轉(zhuǎn)彎方式進(jìn)行了詳細(xì)的討論。徐博等[22-23]對五邊形邊界單田塊的無人機(jī)作業(yè)路徑提出了具體算法，研究了多田塊路徑調(diào)度優(yōu)化，并基于最小能耗對單一大面積矩形邊界田塊中的架次進(jìn)行了研究。李繼宇等[24]基于能量利用率最大化原則，通過增加補(bǔ)給點(diǎn)的方式，對邊界形狀簡單且單一的田塊的補(bǔ)給過程進(jìn)行了研究。此外，針對繞障礙物定向穿越問題，RADMANESH等[25]基于柵格化地圖，研究比較了類似于地面機(jī)器的3種無人機(jī)繞障路徑在線生成算法。

與此同時(shí)，以大疆、極飛為代表的中國企業(yè)不斷推出自動化程度更高、作業(yè)性能更加優(yōu)越、功能更加多樣化的農(nóng)用無人機(jī)商用平臺，使得無人機(jī)農(nóng)業(yè)應(yīng)用的場景更加多樣化、操作過程更加簡單化。因此，對作業(yè)路徑的要求也越來越高。

農(nóng)用無人機(jī)路徑規(guī)劃研究正向復(fù)雜邊界田塊條件(邊界形狀、障礙物、高度差、多田塊)、按需補(bǔ)給調(diào)度、多機(jī)協(xié)同等方向發(fā)展。本文針對具有自主飛行功能的旋翼農(nóng)用無人機(jī)在同一區(qū)域內(nèi)相鄰多田塊間的作業(yè)任務(wù)規(guī)劃問題，從無人機(jī)應(yīng)用過程中遇到的續(xù)航、負(fù)重等實(shí)際問題出發(fā)，考慮種肥藥液和電力能源等消耗品的按需多次補(bǔ)給問題，提出并實(shí)現(xiàn)一套含障礙物多田塊條件下單機(jī)多架次作業(yè)的農(nóng)用旋翼無人機(jī)自主飛行作業(yè)的路徑規(guī)劃算法。

1 作業(yè)路徑規(guī)劃優(yōu)化原理

1.1 優(yōu)化目標(biāo)模型

無人機(jī)路徑規(guī)劃優(yōu)化的總體目標(biāo)是以最小的作業(yè)投入消耗(時(shí)間、能源、農(nóng)資)實(shí)現(xiàn)待作業(yè)田塊的無差別全覆蓋作業(yè)。這可看成為一個多目標(biāo)優(yōu)化問題，由最小重漏面積、最小總路徑長度、最小作業(yè)時(shí)長等子目標(biāo)組成，但各子目標(biāo)對總目標(biāo)的權(quán)重?zé)o法準(zhǔn)確量化。優(yōu)化時(shí)要考慮很多的約束條件，比如田塊的邊界及障礙物、飛機(jī)的作業(yè)參數(shù)(工作幅寬、作業(yè)和跳轉(zhuǎn)時(shí)的速度和加減速度、噴播速率、總?cè)莘e、總電量等)。數(shù)學(xué)模型為

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

(1)

式中x——某一具體的路徑規(guī)劃方案

F(x)——多目標(biāo)優(yōu)化總函數(shù)

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

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

L(x)——作業(yè)路徑總長度,m

T(x)——作業(yè)時(shí)間,min

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

W(x)——農(nóng)資消耗量,L

在這些優(yōu)化目標(biāo)中，由于旋翼無人機(jī)作業(yè)時(shí)不與地表接觸，可任意方向移動不需要轉(zhuǎn)彎空間，且配備厘米級高精度定位傳感器等，因此自主飛行作業(yè)模式下理論上作業(yè)重漏面積可忽略不計(jì)。而作業(yè)時(shí)間T(x)、能源消耗量E(x)、農(nóng)資消耗量W(x)均與作業(yè)路徑總長度L(x)存在一定的依存關(guān)系，按照運(yùn)動學(xué)方程及消耗模型，該多目標(biāo)優(yōu)化問題最后可統(tǒng)一轉(zhuǎn)化為以最小路徑總長度為優(yōu)化函數(shù)的單目標(biāo)優(yōu)化問題進(jìn)行求解。

為簡化計(jì)算過程，作以下假設(shè)：忽略自然風(fēng)和旋翼氣流造成的影響，不考慮藥液或種肥的漂移；田塊無起伏、田塊間無高度差，或起伏量、高度差相對于作業(yè)高度在可接受范圍內(nèi)(仿地飛行模式下)；補(bǔ)給點(diǎn)與起降點(diǎn)位置重合；機(jī)器能按照規(guī)劃順利完成工作，不考慮機(jī)器故障等實(shí)際作業(yè)過程中不可預(yù)知的潛在動態(tài)變化因素。

1.2 數(shù)據(jù)定義及算法流程

從確保作業(yè)安全、操作方便和便于程序代碼編制的角度考慮數(shù)據(jù)定義和表征方法。以多邊形表征田塊邊界，外邊界以逆時(shí)針方向、內(nèi)邊界以順時(shí)針方向依次存儲各頂點(diǎn)，每一田塊為一多邊形數(shù)組。這里的“邊界”，雖然通常一般主要指田塊的邊界，但實(shí)際上也是障礙物的邊界，即：外邊界以內(nèi)、內(nèi)邊界以外的區(qū)域是作物種植區(qū)；同時(shí)，外邊界以外或內(nèi)邊界以內(nèi)的區(qū)域可認(rèn)為是障礙物區(qū)。也就是說在獲取作物種植區(qū)的邊界時(shí)，可以忽略外邊界以外的障礙物(設(shè)定外邊界以外區(qū)域，除起降補(bǔ)給點(diǎn)外，其他區(qū)域全是障礙物)，但要注意將外邊界以內(nèi)的障礙物以內(nèi)邊界形式表征出來。此外，統(tǒng)一所有障礙物高度為同一最大高度。

將機(jī)器簡化為其幾何中心上的一點(diǎn)，作業(yè)路徑即為無人機(jī)移動時(shí)機(jī)器中心的軌跡線，以點(diǎn)數(shù)組按照先后順序存儲。下文各圖中有效作業(yè)路徑(即航線)用實(shí)線表示，轉(zhuǎn)移等輔助過程中的軌跡(即無效作業(yè)路徑)用虛線表示；垂直起降軌跡用小圓圈表示。

算法設(shè)計(jì)時(shí)，采用兩步優(yōu)化法進(jìn)行。即“先路徑、后航次”，以最短路徑總長度為優(yōu)化目標(biāo)，先規(guī)劃作業(yè)方向和航線順序獲得初始作業(yè)路徑，再考慮作業(yè)消耗品(油電、農(nóng)資)按需補(bǔ)給，規(guī)劃作業(yè)航次獲得最終的路徑軌跡。以田塊及障礙物邊界和作業(yè)參數(shù)為輸入，以作業(yè)路徑為輸出，整個算法的流程如圖1所示。

圖1 旋翼無人機(jī)多田塊下作業(yè)路徑規(guī)劃算法流程圖Fig.1 Flow chart of path planning algorithm for autonomous drone in multiple fields

1.3 邊界分組與田塊識別

田塊以及障礙物的邊界一般通過人工手持GPS直接打點(diǎn)或在GIS系統(tǒng)中鼠標(biāo)打點(diǎn)獲得，打點(diǎn)、存儲的順序可能具有隨意性，不一定完全符合1.2節(jié)中的規(guī)定。因此經(jīng)緯度球面坐標(biāo)系轉(zhuǎn)換成直角坐標(biāo)系后，首先需要對表征邊界的多邊形按照相關(guān)性進(jìn)行分組，從數(shù)據(jù)結(jié)構(gòu)上建立田塊區(qū)域的概念。

采用多邊形表征田塊區(qū)域時(shí)具有以下規(guī)律：每個田塊有且只有一個外邊界，可能沒有也可能有多個相離的內(nèi)邊界，且內(nèi)邊界一定包含在外邊界內(nèi)部；每個邊界都是一個簡單多邊形(除相鄰邊外，其他各邊之間互不相交)，可以是凸多邊形也可以是凹多邊形；每2個田塊的外邊界之間以及屬于同一田塊的兩內(nèi)邊界之間均為相離關(guān)系(既不相交也不相互包含)。

分組算法的核心思想是建立多邊形包含關(guān)系矩陣[26]，根據(jù)被包含次數(shù)區(qū)分內(nèi)邊界和外邊界，然后將每個外邊界及所包含的內(nèi)邊界構(gòu)建成獨(dú)立的田塊區(qū)域。如圖2所示待作業(yè)場景中，邊界B1、B2和B4不被任何邊界包含，判定為外邊界，而其他各邊界被包含一次故被判定為內(nèi)邊界；外邊界B1、B2和B4分別與其包含的內(nèi)邊界組成3個獨(dú)立田塊F1、F2和F3。

圖2 多邊形分組算法示意圖Fig.2 Schematic of polygons grouping algorithm

1.4 有效作業(yè)路徑的生成

有效作業(yè)路徑是機(jī)器移動過程中同步進(jìn)行具體某種作業(yè)操作(噴播)的路徑，即作業(yè)實(shí)施過程中遵循的設(shè)定軌跡，對無人機(jī)來說俗稱“航線”。旋翼無人機(jī)以作業(yè)幅寬w實(shí)現(xiàn)對待作業(yè)田塊所有區(qū)域的全覆蓋，要求類似于計(jì)算機(jī)圖形學(xué)中的多邊形填充問題，在數(shù)控型腔銑、3D打印等領(lǐng)域也有類似應(yīng)用。其基本思路是用一組間距為w的平行直線族去覆蓋多邊形區(qū)域，然后用多邊形去裁剪各條直線，獲得的線段集合即為航線集合。該求解過程的最常用算法是活性邊表法，是計(jì)算機(jī)圖形學(xué)中的經(jīng)典算法[26]，在此不作贅述。

1.5 作業(yè)方向與航線調(diào)度次序優(yōu)化

計(jì)算航線時(shí)，所使用平行直線族所在的方向即是無人機(jī)的作業(yè)方向，而所獲得線段在集合中的存儲順序即為航線的調(diào)度次序。作業(yè)方向與航線調(diào)度次序共同決定著航線間銜接轉(zhuǎn)移路徑總長度。

在優(yōu)化作業(yè)方向時(shí)，包括多田塊方向一致性原則(All in one direction, AOD)和單田塊方向最優(yōu)原則(Different direction for different field, DDDF)；而航線調(diào)度次序優(yōu)化時(shí)，又有各田塊集中調(diào)度作業(yè)原則(Field by field, FBF)和允許跨田塊穿插調(diào)度作業(yè)行原則(Swath by swath, SBS)。因此實(shí)際操作時(shí)存在4種情況，如圖3所示。

圖3 4種不同航向及調(diào)度優(yōu)化策略組合Fig.3 Four different optimization combinations of orientation and ordering strategy

設(shè)定某一優(yōu)化原則后，在求解作業(yè)方向時(shí)，有兩種具體處理方案(步進(jìn)旋轉(zhuǎn)法和最小跨度法)。前者通過枚舉法，比較所有可能作業(yè)方向下的作業(yè)路徑總長度后取最小者，通常取步距角0.5°，計(jì)算過程復(fù)雜、耗時(shí)但穩(wěn)定并適用于各種形狀田塊。后者首先計(jì)算包含所有邊界點(diǎn)點(diǎn)集的凸包多邊形，然后確定該多邊形的最小跨度方向，并以此作為最優(yōu)作業(yè)方向。最小跨度法計(jì)算過程簡單，但結(jié)果對于凸多邊形的單田塊情形是準(zhǔn)確的，對于凹多邊形、孔洞多邊形田塊以及多個田塊的情形，計(jì)算結(jié)果一般并非為最優(yōu)方向。

優(yōu)化航線調(diào)度次序時(shí)，若將每一條航線視為一個城市，這將是一個典型的TSP旅行商問題，屬于NP-hard。采用傳統(tǒng)的貪婪算法進(jìn)行求解，雖然不一定得到最優(yōu)解，但能在確保算法高效、穩(wěn)定、可靠的前提下得到可以接受的可行解。實(shí)際算法設(shè)計(jì)及編碼過程中，需充分考慮上述4種不同的優(yōu)化策略組合，對不同方向、不同田塊條件下產(chǎn)生的航線進(jìn)行分級分類的處理。

航線間轉(zhuǎn)移時(shí)，若轉(zhuǎn)移線段與田塊邊界之間存在非完全包含關(guān)系(即存在位于田塊外部的線上點(diǎn)，如圖4所示)，則無人機(jī)轉(zhuǎn)移過程中會跳出到田塊邊界的外部。因田塊邊界外部可能存在高于作業(yè)高度的障礙物(尤其在田塊間轉(zhuǎn)移時(shí))，為確保安全，需找出此種情形下的轉(zhuǎn)移線段并進(jìn)行必要處理。

圖4 安全邊界相交性測試示意圖Fig.4 Schematic of intersection test of safety boundary

采用“安全邊界相交性測試法”來判別某條候選轉(zhuǎn)移路徑線段Ji與田塊邊界多邊形組{Bi}是否屬于非包含關(guān)系。具體做法如下：根據(jù)障礙物情況，人為設(shè)立安全距離d和安全高度h(大于所有障礙物的高度)；將田塊邊界多邊形組{Bi}向外偏置d(外邊界擴(kuò)大、內(nèi)邊界縮小)，得到偏置后多邊形組{B′i}；判斷轉(zhuǎn)移線段Ji與多邊形組{B′i}的相交性，若相交，則視為“危險(xiǎn)轉(zhuǎn)移過程”。

如圖4所示，對于田塊F0的某條候選轉(zhuǎn)移路徑PiPj，因?yàn)榫€段PiPj與外邊界B0偏置后多邊形B′0存在交點(diǎn)C1和C2，故該轉(zhuǎn)移過程視為危險(xiǎn)轉(zhuǎn)移過程。對于此類轉(zhuǎn)移過程，為確保絕對安全，實(shí)際操作時(shí)，飛機(jī)先從Pi點(diǎn)從作業(yè)高度h0拉升至安全高度h，轉(zhuǎn)移至Pj點(diǎn)后再下降至作業(yè)高度繼續(xù)作業(yè)。計(jì)算轉(zhuǎn)移路線長度時(shí)在原計(jì)算值上加上高度調(diào)整量2(h-h0)。上述過程中涉及到多邊形偏置算法、多邊形與線段間求交算法，也是計(jì)算機(jī)圖形學(xué)中經(jīng)典問題[26]，限于篇幅問題，不贅述。

1.6 按需多次補(bǔ)給方案

因載質(zhì)量及續(xù)航時(shí)間限制，無人機(jī)田間作業(yè)時(shí)往往需要執(zhí)行多個架(航)次，中間進(jìn)行能源及藥肥種等農(nóng)資消耗品的補(bǔ)給填裝。分為動力消耗補(bǔ)給(Refuel or recharge)和農(nóng)資消耗補(bǔ)給(Refill)兩種，前者要求對所有飛行過程中能源累積消耗值與初始值差值和最低允許值進(jìn)行比較，確定返航點(diǎn)；后者則主要考慮有效作業(yè)段的物資累積消耗值與初始值之間的差值是否為零來確定返航點(diǎn)。

就植保無人機(jī)而言，單次電池的續(xù)航能力一般在10～25 min之間，飛行速度2～10 m/s，換算成距離在1 200～15 000 m之間，實(shí)際還受自然風(fēng)、起降次數(shù)、懸停時(shí)間和飛手操作熟練程度等因素的影響。而藥箱一般在8～16 L之間，平均10～12 L，根據(jù)不同的作物、病蟲害類型及危害程度，單位面積噴播量設(shè)置不同。有兩種參數(shù)設(shè)置方式，一種為恒速噴播模式，農(nóng)資消耗量與作業(yè)時(shí)間成正比，單位是mL/s；另一種是變量/隨速噴播模式，農(nóng)資消耗量與作業(yè)距離或面積成正比，單位是mL/hm2。不同的消耗品初始值及消耗速度，決定了需要補(bǔ)給時(shí)的返航點(diǎn)一般也不同，但不管哪一種消耗品需要補(bǔ)給，都必須立即做出響應(yīng)，否則會導(dǎo)致安全事故或作業(yè)遺漏。

如圖5所示，在通過前述作業(yè)方向及航線調(diào)度次序優(yōu)化后獲得的初步作業(yè)路徑中，作業(yè)航線與航線間轉(zhuǎn)移路徑是相間排列的。若用P0表示起降補(bǔ)給點(diǎn)，n條作業(yè)航線用{P1→P2，P3→P4,…，P2i+1→P2i+2,…，P2n-1→P2n}表示,則對應(yīng)的跳轉(zhuǎn)路徑為n+1條，且可表示為{P0→P1,P2→P3,…，P2i→P2i+1,…，P2n→P0}?？梢钥吹剑醪阶鳂I(yè)路徑中，除起降點(diǎn)外，還包含2n個航點(diǎn)，從當(dāng)前航點(diǎn)編號的奇偶性可以判斷出飛行器的下一動作是航線間轉(zhuǎn)移還是沿航線作業(yè)。

圖5 按需補(bǔ)給返航點(diǎn)示意圖Fig.5 Schematic of return point to refill and recharge on demand

補(bǔ)給方案生成時(shí)，從P0點(diǎn)出發(fā)，依次遍歷作業(yè)航線及轉(zhuǎn)移路徑，計(jì)算到達(dá)某個航點(diǎn)的累計(jì)里程(包括從該點(diǎn)返回至補(bǔ)給點(diǎn)的距離及危險(xiǎn)轉(zhuǎn)移過程中的高度調(diào)整距離)及農(nóng)資消耗量，當(dāng)二者之一達(dá)到返航補(bǔ)給條件時(shí)，考慮返航。

對于第i條作業(yè)航線P2i+1→P2i+2(i=0,1,2,…，n-1)而言，若長度為Li,則在變量/隨速噴播模式(噴播量與實(shí)際作業(yè)距離或面積成正比)下，單位面積噴播量為q，則消耗的農(nóng)資量為

Qi=LiWq

(2)

對于第i條航線間跳轉(zhuǎn)路徑P2i→P2i+1(i=0,1,2,…，n)而言，長度為L′i，因噴播系統(tǒng)關(guān)閉，故農(nóng)資消耗量為0。若為危險(xiǎn)轉(zhuǎn)移過程，里程加上高度調(diào)整值2(h-h0)或2h-h0(包含補(bǔ)給點(diǎn)時(shí))。

對于包含n條初始作業(yè)航線的模型而言，航點(diǎn)數(shù)為2n，按次序飛行作業(yè)至航點(diǎn)j的累計(jì)里程及農(nóng)資消耗量分別用L0～j和Q0～j表示，從j點(diǎn)返航回至補(bǔ)給點(diǎn)的里程用Lj→0表示，經(jīng)過m次危險(xiǎn)轉(zhuǎn)移過程，則

(3)

(4)

若用Lmax和Qmax分別表示最大續(xù)航里程和農(nóng)資容積，則當(dāng)累計(jì)耗時(shí)量及農(nóng)資消耗量滿足條件

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

(5)

Q0～j≥Qmax≥Q0～j-1

(6)

即安排返航，也稱之為“按需返航”。

當(dāng)按照公式(5)條件返航時(shí)，若j為奇數(shù)，則從上一航線的末端點(diǎn)(即j-1)處返航；若j為偶數(shù)，則采用插值法在航線中間某點(diǎn)Pnew返航，則L0～new+Lnew→0+2h-h0=Lmax。

當(dāng)按照公式(6)條件返航時(shí)，若j為奇數(shù)，則從上一航線的末端點(diǎn)(即j-1)處返航；若j為偶數(shù)，則采用插值法在航線中間點(diǎn)Pnew返航，則Q0～new=Qmax。

將中間點(diǎn)Pnew用參數(shù)表達(dá)式(即Pnew=λPj-1+(1-λ)Pj,λ∈[0,1])表示后代入上面等式，即可求出該點(diǎn)坐標(biāo)，求解時(shí)可利用迭代法快速解算。

返航至補(bǔ)給點(diǎn)后，在補(bǔ)給點(diǎn)進(jìn)行物資補(bǔ)給時(shí)，有兩種處置方式：按需重置(Reset on demand,ROD)，只將達(dá)到使用極限的物資進(jìn)行再次加載重置，未達(dá)到使用極限的物資不作處理，也稱之為“按需補(bǔ)給”；完全重置(All reset,AR)，只要是返回至補(bǔ)給點(diǎn)，即將所有物資全部重置，包括未使用完畢的電池或燃油、種肥藥等農(nóng)資消耗品，也稱之為“完全補(bǔ)給”。

此外，對剩余航線的遍歷作業(yè)(續(xù)航、續(xù)作)也有兩種處置方案：按照原計(jì)劃從返航點(diǎn)繼續(xù)作業(yè)，直至找到新的返航點(diǎn)或完成所有航線的遍歷作業(yè)，稱之為斷點(diǎn)續(xù)作(Go back to breakpoint and continue，GBC)；對剩余航線進(jìn)行重新排序，按新次序安排作業(yè)，直至找到新的返航點(diǎn)或完成所有航線的遍歷作業(yè)，稱之為重排續(xù)作(Go on with new order,GNO)。兩種方案均可采用遞歸算法進(jìn)行求解。因此形成表1所示4種補(bǔ)給續(xù)航組合策略。

表1 4種補(bǔ)給續(xù)航組合策略Tab.1 Four different combinations of refill-recharge and go-on strategies

2 實(shí)例仿真計(jì)算

上述全部算法過程在Visual C++ 6.0平臺上編碼實(shí)現(xiàn)，在Intel(R) Core(TM)i7-3370 @3.4 GHz CPU、8 GB 1 600 MHz內(nèi)存、Windows 7操作系統(tǒng)環(huán)境下，分別對4組典型場景算例在多組不同工作參數(shù)條件(田塊屬性及補(bǔ)給點(diǎn)位置如表2所示)下進(jìn)行算法穩(wěn)定性和計(jì)算效率測試試驗(yàn)。

表2 測試算例田塊參數(shù)Tab.2 Field parameters for case studies

算例1、2田塊均為假想邊界(算例2田塊邊界來自文獻(xiàn)[25])，算例3為田塊中帶孔洞的假想邊界，算例4田塊邊界來自開源地面站軟件MissionPlanner中Google Earth環(huán)境下的實(shí)際田塊。計(jì)算過程中，算法對導(dǎo)入的邊界自動進(jìn)行分組，識別區(qū)分不同田塊并逐一處理，對于單一邊界且為凸多邊形的田塊采用“最小跨度法”優(yōu)化航向，其他的情形則采用“步進(jìn)旋轉(zhuǎn)法”(步距角0.5°)優(yōu)化航向。采用貪婪算法進(jìn)行航線調(diào)度次序優(yōu)化。計(jì)算過程中對每一潛在轉(zhuǎn)移過程均進(jìn)行安全判斷并對危險(xiǎn)轉(zhuǎn)移

過程進(jìn)行處理。統(tǒng)一設(shè)定作業(yè)高度2 m，安全轉(zhuǎn)移高度6 m，安全邊界距離1 m。路徑總長度通過線段長度求和得到，算法耗時(shí)通過GetTickCount()函數(shù)獲取算法運(yùn)行前后的系統(tǒng)時(shí)間后再求差得到，且測試時(shí)包括界面顯示更新相關(guān)操作。

每個作業(yè)場景下進(jìn)行2組試驗(yàn)測試。試驗(yàn)1測試不同場景田塊算例在不同作業(yè)參數(shù)下，在不考慮作業(yè)補(bǔ)給條件下，4種不同作業(yè)方向及航線調(diào)度優(yōu)化策略對作業(yè)路徑總長度的優(yōu)化效果，測試結(jié)果相關(guān)數(shù)據(jù)如表3所示。轉(zhuǎn)移路徑優(yōu)化效果S=(S1-S2)/S1×100%，S1、S2分別為較差的優(yōu)化結(jié)果和較好的優(yōu)化結(jié)果，在表3中對應(yīng)的數(shù)據(jù)用*和** 標(biāo)識，而對應(yīng)的路徑截圖如表4所示。

表3 4種不同作業(yè)航向及航線調(diào)度組合策略下初始路徑規(guī)劃測試結(jié)果Tab.3 Test results of 4 different strategies for route orientation and order

表4 較好及較差航向及航線調(diào)度優(yōu)化組合策略對應(yīng)的初始路徑截圖Tab.4 Screen shots of initial route with optimal and worst combination of orientation and order strategies

試驗(yàn)2在試驗(yàn)1基礎(chǔ)上進(jìn)一步測試返航補(bǔ)給規(guī)劃算法的穩(wěn)定性及計(jì)算效率。因各田塊集中調(diào)度FBF原則可能會在補(bǔ)給規(guī)劃時(shí)被破壞掉，且由表3可知，AOD×SBS幾乎是最優(yōu)的作業(yè)方向及調(diào)度組合策略，因此統(tǒng)一選擇在該方向及調(diào)度策略下，進(jìn)一步設(shè)置補(bǔ)給相關(guān)試驗(yàn)條件(電力或燃油續(xù)航能力4 000 m，農(nóng)資消耗品一次加載12 L，隨速變量噴播模式下單位面積噴播量18 L/hm2)，測試在4種不同補(bǔ)給及續(xù)作組合策略方式下的補(bǔ)給次數(shù)和轉(zhuǎn)移路徑的差別，結(jié)果如表5所示。進(jìn)一步將其中的較好結(jié)果及較差結(jié)果對應(yīng)的補(bǔ)給路徑截圖在表6中(不同顏色區(qū)域表示不同的航次)進(jìn)行對比展示。

表5 按需返航后4種不同補(bǔ)給續(xù)作組合策略下航次(最終路徑)規(guī)劃測試結(jié)果Tab.5 Test results of final fights and route by four different combinations of refuel-refill and go-on strategies

表6 較好及較差補(bǔ)給續(xù)作優(yōu)化組合策略對應(yīng)的最終路徑截圖Tab.6 Screenshots of final flight route with optimal and worst combination of refuel-refill and go-on strategies

3 討論

針對含障礙物多田塊中單一旋翼無人機(jī)不考慮補(bǔ)給及考慮補(bǔ)給條件下的路徑規(guī)劃問題，所設(shè)計(jì)的算法分別對多組不同面積、田塊數(shù)目、邊界數(shù)目和節(jié)點(diǎn)數(shù)目的假想田塊、實(shí)際田塊在不同作業(yè)幅寬條件下進(jìn)行了無差別測試，優(yōu)化計(jì)算結(jié)果穩(wěn)定、具有可重復(fù)性。

從表3可以看出，算法耗時(shí)隨田塊邊界復(fù)雜程度而增加，隨作業(yè)幅寬增加而減小，測試算例耗時(shí)從78 ms到105 161 ms不等。這其中對于潛在轉(zhuǎn)移過程的安全性判斷耗費(fèi)了大量時(shí)間。同一工作幅寬條件下，有效工作路徑總長度相當(dāng)，因?yàn)樵摂?shù)值與工作幅寬的乘積與田塊面積相當(dāng)。對于轉(zhuǎn)移路徑的優(yōu)化，較好結(jié)果相對于較差結(jié)果的提升效果從10.25%到33.81%不等，AOD×SBS幾乎具有絕對的優(yōu)化效果，但不是絕對最優(yōu)組合策略。在時(shí)間允許情況下，建議用戶對這4種航向及調(diào)度組合策略進(jìn)行逐一測試并優(yōu)選。

考慮消耗品補(bǔ)給時(shí)，算法同樣具有很好的穩(wěn)定性和計(jì)算效率。測試中，算法耗時(shí)從21 170 ms到106 393 ms不等，影響因素與不考慮補(bǔ)給時(shí)相當(dāng)，數(shù)值上略有增加，主要由補(bǔ)給算法模塊引起。4種不同補(bǔ)給續(xù)航組合策略條件下的優(yōu)化效果中，補(bǔ)給次數(shù)的最好優(yōu)化效果從15次降到10次，補(bǔ)給次數(shù)少的轉(zhuǎn)移路徑長度小，轉(zhuǎn)移路徑長度的較好結(jié)果相對于較差結(jié)果的優(yōu)化幅度從14.00%到26.27%不等，總體來說同條件下完全重置+重排續(xù)作的組合策略的表現(xiàn)較優(yōu)，但并不絕對，因此實(shí)際操作時(shí)建議對4種不同補(bǔ)給續(xù)航組合策略進(jìn)行現(xiàn)場優(yōu)選。

實(shí)際作業(yè)過程中，飛行器的耗電量或耗油量除了與飛行時(shí)間有關(guān)，還與飛行高度、加減速、噴播量、風(fēng)速甚至各傳感器信號強(qiáng)弱程度等很多因素有關(guān)，飛行距離只是其中消耗能源占比最大的一個。因此實(shí)際使用時(shí)續(xù)航能力采用距離來衡量和設(shè)置時(shí)，應(yīng)多次試驗(yàn)近似確定，同時(shí)為確保安全，最好設(shè)置一個安全系數(shù)。

算例中的補(bǔ)給點(diǎn)都是事先人工隨機(jī)確定的。事實(shí)上補(bǔ)給點(diǎn)的數(shù)量和位置至關(guān)重要，如何合理地設(shè)置數(shù)量和位置，需要進(jìn)一步深入研究。

實(shí)際田塊中障礙物的具體表現(xiàn)形式(邊界形狀、高度和位置)具有多樣性，文中做法僅考慮了田塊內(nèi)部障礙物的邊界形狀和位置多樣性，其他都進(jìn)行了簡單化處理：以最大障礙物高度作為所有障礙物高度來進(jìn)行安全轉(zhuǎn)移時(shí)的高度調(diào)整；忽略田塊外部障礙物的具體邊界形狀及位置(除起降補(bǔ)給點(diǎn)，認(rèn)為外邊界以外都是障礙物)。這種處理方式也是目前大多商用無人機(jī)對障礙物的通行處理做法。雖可以確保飛行安全，但有可能增加轉(zhuǎn)移路徑中不必要的高度調(diào)整值，增加時(shí)間及能源消耗，這也是需要細(xì)化深入研究的內(nèi)容。

4 結(jié)論

(1)針對同一區(qū)域內(nèi)相鄰多田塊無人機(jī)作業(yè)任務(wù)規(guī)劃問題，從無人機(jī)應(yīng)用過程中遇到的續(xù)航、負(fù)重等實(shí)際問題出發(fā)，考慮種肥藥液和電力能源等消耗品的按需多次補(bǔ)給，提出并實(shí)現(xiàn)一套含障礙物復(fù)雜多田塊條件下單機(jī)多架次作業(yè)的農(nóng)用旋翼無人機(jī)自主飛行作業(yè)的路徑規(guī)劃算法。

(2)針對假想田塊及實(shí)際田塊的算例仿真測試結(jié)果表明，提出的規(guī)劃算法運(yùn)行穩(wěn)定可靠、效率高、優(yōu)化效果明顯，可滿足農(nóng)用無人機(jī)單機(jī)作業(yè)時(shí)的相關(guān)要求。