農(nóng)用無人機多機多田塊作業(yè)路徑規(guī)劃算法

唐燦，宗望遠,2，黃小毛,2，羅承銘,2，李文成,2，王紹帥

1.華中農(nóng)業(yè)大學(xué)工學(xué)院，武漢 430070； 2.農(nóng)業(yè)農(nóng)村部長江中下游農(nóng)業(yè)裝備重點實驗室，武漢 430070

近年來，無人機逐漸發(fā)展成為一種常見的農(nóng)業(yè)生產(chǎn)機械[1]，可以實現(xiàn)遙感[2]、植保[3]、播撒[4]等多種農(nóng)業(yè)作業(yè)任務(wù)。相較于單個無人機作業(yè)，多機協(xié)同作業(yè)可顯著提高作業(yè)效率，減少具體田塊的作業(yè)處理時間[5-6]，是大面積多區(qū)域作業(yè)時的一項重要形式[7]。

路徑規(guī)劃問題是近些年無人機領(lǐng)域的研究熱點。由于實際作業(yè)工況多種多樣，對單機單田塊區(qū)域、多田塊區(qū)域、含障礙物區(qū)域、按需補給以及多機協(xié)同等都有相關(guān)研究。比如單架無人機作業(yè)路徑規(guī)劃方面，Valente等[8]提出一種基于“和諧搜索”(harmony search)的啟發(fā)式搜索算法去求解單機作業(yè)情況下的遍歷網(wǎng)格的最優(yōu)次序，王宇等[9]提出一種基于柵格模型的路徑規(guī)劃算法，黃小毛等[10-11]提出基于多邊形掃描填充線快速求解的無人機路徑規(guī)劃算法，嚴煒等[12]提出一種基于差分量子退火算法的農(nóng)用無人機路徑規(guī)劃方法。

多機協(xié)同作業(yè)時，主要考慮待作業(yè)任務(wù)的劃分，為使得任務(wù)盡可能均衡，一般采用“等面積法”劃分待作業(yè)區(qū)域后再分別規(guī)劃航線[13-14]。此外，Barrientos等[15]將待作業(yè)區(qū)域進行網(wǎng)格化處理，并提出一種基于任務(wù)協(xié)商機制的作業(yè)路徑規(guī)劃算法，Nigam等[16]提出一種適用于矩形區(qū)域的區(qū)域劃分與分配算法。由于載荷及續(xù)航問題，對于多田塊區(qū)域，單航次往往無法滿足作業(yè)要求，因此，需要考慮中途返航至補給點進行電量以及農(nóng)資的補給。徐博等[17]基于最小能耗對單一大面積矩形邊界田塊中的補給架次進行了研究。李繼宇等[18]基于能量利用率最大化原則，對邊界形狀簡單且單一的田塊補給過程進行了研究。

隨著電動旋翼農(nóng)用無人機應(yīng)用日益廣泛，對含障礙物大面積多田塊區(qū)域的作業(yè)任務(wù)需求日益增多。本研究在筆者所在課題組前期工作基礎(chǔ)上，針對含障礙物多田塊條件下，綜合考慮電量以及農(nóng)資補給，提出一套基于Google OR-Tools[19]的農(nóng)用無人機多機協(xié)同作業(yè)路徑靜態(tài)規(guī)劃算法，旨在為多田塊條件下的多機協(xié)同作業(yè)路徑規(guī)劃優(yōu)化提供參考。

1 材料與方法

多臺農(nóng)用無人機協(xié)同作業(yè)路徑規(guī)劃的任務(wù)是先計算出完全覆蓋田塊多邊形區(qū)域的基礎(chǔ)作業(yè)航線，再分配給多臺無人機并合理安排多次補給續(xù)航方案。本研究計算時忽略無人機在工作時可能發(fā)生的碰撞問題以及天氣、風(fēng)速等外部環(huán)境影響和因作業(yè)進程而變化的實際載荷對動力的動態(tài)影響。

1.1 算法總體流程

以最小轉(zhuǎn)移路徑長度為作業(yè)優(yōu)化目標，基于多邊形掃描填充算法[10-11]計算出水平航向條件的初始覆蓋作業(yè)航線，將田塊邊界障礙物進行安全邊界相交性測試[10-11]，并分別針對各田塊采用凸多邊形“最小跨度法”[10-11]以及非凸多邊形“步進旋轉(zhuǎn)法”[10-11]優(yōu)化作業(yè)航向。再基于Google OR-Tools組合優(yōu)化開源軟件工具包，綜合考慮消耗品按需返航后的補給與續(xù)作問題，進行航線調(diào)度次序及作業(yè)航次的規(guī)劃。

