基于改進ACO 的帶續航約束無人機全覆蓋作業路徑規劃

于全友，徐止政，*，段納，徐覓蜜，程義

1.江蘇師范大學 電氣工程及自動化學院，徐州 221000

2.江蘇蒲公英無人機有限公司，徐州 221000

電動多旋翼無人機具有效率高、成本低、地形適應性強、操作靈活等優點［1］，得到廣泛應用。路徑規劃是提高無人機作業效率和降低作業總能耗的有效途徑，受到學者關注，目前在作業路徑生成［2-5］、避障策略［6-7］、多機協同作業［8-9］和圖形拆分［10］等方面已取得重要進展。受無人機電池容量和載重能力限制，若作業區域面積較大，無人機在作業過程中需多次返回補給點更換電池和補給物料［5］。如何合理規劃帶續航約束的單機多航次作業的返航點以減少額外的時間和能量消耗，是路徑規劃研究需要考慮的重要內容。

目前許多學者已對單機多航次路徑規劃問題展開研究，一般采用“先路徑、后航次”策略，即先不考慮續航約束求得無人機總的作業路徑，再對返航點數量和位置進行規劃。針對較規則的凸多邊形作業區域農藥噴施作業，李繼宇等［6］先采用柵格法確定作業路徑，再根據電池或農藥續航里程約束將返航點設置在臨近補給點的作業區域邊界上，最后根據各航次作業里程配置載荷，實現航線、載荷和能量三者優化配置。徐博等［11-12］在柵格法確定的作業路徑基礎上，根據作業路徑總長度確定最少返航點數量，再通過調整各航次噴施量確定各返航點位置。王宇等［13］用柵格法求得總作業路徑后，以各航次飛行距離為優化變量，以最小化返航點與保障點之間往返距離總和為優化目標，采用引力搜索算法求解返航點數量和位置。隨后，王宇等［14］又將引力搜索算法應用到三維地形路徑規劃問題。闞平等［15］研究多植保無人機協同路徑規劃問題，先用柵格法確定作業路徑，然后以各植保無人機作業距離作為優化變量，以補給總次數、返航補給總時間、總耗時和最小補給時間間隔為優化目標，采用改進粒子群算法求得無人機返航順序和返航點位置。對于凸多邊形作業區域可采用區域跨度法［16］確定航向角。以上針對研究形狀規則田地的單機多航次作業路徑規劃研究的方法并不適用于復雜形狀田地的作業路徑規劃。

對于復雜作業地形一般采用掃描線方法［17］生成作業路徑，再利用步進旋轉法［18］對掃描線方向角進行優化。黃小毛等［19-21］針對復雜形狀田地的植保無人機作業路徑規劃問題展開研究，先以最短總飛行路徑為優化目標確定初始作業路徑，再考慮消耗品按需返航后的補給與續作問題進行航次規劃，采用貪婪算法求解。將補給方式歸納為按需補給和完全重置2 種策略，將續航方式歸納為斷點續作（Go back to Breakpoint and Continue，GBC）和重排續作（ Go on with New Order，GNO）2 種策略，并對4 種策略組合進行驗證。上述文獻著重討論不同的補給和續航策略組合對路徑規劃的影響，沒有從全局優化角度對續航約束進行討論。

無人機的返航點是在作業過程中動態生成的新的路徑節點，它既改變了有效作業路徑的數量也改變了它們之間的代價函數，求解困難，目前研究尚少。在動態旅行商問題（Dynamic Traveling Salesman Problem，DTSP）中［22］中 也存在互換城市位置、改變城市之間代價函數等參數隨時間變化問題，但DTSP 與本文問題有顯著區別。DTSP 的參數每隔一段時間產生變化，可視為一系列靜態TSP 問題，對求解算法實時性和魯棒性要求高［23-24］；而本文問題的參數變化與解本身有關，與時間無關，對求解算法搜索能力要求高。目前TSP 問題常采用蟻群算法求解［25-30］。

