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

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

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

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

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

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

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

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

1 問題描述與建模

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

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

圖1 作業(yè)路徑節(jié)點間轉移示意圖Fig.1 Schematic of transfer between nodes of operation path

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

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

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

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

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

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

設計變量：

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

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

約束條件：

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

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

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

2 求解方法

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

2. 1 掃描線方向角優(yōu)化

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

2. 2 改進的蟻群算法

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

2.2.1 續(xù)航約束處理

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

1）第1 種情況

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

2）第2 種情況

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

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

2.2.2 改進的距離矩陣

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

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

2.2.3 改進的信息素更新機制

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

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

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

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

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

3 仿真實驗與分析

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

表1 作業(yè)區(qū)域基本屬性Table 1 Basic properties of operation area

3. 1 步進角實驗

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

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

3. 2 路徑規(guī)劃算法實驗

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

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

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

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

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

1）掃描線方向角的影響

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

2）電池續(xù)航里程的影響

算例1 提出的算法在1 000、1 500、2 000 m續(xù)航里程上獲得最優(yōu)轉移路徑長度分別為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%。與其他算法相比，提出的算法在作業(yè)路徑長度上的改進程度隨著電池續(xù)航里程減小而減小，原因是算例1 的作業(yè)區(qū)域較規(guī)則，求解比較簡單，難以體現(xiàn)本文算法全局搜索的優(yōu)勢。

算例2 提出的算法在1 000、1 500、2 000 m續(xù)航里程上獲得最優(yōu)路徑長度分別為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 作業(yè)路徑長度上的改進程度總體上是隨著電池續(xù)航里程減小而增加的，原因是續(xù)航里程越小返航點數(shù)量越多，問題求解越復雜，提出的算法全局搜索的優(yōu)勢體現(xiàn)越顯著。

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

4 結 論

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

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