對運動船舶的多無人機協同查證路徑規劃方法

趙興剛， 趙翌僮， 康元基， 陳子勻， 楊雙玲

(中國人民解放軍66136部隊， 北京 100041)

隨著經濟全球化不斷發展，船舶艘次和噸位不斷增加，港口吞吐量日益增大，船只事故與非法沖闖行為時有發生，對艦船海事監管提出了更高要求。當前我國海事監管平臺設備主要有海巡船、海事直升機、船舶交管中心、自動查證系統和視頻監控等，然而上述平臺設備存在受海況影響大、信息不直觀、對未安裝或故意關閉識別設備船舶存在監控盲區等缺陷[1-2]。近年來，無人機(unmanned aerial vehicle，UAV)在感知、定位、導航和通信等技術方面取得突破性進展，可對船只進行調查取證，盡早發現事故或非法船只，作為傳統海事監管設備重要補充，為海上監管部門提供先進技術支持[3]。

近年來，不少學者在海事監管領域采用啟發式算法開展無人機路徑規劃應用探索，分析無人機應用于海上立體監管的可行性[4-5]。文獻[6]通過聚類處理獲取重點區域巡航范圍，并基于巡航范圍的形狀確定無人機最佳巡航方向，設計混合整數線性優化算法探究無人機在各重點巡航區域間巡航的耗時最短路徑。文獻[7]基于多旅行商問題，設計了一種均衡單個旅行商路徑長度的集中式搜索策略，實現了無人機集群對搜索地圖的快速全面覆蓋和每架無人機的搜索路徑均衡。但是文獻[6-7]采用區域覆蓋的方式，利用無人機對關注區域進行監控，沒有給出針對具體目標的搜索方法。文獻[8]提出了一種聚類算法和遺傳算法進行分布組合的優化算法，提高了對大規模多無人機協同搜索多目標問題的計算效率并改善了規劃結果。文獻[9]考慮多無人機的任務執行能力、資源和所受威脅等約束，采用多旅行商問題建立了無人機協同任務規劃問題的組合優化模型，并采用模擬退火算法對模型進行修正求解。文獻[10]建立飛行高度時變的傳感器模型和海域環境概率圖模型，并設計新的搜索圖更新方案，提出了改進的多蜂群算法，實現了多無人機在未知海域中對目標的自適應搜索路徑規劃。文獻[11]提出了基于K-means++聚類與改進型粒子群優化(particle swarm optimization，PSO)的求解算法完成多無人機多目標路徑規劃，能夠使無人機避開障礙物并根據自身的速度規劃出合理的飛行路徑。

現有研究通過將啟發式算法引入無人機協同偵察任務中，實現了對多固定目標的定點偵查[8-11]，然而，在實際運用中，對于入港船舶監管，仍存在兩個問題：①進港船舶時刻處于運動過程中，對其跟蹤識別具有高度時間敏感性，基于區域覆蓋監管與固定目標位置的方法難以給出對運動船舶的具體查證路線；②港口吞吐量較大，無人機資源相對緊張且對運算實時性要求高，導致無人機對進港船舶監管中的實際運用效果較差。

為此，針對大量移動目標，設計一種基于改進模擬退火算法的多無人機協作跟蹤查證的路徑規劃方法，對入港船舶的運動、無人機對船舶的查證和無人機在船舶間的運動過程進行建模描述；然后，改進模擬退火算法，使其適應于無人機數量未定與運動目標位置隨時變化的情況，通過迭代遞推的方式，得到所需最少無人機數量和對應的運動船舶查證路徑規劃方案；最后利用仿真實驗驗證了算法的可行性和有效性。

1 無人機查證問題描述

無人機可利用自身攜帶的電視攝像機、前視紅外儀和合成孔徑雷達等設備對入港船舶進行盤旋查證，操作員根據回傳圖像可確定入港船只國籍、舷號、船型和物資類型等信息，并實時與船舶交管中心掌握的船舶登記信息比對，判斷船名與外觀是否一致，有無涂改、偽造船名、不良記錄或運載非法物資等情況，對問題船只進行初步篩選，為海事執法部門下步處置提供情報支撐。

在實際查證過程中，需保證無人機續航時間大于查證時間，不考慮返港補給情況，單架無人機升空后可擔負多艘船只的查證任務。在查證任務開始時，無人機通常按照情報提供位置信息，位首艘船只計劃查證位置盤旋等待，發現船只后降低高度，對其繞飛數周進行多角度攝像取證，完成查證后飛離前往下一艘查證船只，直至所有船只查證完畢結束。但由于各船只保持運動狀態且速度不一，則任意時刻，兩艘船間的位置是動態變化的，導致無人機在兩艘船舶間飛行時間受查證順序影響，當涉及多架無人機協同查證時，船只查證任務的分配也將影響查證總時間。

(1)

2 基于改進模擬退火的無人機查證路 徑生成算法

2.1 無人機查證位置計算

由于船只處于運動狀態，需求解兩項查證任務之間的時間間隔，再根據船只速度確定無人機與待查證船舶相遇位置。具體求解過程可分為以下步驟。

步驟1假設t0時刻商船s1和s2的位置分別為(xs1,ys1)和(xs2,ys2)，一架無人機計劃先后對s1和s2進行查證。在t0時刻無人機首先開始查證商船s1，持續tl分鐘，在此期間隨商船s1原航向繞飛查證。

步驟2t0+tl時刻無人機結束對商船s1查證，開始飛向下一待查證商船s2，無人機及商船位置如圖1(a)所示。在t0+tl時刻，假設商船s1和s2的位置分別為(x′s1,y′s1)和(x′s2,y′s2)。由于商船起始位置已知，航向、航速一定，那么可以計算得方程組為