本文主要貢獻如下：①基于掃描線路徑生成方法建立帶續航約束的無人機全覆蓋路徑規劃數學模型，并給出無人機返航時機判斷機制和返航點計算方法；②針對該全覆蓋路徑規劃模型特點，提出改進蟻群算法（Ant Colony Optimization，ACO），設計距離矩陣動態更新機制，處理返航點導致的節點拓撲結構動態變化問題；③設計滾動權值加權和信息素更新機制，兼顧全局啟發性和局部啟發性信息。

1 問題描述與建模

本文研究的無人機路徑規劃問題為不規則地形全覆蓋路徑規劃問題。無人機作業過程的飛行路徑可分為2 部分：一是作業路徑，即執行作業任務（例如農藥噴施）的飛行路徑；二是轉移路徑，即在作業路徑間進行切換的飛行路徑。基于掃描線方法生成作業路徑，在此基礎上，重點研究帶續航約束的作業路徑執行次序的優化。

如果將作業路徑視為城市節點，將轉移路徑視為城市之間的距離，則無人機路徑規劃問題可視為一類特殊的旅行商問題 （Traveling Salesman Problem，TSP）。特殊之處有2 點：一是城市節點由作業路徑的2 個端點描述，城市之間的代價函數不唯一，如圖1（a）所示；二是無人機因續航約束從作業路徑上返航后會生成新的作業路徑端點，從而改變城市節點的拓撲結構，如圖1（b）所示。因此，帶續航約束的無人機路徑規劃問題的數學模型也與一般的TSP 問題的數學模型不同。

圖1 作業路徑節點間轉移示意圖Fig.1 Schematic of transfer between nodes of operation path

基于掃描線方法［16］建立帶續航約束的無人機全覆蓋路徑規劃數學模型。如圖2 所示，設掃描線的方向角為α，無人機作業寬幅為ω，然后采用一組間距為ω、方向角為α 的平行掃描線覆蓋作業區域，掃描線與作業區域邊界（含障礙物）的任意相鄰兩交點可確定一條作業路徑，如{P2i-1，P2i}和{P2i，P2i+1}，取 經 過 作 業 區 域 內 部的掃描線作為作業路徑，如{P2i-1，P2i}。設通過掃描線方法獲得的有效路徑的端點總數為N，若將所有端點從下至上，從左至右順序編號，則相鄰的一對奇偶端點（奇數在前，偶數在后）確定一條無人機的作業路徑，作業路徑總個數為N 2。由此可見，任意一條作業路徑Li可由其2 個端點表 示，即Li={P2i-1，P2i}。由于Li的2 個端點 均可作為駛入端或駛出端，因此Li也可以表示 為，其 中，且。

圖2 掃描線法生成全覆蓋作業路徑Fig.2 Coverage operation path generation based on sweep method

由此可見，一旦掃描線方向角α 確定，無人機作業路徑總長度可由式（1）確定：

式中：(x2i，y2i)為P2i的坐標；(x2i-1，y2i-1)為P2i-1的坐標。

令二元決策變量rij表示有效作業路徑Li和Lj之間的連接關系，即

令E 表示無人機單位距離能耗，則可建立帶續航約束的無人機路徑規劃數學模型。

設計變量：

式中：α 為掃描線的方向角；R 為二元決策變量矩陣；二元決策變量rij為R 的元素。

式中：為作業路徑Li和Lj之間的轉移路徑長度；i=0 表示作業起點或電量補給點。

約束條件：

1）為了保證任意一條作業路徑均通過轉移路徑與其他兩條不同的作業路徑相連，需滿足

2）設Pk為任意有效作業路徑Li上一點，P0為電量補給點，無人機剩余電量為Ck，為保證無人機能夠安全返航，需滿足

3）當Pk為Li的駛出端點時，為保證無人機有足夠電量轉移至目標作業路徑Lj，需滿足

2 求解方法

帶續航約束的無人機全覆蓋路徑規劃問題總體求解思路如下：鑒于掃描線的方向角和作業路徑次序一體化尋優非常復雜，采用簡化的分步優化策略，即先對方向角進行優化，在得到的優化的方向角基礎上利用掃描線法獲得田塊的作業路徑，然后給出改進的蟻群算法對作業路徑的執行次序進行尋優。為了處理返航點的問題，在改進的蟻群算法中給出無人機返航時機判斷機制和返航點計算方法、距離矩陣動態更新機制以及滾動權值加權和信息素更新機制。

