含障礙物多田塊下旋翼無人機(jī)作業(yè)返航補(bǔ)給規(guī)劃研究

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

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

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

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

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

農(nóng)用無人機(jī)路徑規(guī)劃研究正向復(fù)雜邊界田塊條件(邊界形狀、障礙物、高度差、多田塊)、按需補(bǔ)給調(diào)度、多機(jī)協(xié)同等方向發(fā)展。本文針對(duì)具有自主飛行功能的旋翼農(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è)。這可看成為一個(gè)多目標(biāo)優(yōu)化問題，由最小重漏面積、最小總路徑長度、最小作業(yè)時(shí)長等子目標(biāo)組成，但各子目標(biāo)對(duì)總目標(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í)不與地表接觸，可任意方向移動(dòng)不需要轉(zhuǎn)彎空間，且配備厘米級(jí)高精度定位傳感器等，因此自主飛行作業(yè)模式下理論上作業(yè)重漏面積可忽略不計(jì)。而作業(yè)時(shí)間T(x)、能源消耗量E(x)、農(nóng)資消耗量W(x)均與作業(yè)路徑總長度L(x)存在一定的依存關(guān)系，按照運(yùn)動(dòng)學(xué)方程及消耗模型，該多目標(biāo)優(yōu)化問題最后可統(tǒng)一轉(zhuǎn)化為以最小路徑總長度為優(yōu)化函數(shù)的單目標(biāo)優(yōu)化問題進(jìn)行求解。

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

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

從確保作業(yè)安全、操作方便和便于程序代碼編制的角度考慮數(shù)據(jù)定義和表征方法。以多邊形表征田塊邊界，外邊界以逆時(shí)針方向、內(nèi)邊界以順時(shí)針方向依次存儲(chǔ)各頂點(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ī)器簡(jiǎn)化為其幾何中心上的一點(diǎn)，作業(yè)路徑即為無人機(jī)移動(dòng)時(shí)機(jī)器中心的軌跡線，以點(diǎn)數(shù)組按照先后順序存儲(chǔ)。下文各圖中有效作業(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è)路徑為輸出，整個(gè)算法的流程如圖1所示。

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

1.3 邊界分組與田塊識(shí)別

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

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

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

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

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

有效作業(yè)路徑是機(jī)器移動(dòng)過程中同步進(jìn)行具體某種作業(yè)操作(噴播)的路徑，即作業(yè)實(shí)施過程中遵循的設(shè)定軌跡，對(duì)無人機(jī)來說俗稱“航線”。旋翼無人機(jī)以作業(yè)幅寬w實(shí)現(xiàn)對(duì)待作業(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è)方向，而所獲得線段在集合中的存儲(chǔ)順序即為航線的調(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ǎn)單，但結(jié)果對(duì)于凸多邊形的單田塊情形是準(zhǔn)確的，對(duì)于凹多邊形、孔洞多邊形田塊以及多個(gè)田塊的情形，計(jì)算結(jié)果一般并非為最優(yōu)方向。

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

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

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

采用“安全邊界相交性測(cè)試法”來判別某條候選轉(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所示，對(duì)于田塊F0的某條候選轉(zhuǎn)移路徑PiPj，因?yàn)榫€段PiPj與外邊界B0偏置后多邊形B′0存在交點(diǎn)C1和C2，故該轉(zhuǎn)移過程視為危險(xiǎn)轉(zhuǎn)移過程。對(duì)于此類轉(zhuǎn)移過程，為確保絕對(duì)安全，實(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í)行多個(gè)架(航)次，中間進(jìn)行能源及藥肥種等農(nóng)資消耗品的補(bǔ)給填裝。分為動(dòng)力消耗補(bǔ)給(Refuel or recharge)和農(nóng)資消耗補(bǔ)給(Refill)兩種，前者要求對(duì)所有飛行過程中能源累積消耗值與初始值差值和最低允許值進(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)，否則會(huì)導(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}表示,則對(duì)應(yīng)的跳轉(zhuǎn)路徑為n+1條，且可表示為{P0→P1,P2→P3,…，P2i→P2i+1,…，P2n→P0}?？梢钥吹?，初步作業(yè)路徑中，除起降點(diǎn)外，還包含2n個(gè)航點(diǎn)，從當(dāng)前航點(diǎn)編號(hào)的奇偶性可以判斷出飛行器的下一動(dòng)作是航線間轉(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á)某個(gè)航點(diǎn)的累計(jì)里程(包括從該點(diǎn)返回至補(bǔ)給點(diǎn)的距離及危險(xiǎn)轉(zhuǎn)移過程中的高度調(diào)整距離)及農(nóng)資消耗量，當(dāng)二者之一達(dá)到返航補(bǔ)給條件時(shí)，考慮返航。

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

