混合模擬退火與粒子群優(yōu)化算法的無(wú)人艇路徑規(guī)劃*

鄭佳春， 吳建華， 馬　勇, 龍　延

(1.集美大學(xué)，福建 廈門(mén)361021； 2.武漢理工大學(xué)，湖北 武漢430063)

?

混合模擬退火與粒子群優(yōu)化算法的無(wú)人艇路徑規(guī)劃*

鄭佳春1， 吳建華2， 馬勇2, 龍延1

(1.集美大學(xué)，福建 廈門(mén)361021； 2.武漢理工大學(xué)，湖北 武漢430063)

針對(duì)水面無(wú)人艇路徑規(guī)劃中單獨(dú)使用模擬退火算法存在的不足，以提高無(wú)人艇在執(zhí)行任務(wù)時(shí)的安全性為研究目的，解決傳統(tǒng)無(wú)人艇在航行中未考慮來(lái)往船只而導(dǎo)致的碰撞危險(xiǎn)，提出了模擬退火算法與粒子群算法相結(jié)合的混合路徑規(guī)劃算法，利用該算法的高收斂性和容易跳出局部最優(yōu)等特點(diǎn)，結(jié)合避碰規(guī)則，實(shí)現(xiàn)海事無(wú)人艇在同一靜態(tài)環(huán)境下對(duì)遇、交叉和追越三種會(huì)遇局面的最優(yōu)路徑規(guī)劃。仿真結(jié)果表明：本文提出的算法可以實(shí)現(xiàn)無(wú)人艇在復(fù)雜水域條件下快速路徑規(guī)劃，使與他船的自動(dòng)避碰行為成為可能，給出的路徑規(guī)劃具有可行、有效，能夠?yàn)闊o(wú)人艇安全的航行、順利的執(zhí)行任務(wù)提供保障。

混合模擬退火與粒子群算法；無(wú)人艇；最優(yōu)路徑規(guī)劃；自動(dòng)避碰

引用格式：鄭佳春， 吳建華， 馬勇， 等. 混合模擬退火與粒子群優(yōu)化算法的無(wú)人艇路徑規(guī)劃[J]. 中國(guó)海洋大學(xué)學(xué)報(bào)(自然科學(xué)版), 2016, 46(9)： 116-122.

ZHENGJia-Chun,WUJian-Hua,MAYong,etal.AHybridoptimizationalgorithmofSimulatedAnnealingandParticleSwarmforUnmannedSurfaceVesselPathPlanning[J].PeriodicalofOceanUniversityofChina, 2016, 46(9)： 116-122.

隨著海洋資源的探索與開(kāi)發(fā)，無(wú)人艇(UnmannedSurfaceVessel,USV)已經(jīng)成為當(dāng)前的研究熱點(diǎn)[1-5]。路徑規(guī)劃是USV自主導(dǎo)航的關(guān)鍵技術(shù)之一，其核心技術(shù)是路徑規(guī)劃算法(PathPlanningAlgorithm,PPA)。目前常見(jiàn)的路徑規(guī)劃算法主要有：Dijkstra算法、神經(jīng)網(wǎng)絡(luò)算法、禁忌搜索算法、人工勢(shì)場(chǎng)法、模擬退火算法、蟻群算法、遺傳算法、粒子群算法等。在無(wú)人艇路徑規(guī)劃領(lǐng)域，莊佳園等[6]利用去噪平滑算法和自適應(yīng)閾值法設(shè)計(jì)了一種基于航海雷達(dá)圖像處理的方法，采用Dijkstra算法搜索最佳路徑；陳超和唐堅(jiān)[7]提出一種將A*算法與可視圖法相結(jié)合的路徑規(guī)劃算法，解決了傳統(tǒng)可視圖法靈活性差的問(wèn)題并通過(guò)實(shí)驗(yàn)驗(yàn)證了該算法的有效性；饒森[8]將路徑規(guī)劃的基本技術(shù)提升至分層次規(guī)劃運(yùn)行，其在對(duì)分層路徑尋優(yōu)的研發(fā)中，對(duì)ActivateValue計(jì)算方法與遺傳算法協(xié)同融合，進(jìn)行了全局路徑規(guī)劃的計(jì)算機(jī)仿真實(shí)驗(yàn)；但是，這些算法均存在局部最優(yōu)和收斂性問(wèn)題。粒子群算法(ParticleSwarmOptimization，PSO)是近年來(lái)發(fā)展起來(lái)的進(jìn)化算法，和模擬退火算法相似，也是從隨機(jī)解出發(fā)，通過(guò)迭代尋找最優(yōu)解，也是通過(guò)適應(yīng)度來(lái)評(píng)價(jià)解的品質(zhì)，但它比遺傳算法規(guī)則更為簡(jiǎn)單，它沒(méi)有遺傳算法的“交叉”和“變異”操作，它通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)。在PSO中，粒子飛行速度直接影響算法的性能：如果速度太大，微?？赡茱w過(guò)最優(yōu)解；反之，微粒容易進(jìn)入局部搜索空間而導(dǎo)致無(wú)法進(jìn)行全局搜索。為此，本文提出在PSO算法引入模擬退火機(jī)制更新粒子的位置和速度，計(jì)算更新前后的粒子適應(yīng)度及其差值，對(duì)進(jìn)化后的適應(yīng)值按Metropolis準(zhǔn)則接受優(yōu)化解并以一定的概率接受惡化解，使PSO算法能從局部極值區(qū)域中跳出，收斂至全局最優(yōu)粒子群解。利用該混合算法(SAPSO)的高收斂性和容易跳出局部最優(yōu)等特點(diǎn)，結(jié)合避碰規(guī)則模擬仿真獲取海事無(wú)人艇(MarineUnmannedSurfaceVessel，MUSV)自主避障的最優(yōu)路徑規(guī)劃，取得很好的效果。

