基于改進(jìn)ACO 的帶續(xù)航約束無(wú)人機(jī)全覆蓋作業(yè)路徑規(guī)劃

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

1.江蘇師范大學(xué) 電氣工程及自動(dòng)化學(xué)院，徐州 221000

2.江蘇蒲公英無(wú)人機(jī)有限公司，徐州 221000

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

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

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

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

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

1 問(wèn)題描述與建模

本文研究的無(wú)人機(jī)路徑規(guī)劃問(wèn)題為不規(guī)則地形全覆蓋路徑規(guī)劃問(wèn)題。無(wú)人機(jī)作業(yè)過(guò)程的飛行路徑可分為2 部分：一是作業(yè)路徑，即執(zhí)行作業(yè)任務(wù)（例如農(nóng)藥噴施）的飛行路徑；二是轉(zhuǎn)移路徑，即在作業(yè)路徑間進(jìn)行切換的飛行路徑?；趻呙杈€方法生成作業(yè)路徑，在此基礎(chǔ)上，重點(diǎn)研究帶續(xù)航約束的作業(yè)路徑執(zhí)行次序的優(yōu)化。

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

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

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

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

由此可見(jiàn)，一旦掃描線方向角α 確定，無(wú)人機(jī)作業(yè)路徑總長(zhǎng)度可由式（1）確定：

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

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

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

設(shè)計(jì)變量：

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

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

約束條件：

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

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

3）當(dāng)Pk為L(zhǎng)i的駛出端點(diǎn)時(shí)，為保證無(wú)人機(jī)有足夠電量轉(zhuǎn)移至目標(biāo)作業(yè)路徑Lj，需滿足

2 求解方法

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

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

采用掃描線方法確定無(wú)人機(jī)的作業(yè)路徑時(shí)，對(duì)于同一塊作業(yè)區(qū)域，不同方向角的掃描線生成的作業(yè)路徑數(shù)量也不同。一般來(lái)說(shuō)，作業(yè)路徑的數(shù)量決定了轉(zhuǎn)移作業(yè)路徑的長(zhǎng)度，作業(yè)路徑數(shù)量越多，則對(duì)應(yīng)的轉(zhuǎn)移路徑長(zhǎng)度越長(zhǎng)。本文以作業(yè)路徑的數(shù)量作為優(yōu)化目標(biāo)，采用步進(jìn)旋轉(zhuǎn)法［18］對(duì)方向角進(jìn)行優(yōu)化，采用試驗(yàn)方法確定合適的步進(jìn)角度。

2. 2 改進(jìn)的蟻群算法

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

2.2.1 續(xù)航約束處理

無(wú)人機(jī)在大田塊作業(yè)過(guò)程中需多次返回補(bǔ)給點(diǎn)進(jìn)行電量或物料補(bǔ)給，如第1 節(jié)所述無(wú)人機(jī)作業(yè)路徑包括作業(yè)路徑和轉(zhuǎn)移路徑，在轉(zhuǎn)移作業(yè)路徑上不執(zhí)行作業(yè)任務(wù)，若無(wú)人機(jī)在轉(zhuǎn)移路徑上返航，則會(huì)增加無(wú)效能耗，因此應(yīng)將返航點(diǎn)限制在作業(yè)路徑上。令作業(yè)路徑Li駛?cè)攵说氖Ｓ嚯娏勘硎緸?，則在螞蟻選擇作業(yè)路徑Li之后，分2 種情況討論。

1）第1 種情況

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

2）第2 種情況

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

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

2.2.2 改進(jìn)的距離矩陣

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

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

2.2.3 改進(jìn)的信息素更新機(jī)制

受續(xù)航約束限制，蟻群中每只螞蟻在遍歷完所有作業(yè)路徑端點(diǎn)后都會(huì)生成若干返航點(diǎn)，返航點(diǎn)將螞蟻路線分割成若干相互獨(dú)立的部分，返航點(diǎn)的位置取決于該返航點(diǎn)與前一個(gè)返航點(diǎn)之間的局部路線。因此，在計(jì)算局部路線上的信息素時(shí)，既要考慮螞蟻總路線上的轉(zhuǎn)移路徑長(zhǎng)度（即全局目標(biāo)），也要突出螞蟻局部路線上的轉(zhuǎn)移路徑長(zhǎng)度（即局部目標(biāo)）。傳統(tǒng)的信息素更新機(jī)制均勻地利用螞蟻各段路徑長(zhǎng)度計(jì)算信息素增量，沒(méi)有對(duì)不同的局部路線做出針對(duì)性評(píng)價(jià)。提出滾動(dòng)權(quán)值加權(quán)和方法，在計(jì)算局部路線上的信息素時(shí)，增大局部路線的轉(zhuǎn)移路徑長(zhǎng)度的比重，實(shí)現(xiàn)對(duì)局部路線的個(gè)性化評(píng)價(jià)。第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 個(gè)返航點(diǎn)和第b-1 個(gè)返航點(diǎn)之間局部路線上轉(zhuǎn)移路徑長(zhǎng)度；Bk為第k 只螞蟻的返航點(diǎn)數(shù)量；ωb為的 權(quán) 重；K 為＞1 的 常 數(shù)，設(shè)置為5。

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

圖6 改進(jìn)蟻群算法流程圖Fig.6 Improved ant colony algorithm flow chart

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

3 仿真實(shí)驗(yàn)與分析

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

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

3. 1 步進(jìn)角實(shí)驗(yàn)

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

圖7 步進(jìn)角度實(shí)驗(yàn)結(jié)果Fig.7 Step angle experiment results

3. 2 路徑規(guī)劃算法實(shí)驗(yàn)

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

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

表2 不同算法獲得最優(yōu)路徑結(jié)果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 可見(jiàn)，提出的算法與其他4 種算法相比，在所有優(yōu)化方向角的算例中均取得最優(yōu)結(jié)果，以下從掃描線方向角和續(xù)航里程2 個(gè)方面對(duì)算法的影響進(jìn)行詳細(xì)分析。

1）掃描線方向角的影響

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

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

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

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

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

4 結(jié) 論

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

本文研究問(wèn)題屬單機(jī)單補(bǔ)給點(diǎn)帶續(xù)航約束路徑規(guī)劃問(wèn)題，未來(lái)將進(jìn)一步在實(shí)際無(wú)人機(jī)應(yīng)用場(chǎng)景中，設(shè)置多個(gè)補(bǔ)給點(diǎn)和無(wú)人機(jī)以提高無(wú)人機(jī)作業(yè)效率，研究多機(jī)多補(bǔ)給點(diǎn)協(xié)同作業(yè)路徑規(guī)劃。