內(nèi)河船舶尾氣監(jiān)測的多無人機(jī)路徑規(guī)劃研究

王廣生，孫祎崢，孫海軍，魚 童，張 鋮，周云鵬

（1.中國港灣工程有限責(zé)任公司，北京 100027；2.河海大學(xué)港口海岸與近海工程學(xué)院，江蘇南京 210098）

引言

近年來，盡管國際海事組織（IMO）及各國政府通過降低船用燃料油中的硫含量來控制船舶大氣污染物排放，但由于高、低硫油價(jià)格存在較大差距，低硫油高昂的使用成本使得高硫燃油使用的違規(guī)率依然較高。為解決此問題，已有眾多研究嘗試通過移動式監(jiān)測系統(tǒng)[1]、岸基遙感監(jiān)測[2]、無人機(jī)嗅探檢測[3]等方式開展船舶尾氣污染防治工作。其中，無人機(jī)嗅探檢測方式憑借在機(jī)動性強(qiáng)和執(zhí)法效率高等優(yōu)勢，受到了行業(yè)內(nèi)學(xué)者的廣泛關(guān)注，在海事管理領(lǐng)域的可行性得到了充分的證明[4-6]。

然而，在船舶流量密度較大的情況下，僅依靠人工操控?zé)o人機(jī)完成檢測工作效率低、危險(xiǎn)性也較高，因此研究續(xù)航時(shí)間有限的條件下，多無人機(jī)協(xié)同是實(shí)現(xiàn)無人機(jī)自動化監(jiān)測的關(guān)鍵問題。

多無人機(jī)協(xié)同類屬于任務(wù)分配問題[7]，即在已知無人機(jī)數(shù)量和任務(wù)數(shù)量的條件下，考慮到環(huán)境威脅、無人機(jī)的續(xù)航能力、載荷能力約束以及任務(wù)的特殊需求，進(jìn)行合理的任務(wù)分配，使得各無人機(jī)均能夠以最優(yōu)效率協(xié)同完成工作。路徑尋優(yōu)問題一般可將其歸為經(jīng)典的旅行商問題[8]，多無人機(jī)協(xié)同的情景涉及到多旅行商問題（Multiple Traveling Salesman Problem,MTSP）和移動目標(biāo)旅行商問題（Moving Target Traveling Salesman Problem,MTTSP）。針對MTSP 問題，目前主要采用啟發(fā)式算法進(jìn)行求解，如雜草入侵算法[9]、人工蜂群算 法[10]、遺傳算法[11]、粒子群算法[12]等。例如，Bourjolly等[13]建立了具有時(shí)間相關(guān)性的MTTSP 問題模型，并使用禁忌搜索算法求解航天器在軌服務(wù)問題；Moraes 等[14]通過對比遺傳算法、蟻群算法、模擬退火算法在解決MTTSP 時(shí)的表現(xiàn)，得出遺傳算法在求解質(zhì)量和求解效率等方面表現(xiàn)最佳。

本文基于MTTSP 和MTSP 模型，構(gòu)建了多無人機(jī)巡檢路徑規(guī)劃模型（Multiple UAVs’ Path Planning,MUPP）。針對多無人機(jī)巡檢任務(wù)分配的需求，提出兩階段算法（Two Phase Algorithm,TPA）以提升算法的求解性能，并以長江干線航道斷面為例進(jìn)行仿真，驗(yàn)證模型的科學(xué)性和算法的有效性。

1 模型構(gòu)建

1.1 模型假設(shè)

為了將實(shí)際問題理論化，便于模型構(gòu)建，需對模型做出以下假設(shè)：

1）無人機(jī)前往檢測時(shí)的速度恒定且快于船舶；在檢測時(shí)間內(nèi)，船舶按當(dāng)前速度和航向行駛；無人機(jī)到達(dá)目標(biāo)點(diǎn)后能夠完成船舶燃油品質(zhì)的檢測；

2）無人機(jī)跟隨檢測時(shí)的速度與被檢測船舶速度一致，檢測所需時(shí)間不隨船舶變化；

3）旋翼無人機(jī)不同于固定翼無人機(jī)，其轉(zhuǎn)彎半徑較小，故不考慮最小轉(zhuǎn)彎半徑約束；不考慮飛行過程中威脅、地形和氣候等因素的影響。

1.2 模型建立

基于上述假設(shè)，多無人機(jī)巡檢路徑規(guī)劃（Multiple UAVs’ Path Planning,MUPP）問題的表達(dá)如下：

式中：

L—巡航路徑總長度；

K—無人機(jī)的集合；

M—無人機(jī)的數(shù)量；

dij—船舶si與船舶sj的距離；

T—檢測總時(shí)間；

