農用無人機多機多田塊作業路徑規劃算法

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

1.華中農業大學工學院，武漢 430070； 2.農業農村部長江中下游農業裝備重點實驗室，武漢 430070

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

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

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

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

1 材料與方法

多臺農用無人機協同作業路徑規劃的任務是先計算出完全覆蓋田塊多邊形區域的基礎作業航線，再分配給多臺無人機并合理安排多次補給續航方案。本研究計算時忽略無人機在工作時可能發生的碰撞問題以及天氣、風速等外部環境影響和因作業進程而變化的實際載荷對動力的動態影響。

1.1 算法總體流程

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

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

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

1.2 航線調度優化

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

(1)

i,j∈B,k∈C

(2)

(3)

(4)

(5)

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

表1 4種航線調度組合策略 Table 1 Four combined strategies for route scheduling

1.3 按需多次補給

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

(7)

(8)

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

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

2 結果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

續表5 Continued Table 5

3 討 論

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