以田塊及障礙物的邊界和飛行作業(yè)參數(shù)為輸入，以作業(yè)路徑為輸出，整個算法的流程如圖1所示。

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

1.2 航線調(diào)度優(yōu)化

建立航線調(diào)度目標模型，參照旅行商問題(traveling salesman problem,TSP)，將初始作業(yè)航線的每個端點簡化為1個“城市”。為保證航線上每個點均可被遍歷且無人機可以從航線的一端飛向另一端，在構(gòu)建TSP距離矩陣時將位于同一航線上的2個城市點間的名義距離設(shè)為0，而將實際距離均分到該航線與其他航線間的轉(zhuǎn)移路徑上。假設(shè)有m臺無人機，n條作業(yè)航線(加上起降點，共對應(yīng)2n+1座城市)，集合A={1，2，…，2n}、B={0,1，2，…，2n}、C={1，2，…，m}，每臺無人機中有rk次不包含補給點的危險轉(zhuǎn)移過程[10-11]，sk次包含補給點的危險轉(zhuǎn)移過程，h0為作業(yè)高度，h為安全高度，則該問題的數(shù)學(xué)模型可描述如下：

(1)

i,j∈B,k∈C

(2)

(3)

(4)

(5)

按照上述模型，可在基礎(chǔ)航線數(shù)據(jù)上建立該問題的距離矩陣，并通過算法進行求解。窮舉搜索所有航線調(diào)度方式可得到最小轉(zhuǎn)移路徑，但計算效率較低。本研究采用Google OR-Tools開源工具包中的智能算法，在規(guī)定時間內(nèi)找出盡可能最優(yōu)的解。解決路徑問題時，OR-Tools提供2種解算器，本研究采用其中最常用的解算器CP-SAT。OR-Tools使用最先進的算法縮小搜索集范圍，以便找到最佳(或接近最佳)的解決方案[19]，解算器包含了14種初始解構(gòu)造策略算法(first solution strategy)和5種優(yōu)化搜索策略算法(local search options)。前者負責(zé)構(gòu)造初始解，包括節(jié)約算法(savings)、掃描算法(sweep)、最近插入法(best insertion)、克里斯托菲德斯算法(Christofides)等經(jīng)典求解算法；后者對初始解進一步優(yōu)化，包含改良貪心算法(greedy descent)、引導(dǎo)式本地搜索算法(guided local search)、模擬退火算法(simulated annealing)、禁忌搜索算法(tabu search)與目標禁忌搜索算法(objective tabu search)。二者組合起來將形成70種組合策略算法，因篇幅有限，列舉其中4種組合策略如表1所示。

表1 4種航線調(diào)度組合策略 Table 1 Four combined strategies for route scheduling

1.3 按需多次補給

無人機具有最大起飛質(zhì)量限制，作業(yè)時攜帶的種肥藥液等農(nóng)業(yè)物資也會消耗大量的動力，而電池或燃油容量與其質(zhì)量成正比。因此，每個航次攜帶農(nóng)資的最大質(zhì)量和電池的容量會受到限制，一般會有一個經(jīng)濟值。本研究暫不考慮農(nóng)資消耗過程對續(xù)航能力的動態(tài)影響，設(shè)每臺無人機最大農(nóng)資載荷為Q，每個航次的最大續(xù)航里程為Lmax。航線作業(yè)時會消耗一定量的農(nóng)資，消耗量與航線對應(yīng)的單位距離或覆蓋面積成正比。求解時，將每條航線需要消耗的農(nóng)資量均攤到2個航線端點“城市”上。設(shè)每個航線端點的農(nóng)資需求量為qi(i=1,2,…,2n)，yki為無人機k到訪端點i，本航次已完成其中u條航線的遍歷任務(wù)，D為對應(yīng)的端點序號集合，則農(nóng)資消耗約束條件為：

(7)

(8)

當(dāng)動力與農(nóng)資的累積消耗量其中任意一種超過限制時，執(zhí)行補給操作，即返回至補給點將動力與農(nóng)資完全重置。補給完成后，將剩余航線進行重新排序，直至找到新的返航點或完成所有航線的遍歷作業(yè)[11]。