1　MUSV海上環(huán)境建模

考慮近海水域內(nèi)，船舶數(shù)量多、交通流量大的特點(diǎn)，結(jié)合相關(guān)海上避碰規(guī)則；再綜合對(duì)比柵格法[9-10]、單元樹(shù)法[11]、可視圖法[12]、Voronoi[13-15]等常用環(huán)境建模方法的優(yōu)缺點(diǎn)，選擇采用柵格法二維平面空間按以下步驟進(jìn)行環(huán)境建模：

(1)確定柵格粒度：假設(shè)：lmax是柵格的最大邊長(zhǎng)，lmin是柵格的最小邊長(zhǎng)，l是最終的柵格邊長(zhǎng)，Sab為障礙物的面積和，Stotal為地圖區(qū)域總面積,LM為MUSV在運(yùn)動(dòng)中的最大寬度，則柵格粒度大小為：

(1)

式(1)中，max表示取最大值。

(2)建立柵格坐標(biāo)系：以左上角為坐標(biāo)原點(diǎn)，水平向右橫坐標(biāo)增加為X軸，垂直向下縱坐標(biāo)增加為Y軸。同時(shí)采用序號(hào)法和直角坐標(biāo)法相結(jié)合來(lái)表示柵格。每個(gè)柵格的位置用該柵格的中心點(diǎn)坐標(biāo)來(lái)描述，用(x，y)表示，例如：柵格1的坐標(biāo)表示為(0.5,0.5)。

假設(shè)：Xmax表示X軸坐標(biāo)的最大值，Ymax表示Y軸坐標(biāo)的最大值，NX，NY分別表示X軸、Y軸的最大柵格數(shù)，由式(1)可得：NX=Xmax/l,NY=Ymax/l。

柵格用序號(hào)的表示以左上角為坐標(biāo)的原點(diǎn)，水平向右，自上到下依次對(duì)每個(gè)柵格進(jìn)行編號(hào)，編號(hào)的順序?yàn)?，2，3，…。柵格位置坐標(biāo)(x，y)與柵格編號(hào)i的映射變換關(guān)系如式(2)、(3)、(4)所示。

(2)

x=mod((i-1),Nx)+0.5，

(3)

y=fix((i-1)/Nx)+0.5。

(4)

式(3)中，mod表示取余函數(shù)，式(4)中fix表示取整函數(shù)。

(3)障礙區(qū)的柵格處理：忽略MUSV的旋轉(zhuǎn)運(yùn)動(dòng)，則障礙物可視為整體障礙區(qū)。為了航行安全和避免算法出現(xiàn)局部死區(qū)，將障礙區(qū)作如下處理：1)如果劃分區(qū)域內(nèi)的障礙物不滿1個(gè)柵格，按1個(gè)柵格表示；2)將障礙物內(nèi)的空凹部分與該障礙物連成1個(gè)整體；3)如果2個(gè)障礙物間的距離較近，則把這兩個(gè)障礙物連成為1個(gè)障礙物。在二維柵格坐標(biāo)(x,y)存在障礙物時(shí)，B(x，y)采用表示：