Qi=LiWq

(2)

對(duì)于第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í))。

對(duì)于包含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ǔ)給”。

此外，對(duì)剩余航線的遍歷作業(yè)(續(xù)航、續(xù)作)也有兩種處置方案：按照原計(jì)劃從返航點(diǎn)繼續(xù)作業(yè)，直至找到新的返航點(diǎn)或完成所有航線的遍歷作業(yè)，稱之為斷點(diǎn)續(xù)作(Go back to breakpoint and continue，GBC)；對(duì)剩余航線進(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平臺(tái)上編碼實(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)境下，分別對(duì)4組典型場(chǎng)景算例在多組不同工作參數(shù)條件(田塊屬性及補(bǔ)給點(diǎn)位置如表2所示)下進(jìn)行算法穩(wěn)定性和計(jì)算效率測(cè)試試驗(yàn)。

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

算例1、2田塊均為假想邊界(算例2田塊邊界來自文獻(xiàn)[25])，算例3為田塊中帶孔洞的假想邊界，算例4田塊邊界來自開源地面站軟件MissionPlanner中Google Earth環(huán)境下的實(shí)際田塊。計(jì)算過程中，算法對(duì)導(dǎo)入的邊界自動(dòng)進(jìn)行分組，識(shí)別區(qū)分不同田塊并逐一處理，對(duì)于單一邊界且為凸多邊形的田塊采用“最小跨度法”優(yōu)化航向，其他的情形則采用“步進(jìn)旋轉(zhuǎn)法”(步距角0.5°)優(yōu)化航向。采用貪婪算法進(jìn)行航線調(diào)度次序優(yōu)化。計(jì)算過程中對(duì)每一潛在轉(zhuǎn)移過程均進(jìn)行安全判斷并對(duì)危險(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í)間后再求差得到，且測(cè)試時(shí)包括界面顯示更新相關(guān)操作。

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

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

表4 較好及較差航向及航線調(diào)度優(yōu)化組合策略對(duì)應(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)一步測(cè)試返航補(bǔ)給規(guī)劃算法的穩(wěn)定性及計(jì)算效率。因各田塊集中調(diào)度FBF原則可能會(huì)在補(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)，測(cè)試在4種不同補(bǔ)給及續(xù)作組合策略方式下的補(bǔ)給次數(shù)和轉(zhuǎn)移路徑的差別，結(jié)果如表5所示。進(jìn)一步將其中的較好結(jié)果及較差結(jié)果對(duì)應(yīng)的補(bǔ)給路徑截圖在表6中(不同顏色區(qū)域表示不同的航次)進(jìn)行對(duì)比展示。

表5 按需返航后4種不同補(bǔ)給續(xù)作組合策略下航次(最終路徑)規(guī)劃測(cè)試結(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)化組合策略對(duì)應(yīng)的最終路徑截圖Tab.6 Screenshots of final flight route with optimal and worst combination of refuel-refill and go-on strategies

3 討論

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

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

考慮消耗品補(bǔ)給時(shí)，算法同樣具有很好的穩(wěn)定性和計(jì)算效率。測(cè)試中，算法耗時(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é)果相對(duì)于較差結(jié)果的優(yōu)化幅度從14.00%到26.27%不等，總體來說同條件下完全重置+重排續(xù)作的組合策略的表現(xiàn)較優(yōu)，但并不絕對(duì)，因此實(shí)際操作時(shí)建議對(duì)4種不同補(bǔ)給續(xù)航組合策略進(jìn)行現(xiàn)場(chǎng)優(yōu)選。

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

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

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

4 結(jié)論

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