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

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

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

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

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

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

1 無人機(jī)查證問題描述

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

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

(1)

2 基于改進(jìn)模擬退火的無人機(jī)查證路 徑生成算法

2.1 無人機(jī)查證位置計(jì)算

由于船只處于運(yùn)動(dòng)狀態(tài)，需求解兩項(xiàng)查證任務(wù)之間的時(shí)間間隔，再根據(jù)船只速度確定無人機(jī)與待查證船舶相遇位置。具體求解過程可分為以下步驟。

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

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

(2)

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

(3)

求解方程組可得

(4)

(5)

圖1 無人機(jī)在兩艘船間運(yùn)動(dòng)過程Fig.1 Movement process of the UAV between two moving ships

2.2 無人機(jī)查證序列路徑及耗時(shí)計(jì)算

表示無人機(jī)；S為無人機(jī)查證商船的序列； 為無人機(jī)i的商船查證序列中的第k艘商船圖2 無人機(jī)識(shí)別運(yùn)動(dòng)商船序列Fig.2 UAV verification sequence for moving ships

(6)

(7)

(8)

2.3 基于模擬退火的無人機(jī)運(yùn)動(dòng)路徑生成算法執(zhí)行步驟

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

Step 1給定初始無人機(jī)數(shù)量n0，初始溫度T0和終止溫度Tf。

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

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

Step 5若達(dá)到熱平衡[內(nèi)循環(huán)次數(shù)大于n(Tk)]轉(zhuǎn)Step 6；否則轉(zhuǎn)Step 3。

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

根據(jù)上述計(jì)算步驟，算法流程圖如圖3所示。

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

3 仿真分析

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

入港商船運(yùn)動(dòng)狀態(tài)數(shù)據(jù)如表1所示，航向均指向港口，現(xiàn)利用算法確定需派遣進(jìn)行查證的無人機(jī)最少數(shù)量及查證路徑。

圖4 初始仿真場(chǎng)景想定Fig.4 Initial simulation scenario

表1 入港商船運(yùn)動(dòng)狀態(tài)數(shù)據(jù)

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

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

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

圖5 無人機(jī)最大路徑耗時(shí)與迭代次數(shù)間關(guān)系Fig.5 The relationship between the maximum UAV verification time and the number of iterations

3架無人機(jī)的飛行路線和對(duì)應(yīng)完成的識(shí)別任務(wù)如圖6所示，標(biāo)出了每一架無人機(jī)識(shí)別的商船序號(hào)，其中，紅色線段表示在商船識(shí)別過程中無人機(jī)飛過的軌跡，藍(lán)色線段表示無人機(jī)在識(shí)別完一艘商船后，到下一艘識(shí)別商船的飛行軌跡，所有的紅色線段與藍(lán)色線段相互連接，構(gòu)成無人機(jī)在完成整個(gè)任務(wù)過程中的飛行路線。

表2～表4給出了3 架無人機(jī)具體完成的識(shí)別商船序列，以及識(shí)別序列中每一艘商船對(duì)應(yīng)的識(shí)別開始位置、識(shí)別結(jié)束位置、識(shí)別開始時(shí)間和識(shí)別結(jié)束時(shí)間。這里的時(shí)間以某日6：00為時(shí)間起點(diǎn)，記為0 min。

4 結(jié)論

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

圖6 無人機(jī)對(duì)運(yùn)動(dòng)船舶的查證路徑Fig.6 UAV verification path for moving ships

表2 無人機(jī)1識(shí)別序列對(duì)應(yīng)的識(shí)別位置和識(shí)別時(shí)間

表3 無人機(jī)2識(shí)別序列對(duì)應(yīng)的識(shí)別位置和識(shí)別時(shí)間

表4 無人機(jī)3識(shí)別序列對(duì)應(yīng)的識(shí)別位置和識(shí)別時(shí)間