考慮船舶操縱性約束的改進(jìn)遺傳算法航線規(guī)劃

王立鵬，張智，馬山，王學(xué)武

(1.哈爾濱工程大學(xué) 智能科學(xué)與工程學(xué)院，黑龍江 哈爾濱 150001；2.哈爾濱工程大學(xué) 船舶工程學(xué)院，黑龍江 哈爾濱 150001)

船舶是水面交通運(yùn)輸領(lǐng)域最為重要的交通工具，船舶航行安全是世界船舶領(lǐng)域長期的研究課題，其經(jīng)濟(jì)性與社會意義十分重大。船舶航行常規(guī)方式是操控人員憑借駕駛經(jīng)驗，開展航線規(guī)劃和船舶操控，規(guī)劃和操控效果往往過度依賴操控人員判斷能力及經(jīng)驗，出現(xiàn)差錯可能性高且潛在風(fēng)險大。統(tǒng)計數(shù)據(jù)表明：80%的船舶碰撞事故是人為因素造成的[1]。當(dāng)前船舶航行要求越來越高，只采用人為決策與操控方式，難以滿足船舶航行安全性要求，因此船舶航線自動規(guī)劃具有重要的理論研究及實際應(yīng)用意義。

船舶航線規(guī)劃方法主要有傳統(tǒng)控制方法和智能控制方法2類。文獻(xiàn)[2]提出一種非線性遺傳算法，用以彌補(bǔ)優(yōu)化過程局部極小問題。Mostef等[3]綜合運(yùn)用分支界限法、動態(tài)規(guī)劃和遺傳算法設(shè)計船舶安全航行路徑，利用模糊集理論設(shè)計新型的船舶避碰系統(tǒng)。氣象環(huán)境對船舶航線規(guī)劃影響較大，一些學(xué)者[4-5]采用A*等算法設(shè)計安全航線以規(guī)避氣象風(fēng)險。文獻(xiàn)[6]針對船舶避障路徑規(guī)劃問題，綜合考慮本船負(fù)載、目標(biāo)船運(yùn)動狀態(tài)、航行環(huán)境以及時間等因素。Kuczkowski等[7]創(chuàng)新地提出單種群和多種群遺傳算法，引入船舶航行相關(guān)約束條件，實現(xiàn)船舶避障路徑規(guī)劃。Lisowski等[8]利用最優(yōu)控制理論、博弈論、人工神經(jīng)網(wǎng)絡(luò)，模擬船舶駕駛?cè)藛T的思維，設(shè)計了船舶航行規(guī)劃及控制算法。一些學(xué)者[9-10]采用蟻群算法等智能控制算法設(shè)計船舶航線，并利用仿真手段加以實現(xiàn)。文獻(xiàn)[11]采用模糊控制設(shè)計船舶航行避碰算法，在模糊規(guī)則設(shè)計方面較具特色。Caldwell等[12-13]采用MPC算法開展船舶避障與航跡規(guī)劃，考慮推進(jìn)系統(tǒng)動態(tài)、風(fēng)浪流作用力以及運(yùn)動障礙。

以上船舶航線規(guī)劃方法存在如下問題：首先，航線規(guī)劃結(jié)果并未考慮船舶操縱性約束，因此按照規(guī)劃結(jié)果航行時易與目標(biāo)船碰撞；其次，檢測規(guī)劃航線與陸地元素(島嶼等)相對位置時，往往將陸地元素簡化為規(guī)則的幾何形狀，與現(xiàn)實海圖不符。

本文建立船舶水動力模型，利用海圖數(shù)據(jù)中陸地信息構(gòu)建不規(guī)則多邊形，并設(shè)計基于四叉樹方法的航線與不規(guī)則多邊形位置關(guān)系快速檢測算法，精準(zhǔn)計算船舶航行過程與目標(biāo)船會遇的時間和位置，構(gòu)建綜合考慮航線長度、相鄰航段轉(zhuǎn)角、與靜態(tài)障礙物距離和動態(tài)目標(biāo)船距離的復(fù)合適應(yīng)度遺傳算法，通過2次遺傳算法設(shè)計船舶航線，實現(xiàn)船舶避開靜、動態(tài)障礙物的任務(wù)，解決以往航線規(guī)劃方法的常見問題。

1 船舶運(yùn)動學(xué)建模

本文涉及到的坐標(biāo)系包括墨卡托坐標(biāo)系和船舶本體系，具體如圖1所示。

圖1 船舶運(yùn)動學(xué)建模相關(guān)坐標(biāo)系

