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

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

?

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

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

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

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

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

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

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

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

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

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

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

(1)

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

(2)建立柵格坐標(biāo)系：以左上角為坐標(biāo)原點，水平向右橫坐標(biāo)增加為X軸，垂直向下縱坐標(biāo)增加為Y軸。同時采用序號法和直角坐標(biāo)法相結(jié)合來表示柵格。每個柵格的位置用該柵格的中心點坐標(biāo)來描述，用(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。

柵格用序號的表示以左上角為坐標(biāo)的原點，水平向右，自上到下依次對每個柵格進(jìn)行編號，編號的順序為1，2，3，…。柵格位置坐標(biāo)(x，y)與柵格編號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)運動，則障礙物可視為整體障礙區(qū)。為了航行安全和避免算法出現(xiàn)局部死區(qū)，將障礙區(qū)作如下處理：1)如果劃分區(qū)域內(nèi)的障礙物不滿1個柵格，按1個柵格表示；2)將障礙物內(nèi)的空凹部分與該障礙物連成1個整體；3)如果2個障礙物間的距離較近，則把這兩個障礙物連成為1個障礙物。在二維柵格坐標(biāo)(x,y)存在障礙物時，B(x，y)采用表示：

(5)

式(5)中，0

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

2　路徑規(guī)劃算法

2.1 問題描述

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

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

(6)

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

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

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

D≥dmin。

(7)

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

(8)

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

(9)

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

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

SAPSO算法描述如下：

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

t0=f(pg)/ln5。

(10)

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

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

(11)

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

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)計算各個微粒新的目標(biāo)值，更新各個微粒的pi值及群體的pg值；

(e)進(jìn)行退溫操作，退火方式按式(14)進(jì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ù)n=50，設(shè)定最大迭代次數(shù)MaxDT=50，搜索空間維數(shù)D=8。

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

3.1 仿真環(huán)境

表1　仿真條件

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

注：MUSV數(shù)據(jù)以國內(nèi)自主研發(fā)的第一艘無人巡航艇為例；它船數(shù)據(jù)來源于《海港總平面設(shè)計規(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)原點O，橫坐標(biāo)、縱坐標(biāo)每格均代表100m。在柵格環(huán)境中隨機(jī)散布仿真靜態(tài)障礙物，在MATLAB界面上顯示，輸出如圖2所示，圖中圓圈T代表無人艇巡航的目的地。

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

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

3.3 單船路徑仿真

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

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

3.4 會遇局面下的路徑仿真

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

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

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

圖4　對遇局面仿真

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

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

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

圖5　交叉局面仿真

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

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

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

圖6　追越局面仿真

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

3.5 仿真結(jié)果分析

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

通過分析上述USV的仿真實驗結(jié)果，可以得出以下幾個結(jié)論：

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

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

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

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

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

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

4　結(jié)語

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

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

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

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

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

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

[4]楊煒帆. 水面無人艇的建模與運動特性仿真[D]. 大連: 大連海事大學(xué), 2013.

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

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

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

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

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

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

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

[8]饒森. 水面無人艇的全局路徑規(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ī), 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é)報, 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]盧艷爽. 水面無人艇路徑規(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

國家自然科學(xué)基金項目(51309186)“復(fù)雜海況下的海事無人艇路徑規(guī)劃研究”；福建省科技計劃重點項目(2014H0036)；福建省自然科學(xué)基金項目(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)