Q—無人機(jī)續(xù)航能力；

式（1）為目標(biāo)函數(shù)，表示優(yōu)化的目的為多無人機(jī)總飛行長度最小。約束條件（2）表示對巡檢總時(shí)間T 進(jìn)行限制。約束條件（3）表示每艘船舶僅能被一架無人機(jī)檢測一次。約束條件（4）、（5）表示路徑中每個(gè)船舶只能分別與兩個(gè)船舶相連，保證路徑的連續(xù)性。

1.3 數(shù)據(jù)準(zhǔn)備

MUPP 模型中的L、T值按照圖1 方法計(jì)算，圖中tr、dr為無人機(jī)返回基站的時(shí)間和距離；tj為無人機(jī)飛往船舶的時(shí)間；td為無人機(jī)跟隨檢測的時(shí)間；vd為無人機(jī)速度；vH(i)為船舶H(i)的速度；tH(i)為檢測時(shí)間；dH(i)為飛行距離。

圖1 無人機(jī)飛行總長度和時(shí)間的計(jì)算方法Fig.1 Calculation method of total flight length and time of UAVs

其中，飛行時(shí)間tf的計(jì)算原理為：已知無人機(jī)檢測完H(i)船后的位置D 點(diǎn)坐標(biāo)為(x1,y1)，待檢船舶H(j)位置O 點(diǎn)坐標(biāo)為(x2,y2)。以(x2,y2)為原點(diǎn)，H(j)船舶航行方向?yàn)閥 軸建立直角坐標(biāo)系，船舶H(j)勻速前行至檢測點(diǎn)M 后，無人機(jī)飛行方向與y 軸夾角為θ，得到方程式（6），化簡可得飛行時(shí)間tf的計(jì)算式（7）。計(jì)算簡圖如圖2 所示。

圖2 飛行時(shí)間計(jì)算示意圖Fig.2 Schematic diagram of flight time calculation

1.4 模型求解

MUPP 模型中的路徑規(guī)劃問題屬于NP-hard 問題，本文采用融合了遺傳算法（GA）和模擬退火算法（SA）兩種算法的混合模擬退火遺傳算法[15]（Simulated Annealing Genetic Algorithm,SAGA）作為基本算法。該改進(jìn)遺傳算法同時(shí)具有遺傳算法的全局搜索特性和模擬退火算法的局部搜索特性。

此外，由于MUPP 模型需要多無人機(jī)協(xié)同完成巡檢任務(wù)，故涉及到任務(wù)分配的問題?；诟倪M(jìn)的聚類算法，將該任務(wù)分配問題抽象為MTSP 后，再將MTSP 轉(zhuǎn)化為多個(gè)TSP 進(jìn)行求解。

考慮到船舶運(yùn)動特點(diǎn)及無人機(jī)任務(wù)分配的均衡，在上下行船舶數(shù)量較為接近的條件下，提出一種基于上下行船舶分組和任務(wù)均分的K-means++算法。其主要思想為將船舶數(shù)據(jù)集分為上下行兩組數(shù)據(jù)集，再引入容量限制要求，使得聚類形成的集合中船舶數(shù)量較為均勻。GT-K-means++算法的具體步驟如下：

設(shè)V=｛v1|i=1,2,…,n｝表示待檢測船舶節(jié)點(diǎn)集，初始簇集為s=(c1,c2,…,cj,…,ck)，k 為類簇?cái)?shù)量。初始類簇cj的中心為μj,j=1,2,…,k，每個(gè)類簇中節(jié)點(diǎn)的個(gè)數(shù)qj=0。

1）根據(jù)船舶航向數(shù)據(jù)，將船舶節(jié)點(diǎn)集分為上行船舶節(jié)點(diǎn)集Vup和下行船舶節(jié)點(diǎn)集Vdown；接著初始化類簇容量，即每個(gè)類簇中船舶數(shù)量上限為Q=ceil(n/k)。

2）對上行船舶節(jié)點(diǎn)集Vup，初始聚類中心是該集合中隨機(jī)選取的一個(gè)船舶點(diǎn)；用最短距離D(x)表示每個(gè)船舶點(diǎn)與已有聚類中心之間的距離，然后用輪盤賭法選出下個(gè)聚類中心點(diǎn)；重復(fù)以上操作，直到選出上行船舶的kup個(gè)聚類中心點(diǎn)。

3）對下行船舶節(jié)點(diǎn)集Vdown，按照步驟2 中的方法選出下行船舶的kdown個(gè)聚類中心點(diǎn)。

4）針對各上行船舶點(diǎn)vi?Vup，按照公式（8）計(jì)算各船舶點(diǎn)vi到其類簇中心μj的歐幾里得距離ρ(vi,μj)。

