海上無人機多機協同巡檢航跡規劃方法

李 果，秦筱楲，郝貴斌，蔡 超，李鵬展

（1.航天科工海鷹集團有限公司，北京 100070；2.華中科技大學人工智能與自動化學院，武漢 430030）

0 引言

隨著無人機（unmanned aerial vehicle，UAV）技術的不斷進步，無人機已被廣泛應用于海洋資源管理、海上安全、環境監測、目標詳查等領域[1]。海上無人機的主要作業任務是對在指定海域上空抵近需要詳查的目標點進行巡檢。在無人機巡檢過程中，航跡規劃是無人機海上巡檢的重要組成部分，需要根據無人機的性能參數設定起飛后的巡航路線，確保無人機在可控狀態下能夠完成指定海域的巡檢作業[2]?？紤]到海面環境復雜，當存在多個待詳查目標時，無人機要根據已知的或由本身載荷得到的各目標位置，考慮能耗、載荷有效范圍等條件約束，確定至少需要配備的無人機數量，并給出較優的無人機調度策略，規劃出每一架無人機的航線，確保以最優的代價協同作業完成巡檢任務[3-5]。

本文通過對海上無人機協同規劃整體流程進行研究分析，針對靜態、動態2 種不同的場景，通過構建靜態問題和動態問題模型，分別進行多無人機航跡協同規劃，并給出多無人機航跡協同規劃的最優方案和仿真結果。

1 海上無人機協同規劃流程

海上無人機協同航跡規劃問題本質上是具有約束條件的最優化求解，旨在解決多架無人機在目標區域內從起始點出發，以盡可能小的代價規劃出盡可能優的航跡組的問題[6-8]。采用基于圖的建模方法是無人機對目標區域進行搜索活動是否合理有效的前提[9]：首先，根據指定作業海域柵格圖，采用基于圖的建模方法對海域地圖進行分區，并對每個分區采用柵格化的網絡圖進行表達，對不確定的目標區域環境信息進行合理的描述，有利于規劃不同類型無人機的作業軌跡；其次，假設在進行搜索行動時，無人機具有自主避障的功能，而且可以及時獲取其他無人機的實時信息，針對每個分區，根據無人機的類型、其他無人機信息及無人機機場分布情況，求解出最佳的巡航方案。

海上無人機巡檢協同規劃分為靜態場景規劃和動態場景規劃，其整體規劃流程如圖1 所示。從圖1可以看出：靜態場景下，無人機巡航軌跡規劃的目標是為每架無人機劃分作業區域、生成作業路徑，使得整個巡檢作業的航跡長度代價與作業時間代價最??；而動態場景下，無人機巡航軌跡規劃需針對不同的突發狀況建立對應的場景模型和求解算法，評估不同突發場景下最佳的動態調整方案。動態問題求解后，會將求解的方案重新返回到靜態問題模型中，無人機按照新的靜態航線飛行，再次遇到動態問題則重復上述步驟，實現動態調整，保證無人機的正常作業。

圖1 海上無人機巡檢協同規劃整體流程圖Fig.1 Overall flowchart for collaborative planning and inspection of UAVs

2 基于分支定界法的靜態場景無人機巡檢航跡規劃

海上無人機靜態場景規劃是指在不考慮海面上的突發狀況情況下，按照指定的作業海域，根據無人機的最大單位巡檢范圍和機場位置等信息，規劃出不同海域的無人機巡檢路徑，需在無人機起飛前規劃出巡檢航跡[10]。

考慮到無人機能耗的關系，每個海域往往不能由1 架無人機完成所有巡檢，此時需要不同的無人機在不同的子區合力協同完成該海域的巡檢任務。每一架無人機在各自巡檢子區內按照S型飛行路徑進行作業巡檢，在給定的海域柵格圖上需要確定的是每一架無人機的起始巡航位置、轉彎機動位置及最后的返航位置（圖2）。

圖2 靜態場景航軌規劃示意圖Fig.2 Schematic diagram of path planning in static condition

針對靜態場景規劃建立靜態問題模型，通過輸入無人機數量、屬性（飛行速度、能耗、最大飛行里程、最大起飛質量、巡檢半徑）、機場位置（坐標）、機場各類型無人機數量、機場容量、海域柵格圖、海域最低覆蓋率、巡檢時間窗要求（有效巡檢時間）等參數，為每架無人機劃分作業區域，然后生成作業路徑，使得整個巡檢作業的航跡長度代價與作業時間代價最小，即最小化M。

靜態場景航路規劃方案的目標函數為：

其中，約束條件如下：