(5)

式(5)中，0

(4)環(huán)境場(chǎng)景設(shè)置為海上靜態(tài)環(huán)境和動(dòng)態(tài)環(huán)境。靜態(tài)環(huán)境為已知障礙區(qū)的位置和數(shù)目，同時(shí)，不考慮船舶縱向運(yùn)動(dòng)以及外界環(huán)境對(duì)船舶運(yùn)動(dòng)的影響；動(dòng)態(tài)環(huán)境為海事無(wú)人艇實(shí)際航行中，既要按航線的要求行進(jìn)，還會(huì)受到風(fēng)、浪和流的影響，也需要考慮一些隨機(jī)因素的影響，如附近船舶的航行，水面漂浮物，以及其他突然出現(xiàn)的干擾等。本文研究時(shí)暫不考慮風(fēng)浪流等因素對(duì)MUSV路徑規(guī)劃的作用，動(dòng)態(tài)環(huán)境也主要是考慮與他船對(duì)遇、交叉、追越的3種局面。

2　路徑規(guī)劃算法

2.1 問(wèn)題描述

MUSV的路徑規(guī)劃問(wèn)題可以描述為：某一海事無(wú)人艇在假定的條件和參數(shù)下，感知外界環(huán)境信息，在可航行區(qū)域內(nèi)避開(kāi)其他船舶的干擾，從設(shè)定Start點(diǎn)尋求最短航線L到達(dá)設(shè)定Target點(diǎn)。路徑規(guī)劃過(guò)程如下：

(1)設(shè)置仿真無(wú)人艇的基本參數(shù)，包括艇長(zhǎng)、艇寬、吃水及控制方程。

(6)

式(6)中，T為追隨性指數(shù)(s)，ω為旋回角速度(1/s)，K為旋回性指數(shù)(1/s)，δ為舵角。

(2)提取電子海圖中島嶼、灘涂、航標(biāo)等障礙物信息，建立柵格坐標(biāo)系并分別以0、1表示可航區(qū)域與不可航區(qū)域。提取動(dòng)態(tài)船舶信息并預(yù)測(cè)其路徑趨勢(shì)，根據(jù)與來(lái)船的方位差Δθ判斷本船責(zé)任。

(3)無(wú)人艇與障礙物之間的距離(D)要求大于最小安全距離(dmin)。

D≥dmin。

(7)

相對(duì)距離(d)代表碰撞危險(xiǎn)度如式(8)所示，當(dāng)d小于設(shè)定值時(shí)，無(wú)人艇轉(zhuǎn)向避讓。

(8)

(4)選取巡航出發(fā)點(diǎn)S(x0,y0)和目標(biāo)點(diǎn)T(xt,yt)坐標(biāo)；基于SAPSO求解可行路徑的解空間：

(9)

式(9)中，L為規(guī)劃路徑的總長(zhǎng)，Li為第i段路徑的長(zhǎng)度。選取出路徑最短的解為最優(yōu)規(guī)劃路徑，得到最優(yōu)解minL。

2.2 混合模擬退火機(jī)制的粒子群算法

SAPSO算法描述如下：

(a)隨機(jī)初始化種群中各個(gè)微粒的位置及速度，并按式(10)設(shè)置初始溫度；

t0=f(pg)/ln5。

(10)

式(10)中，pg為種群的群體極值，其選擇為粒子群中適應(yīng)值的最大值。

(b)將當(dāng)前各個(gè)微粒的位置及適應(yīng)值存于個(gè)體極值(pi)中，將適應(yīng)值最優(yōu)個(gè)體(pbest)的位置及適應(yīng)值存儲(chǔ)于pg中，根據(jù)式(11)計(jì)算各個(gè)微粒的適應(yīng)值。

(11)

(c)從所有pi中確定全局最優(yōu)適應(yīng)值更新pg，然后用式(12)更新各個(gè)微粒的速度，以式(13)更新各個(gè)微粒的位置。