接著將所有船舶點(diǎn)按照距離值從小到大排序。

5）聚類。取到類簇中心μj距離值最小的船舶點(diǎn)vi，并令qj=qj+1，判斷類簇cj當(dāng)前船舶點(diǎn)個(gè)數(shù)是否滿足qj≤Q。若滿足，則將該船舶點(diǎn)vi分配給類簇cj；若不滿足，則將該船舶點(diǎn)vi到類簇cj的距離值設(shè)為無窮大，重新排序并分配下一船舶點(diǎn)，直到分配完所有船舶點(diǎn)。

6）根據(jù)公式更新聚類中心點(diǎn)jμ的坐標(biāo)，類簇cj中船舶點(diǎn)數(shù)量是，若其中心點(diǎn)坐標(biāo)沒有發(fā)生變化，則聚類完成收斂，輸出聚類結(jié)果；否則，轉(zhuǎn)4）。

7）針對各下行船舶點(diǎn)vi?Vdown，按照4）至 6）的方法完成聚類，并輸出聚類結(jié)果。

綜上，本文采用了GT-K-means++算法對水域內(nèi)待檢測船舶點(diǎn)進(jìn)行聚類，將船舶分成多個(gè)子集后，運(yùn)用SAGA 對每一個(gè)船舶子集進(jìn)行無人機(jī)巡檢路徑規(guī)劃，從而構(gòu)成“GT-K-means++”+“SAGA”的二階段算法（Two Phase Algorithm,TPA），以此來分段求解MUPP。

2 實(shí)驗(yàn)分析

2.1 研究范圍

本文選擇中國長三角船舶排放控制區(qū)范圍內(nèi)長江干線航道南京段進(jìn)行仿真實(shí)驗(yàn)（如圖3 所示），并作參數(shù)影響分析。研究范圍中頂點(diǎn)經(jīng)緯度為：32.25241 °N，119.156 °E；32.23642 °N，119.22114 °E；32.21797 °N，119.21249 °E；32.2372 °N，119.15147 °E。研究范圍的斷面長度約4 km，寬度約1.3 km。船舶航行數(shù)據(jù)均源自中國交通運(yùn)輸部海事局的AIS 信息服務(wù)平臺。圖中圓形點(diǎn)表示設(shè)定的無人機(jī)基站位置，黑色線段為航道邊界線，船形標(biāo)志表示船舶分布位置。

圖3 基于AIS 的研究范圍和船舶實(shí)時(shí)位置Fig.3 The research scope based on AIS and the real-time positions of the ships

2.2 仿真結(jié)果分析

算法采用Python 語言編寫，相關(guān)參數(shù)與模型參數(shù)設(shè)置如表1 所示，結(jié)合船舶AIS 航行數(shù)據(jù)，給范圍內(nèi)所有船舶設(shè)定相應(yīng)的編號、速度以及坐標(biāo)。

表1 仿真參數(shù)設(shè)置Tab.1 Simulation parameter settings

TPA 算法迭代收斂圖如圖4 所示，從迭代結(jié)果可知，約350 次后收斂，表2 為使用TPA 算法運(yùn)算得到的各無人機(jī)的巡檢路徑及所需時(shí)間。計(jì)算結(jié)果顯示，各無人機(jī)的任務(wù)量均為9，各無人機(jī)巡檢時(shí)間平均值19.5 min，方差為1.57，任務(wù)量較為接近，且滿足無人機(jī)的續(xù)航時(shí)間要求，四架無人機(jī)可均衡、高效地完成巡檢工作。

表2 巡航路徑和時(shí)間Tab.2 Cruise path and tim

圖4 TPA 迭代結(jié)果Fig.4 TPA iteration results

2.3 模型參數(shù)影響分析

1）船舶數(shù)量及無人機(jī)數(shù)量對TPA 結(jié)果的影響

假設(shè)各無人機(jī)速度vd均為20 m/s，單船檢測時(shí)間td為3 s。分別在不同場景下運(yùn)行10 次程序，得到最優(yōu)的路徑總時(shí)間T，如表3 所示。結(jié)果顯示當(dāng)船舶數(shù)量大于60 艘時(shí)，出現(xiàn)2 艘無人機(jī)無法滿足巡檢要求的情況，并隨著船舶數(shù)量的增加，所需無人機(jī)數(shù)量不斷增加，當(dāng)船舶數(shù)量達(dá)到100 艘時(shí)，需4 臺無人機(jī)才能完成巡檢任務(wù)。

表3 16 種場景下的最優(yōu)路徑時(shí)間Tab.3 Optimal path time under 16 scenarios