墨卡托坐標(biāo)系xgogyg：原點位于經(jīng)緯度(0,0)處，橫軸xg指向東方，縱軸yg指向北方；船舶本體系xbobyb：原點ob位于船舶幾何重心，橫軸xb指向右舷方向，縱軸yb指向船艏方向。本文采用致密的離散墨卡托地圖來描述海圖上任意形狀的物標(biāo)。

在不考慮風(fēng)浪流干擾情況下，本文構(gòu)建VLCC船舶的K-T方程[14]，以此建立船舶舵角與艏向角速度傳遞函數(shù)，簡化表示其動態(tài)運(yùn)動特性：

(1)

式中：T是追隨性指數(shù);K是旋回性指數(shù)。

在船舶操縱性研究的文獻(xiàn)中，通常將回轉(zhuǎn)過程的速度設(shè)置為恒定值，這與船舶實際情況不符。本文構(gòu)建船舶回轉(zhuǎn)降速傳遞函數(shù)模型，根據(jù)車鐘計算船舶的航速：

(2)

式中：Rd為速度下降百分比；Rt為速度下降過渡時間。

2 海圖物標(biāo)多邊形檢測算法

基于四叉樹方法，設(shè)計線段與不規(guī)則多邊形相對位置快速檢測算法，實現(xiàn)規(guī)劃航段與島嶼關(guān)系的高效快速檢測任務(wù)，具體原理如圖2所示。

本文島嶼采用不規(guī)則多邊形表示，圖2(a)為一個海圖文件所示的矩形區(qū)域，利用四叉樹基本原理不斷切分所示矩形直至規(guī)定尺寸的最小矩形，根據(jù)目標(biāo)航段位置，快速確定航段穿過樹形結(jié)構(gòu)的矩形，并且只處理含有島嶼元素的矩形，以圖2中D13為例，放大效果如圖2(b)，開展如下預(yù)處理工作：

圖2 規(guī)劃航段與島嶼位置關(guān)系檢測原理

1)設(shè)目標(biāo)航段與陸地元素的安全距離為Dsafe，則四叉樹最小矩形邊長Lr min規(guī)定為：

Lr min≥Dsafe

(3)

2)對原始海圖中陸地元素進(jìn)行插值處理，保證插值后相鄰輪廓點的距離P1P2滿足：

P1P2≤0.5Dsafe

(4)

線段PstPet為目標(biāo)航段，起點為(xst,yst)，終點為(xet,yet)，最小矩形平面內(nèi)含有由若干線段收尾相連組成的島嶼輪廓，此處取其中一點島嶼輪廓點Pid=(xid,yid)，根據(jù)三角函數(shù)關(guān)系，可計算該點到目標(biāo)航段距離DLine：

(5)

(6)

DLine=Dis·sin(θLine)

(7)

3 航線規(guī)劃目標(biāo)函數(shù)

規(guī)劃航線需綜合考慮各影響因素，本文航線規(guī)劃目標(biāo)影響因素包括：航線里程、相鄰航段夾角、與靜態(tài)障礙物距離、與動態(tài)目標(biāo)船距離。

1)航線里程評價函數(shù)。

本文船舶規(guī)劃航線里程評價函數(shù)Ltraj為：

(8)

式中：n為航跡點數(shù)量；Px和Py為各航跡點的橫縱坐標(biāo)。

2)相鄰航段夾角評價函數(shù)。

本文相鄰規(guī)劃航段的夾角評價函數(shù)θtraj為：

(9)

式中：θi,i+1表示各航段夾角，該值可用平面幾何關(guān)系計算。

3)與靜態(tài)障礙物距離評價函數(shù)。

本文將靜態(tài)障礙物按照海圖中真實數(shù)據(jù)將其表示為不規(guī)則多邊形，按照第2節(jié)所描述的方法來規(guī)劃航段與陸地的最小距離，評價函數(shù)Dsta為：

(10)

式中：Nsta為靜態(tài)障礙物數(shù)量；Ntra-1為規(guī)劃航段數(shù)；dj,k為第j個障礙物與第k個航段距離。

4)與動態(tài)目標(biāo)船距離評價函數(shù)。

本文將目標(biāo)船簡化為質(zhì)點處理，利用點與線段集合的幾何關(guān)系來計算目標(biāo)船與所有規(guī)劃航段的最小距離，因此評價函數(shù)Ddyn表示為：

(11)