2. 1 掃描線方向角優化

采用掃描線方法確定無人機的作業路徑時，對于同一塊作業區域，不同方向角的掃描線生成的作業路徑數量也不同。一般來說，作業路徑的數量決定了轉移作業路徑的長度，作業路徑數量越多，則對應的轉移路徑長度越長。本文以作業路徑的數量作為優化目標，采用步進旋轉法［18］對方向角進行優化，采用試驗方法確定合適的步進角度。

2. 2 改進的蟻群算法

蟻群算法是為解決TSP 問題而提出的一種模擬螞蟻覓食行為的模擬優化算法。如第1 節所述，帶續航約束的無人機全覆蓋路徑規劃問題是一類特殊的TSP 問題，改進的蟻群算法需要解決以下關鍵問題：① 無人機返航時機判斷和返航點計算；② 作業路徑節點拓撲結構變化的處理；③ 單機多架次作業的信息素更新機制。

2.2.1 續航約束處理

無人機在大田塊作業過程中需多次返回補給點進行電量或物料補給，如第1 節所述無人機作業路徑包括作業路徑和轉移路徑，在轉移作業路徑上不執行作業任務，若無人機在轉移路徑上返航，則會增加無效能耗，因此應將返航點限制在作業路徑上。令作業路徑Li駛入端的剩余電量表示為，則在螞蟻選擇作業路徑Li之后，分2 種情況討論。

1）第1 種情況

圖3 返航點不是作業路徑端點Fig.3 Return point is not endpoint of operation path

2）第2 種情況

圖4 返航點是作業路徑端點Fig.4 Return point is endpoint of operation path

按照以上方法，每個螞蟻遍歷完所有作業路徑后都可得到各自的返航點集合。需要說明，無人機返回到補給點后，電池電量重新初始化。

2.2.2 改進的距離矩陣

如2.2.1 節所述，受續航約束限制，無人機必然會在某些作業路徑上返回補給點P0進行電量補給，假設作業路徑Li存在返航點，則無人機從返航至P0后，將劃分成已作業和未作業2 個部分的路徑，即和，其 中Lvisited={L1，visited，L2，visited，…，Li，visited}表 示 已 遍 歷 的 作 業 路徑集合； Lunvisited={L1，unvisited，L2，unvisited，…，Li，unvisited}表示未遍歷的作業路徑集合。顯然，增加了作業路徑數量，改變了作業路徑端點的拓撲結構。為了解決此問題，設計2 種類型的距離矩陣，即全局距離矩陣和局部距離矩陣。全局距離矩陣存儲所有作業路徑端點間的距離，在優化過程中不會改變；局部距離矩陣存儲螞蟻路徑上所有路徑端點間的距離，在優化過程中每產生一個返航點都需要更新一次。需要說明，每只螞蟻在生命周期內只維護一個屬于自己的局部距離矩陣。如圖5 所示，局部距離矩陣更新時，首先需要用返航點的坐標替換掉已遍歷過的作業路徑端點的坐標，然后重新計算Lunvisited中所有作業路徑端點與之間的距離。

圖5 局部距離矩陣更新示意圖Fig.5 Schematic of local distance matrix update

2.2.3 改進的信息素更新機制

受續航約束限制，蟻群中每只螞蟻在遍歷完所有作業路徑端點后都會生成若干返航點，返航點將螞蟻路線分割成若干相互獨立的部分，返航點的位置取決于該返航點與前一個返航點之間的局部路線。因此，在計算局部路線上的信息素時，既要考慮螞蟻總路線上的轉移路徑長度（即全局目標），也要突出螞蟻局部路線上的轉移路徑長度（即局部目標）。傳統的信息素更新機制均勻地利用螞蟻各段路徑長度計算信息素增量，沒有對不同的局部路線做出針對性評價。提出滾動權值加權和方法，在計算局部路線上的信息素時，增大局部路線的轉移路徑長度的比重，實現對局部路線的個性化評價。第t+1 次迭代后路徑{i，j}上的信息素τij(t+1)的更新公式如式（14）所示：