可以發(fā)現(xiàn)，隨著船舶數(shù)量的增加，無人機(jī)巡檢總時(shí)間T 也呈增長趨勢。雖然場景15 中船舶數(shù)量比場景11 中多20 艘，其總時(shí)間T 卻比場景11 少3.7 min，表明船舶數(shù)量是影響巡檢路徑時(shí)間的主要因素。當(dāng)航道中船舶數(shù)量為40 艘時(shí)，配備兩架續(xù)航時(shí)間為40 min 的無人機(jī)即可滿足巡檢要求；當(dāng)船舶數(shù)量為60 艘時(shí)，應(yīng)配備3 架續(xù)航時(shí)間為40 min的無人機(jī)或2 架續(xù)航時(shí)間為60 min 的無人機(jī)；而對于待檢測船舶數(shù)量較多的情況（80 艘、100 艘），則需要配備4 臺續(xù)航時(shí)間為40 min 的無人機(jī)才能夠順利完成巡檢任務(wù)。

當(dāng)船舶數(shù)量為60 和船舶數(shù)量為100 時(shí)，無人機(jī)數(shù)量對巡檢時(shí)間如圖5 所示。圖中方形、圓形線段為兩種場景下T 值的變化曲線，三角形線段為每增加一架無人機(jī)時(shí)T 值下降率的變化曲線。

圖5 不同無人機(jī)數(shù)量下的總巡檢時(shí)間Fig.5 Total inspection time under different numbers of UAVs

從圖5 可以看出，無人機(jī)數(shù)量的增加會減少巡檢路徑總時(shí)間，當(dāng)無人機(jī)數(shù)量由3 增加至4 時(shí)，T值下降率約51 %，變化最為顯著，而在無人機(jī)數(shù)量由4 增加至8 時(shí)，T 值下降率保持在14 %左右，巡檢效率提升不算明顯。由于內(nèi)河航道中船舶流量有明顯的高峰期與低谷期，配備2 架或3 架無人機(jī)不能夠滿足較多船舶數(shù)量情況的巡檢需求，故每個(gè)無人機(jī)基站配備4 臺無人機(jī)最為合理。

2）船舶速度和無人機(jī)速度對TPA 計(jì)算結(jié)果的影響

以場景15 為例，在vd為14、18、22、26、30 m/s的五種情景下，分別求出td為3、6、9、12 s 時(shí)的路徑總時(shí)間T，實(shí)驗(yàn)結(jié)果如圖6 所示。

圖6 不同飛行速度下的總檢測時(shí)間Fig.6 Total detection time at different flight speeds

圖6 顯示，在vd相同的情況下，td每增加3秒，T 值也隨之增長，從3 s 增長至6 s 時(shí)，T 值增長量較小，約6 分鐘；從6 s 增長至9 s 時(shí)，T 值的增長量約23 分鐘；從9 s 增長至12 s 時(shí)，T 值的增長量更多，約42 分鐘?？梢妕d的增加表示無人機(jī)跟隨檢測所需長時(shí)間的增加，同時(shí)由于其他船舶行駛得更遠(yuǎn)，也會導(dǎo)致巡檢時(shí)間的延長。當(dāng)td保持不變時(shí)，隨著vd的增加，T 值逐漸減小，這是由于飛行速度提高導(dǎo)致檢測間隙時(shí)間縮短所致；此外，在vd由14 m/s 增加至22 m/s 的過程中T 值縮減幅度較大，但隨著vd值的繼續(xù)增加，T 值縮減幅度呈現(xiàn)逐漸減小趨勢。綜上分析，為提高巡檢效率，建議執(zhí)法部門選用速度22 m/s 的無人機(jī)，并選配檢測設(shè)備響應(yīng)時(shí)間小于6 s 的檢測儀來完成巡檢工作。

3 結(jié)語

為解決內(nèi)河船舶尾氣排放監(jiān)測工作中無人機(jī)自動化巡檢的部署方案問題，本文以無人機(jī)總飛行長度最小化為目標(biāo)函數(shù)，提出了一種多無人機(jī)動態(tài)路徑規(guī)劃模型（MUPP），并采用“GT-K-means++” +“SAGA”的二階段算法（TPA）對這一NP-hard 問題進(jìn)行求解。以長三角船舶排放控制區(qū)范圍內(nèi)長江干線航道南京段為例，基于實(shí)時(shí)AIS 船舶航行數(shù)據(jù)，利用TPA 算法進(jìn)行實(shí)例分析，結(jié)果顯示：待檢船舶數(shù)量的增多會對無人機(jī)的數(shù)量及續(xù)航時(shí)長有更高的要求，考慮到航道巡檢需求、無人機(jī)的巡檢效率，每個(gè)基站配備4 臺速度為22 m/s 的無人機(jī)，搭載檢測耗時(shí)少于6 s 的高性能檢測儀器較為合理。