vi,j(t+1)=φ{(diào)vi,j(t)+c1r1

(12)

xi,j(t+1)=xi,j(t)+vi,j(t+1)·T,

j=1,2,…, MaxDT。

(13)

(d)計(jì)算各個(gè)微粒新的目標(biāo)值，更新各個(gè)微粒的pi值及群體的pg值；

(e)進(jìn)行退溫操作，退火方式按式(14)進(jìn)行。若滿足終止條件：運(yùn)算精度或迭代次數(shù)達(dá)到預(yù)定值，搜索停止，輸出結(jié)果，否則轉(zhuǎn)向步驟(b)。算法流程圖如圖1所示。

圖1　SAPSO算法流程圖Fig.1　SAPSO algorithm flow chart

tk+1=λtk。

(14)

式(14)中，λ為退火系數(shù)。

仿真時(shí)，基本參數(shù)設(shè)定為初始化粒子群體個(gè)數(shù)n=50，設(shè)定最大迭代次數(shù)MaxDT=50，搜索空間維數(shù)D=8。

3　SAPSO算法路徑規(guī)劃仿真

3.1 仿真環(huán)境

表1　仿真條件

表2　仿真船舶基本參數(shù)

注：MUSV數(shù)據(jù)以國(guó)內(nèi)自主研發(fā)的第一艘無(wú)人巡航艇為例；它船數(shù)據(jù)來(lái)源于《海港總平面設(shè)計(jì)規(guī)范》(JTJ156-2013)。

Note:MUSVdataisbasedonthefirstunmannedcruiseofindependentresearchanddevelopmentboat;othership'sdataisfromthe《Seaporttotalgraphicdesignspecification》(JTJ156-2013)

3.2 環(huán)境柵格模型的建立

3.2.1 靜態(tài)障礙物坐標(biāo)系上建立200×200的柵格，所建坐標(biāo)以m為單位，以左下角為坐標(biāo)原點(diǎn)O，橫坐標(biāo)、縱坐標(biāo)每格均代表100m。在柵格環(huán)境中隨機(jī)散布仿真靜態(tài)障礙物，在MATLAB界面上顯示，輸出如圖2所示，圖中圓圈T代表無(wú)人艇巡航的目的地。

圖2　柵格環(huán)境圖

3.2.2 動(dòng)態(tài)障礙物MUSV在活動(dòng)范圍內(nèi)隨時(shí)可能出現(xiàn)其他活動(dòng)船舶，因此在MUSV的路徑規(guī)劃中還需解決如何處理與來(lái)船會(huì)遇局面的避碰問(wèn)題。MUSV在動(dòng)態(tài)環(huán)境中采取主動(dòng)避讓措施，具體方案是：首先判斷與動(dòng)態(tài)障礙物(來(lái)船)的距離，若d≤200m，再進(jìn)一步確定與來(lái)船航向差，然后根據(jù)避碰規(guī)則決定采用何種避碰措施，即進(jìn)行速度避讓或航向避讓，從而實(shí)現(xiàn)主動(dòng)避碰。

3.3 單船路徑仿真

本文首先在無(wú)他船干預(yù)的情況下進(jìn)行單船路徑仿真，即：根據(jù)MUSV仿真參數(shù)，在隨機(jī)障礙物條件下，實(shí)現(xiàn)MUSV的日常海事巡航，航線為固定起始點(diǎn)S點(diǎn)到固定目標(biāo)點(diǎn)T點(diǎn)的路徑規(guī)劃。在200×200的柵格環(huán)境中，變換環(huán)境中障礙物的數(shù)量，如圖3所示，MUSV所在水域的障礙物數(shù)量不斷增加，在同樣的位置設(shè)置起始點(diǎn)和目標(biāo)點(diǎn)，輸出MUSV路徑仿真圖。從仿真圖中看出，在該算法下，MUSV依然能規(guī)劃出一條從起始點(diǎn)S到目標(biāo)點(diǎn)T的一條不碰路徑，說(shuō)明在障礙物數(shù)量變化的情形下，實(shí)現(xiàn)MUSV的路徑規(guī)劃也是可行的。

圖3　單船路徑環(huán)境仿真

3.4 會(huì)遇局面下的路徑仿真

會(huì)遇局面下的路徑仿真包括在目標(biāo)點(diǎn)之間的安全航行和與他船單船發(fā)生對(duì)遇、交叉和追越3種局面下的自主避障。

3.4.1 與來(lái)船對(duì)遇局面仿真在仿真實(shí)驗(yàn)下，MUSV與來(lái)船航向差范圍在(174°,180°]內(nèi)，當(dāng)與來(lái)船接近至設(shè)定距離為200m(當(dāng)目標(biāo)船與MUSV間的相對(duì)距離小于等于200m時(shí)，即認(rèn)為有碰撞危險(xiǎn)，需對(duì)危險(xiǎn)船采取避讓措施)，MUSV右轉(zhuǎn)，讓清他船后重新規(guī)劃最短路徑直至目標(biāo)T點(diǎn)。如圖5.4～5.6所示，假設(shè)他船航向保持不變，由右上起始點(diǎn)S駛往左下方目標(biāo)T，下方藍(lán)色軌跡線為MUSV航行軌跡，由左下起始點(diǎn)S往右上目標(biāo)點(diǎn)T行駛，中間的航跡段為MUSV繞過(guò)障礙物及讓清他船的過(guò)程圖。

對(duì)遇局面下MUSV避讓過(guò)程為：(1)圖4-1，MUSV與他船同時(shí)從起始點(diǎn)S出發(fā)相向而行，航行一段時(shí)間后MUSV與來(lái)船之間距離為200m，且航向差范圍在(174°,180°]內(nèi)；(2)圖4-2，根據(jù)航行規(guī)則，他船航向保持不變，MUSV為讓路船大幅右轉(zhuǎn)讓清他船；(3)圖4-3，MUSV在避讓成功后，重新規(guī)劃到目標(biāo)點(diǎn)T的最短路徑；(4)圖4-4，MUSV在避開(kāi)靜態(tài)障礙物及來(lái)船后，完成了從起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑仿真。

圖4　對(duì)遇局面仿真

通過(guò)以上3組仿真實(shí)驗(yàn)可以看出，MUSV與來(lái)船在對(duì)遇局面下，能成功避讓靜態(tài)障礙物及來(lái)船，并能在遵守海事無(wú)人艇避碰規(guī)則前提下，完成起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑規(guī)劃任務(wù)。

3.4.2與來(lái)船交叉局面仿真當(dāng)Δθ∈(67.5°,174°]時(shí)，視為交叉局面，MUSV屬于機(jī)動(dòng)性強(qiáng)的小艇船舶，與機(jī)動(dòng)性較差的大型船舶會(huì)遇時(shí)應(yīng)承擔(dān)讓路責(zé)任。他船為位于MUSV右舷時(shí)，屬于大角度交叉局面，MUSV為讓路船，當(dāng)兩船之間直線距離小于等于200m時(shí)，MUSV大幅度右轉(zhuǎn)從他船后方駛過(guò)讓清他船，然后重新規(guī)劃最短路徑。如圖5示，為MUSV與他船交叉局面下的航行軌跡，航行軌跡為藍(lán)色軌跡線，由左下起始點(diǎn)S往右上目標(biāo)點(diǎn)T行駛。

交叉局面下MUSV避讓過(guò)程為：(1)圖5-1，MUSV與他船同時(shí)從起始點(diǎn)S出發(fā)，為(67.5°,174°]的交叉局面，航行一段時(shí)間后，他船為位于MUSV右舷時(shí)；(2)圖5-2，他船航向航速保持不變，MUSV為讓路船與來(lái)船之間距離為200m，此時(shí)MUSV大幅度右轉(zhuǎn)從他船后方駛過(guò)讓清他船；(3)圖5-3，MUSV在避讓成功后，重新規(guī)劃到目標(biāo)點(diǎn)T的最短路徑；(4)圖5-4，MUSV在避開(kāi)靜態(tài)障礙物及來(lái)船后，完成了從起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑仿真。

圖5　交叉局面仿真

通過(guò)以上三組仿真實(shí)驗(yàn)可以看出，MUSV與來(lái)船在交叉局面下，能成功避讓靜態(tài)障礙物及來(lái)船，并能在遵守海事無(wú)人艇避碰規(guī)則前提下，完成起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑規(guī)劃任務(wù)。

3.4.3 追越仿真當(dāng)Δθ∈[0°,67.5°]時(shí)，視為追越局面發(fā)生，仿真實(shí)驗(yàn)中MUSV追越他船，根據(jù)MUSV在避碰規(guī)則，追越船舶有讓路責(zé)任，右轉(zhuǎn)從他船右舷駛過(guò)，而被追越船保速保向。MUSV通常速度較快，追越他船的常有發(fā)生局面，此時(shí)MUSV為讓路船，在本次追越過(guò)程中右轉(zhuǎn)，超過(guò)他船后重新規(guī)劃最短路徑，仿真結(jié)果如圖6所示，坐標(biāo)系中MUSV航行軌跡為長(zhǎng)軌跡線，他船航行軌跡為短軌跡線，同由左下方往右上方行駛。

追越局面下MUSV避讓過(guò)程為：(1)圖6-1，MUSV與他船同時(shí)從左下角起始點(diǎn)S出發(fā)，由于MUSV速度快，航行一段時(shí)間后MUSV與來(lái)船距離縮短，并與被追越船之間距離為200m，且航向差范圍在(174°,180°]內(nèi)；(2)圖6-2，根據(jù)航行規(guī)則，他船航向保持不變，MUSV右轉(zhuǎn)從他船右舷駛過(guò)；(3)圖6-3，MUSV重新規(guī)劃后到目標(biāo)點(diǎn)T的最短路徑后，與他船距離遠(yuǎn)大于200m；(4)圖6-4，MUSV在避開(kāi)靜態(tài)障礙物及來(lái)船后，完成了從起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑仿真。

圖6　追越局面仿真

通過(guò)以上3組仿真實(shí)驗(yàn)可以看出，MUSV與來(lái)船在追越局面下，能成功避讓靜態(tài)障礙物及來(lái)船，并能在遵守海事無(wú)人艇避碰規(guī)則前提下(MUSV從他船右舷駛過(guò))，完成起始點(diǎn)S到目標(biāo)點(diǎn)T的路徑規(guī)劃任務(wù)。

3.5 仿真結(jié)果分析

設(shè)置同樣的起始點(diǎn)S和目標(biāo)點(diǎn)T，對(duì)三種會(huì)遇局面(對(duì)遇、交叉、追越)分別進(jìn)行20次反復(fù)實(shí)驗(yàn)，得出如表3所示的統(tǒng)計(jì)數(shù)據(jù)。

通過(guò)分析上述USV的仿真實(shí)驗(yàn)結(jié)果，可以得出以下幾個(gè)結(jié)論：

(1)SAPSO算法迭代中只涉及初等運(yùn)算，運(yùn)算量少，速度快；

(2)起始點(diǎn)和目標(biāo)點(diǎn)之間的距離越遠(yuǎn)、障礙物越多，MUSV規(guī)劃所需時(shí)間較長(zhǎng)；

(3)SAPSO算法運(yùn)算收斂于最優(yōu)解的幾率高，能完成起始點(diǎn)到目標(biāo)點(diǎn)的路徑規(guī)劃任務(wù)；

(4)系統(tǒng)通過(guò)判斷MUSV與靜態(tài)障礙物是否有碰撞危險(xiǎn)采取避碰決策，能根據(jù)靜態(tài)障礙物的分布位置規(guī)劃出最短路徑。

(5)在更為復(fù)雜的動(dòng)態(tài)障礙物環(huán)境中，MUSV能根據(jù)與他船的會(huì)遇態(tài)勢(shì)做出符合避碰規(guī)則的規(guī)劃，自身作為讓路船調(diào)整航向?qū)崿F(xiàn)避碰。