式中：Ndyn為目標(biāo)船數(shù)量；Ntra-1為規(guī)劃航段數(shù)量；dj,k表示第j個目標(biāo)船與第k個航段距離。

5)航線規(guī)劃綜合指標(biāo)函數(shù)。

本文對以上各個目標(biāo)函數(shù)進(jìn)行綜合加權(quán)，建立航線規(guī)劃綜合指標(biāo)函數(shù)Ffitness：

Ffitness=ω1Ltraj+ω2θtraj+ω3Dsta+ω4Ddyn

(12)

式中：ω1、ω2、ω3、ω4為各指標(biāo)函數(shù)的權(quán)值系數(shù)。本文制定權(quán)值系數(shù)制定原則：

1)由于本船需避免出現(xiàn)與靜態(tài)障礙物和動態(tài)目標(biāo)船撞擊情況，本文設(shè)置當(dāng)Dsta或Ddyn為0時，ω3或ω4為極大值；

2)本船航線里程與相鄰航段夾角相比，更能夠體現(xiàn)油耗情況，因此設(shè)置ω1比ω2略大。

4 考慮靜態(tài)障礙物的一次航線規(guī)劃

本文設(shè)計二次遺傳算法尋優(yōu)方式，開展航線優(yōu)化工作，本節(jié)將僅考慮靜態(tài)障礙物對航線規(guī)劃的影響，開展船舶航線一次優(yōu)化，即式(12)中ω4=0。

4.1 遺傳算法種群元素設(shè)置

定義船舶航行區(qū)域是邊長為Larea的正方形，設(shè)航跡點種群總數(shù)為Mpop，種群每個個體染色體節(jié)點數(shù)為Nind，每個染色體節(jié)點為二維變量[Pchorm_x,Pchorm_y]，表示航路點平面坐標(biāo)。種群進(jìn)化迭代次數(shù)為Niter，種群進(jìn)化交叉和變異概率分別為pcross和pmut?？紤]到遺傳算法尋優(yōu)結(jié)果可能為局部最優(yōu)情況，本文強(qiáng)制算法完成多次進(jìn)化次數(shù)，從而避免局部最優(yōu)問題，本文中用Niter變量表示。

4.2 基于變概率策略的交叉、變異和選擇操作

定義如下形式的交叉和變異概率pcross和pmut：

(13)

式中：pc0和pm0分別為交叉和變異的初始概率；Fopt為當(dāng)前代最優(yōu)個體適應(yīng)度；Fave為當(dāng)前代的平均適應(yīng)度。

1)交叉操作。

針對當(dāng)前代每個個體Ii，根據(jù)pcross判斷是否進(jìn)行交叉操作，如需要，則在[1,Ii)和(Ii,Mpop]中得到均勻分布的隨機(jī)數(shù)R，將個體Ii和IR開展交叉。

2)變異操作。

針對當(dāng)前代每個個體Ii，根據(jù)pmut判斷是否進(jìn)行變異操作，變異操作采用航跡點位置增加或減少方式，分別在[1,Nind]、[0,1]、[-1,1]中得到均勻分布的隨機(jī)數(shù)Q、增加或減少權(quán)值隨機(jī)數(shù)Nrand、增加或減少概率pmx和pmy，確定個體Ii的染色體節(jié)點Q所代表的航跡點需要變異，利用pmx和pmy決定航跡點增加或減少，航跡點位置變異操作后坐標(biāo)PQ_x和PQ_y計算式為：

(14)

式中Ncur為在Niter次迭代過程中的代數(shù);PQ_x0、PQ_y0分別為變異前的染色體節(jié)點變量。

3)選擇操作。

計算上一代種群中最優(yōu)個體染色體，建立初始可行航跡點個體Ifsb，其染色體節(jié)點為[Pfsb_x1,Pfsb_y1]，[Pfsb_x2,Pfsb_y2]，…，[Pfsb_xN,Pfsb_yN]，逐一判斷當(dāng)前代每個個體Ij是否存在穿越靜態(tài)障礙物的情況，如存在(即Dsta=0)，則使用最優(yōu)染色體Ifsb來替換Ij，否則保留個體Ij，將替換篩選后的個體組成臨時種群Mpop_tmp，設(shè)定適應(yīng)度閾值Ffit_td為：

(15)

式中：Fj_min和Fj_max分別表示當(dāng)前j代種群Mpop_tmp中最小適應(yīng)度和最大適應(yīng)度。

5 考慮動態(tài)目標(biāo)船的二次航線規(guī)劃