式中：τij(t)為第t次迭代后路徑{i，j}上的信息素；為第t 次迭代中蟻群中第k 只螞蟻在路徑{i，j}上釋放的信息素；m 為螞蟻數量；ρ 為信息素衰減系數(0 ＜ρ ＜1)；Q 為信息素常量；為第k只螞蟻路線上第b 個返航點和第b-1 個返航點之間局部路線上轉移路徑長度；Bk為第k 只螞蟻的返航點數量；ωb為的 權 重；K 為＞1 的 常 數，設置為5。

改進的蟻群算法流程如圖6 所示。作業路徑之間的轉移路徑是根據轉移概率確定的，作業路徑端點之間的轉移概率可根據端點之間信息素和距離計算。然而當存在返航點時，不同的螞蟻產生的返航點的數量和位置并不相同，因此一只螞蟻在返航點與作業路徑端點之間或返航點與返航點之間留下的信息素對其他螞蟻并沒有參考價值，此時只根據返航點與作業路徑端點之間距離或返航點與返航點之間距離計算轉移概率即可。轉移概率計算如式（17）所示：

圖6 改進蟻群算法流程圖Fig.6 Improved ant colony algorithm flow chart

式中：δ 為信息素啟發因子；β 為期望度啟發因子；unvisitedk表示螞蟻k 可達節點集合；τij(t)和ηij(t)分別為第t 次迭代路徑{i，j}上的信息素數值和螞蟻k 路線上總路徑長度的倒數；如果i 或j都不是返航點，α 取設定值，否則α 取值為0。

3 仿真實驗與分析

為了驗證提出的算法在求解無人機全覆蓋路徑規劃問題上的可行性和有效性，以植保無人機作業為例，從實際農田采集2 個作業區域的數據作為算例進行仿真驗證，其中算例1 由3 個較規則田塊組成，算例2 由3 個不規則田塊組成，各作業區域基本屬性如表1 所示。同時將提出的算法與基本蟻群算法（ACO）、文獻［16］中采用的貪婪算法（Greedy）進行對比分析。需要說明，基本蟻群算法、貪婪算法分別與文獻［16］中斷點續作（GBC）和重排續作（GNO）2 種續航方式組合出4 種對比算法：ACO-GBC、ACO-GNO、Greedy-GBC 和Greedy-GNO。

表1 作業區域基本屬性Table 1 Basic properties of operation area

3. 1 步進角實驗

為了確定合適的航向角優化的步進角度，本文從算例2 中選擇一個形狀復雜的作業區域作為測試地形，測試的步進角度為0.1°（含）～90°之間所有整數值，共91 個數值，測試結果如圖7 所示。由圖7 可見，總計有［0.1， 1， 2， 3， 5， 6， 9， 10，15， 18， 30， 45， 90］（°）等13 個步進角度獲得最少的路徑節點數量；步進角度越小，獲得最優步進角的概率越高，但是耗時更長。為了兼顧有效性和計算效率，仿真實驗設置步進角度設為1°（π/180 rad）。

圖7 步進角度實驗結果Fig.7 Step angle experiment results

3. 2 路徑規劃算法實驗

路徑規劃算法的運行環境為Windows10，Intel（R）Core（TM） i7-9750H CPU @2.60 GHz，編程環境為MATLAB2019b。蟻群算法的參數設置如下：種群規模N=100；最大迭代次數Max_iter=200；信息素啟發因子α=1；期望度啟發因子β=5；信息素衰減因子ρ=0.2；信息素常量Q=20；植保無人機的作業幅寬ω=3 m。