表3　仿真數(shù)據(jù)統(tǒng)計(jì)分析

4　結(jié)語(yǔ)

本文采用SAPSO求解MUSV最優(yōu)路徑的問(wèn)題，取得了較好的效果。通過(guò)在同一環(huán)境中將他船的行動(dòng)融入到動(dòng)態(tài)環(huán)境模型中，實(shí)現(xiàn)了在對(duì)遇、交叉和追越三種局面下，MUSV從起點(diǎn)到達(dá)目標(biāo)點(diǎn)自動(dòng)實(shí)施安全避碰決策的仿真實(shí)驗(yàn)。仿真結(jié)果驗(yàn)證了本文提出的算法可為實(shí)現(xiàn)MUSV在執(zhí)行任務(wù)中與其他船舶發(fā)生對(duì)遇、交叉、追越局面下的自主避障，也可在更為復(fù)雜的動(dòng)態(tài)障礙物環(huán)境中根據(jù)與他船的會(huì)遇態(tài)勢(shì)做出符合避碰規(guī)則的規(guī)劃，自動(dòng)讓路調(diào)整航向?qū)崿F(xiàn)避碰。

[1]ShowalterS,ManleyJ.Legalandengineeringchallengestowidespreadadoptionofunmannedmaritimevehicles[C]//ProceedingsofOCEANS2009,MTS/IEEEBiloxi-MarineTechnologyforOurFuture:GlobalandLocalChallenges.IEEE, 2009: 1-5.