本節(jié)在第1次航線規(guī)劃基礎(chǔ)上開展第2次航線規(guī)劃任務(wù)，處理本船一次規(guī)劃結(jié)果與目標(biāo)船遭遇問題。

5.1 船舶會遇時間預(yù)測與安全性判定

引入船舶運(yùn)動方程用以預(yù)測本船與目標(biāo)船的會遇狀況，預(yù)測原理如下：設(shè)規(guī)劃航線為圖3中A-B-C段，本船起點為航跡點A，目的地為航跡點C，其間經(jīng)過航跡點B來避開靜態(tài)障礙物，第1次遺傳算法尋優(yōu)得到圖中ADEC所示航線，船舶直航和轉(zhuǎn)彎過程的航速變化情況，可簡化表示為圖3中的下部所示曲線。

圖3 兩船會遇時間預(yù)測

假設(shè)船舶初始為直航狀態(tài)，速度穩(wěn)定在最大航速，然后左轉(zhuǎn)90°后直航，再右轉(zhuǎn)90°后直航，航行過程位置和速度曲線如圖4、5所示的7個階段：階段1：維持最大航速；階段2：左轉(zhuǎn)過程速度下降；階段3：由左轉(zhuǎn)到直航過程，速度上升；階段4：速度上升至最大并保持；階段5：右轉(zhuǎn)過程速度下降；階段6：由右轉(zhuǎn)到直航過程，速度上升；階段7：速度上升至最大并保持。

圖4 船舶航行軌跡曲線

根據(jù)圖4和圖5可知，在第1次規(guī)劃航線的基礎(chǔ)上，代入船舶操縱性約束后，可處理直航航段和回轉(zhuǎn)航段，其中回轉(zhuǎn)航段圓弧半徑為本船的轉(zhuǎn)彎半徑?jīng)Q定，本文將根據(jù)船舶運(yùn)動學(xué)方程(1)和(2)，分別針對直航階段和回轉(zhuǎn)階段，計算本船由航跡點A運(yùn)動到會遇點的總時間。

圖5 船舶航速變化曲線

在圖3中，第1次規(guī)劃航線AB段和BC段夾角為2θ，設(shè)本船完成該轉(zhuǎn)彎過程的轉(zhuǎn)彎半徑為R，圓弧與AB段和BC段的切點為D和E，設(shè)航跡點A、B、C的坐標(biāo)分別為(Pax,Pay)、(Pbx,Pby)、(Pcx,Pcy)，根據(jù)幾何關(guān)系，可計算求得D和E的坐標(biāo)(Pdx,Pdy)、(Pex,Pey)為：

(16)

(17)

船舶航行過程往往保持發(fā)動機(jī)功率，航速變化往往是改變舵角所致，本文基于船舶運(yùn)動學(xué)方程開展仿真試驗，獲得船舶在不同舵角情況下的航速、位置和時間變化數(shù)據(jù)，仿真工況如下：船舶最大航速16 kn；舵角分別為5°、10°、15°、20°、25°。

轉(zhuǎn)彎減速仿真曲線如圖6所示。按照圖6所示方式，可建立航速、舵角、時間以及航程的關(guān)系表，由于篇幅限制，此處不列出。為實現(xiàn)對船舶轉(zhuǎn)彎降速及直航升速過程的量化計算，本文采用如下步驟加以實現(xiàn)：

1)船舶轉(zhuǎn)彎時，根據(jù)船舶回轉(zhuǎn)跟蹤的相鄰航段夾角，確定船舶舵角角度；船舶即將直航時，確定船舶直航前舵角角度。

2)根據(jù)船舶轉(zhuǎn)彎或直航航程，確定船舶轉(zhuǎn)彎或直航過程航速變化及用時情況，在圖6中查找船舶航速和時間。

圖6 船舶轉(zhuǎn)彎過程航速與時間關(guān)系曲線

5.2 附加航跡點的遺傳算法二次規(guī)劃

針對與目標(biāo)船會遇導(dǎo)致一次規(guī)劃航線不合理問題，本節(jié)提出遺傳算法二次規(guī)劃策略，原理如圖7。

如圖7所示，如目標(biāo)船在第1次規(guī)劃航線的航跡點B和C之間與本船會遇，在遺傳算法中增加染色體F，以第1次規(guī)劃航跡點為初始種群，開展第2次尋優(yōu)以獲得F坐標(biāo)。為了增加第2次尋優(yōu)速度，并且不對已有航跡點做較大改變，采用如下策略：