式（1）～（6）中：M為無人機的整體航路長度代價和協同巡檢的有效時間的加權和；L為n架無人機的整體航路長度代價；te為n架無人機協同巡檢的有效時間；s為每架無人機巡檢區域的面積；vi,max為無人機的最大巡航速度；pi為每架無人機的巡檢覆蓋率；Ri為無人機的最大航程；wi為每架無人機載荷傳感器的探測范圍；ti為第i架無人機的傳感器有效工作時間；k1、k2分別為航路長度代價和時間代價的加權系數，且滿足k1+k2=1的條件。

靜態場景下的無人機巡航路徑規劃隸屬全局路徑規劃，既需考慮約束條件（如飛機性能限制、任務約束等），又需考慮性能指標（如按照規定時間到達、飛行時間最短、任務效能最高等）。本文采用分支定界算法（branch and bound method）框架[11]（圖3），通過將靜態場下的全覆蓋問題進行混合整數規劃模型建模，并使用cplex、gurobi等求解器最小化目標函數（式1），從而進行規劃問題的最優求解。

圖3 分支定界算法流程圖Fig.3 Flowchart of branch and bound method

運用上述方法進行海上無人機巡檢系統仿真，設定靜態場景下設計規劃的無人機規模為50架次，海域的最低覆蓋率為90%，整體模型的求解時間不超過30 s，則可以在20 s 內給出可行的多無人機協調巡檢航跡規劃方案。

3 基于啟發式算法的動態場景無人機巡檢航跡規劃

海上無人機動態場景規劃是指無人機在巡檢過程中，遇到海面上的突發狀況，例如：由于海面上空的天氣因素影響，使得設定的飛行路徑的部分軌跡和極端天氣發生區域重合，為減少風險，此時需要根據現場情況局部動態調整原有飛行路徑，避免無人機直接穿越該區域；在海面巡檢過程中，發現目標并需要對目標進行連續跟監，或者遇到其他海上環境變化時，同樣需要動態調整無人機的局部路徑，決策無人機飛行路徑，并滿足指定海域的巡檢要求[12-13]。因此，面向動態場景的航跡重規劃問題需著重考慮2 個方面：一是根據實時環境信息進行避障規劃，避障結束后能返回預設航跡繼續飛行；二是出現突發障礙物時，無人機能夠綜合當前位置和環境信息，重新規劃航跡以規避障礙物[14]。

動態場景無人機的路徑規劃主要是對時效性要求比較高，要求算法模型能夠快速給出1 個可行方案。在動態場景下，無人機先按照靜態場景下事先規劃好的路徑進行巡檢，遇到突發情況，則會根據突發事件的場景觸發不同的動態問題模型。每個模型都需設計獨有的目標函數，用于評估不同場景下最佳的動態調整方案。

對動態場景無人機巡航軌跡規劃建立動態問題模型，主要針對氣象變化、連續跟蹤、海域變化等突發場景。

3.1 氣象變化場景

氣象變化場景是指無人機在按照靜態場景規劃的航線巡檢過程中，突發遇到極端惡劣天氣情況。此時無人機會自動獲取極端天氣的區域及此時所有無人機的飛行位置，及時調整事先規劃好的靜態航跡，既要避開極端天氣區域，又要完成巡檢作業。

不考慮氣象變化的靜態場景規劃的航線巡檢方案如圖4所示。此時，假定在靜態場景下，該海域最佳的無人機數量為2架，使用藍色和綠色無人機各1架，每架無人機分別從2 個機場起飛后，各自按照設定好的S型軌跡完成巡檢，最后返回各自的機場。

圖4 氣象變化場景下動態調整前的無人機航線圖Fig.4 Planning path of UAVs before dynamic adjustments under changing meteorological conditions

當無人機飛行過程中遇到雷暴等極端天氣時，觸發整體流程圖（圖1）中動態場景里的氣象變化場景模型。該場景根據當前無人機的航線任務和各自的位置信息，通過引入發生極端天氣海域柵格圖、靜態規劃下的所有參數、所有無人機位置信息（包含機場內的無人機和正在執行任務的無人機）、無人機的電量信息、無人機的任務信息等約束條件，建立氣象變化場景問題模型進行動態調整，重新調整局部航跡。

為節約能耗，無人機的巡檢總時間越短越好。同時在天氣惡劣的情況下，考慮無人機的安全性，要求在外執行無人機的數量越少越好，所以氣象變化場景下的航路規劃的目標函數應設計為使得無人機在完成任務的基礎上巡檢時間最小且執行任務的無人機數量最少，即最小化Q：

式（7）中：Q為無人機的巡檢時間和執行任務的無人機數量的加權和；n為無人機數量；k1、k2分別為無人機數量和時間代價的加權系數，同樣需滿足k1+k2=1的條件。