[2]吳博, 文元橋, 肖長(zhǎng)詩(shī). 一種內(nèi)河海事無(wú)人艇路徑規(guī)劃算法設(shè)計(jì)與仿真[J]. 計(jì)算機(jī)工程與應(yīng)用, 2013, 49(14): 241-246.

WuBo,WenYuanqiao,XiaoChangShi.Aninlandrivermaritimeunmannedvehiclepathplanningalgorithmdesignandsimulation[J].ComputerEngineeringandApplication, 2013, 49(14): 241-246.

[3]王雨迪. 基于自抗擾控制算法的水面無(wú)人艇航向自動(dòng)舵設(shè)計(jì)[D]. 大連: 大連海事大學(xué), 2014.

WangYudi.DesignofCourseAutopilotofUnmannedSurfaceVesselBasedontheImmunityControlAlgorithm[D].Dalian:DalianMaritimeUniversity, 2014.

[4]楊煒?lè)? 水面無(wú)人艇的建模與運(yùn)動(dòng)特性仿真[D]. 大連: 大連海事大學(xué), 2013.

YangWeifan.UnmannedSurfaceVehicleModelingandMtionSimulation[D].Dalian:DalianMaritimeUniversity, 2013.

[5]董早鵬. 無(wú)人艇運(yùn)動(dòng)模糊控制技術(shù)研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2013.