采用OR-Tools中的CVRP(capacitated vehicle routing problem,具有能力約束的車輛路徑問題)求解算法，進行航線任務(wù)分配及補給方案的求解。

2 結(jié)果與分析

前述算法過程基于Python 3.8語言在PyCharm平臺上編碼實現(xiàn)，在AMD Ryzen 7 4800,1.8 GHz CPU、16 GB 1 600 MHz內(nèi)存、Windows 10操作系統(tǒng)環(huán)境下，分別對4組人工假想和實際多田塊邊界在多組不同工作參數(shù)條件下進行2次試驗，以測試算法穩(wěn)定性、計算效率和優(yōu)化效果。

田塊邊界用藍色多邊形表示，每臺無人機航線分別用紅色、藍色、黑色等不同顏色線段表示，轉(zhuǎn)移路徑用綠色虛線段表示，無人機的補給返航點用與航線顏色相同的圓圈標記，每個航次起始處加數(shù)字標記，其中危險轉(zhuǎn)移過程對應(yīng)航點處加黑色三角形標記。

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

設(shè)無人機臺數(shù)為3。實際田塊邊界利用Omap獲取并以KML文件格式導(dǎo)出；假想田塊邊界利用CAD繪制并以DXF格式導(dǎo)入。計算過程中，先基于多邊形掃描填充算法計算出水平航向條件的初始覆蓋作業(yè)航線，再采用凸多邊形“最小跨度法”與非凸多邊形“步進旋轉(zhuǎn)法”(取步距角Δθ=0.5°)優(yōu)化作業(yè)航向；后基于OR-Tools求解出田塊最優(yōu)航線調(diào)度次序并將航線分配給3臺無人機，最后按照無人機性能建立能量與物資消耗模型，調(diào)用OR-Tools優(yōu)化作業(yè)航次，計算過程中對每個潛在轉(zhuǎn)移過程均進行安全判斷并對危險轉(zhuǎn)移過程進行處理。

算法中統(tǒng)一設(shè)定作業(yè)高度2 m(實際作業(yè)中，為保證絕對安全，要求航線間轉(zhuǎn)移時不同飛機必須采用不同的轉(zhuǎn)移高度，此處作簡化處理)，安全轉(zhuǎn)移高度6 m，安全邊界距離1 m。參考文獻[11]中作業(yè)參數(shù)，設(shè)定無人機速度為3 m/s，電力或燃油續(xù)航能力4 000 m，單次航行所需農(nóng)資為12 L，變量噴播模式下單位面積噴播量為18 L/hm2。同時為避免OR-Tools出現(xiàn)因過分追求最優(yōu)解使得求解時間過長的情況，設(shè)置該環(huán)節(jié)最大求解時長為30 s。

首先嘗試通過初步試驗，對比測試70種不同組合策略對不考慮補給時的調(diào)度優(yōu)化算法效果。因篇幅有限，而測試結(jié)果表明進一步優(yōu)化搜索策略算法中引導(dǎo)式本地搜索算法優(yōu)化效果最好，禁忌搜索算法優(yōu)化效果最差；同時克里斯托菲德斯算法(Christofides)是旅行商問題中近似比最好的結(jié)果，掃描算法(sweep)也是車輛路徑問題中較為常用的方法，因此只截取由以上4種算法所組成的4種組合策略優(yōu)化結(jié)果，如表3所示。

從表3可以看出，“Christofides算法×引導(dǎo)式本地搜索算法(C×G)”組合下的計算結(jié)果，無論在路徑總長度還是算法耗時上，都與“sweep算法×引導(dǎo)式本地搜索算法(S×G)”大致相當(dāng)；“Christofides算法×禁忌搜索算法(C×T)”組合下的計算結(jié)果與“sweep算法×禁忌搜索算法(S×T)”也是基本一致。而當(dāng)比較“Christofides算法×引導(dǎo)式本地搜索算法(C×G)”和“Christofides算法×禁忌搜索算法(C×T)”組合下的計算結(jié)果時，出現(xiàn)了相對較大的差異，同樣的趨勢出現(xiàn)在“sweep算法×引導(dǎo)式本地搜索算法(S×G)”和“sweep算法×禁忌搜索算法(S×T)”組合下的計算結(jié)果。這說明，不同的初始解構(gòu)造策略對結(jié)果影響不大，結(jié)果上的差異主要由進一步的優(yōu)化搜索策略算法的不同而引起并決定。