策略1：僅對由于動態(tài)目標(biāo)船產(chǎn)生的附加航跡點及其前面1個航跡點開展動態(tài)尋優(yōu)，即圖中航跡點F和航跡點B；

策略2：對于航跡點B，在第1次規(guī)劃航線時確定的位置上正方形范圍，正方形的邊長為航段AB和航段BC長度的較小長度的一半；對于航跡點F，在目標(biāo)船航向的反向延長線上尋優(yōu)。

6 仿真分析與驗證

本文在已構(gòu)建的船舶航行半物理仿真平臺上開展算法驗證工作，仿真平臺如下圖所示：由船舶動力學(xué)仿真系統(tǒng)、實船船橋軟硬件系統(tǒng)、三維視景系統(tǒng)以及評估系統(tǒng)組成，以上各系統(tǒng)按照實船通信方式，利用網(wǎng)絡(luò)和串口完成通信，仿真步長為0.1 s。

仿真初始工況如下：船舶航行海域為東經(jīng)122.6°～123.5°，北緯28.2°～29.75°，本船起點為29.911 7°N，122.071°E，終點為29.705 6°N，122.440 7°E，本船航速16 kn。航線規(guī)劃區(qū)域存在2個目標(biāo)船，均直線航行，航速為12 kn，出發(fā)地分別為29.705 6°N，122.440 7°E和29.705 6°N，122.440 7°E，目的地均為29.705 6°N，122.440 7°E。遺傳算法中航跡點種群變量：Mpop=100，Nind=5，Niter=30，Ninip=5，開展一次尋優(yōu)算法航線規(guī)劃。

圖8 船舶航行半物理仿真平臺

在海圖上繪制規(guī)劃航線如下圖所示：VLCC所在虛線為本船航線，其余虛線為目標(biāo)船航線。

如圖9所示，按照本文一次規(guī)劃算法可得到由起點到終點的航線，算法僅考慮規(guī)劃航程、相鄰航段航向轉(zhuǎn)角以及與靜態(tài)障礙物距離。但是由于規(guī)劃航區(qū)存在2個目標(biāo)船，航線規(guī)劃并未考慮船舶操縱性約束，導(dǎo)致本船按照規(guī)劃航線行駛時，與目標(biāo)船“Bulk carrier”和“Merchant ship”出現(xiàn)會遇情況，如圖10所示，本船與目標(biāo)船“Bulk carrier”存在碰撞可能性。雖然本船可通過會遇前調(diào)整航向?qū)嵤┍芘?，但此時的航線并不是最優(yōu)的，仍需改進(jìn)。

圖10 本船與目標(biāo)船會遇場景

按照本文第5節(jié)算法，開展第2次航線規(guī)劃任務(wù)，在與“Bulk carrier”和“Merchant ship”會遇的航段中增加航跡點。在海圖上繪制規(guī)劃航線如下。

如圖11所示，本文在與目標(biāo)船會遇的第2航段和第3航段中增加2個新航跡點，本船按照二次規(guī)劃后航線行駛，利用新增航跡點可避開目標(biāo)船“Bulk carrier”，具體如圖12所示。由于篇幅原因，此處不贅述避開目標(biāo)船“Merchant ship”內(nèi)容。

圖11 遺傳算法第2次規(guī)劃航線

圖12 第2次規(guī)劃算法避開目標(biāo)船

7 結(jié)論

1)構(gòu)建船舶運(yùn)動學(xué)模型，可精準(zhǔn)計算船舶在轉(zhuǎn)彎和直航期間速度變化情況。引入船舶操縱性約束，與采用傳統(tǒng)遺傳算法共同構(gòu)建航線規(guī)劃算法，在航線跟蹤過程中可避免與動態(tài)目標(biāo)船出現(xiàn)會遇情況，提高了航行的安全性；

2)基于四叉樹思想，建立的線段與不規(guī)則多邊形的位置關(guān)系檢測算法，可快速準(zhǔn)確判定規(guī)劃航段與海圖陸地元素的位置關(guān)系；

3)本文利用的2次遺傳算法的思想，可綜合考慮船舶航程、相鄰航段轉(zhuǎn)向、與靜態(tài)障礙物距離以及動態(tài)躲避目標(biāo)船，并通過優(yōu)化上述指標(biāo)的適應(yīng)度函數(shù)，得到可行的優(yōu)化航線。

本文并未考慮船舶航線規(guī)劃對海圖中等深線信息，簡化為與陸地元素的距離，將來將就此問題開展更進(jìn)一步的研究工作。