DongZaopeng.TheResearchofFuzzyControlTechnologyofUnmannedSurfaceVessel[D].Harbin:HarbinEngineeringUniversity, 2013.

[6]莊佳園, 蘇玉民, 廖煜雷, 等. 基于航海雷達(dá)的水面無(wú)人艇局部路徑規(guī)劃[J]. 上海交通大學(xué)學(xué)報(bào), 2012, 46(9): 1371-1375.

ZhuangJiayuan,SuYumin,LiaoYulei,etal.ThelocalpathplanningofunmannedsurfacevesselbasedontheMarineradar[J].JournalofShanghaiJiaotongUniversity, 2012,46(9): 1371-1375.

[7]陳超, 唐堅(jiān). 基于可視圖法的水面無(wú)人艇路徑規(guī)劃設(shè)計(jì)[J]. 中國(guó)造船, 2013, 54(1): 129- 135.

ChenChao,TangJian.Thepathplanningdesignforunmannedsurfacevesselbasedonthemethodofvisibilitygraph[J].JournalofChinaShipbuilding, 2013, 54(1): 129-135.

[8]饒森. 水面無(wú)人艇的全局路徑規(guī)劃技術(shù)研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2007.

RaoSen.ResearchoftheGlobalPathPlanningforUnmannedSurfaceVessel[D].Harbin:HarbinEngineeringUniversity, 2007.

[9]王娟娟, 曹凱. 基于柵格法的機(jī)器人路徑規(guī)劃[J]. 農(nóng)業(yè)裝備與車輛工程, 2009, 47(4):14-17.

WangJuanjuan,CaoKai.TheRobotpathplanningbasedonthegridmethod[J].JournalofAgriculturalEquipmentandVehicleEngineering, 2009, 47(4): 14-17.

[10]朱慶保, 張玉蘭. 基于柵格法的機(jī)器人路徑規(guī)劃蟻群算法[J]. 機(jī)器人, 2005(2): 132-136.

ZhuQingbao,ZhangYulan.Therobotpathplanningofantcolonyalgorithmbasedongridmethod[J].Robot, 2005(2): 132-136.

[11]于紅斌, 李孝安. 基于柵格法的機(jī)器人快速路徑規(guī)劃[J]. 微電子學(xué)與計(jì)算機(jī), 2005(6): 98-100.

YuHongbin,LiXiaoan.Robotfastpathplanningbasedonthegridmethod[J].JournalofMicroelectronicsandComputer, 2005(6): 98-100.