(2)

步驟3假設無人機以巡航速度vuav沿最短路徑，經過Δt時間后(Δt為時間間隔，其長度為無人機結束對s1商船查證時刻到開始對商船s2查證時刻的差)，在t0+tl+Δt時刻于(x″s2,y″s2)處與以速度v2航行的商船s2相遇并開始查證，無人機及商船位置如圖1(b)所示。(x″s2,y″s2)在商船s2的航線上可得方程組為

(3)

求解方程組可得

(4)

(5)

圖1 無人機在兩艘船間運動過程Fig.1 Movement process of the UAV between two moving ships

2.2 無人機查證序列路徑及耗時計算

表示無人機；S為無人機查證商船的序列； 為無人機i的商船查證序列中的第k艘商船圖2 無人機識別運動商船序列Fig.2 UAV verification sequence for moving ships

(6)

(7)

(8)

2.3 基于模擬退火的無人機運動路徑生成算法執行步驟

模擬退火算法在搜索過程中具有突跳的能力，可以有效避免搜索陷入局部最優解，基于此，利用模擬退火的思想生成并迭代優化無人機路徑，以確定所需最少無人機數量并降低查證路線耗時，具體流程如下。

Step 1給定初始無人機數量n0，初始溫度T0和終止溫度Tf。

Step 2隨機生成長度等于待查證船只數的序列，并根據無人機數量n0，隨機選擇序列位置，通過插入0值對序列進行切分，得到每架無人機查證商船序列Pi0。根據2.2給出方法，計算得到優化目標初始值maxτ(Pi0)，迭代指標k=0，Tk=T0。

Step 3等概率隨機選用交換、位移和倒置算子生成新查證序列P′i，計算目標值增量Δf=maxτ(P′i)-maxτ(Pi0)。

Step 5若達到熱平衡[內循環次數大于n(Tk)]轉Step 6；否則轉Step 3。

Step 6降低Tk，k=k+1，若Tk

根據上述計算步驟，算法流程圖如圖3所示。

圖3 基于模擬退火的多無人機協同查證路徑生成算法Fig.3 Multi-UAV collaborative path planning method for moving ships based on simulated annealing

3 仿真分析

使用MATLAB進行仿真實驗以驗證算法有效性，仿真場景如下：選取某日上午6：00擬進某港的船舶情況如圖4所示，該港外航線位于以港口為圓心，方位在與正北方向順時針夾角20°～70°的扇形區域，設港口為原點，監管處置線端點坐標分別為：C點坐標(170.99,62.23)，D點坐標(62.23，170.99)。

入港商船運動狀態數據如表1所示，航向均指向港口，現利用算法確定需派遣進行查證的無人機最少數量及查證路徑。

圖4 初始仿真場景想定Fig.4 Initial simulation scenario

表1 入港商船運動狀態數據

由于各船舶運動方向不變，根據船舶速度、方向和CD線位置，可以計算得到各船舶達到CD線的時間。計算結果表明首艘到達CD線的為1號船，所需時間為8.41 h，即無人機查證總時間最大值t*=8.41 h(約504 min)。

設無人機飛行速度為120 km/h，查證時飛行速度與待查證船舶航速一致，查證時間為10 min。

利用Intel(R) Core(TM) i5-10300H CPU，16.0 GB 內存的筆記本電腦使用MATLAB進行無人機查證路徑優化，計算共耗時396.74 s，結果表明，當無人機數量為3時，無人機最大路徑耗時計算結果達到收斂(圖5)，此時的無人機最大路徑耗時為470.1 min,小于t*=8.41 h=504.6 min，滿足條件，因而確定所需要的最少無人機數量為3架。

圖5 無人機最大路徑耗時與迭代次數間關系Fig.5 The relationship between the maximum UAV verification time and the number of iterations

3架無人機的飛行路線和對應完成的識別任務如圖6所示，標出了每一架無人機識別的商船序號，其中，紅色線段表示在商船識別過程中無人機飛過的軌跡，藍色線段表示無人機在識別完一艘商船后，到下一艘識別商船的飛行軌跡，所有的紅色線段與藍色線段相互連接，構成無人機在完成整個任務過程中的飛行路線。

表2～表4給出了3 架無人機具體完成的識別商船序列，以及識別序列中每一艘商船對應的識別開始位置、識別結束位置、識別開始時間和識別結束時間。這里的時間以某日6：00為時間起點，記為0 min。

4 結論

針對進港運動船舶如何合理分配無人機查證任務，對無人機路徑進行優化進而提高船舶查證效率的問題，基于模擬退火思想提出了一種面向運動目標的路徑規劃算法來對無人機查證路線進行優化求解。算法首先根據港口位置和航道情況，設置監管處置線，并由運動船舶當前狀態，預測其到達處置線時間；然后根據無人機對船舶跟蹤查證時間和序列中相鄰船舶之間的飛行間隔時間，可以得到各無人機查證序列所需時間；最后由小到大設置無人機數量，以最小化各無人機查證序列所需最大耗時為優化目標，利用模擬退火算法對查證序列進行迭代尋優，確定完成查證任務所需最少無人機數量及對應查證路線。仿真結果分析驗證了算法的可行性和有效性。

圖6 無人機對運動船舶的查證路徑Fig.6 UAV verification path for moving ships

表2 無人機1識別序列對應的識別位置和識別時間

表3 無人機2識別序列對應的識別位置和識別時間

表4 無人機3識別序列對應的識別位置和識別時間