針對動態場景下無人機的路徑規劃問題，可以利用構造啟發式/元啟發式等算法[15]、遺傳算法（Genetic Algorithm，GA）[16]、模擬退火算法（Simulated Annealing，SA）[17]、禁忌搜索算法（Tabu Search，TS）[18]、大領域搜索算法（Large Neighborhood Search，LNS）[19]等進行航跡規劃，但這些算法在規劃空間的離散化、規劃效率、約束條件處理和魯棒性等方面分別有不同的局限性。研究表明，快速擴展隨機樹（Rapidly-exploring Random Trees，RRT）算法是1 種比較有效的單次查詢快速路徑規劃算法[20]，并被成功應用于各類路徑規劃研究中。

如圖5 所示，基于RRT 的航跡規劃算法主要包括3個步驟：選擇采樣點、搜索新節點及擴展節點。

圖5 RRT算法當前節點擴展示意圖[20]Fig.5 Schematic diagram of node extension approach of RRT algorithm

本文在RRT算法基本框架下，以一定概率選擇目標點作為采樣點，來提高航跡規劃的速度和質量。同時，在節點擴展過程中，仿照SAS（Sparse A*Search）[21]算法節點的擴展方式，把約束條件和目標函數嵌入到搜索與求解過程中，規劃出氣象變化場景下滿足多種約束條件的最優航跡。具體啟發過程如下：沿著當前擴展點的方向，對稱地選擇最大轉彎角，根據最小擴展步長和最大擴展步長約束，形成1 個扇形區域（圖5），在這個扇形區域內選擇新的擴展點；新節點的產生首先按照一定的約束條件，把扇形區域劃分成許多網格，然后在所有格網中，若滿足某個格網中心與采樣點距離最近并且該格網中心與當前擴展點之間的航跡是可行的，則將該格網中心作為新的擴展點插入到搜索樹中，為減少搜索樹中節點數目，每次限定只產生1個新節點；最后直至擴展樹到達目標點，形成完整航跡數據集，再綜合考慮目標函數求解，最終獲得最優的航跡規劃結果。

假定巡檢區內存在雷暴區域，通過模型約束來進行數據集的預處理，再根據當前無人機的航線任務和各自的位置信息，利用啟發式算法進行問題求解，可將圖4動態調整為圖6的巡檢航跡規劃方案。

圖6 氣象變化場景下動態調整后的無人機航線圖Fig.6 Planning path of dynamically adjusted UAVsunder changing meteorological condition

圖6 顯示：藍色航線的無人機飛到雷暴邊界后返回機場，終止巡航任務；綠色無人機飛到第5個航點后進入原本藍色無人機的巡航軌跡進行巡航，到達雷暴邊界后返回機場。下方機場需再安排1架無人機從機場出發，完成綠色無人機的剩余可巡航路徑。

運用啟發式算法進行海上無人機巡檢系統仿真，設定規劃的無人機規模為50架次，海域最低覆蓋率為80%，整體模型求解時間不超過30 s，則可以在30 s內給出該場景下可行的無人機巡檢航跡規劃方案。

3.2 連續跟監場景

連續跟監場景是指無人機在靜態巡檢作業下，突然發現需要跟蹤的艦船目標，利用機載設備獲取艦船的航行速度和航行方向，并臨機調整事先規劃好的靜態航跡，確保對艦船目標的連續跟監[22]。

無需連續跟監時，2 架無人機按照之前的靜態規劃方案的路徑圖，各自按照設定軌跡完成巡檢（圖5）。若藍色無人機在某時刻發現需要跟蹤的艦船目標，并獲得了該目標的航行速度和航行方向（圖7），此時觸發整體流程圖（圖1）中動態場景里的連續跟監場景模型。該場景根據當前無人機的航線任務和各自的位置信息，通過引入連續跟監場景下的海域柵格圖、目標位置信息（坐標）及數量、目標航線、航向、速度、所有無人機信息（坐標）、電量、跟蹤時間和目標優先級等約束條件，建立持續跟監場景問題模型，對局部航跡進行動態調整。

圖7 連續跟監場景下動態調整前無人機航線圖Fig.7 Planning path of UAVs before dynamic adjustments under continuous tracking and monitoring condition

考慮到在無人機能耗及巡檢覆蓋率的約束下，最大化艦船目標的跟蹤時長的情況下，為保證對艦船目標的持續跟監，該場景下的目標函數應設計為力求對艦船目標的跟蹤時長最大化，即最大化W：

式（8）中：W為無人機的跟蹤時長。

同理，該場景下仍以RRT 算法基本框架為基礎，把約束條件和目標函數嵌入其搜索與求解過程，規劃出連續跟監場景下滿足多種約束條件的最優航跡。