表3 多機作業(yè)4種不同航線調(diào)度組合策略算法下初始路徑規(guī)劃(不考慮補給)測試結(jié)果 Table 3 Results of initial path planning under four different route scheduling combination strategies algorithm for multi UAVs operation without replenishment

進一步固定初始解構(gòu)造策略為常用的Christofides，對比測試5種優(yōu)化搜索策略算法對考慮補給情況下的路徑優(yōu)化效果，并且與文獻[13-14]中等面積劃分算法進行對比，結(jié)果如表4所示。表4中，5種優(yōu)化搜索策略算法的轉(zhuǎn)移路徑總長度的數(shù)據(jù)，相同條件下相比較最好的結(jié)果用**注釋，最差的結(jié)果用*注釋；優(yōu)化結(jié)果分別對比等面積劃分算法結(jié)果，計算出優(yōu)化提升效果。

從表4可知，5種進一步的優(yōu)化搜索策略算法的效果各不相同。從優(yōu)化結(jié)果上看，對轉(zhuǎn)移路徑總長度的優(yōu)化效果，引導(dǎo)式本地搜索算法(G)最好，8個算例中有7個是最優(yōu)的，禁忌搜索算法(T)和目標禁忌搜索算法(OTS)最差，各獲得3個算例的最差結(jié)果，其次是模擬退火算法(SA)和改良貪心算法(GD)獲得1個算例的最差結(jié)果。造成這種差異的主要原因除了算法本身的設(shè)計差異外，可能還在于設(shè)置了30 s求解時間的限制。也就是說部分算法能夠在該時長內(nèi)快速逼近最優(yōu)解，而其他算法可能需要更多的尋優(yōu)時間。

將各算例的OR-Tools優(yōu)化結(jié)果，與等面積劃分法的算法結(jié)果進行對比時，發(fā)現(xiàn)最優(yōu)結(jié)果對轉(zhuǎn)移路徑總長度的優(yōu)化效果為30.92%～47.10%，而最差優(yōu)化效果也能夠達到24.86%～43.96%。這說明，基于OR-Tools優(yōu)化效果顯著，非常有必要。同時，從算法耗時上看，改良貪心算法的耗時最短，其他算法的耗時相當(dāng)，為70～552 s，但基本在路徑離線規(guī)劃優(yōu)化操作的可接受范圍之內(nèi)。

表4 多機作業(yè)5種優(yōu)化搜索策略算法對考慮補給情況下的優(yōu)化結(jié)果 Table 4 Results of five optimizing search strategy algorithms for multi-UAVs considering replenishment

表5中給出了相同初始解構(gòu)造策略算法下5種進一步優(yōu)化搜索策略算法的最優(yōu)和最差結(jié)果與等面積劃分優(yōu)化算法的結(jié)果的相關(guān)圖例，可見算法所得基礎(chǔ)航線對田塊區(qū)域的覆蓋效果良好，基本看不出重漏作業(yè)區(qū)域。

表5 5種優(yōu)化搜索策略算法中最好及最差優(yōu)化結(jié)果和等面積劃分算法結(jié)果截圖 Table 5 Screenshots of the optimal and worst results in 5 optimizing search strategy algorithms

續(xù)表5 Continued Table 5

3 討 論

本研究針對含障礙物多田塊條件下的農(nóng)用無人機路徑規(guī)劃問題，研究了多機協(xié)同全覆蓋路徑規(guī)劃優(yōu)化算法。同時考慮消耗品按需返航后的補給與續(xù)作問題，基于Google OR-Tools組合優(yōu)化開源軟件工具包，對不同的調(diào)度搜索策略進行了對比試驗研究。利用4組假想與實際含障礙物多田塊進行仿真試驗測試，首先測試了Google OR -Tools組合策略算法在不考慮補給時的優(yōu)化效果和計算效率，結(jié)果表明 OR-Tools初始解構(gòu)造策略對最終結(jié)果影響不大，結(jié)果上的差異主要由進一步的優(yōu)化搜索策略算法的不同而引起并決定。然后將本研究設(shè)計的算法與無人機沿航向方向等面積劃分算法相比較，結(jié)果表明算法運行穩(wěn)定可靠，優(yōu)化效果明顯，相比于等面積劃分算法，航線間轉(zhuǎn)移路徑總長度下降了24.86%～47.10%，算法耗時70～552 s，在路徑離線規(guī)劃優(yōu)化操作的可接受范圍之內(nèi)，滿足無人機路徑離線規(guī)劃優(yōu)化的算法耗時要求和優(yōu)化目標。