[12]Lozano-PerezT,WesleyM.Analgorithmforplanningcollision-freepathsamongpolyhedralobstacles[J].CommunicationsoftheACM, 1979(5): 436-450.

[13]劉金義, 劉爽.Voronoi圖應(yīng)用綜述[J]. 工程圖學(xué)學(xué)報(bào), 2004(2): 125-132.

LiuJinyi,LiuShuang.Voronoidiagramapplicationreview[J].JournalofEngineeringGraphics, 2004(2): 125-132.

[14]趙永利. 基于Voronoi圖的機(jī)器人局部路徑規(guī)劃[D]. 南京: 南京理工大學(xué), 2006.

ZhaoYongli.RobotLocalPathPlanningBasedonVoronoiDiagram[D].Working:WorkingUniversityofScienceandTechnology, 2006.

[15]盧艷爽. 水面無(wú)人艇路徑規(guī)劃算法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2010.

LuYanshuang.ResearchonthePathPlanningAlgorithmforUnmannedSurfaceVessel[D].Harbin:HarbinEngineeringUniversity, 2010.

責(zé)任編輯陳呈超

A Hybrid Optimization Algorithm of Simulated Annealing andParticleSwarmforUnmannedSurfaceVesselPathPlanning

ZHENGJia-Chun1,WUJian-Hua2,MAYong2,LONGYan1

(1.JimeiUniversity,Xiamen361021,China; 2.WuhanUniversityofTechnology,Wuhan430063,China)

Withtheexplorationanddevelopmentofmarineresources,UnmannedSurfaceVessel(USV)hasbecomeahotresearchtopic.PathplanningisoneofthekeytechnologiesofUSVautonomousnavigation,anditscoretechnologyisPlanningAlgorithmPath(PPA).Thispaperanalysesandstudiesseveralcommonpathplanningalgorithms,discussestheiradvantagesanddisadvantages.TheParticleSwarmOptimization(PSO)algorithmandSimulatedAnnealing(SA)algorithmareourmainresearchobject,anditisinsufficientbyusingthePSOalgorithmorSAalgorithmalonefortheexistenceofunmannedsurfacevehiclepathplanning.InordertoimprovethesafetyofUSVsailing,tosolvethetraditionalunmannedboatwithoutconsideringthecollisiondangercausedbythecomingandgoingvesselsduringthevoyage,thehybridpathplanningalgorithm(HybridofSimulatedAnnealingandParticleSwarmOptimizationAlgorithm,HSAPSO)combiningSAalgorithmandPSOalgorithmisproposed.TheSAPSOusingthealgorithmcharacteristicsofconvergenceandeasytojumpoutoflocaloptimum,combinedwiththecollisionregulations,itcanbeeasyimplementationtheoptimalpathplanningofUSVinthethreeencountersituationsofheadon,crossingandovertaking,especialforMarineUnmannedSurfaceVessel(MUSV).ThesimulationresultsshowthattheSAPSOalgorithmproposedinthispaperenabletheMUSVtodoautomaticcollisionavoidancebehaviorincomplexwaterconditions,andthegivenpathplanningisfeasibleandeffective.WhichcanprovidesafeguardfortheMUSV’ssafenavigationandsuccessfulimplementationofthetask.

hybridofsimulatedannealingandparticleswarmoptimizationalgorithm；marineunmannedsurfacevessel；optimalpathplanning;collisionavoidance

國(guó)家自然科學(xué)基金項(xiàng)目(51309186)“復(fù)雜海況下的海事無(wú)人艇路徑規(guī)劃研究”；福建省科技計(jì)劃重點(diǎn)項(xiàng)目(2014H0036)；福建省自然科學(xué)基金項(xiàng)目(2013J01203)資助

2015-09-29；

2016-01-20

鄭佳春(1965-)，男，副教授。E-mail:zheng_xxgc@163.com

S948;S943

A

1672-5174(2016)09-116-07

10.16441/j.cnki.hdxb.20150340

SupportbytheNationalNaturalScienceFundProjectofChina(51309186) “ComplexSeaConditionofMaritimeUnmannedCraftPathPlanningResearch”,TheKeyProjectofScienceandTechnologyPlanofFujianProvince(2014H0036);FujianProvinceNaturalScienceFundProject(2013J01203)