植保無人機的續航能力與電池容量和載重有關，為了驗證不同續航里程對算法的影響，本文設置1 000、1 500、2 000 m 3 種不同的續航里程進行對比實驗。同時，為了驗證航向角優化的效果，每組實驗都分成優化方向角和未優化方向角兩種情況，其中未優化方向角情況作業路徑均與坐標系x 軸平行。需要說明，方向角一旦確定以后，路徑節點坐標和作業路徑總長度即為定值，此時優化目標為最小化轉移作業路徑長度。各算法獲得最優路徑統計結果如表2 所示，受篇幅所限，圖8 中僅列出本文算法及對比算法在1 000 m 續航里程下獲得的2 個算例的最優作業路徑。

表2 不同算法獲得最優路徑結果Table 2 Test result of optimal path obtained by each algorithm

圖8 5 種算法在1 000 m 續航條件下獲得的最優作業路徑Fig.8 Optimal operation paths obtained by five algorithms with 1 000 m endurance constrain

由表2 可見，提出的算法與其他4 種算法相比，在所有優化方向角的算例中均取得最優結果，以下從掃描線方向角和續航里程2 個方面對算法的影響進行詳細分析。

1）掃描線方向角的影響

從表2 中5 種算法在優化方向角與未優化方向角的30 組對比數據中，有24 組優化方向角的路徑長度優于未優化方向角的路徑長度，總體有效率是80%。優化方向角并不總是有效的原因是本文方向角優化采用啟發式方法，優化目標是作業路徑的數量最少，而不是總的飛行路徑最短。需要指出，本文所提算法優化方向角的有效率是100%，這是因為本文算法是全局優化算法，能夠更好地發揮方向角優化的作用。

2）電池續航里程的影響

算例1 提出的算法在1 000、1 500、2 000 m續航里程上獲得最優轉移路徑長度分別為1 379.35、1 076.36、916.60 m，分 別 比 第2 名1 405.27 （ACO-GNO）、1 144.67 （ACOGNO）和1 072.30 m （ACO-GNO）縮短1.8%、6.0%和14.5%。與其他算法相比，提出的算法在作業路徑長度上的改進程度隨著電池續航里程減小而減小，原因是算例1 的作業區域較規則，求解比較簡單，難以體現本文算法全局搜索的優勢。

算例2 提出的算法在1 000、1 500、2 000 m續航里程上獲得最優路徑長度分別為3 171.84、1 930.43、1 585.09 m，分 別 比 第2 名3 834.09（ACO-GBC）、2 621.46 （ACO-GNO）和1 788.66 m（ACO-GBC）縮短17.2%、26.4%和11.4%。與其他算法相比，提出的算法在算例2 作業路徑長度上的改進程度總體上是隨著電池續航里程減小而增加的，原因是續航里程越小返航點數量越多，問題求解越復雜，提出的算法全局搜索的優勢體現越顯著。

綜上所述，提出的算法顯著優于采用其他續航策略的局部優化算法，尤其對于復雜作業地形的全覆蓋路徑規劃的優勢更加顯著。

4 結 論

為了解決帶續航約束的無人機全覆蓋路徑規劃問題，首先基于掃描線法建立了帶續航約束的無人機全覆蓋路徑規劃問題的數學模型，采用分步優化策略對掃描線方向角和作業路徑執行次序分別進行優化。針對帶續航約束作業路徑執行次序優化的特點對蟻群算法進行了適應性改進，包括：①給出無人機返航時機判斷機制和返航點計算方法，確定螞蟻路徑上的返航點位置；②給出包括全局距離矩陣和局部距離矩陣的雙距離矩陣架構，并給出局部距離矩陣的動態更新機制，用來處理返航點生成所導致的節點拓撲結構動態變化問題；③給出兼顧全局啟發信息和局部啟發信息的滾動權值加權和信息素更新機制，提高蟻群算法的求解能力。最后以植保無人機作業為例設計仿真實驗，結果表明本文算法在2 個算例上的求解結果均優于其他4 種對比算法，尤其在復雜地形的算例上本文算法的優勢更加顯著，證明了提出的算法的有效性。

本文研究問題屬單機單補給點帶續航約束路徑規劃問題，未來將進一步在實際無人機應用場景中，設置多個補給點和無人機以提高無人機作業效率，研究多機多補給點協同作業路徑規劃。