假定在首次發現艦船目標后，根據當前無人機的航線任務和各自的位置信息，利用啟發式算法進行解算，可將圖7動態調整為圖8的巡檢航跡規劃方案。

圖8 連續跟監場景下動態調整后無人機航線圖Fig.8 Planning path of dynamically adjusted UAVs under continuous tracking and monitoring condition

圖8 顯示，此時的巡檢方案為藍色無人機進行跟蹤，到達綠色無人機航線后直接返回最近機場，由綠色無人機完成后面的跟蹤任務。在藍色無人機開始跟蹤時，機場需要另外派出紫色無人機完成藍色和綠色無人機的靜態巡檢航線，完成后返回最近機場。

運用啟發式算法進行海上無人機巡檢系統仿真，設定規劃的無人機規模為50架次，海域的最低覆蓋率為80%，艦船目標有效跟蹤率不低于95%，整體模型的求解時間不超過30 s，則可以在30 s 內給出該場景下可行的無人機巡檢航跡規劃方案。

3.3 海域變化場景

海域變化場景是指無人機在靜態巡檢作業下，原本設定的航線區域部分被臨時封鎖，無法正常進入封鎖海域，原本已規劃好的巡檢航線中涉及封鎖海域的均不可通行，需重新動態調整巡檢路線，完成指定的巡檢任務。

無海域封鎖時2架無人機按照之前的靜態規劃方案的路徑圖，各自按照設定軌跡完成巡檢（圖5）。若某時刻臨時管控封鎖局部海域，此時無人機不允許進入該海域（圖9），觸發整體流程圖（圖1）中動態場景里的海域變化場景模型。根據當前無人機的航線任務和各自的位置信息，通過引入海域變化場景下的海域柵格圖、封鎖海域位置信息（坐標）及數量、所有無人機信息（坐標）、電量等約束條件，建立海域變化場景模型，對巡檢航跡進行局部化調整。

在考慮無人機能耗基礎上，重點考慮巡檢覆蓋率的問題，在保證巡檢覆蓋率的前提之下，實現巡檢時間最小，即最小化R：

式（9）中：R為無人機巡檢覆蓋率和無人機的有效巡檢時間的加權和；p為無人機巡檢覆蓋率；te為無人機巡檢有效時間；k1、k2分別為無人機巡檢覆蓋率和巡檢有效時間的加權系數，滿足k1+k2=1 的條件，同時要求巡檢覆蓋率的優先級高于巡檢時間優先級。

同理，該場景下仍以RRT 算法基本框架為基礎，把約束條件和目標函數嵌入其搜索與求解過程中，規劃出連續跟監場景下滿足多種約束條件的最優航跡。

假定航線區內臨時封鎖局部海域，根據當前無人機的航線任務和各自的位置信息，同樣采用啟發式算法進行快速求解，可將圖9動態調整為圖10的航跡巡檢規劃方案。

圖10 海域變化場景下動態調整后無人機規劃示意圖Fig.10 Planning path of dynamically adjusted UAVs under changing sea surface area condition

從圖10可以看出，此時藍色無人機的返航點被封鎖區域覆蓋，藍色無人機則在到達封鎖邊界時，直接返回機場，同時不需要額外安排其他無人機繼續執行其原本航線，因為剩余航線均已被封鎖；綠色無人機根據原本航線得到2 個與封鎖邊界相交的點，用這2點作為綠色無人機新的航點，重新構建航線，再依次完成巡航任務。

運用啟發式算法進行海上無人機巡檢系統仿真，設定規劃的無人機規模為50架次，海域的最低覆蓋率為80%，整體模型的求解時間不超過60 s，則可以在60 s 內給出該場景下可行的無人機巡檢航跡規劃方案。

4 結論

海上無人機協同巡檢可以顯著提高海洋巡檢的作業效率和安全性，通過深入了解無人機海上巡檢的航跡規劃、目標函數設計、算法流程等技術細節，有助于提高任務的效率和性能。本文主要論述了海上無人機多機協同巡檢航跡規劃方法，區分靜態和動態兩大場景，分析了海上無人機協同規劃整體流程，并分別介紹了多無人機航跡協同規劃方法。其中：靜態場景下主要采用分支定界法建立全覆蓋問題的混合整數規劃模型；動態場景下重點討論了氣象變化、連續跟監、海域變化3 種突發場景下的無人機巡航軌跡規劃問題，針對不同情況設計不同的目標函數，采用啟發式規劃算法動態調整局部巡檢航跡，確保完成整個巡檢任務。未來，隨著無人機在海洋保護、資源管理和安全維護等領域發揮越來越重要的作用，無人機技術也將日臻完善。