基于改進粒子群算法的海流環境下無人水面艇路徑規劃

白響恩, 孫廣志, 徐笑鋒

(上海海事大學商船學院,上海 201306)

0 引 言

隨著人工智能技術的不斷發展和海上作業需求的日益增長,無人水面艇(unmanned surface vessel,USV)獲得了世界范圍內的廣泛重視。USV由于其靈活性強、成本低、環境適應性強,在海洋采樣和環境檢測、海岸巡邏和救援、資源勘探等領域發揮著重要作用[1]。然而,USV在執行任務時面臨的最大挑戰是安全導航[2],即在復雜的海洋環境中為USV規劃出一條高質量且無沖突的路徑,使船舶安全抵達目的地。為保證USV能夠安全地執行任務,USV的路徑規劃問題變得越來越重要。

目前路徑規劃按照對環境信息的掌握程度可分為全局路徑規劃和局部路徑規劃[3]。全局路徑規劃就是在給定的空間內根據規劃目標和任務要求找到一條從起點到終點的路徑。大量的文獻將全局路徑規劃描述為一個單目標優化問題,規劃的目標分別為路徑長度、能耗、路徑平滑度、安全性等。龍洋等[4]以路徑長度為適應性函數,采用混合細菌覓食算法搜索USV的最短路徑。LEE等[5]提出一種考慮環境影響和航向角的最優路徑規劃算法,目標是找到一條能耗最少的路徑。然而,能耗、路徑平滑度和安全性都是USV路徑規劃的關鍵目標。USV在航行期間的能耗決定了USV的續航性,影響航運成本;路徑平滑度影響USV的機動性;安全性是確保USV順利執行任務的基本要求。因此,在進行USV路徑規劃時必須考慮環境因素和多目標優化問題。

粒子群(particle swarm optimization, PSO)算法是一種基于群體智能的進化算法,具有簡單、易于實現等優點[6],常被用于求解路徑規劃問題,但存在兩個缺點:隨著不斷迭代種群多樣性會下降,算法容易產生過早收斂的問題;算法容易陷入搜索停滯狀態,難以跳出局部最優解。為此,許多學者對PSO算法進行改進:周新宇等[7]提出了一種基于精英反向學習(elite opposition-based learning, EOBL)的PSO算法(記為EOBL-PSO算法),極大地提升了算法的收斂精度;巫光福等[8]為全局最優粒子的速度添加干擾量,并引入非線性慣性權重,有效地提升了算法的收斂速度。除了通過改進PSO算法中的參數提升算法的性能,還有許多學者將PSO算法與其他智能優化算法進行融合:鄭佳春等[9]將模擬退火(simulated annealing, SA)算法與PSO算法相結合(記為SA-PSO算法)來求解USV的路徑規劃問題;曹夢龍等[10]將PSO算法與灰狼算法融合用于機器人路徑規劃。

基于上述文獻分析,本文以路徑長度、能耗和路徑平滑度為優化目標,構建USV的多目標路徑規劃模型,提出一種基于EOBL的自適應PSO算法(記為EOBL-APSO算法),在有海流和障礙物影響的環境中進行USV路徑規劃,并對模型的有效性進行驗證。

1 USV在海流環境下的運動模型

為提高算法的計算效率[11],只考慮USV在水平面上的運動狀態。參考大量關于海流對USV運動影響的文獻,通過疊加多個黏性Lamb渦流,建立時變分布的二維海洋環流模型[12]。僅考慮海流運動的空間變化,故假定海流在USV航行期間在區域內的運動是穩定的。該時變海流速度場的函數表達式如下:

式中:x和y分別為二維空間區域內任意一點的橫坐標和縱坐標;xc,0和yc,0分別為渦流中心的橫坐標和縱坐標;H為渦流強度;δ為渦流半徑;vc,x、vc,y分別為渦流在x和y軸方向上的速度分量。

假設USV處于圖1所示的海流環境中,USV的速度為v,航向角為φ,則USV在x和y軸方向上的速度分量vx和vy分別為

圖1 USV所處的海流環境及路徑示意圖

vx=vcosφ+vc,x

(4)

vy=vsinφ+vc,y

(5)

式(4)和(5)可以反映海流環境下USV的運動狀況。為使USV能夠正向運動到目的地,USV的速度必須大于零,即vx>0,vy>0。圖1中,路徑起點為S,路徑終點為G,Sk(k=1,2,3,4)為起點S與終點G之間的路徑點。

2 USV的路徑規劃模型

2.1 環境和路徑描述

在復雜的海洋環境下尋找一條能避開障礙物并滿足約束條件的最優路徑是USV路徑規劃的主要任務。通常復雜的海洋環境主要由風浪流、島嶼、礁石以及人工建設的海洋基礎設施等組成。本文主要研究海流對USV的影響,為此模擬了2種海流環境:固定海流環境和時變海流環境。將島嶼、礁石等不規則障礙物抽象為圓,因此環境主要由海流和圓形的障礙物構成。如圖1所示:從起點S到終點G的路徑點依次為S,S1,…,G;黑色虛線為等間距線。每個路徑點都落在等間距線上,這樣就可以預先得到每個路徑點的橫坐標,由此只需求解滿足規劃目標的路徑點的縱坐標。

2.2 多目標優化函數

為避免各優化目標之間的沖突,給每個優化目標賦予相應的標準化因子。USV路徑規劃的多目標函數為

z=ω1L+ω2E+ω3F+C

(6)

式中:L為路徑長度,E為能耗,F為路徑平滑度,這3個目標函數值的量綱均為1;ω1、ω2、ω3分別為路徑長度、能耗、路徑平滑度的標準化因子,通常是根據USV的工作環境和實際經驗設定的;C為碰撞指標。z最小時對應的路徑為全局最優路徑。

2.2.1 路徑長度計算

(7)

式中:n為路徑點的數目;xk、yk分別為第k個路徑點的橫坐標和縱坐標。

2.2.2 路徑平滑度計算

如圖2所示,Sk、Sk-1和Sk+1分別為USV的當前路徑點、上一個路徑點和下一個路徑點,其坐標分別為(xk,yk)、(xk-1,yk-1)和(xk+1,yk+1),則路徑段的角度θk的計算式為

圖2 路徑段角度

(8)

因此,路徑平滑度的計算式為

2.2.3 能耗

USV在航行過程中的能耗受到海流的影響:當USV的航向與海流方向保持一致時,USV能獲得來自海流的推進力從而能耗降低;當USV的航向與海流方向相反時,USV需要消耗大量的能量來克服海流的阻力從而能耗增加。本文在研究海流對USV能耗的影響時將重點放在USV的速度變化上。在計算USV的能耗時,先根據USV在海流環境下的速度v′和每段路徑的長度lk計算出每段路徑的航行時間tk,再參考文獻[13]計算每段路徑的能耗Ek,最后求和得到整條路徑的能耗E。

式中:P為USV發動機的額定功率。

2.2.4 碰撞指標

C是用來檢測USV是否與障礙物碰撞的指標,用于確保獲得的可行路徑與障礙物保持一定的安全距離。針對傳統PSO算法規劃出的路徑存在緊貼障礙物的問題,考慮USV自身大小,在路徑規劃中規定USV處于半徑為R的安全區域內(見圖3),在此安全區域內不得含有任何障礙物[14]。C的計算式如下:

圖3 USV的安全區域

式中:di為路徑與第i個障礙物之間的距離。若di≤R,則USV的安全區域受到障礙物的侵犯,此時C被賦值為無窮大,規劃路徑被視為不可行路徑。

3 PSO算法

PSO算法是一種基于群體的啟發式優化算法[15]。假設在D維空間內存在N個粒子,粒子i在D維空間內的位置和速度分別為xi=(xi,1,xi,2,…,xi,D)和vi=(vi,1,vi,2,…,vi,D)。在迭代過程中,由粒子i的最優位置pi,best=(pi,1,pi,2,…,pi,D)和群體的最優位置gbest=(pg,1,pg,2,…,pg,D)決定粒子i下一步的運動。粒子i的速度和位置的更新公式為

式中:i=1,2,…,N;d=1,2,…,D;t為迭代次數;w為慣性權重;r1、r2為[0,1]內的隨機數;c1、c2為加速因子;vi,d,t、xi,d,t、pi,d,t分別為第t次迭代中粒子i的速度、位置、最優位置的第d維分量;pg,d,t為第t次迭代中群體最優位置的第d維分量。

4 EOBL-APSO算法

設計一種自適應慣性權重來平衡PSO算法的全局和局部搜索能力;采用EOBL策略生成由精英個體產生的反向解組成的新種群,提高種群多樣性,降低算法陷入局部最優的概率,提高算法精度。

4.1 自適應慣性權重

w=

(11)

4.2 EOBL策略

PSO算法的不斷迭代會降低種群的多樣性,故引入EOBL策略來產生新的粒子群,增加種群的多樣性和搜索能力。反向學習是TIZHOOSH基于現實世界中事物之間的對立關系提出的解決優化問題的有效方法。對于沒有先驗知識的優化問題,利用相反的候選解比隨機解達到全局最優的概率更高。在PSO算法迭代過程中,如果同時檢測到當前解和相反解,則選擇更好的解作為預測解,增強算法脫離局部最優解的能力,提高算法的搜索效率。反向學習的定義如下:

定義1反向數。假設一個實數x∈[a,b]且x∈R,則x的反向數定義為

ad=minxi,d,bj=maxxi,d

本文在改進PSO算法中融入EOBL策略來提升改進算法的性能,在每次迭代過程中將目標函數值最小的粒子作為精英個體,并基于該精英個體進行反向學習,生成由精英個體產生的反向解組成的新種群,參與進化競爭。

4.3 EOBL-APSO算法步驟

步驟1創建海域環境地圖并初始化環境參數以及USV的起始位置和目標位置。

步驟2初始化粒子的位置和速度,設置參數值,包括種群規模N、空間維度D、最大迭代次數Tmax、最大慣性權重wmax、最小慣性權重wmin、加速因子c1和c2。

步驟3根據式(6)計算粒子當前的目標函數值,按照目標函數值劃分粒子,并根據式(11)求得每個粒子對應的慣性權重。

步驟4根據式(9)和(10)更新粒子的速度和位置,根據式(6)計算粒子當前的目標函數值,選擇目標函數值最小的粒子作為精英個體,采用EOBL策略生成精英個體的多個反向解組成新的種群,計算新種群中粒子的目標函數值。

步驟5比較精英個體生成的種群與其父代種群的目標函數值,選擇更優的個體組成新種群,從當前種群中確定新的全局最優值。

步驟6判斷算法是否達到最大迭代次數:若滿足則停止搜索,輸出USV的全局最優路徑;否則返回步驟3繼續迭代。

5 仿真結果與分析

5.1 EOBL-APSO算法的性能測試

為評估EOBL-APSO算法的求解精度和收斂性,采用4個標準測試函數(見表1),并與線性遞減慣性權重(linear decreasing inertia weight, LDIW)PSO算法[16](記為LDIW-PSO算法)、SA-PSO算法[17]和EOBL-PSO算法[7]進行比較。所有算法的參數設置相同:N=50,w∈[0.40,0.95],c1=c2=2,Tmax=500。

表1 標準測試函數

為避免由偶然性帶來的結果偏差,對每個標準測試函數分別進行50次實驗,統計并計算出最優值、平均值和標準差,結果見表2。

表2 測試函數實驗統計結果

由表2可知:對于這4個標準測試函數,本文所提出的EOBL-APSO算法的最優值優于其他算法的最優值,說明EOBL-APSO算法具有更好的求解精度和收斂性;EOBL-APSO算法的平均值和標準差也優于其他算法,說明EOBL-APSO算法具有更好的穩定性。

5.2 多目標標準化因子的確定

在多目標優化函數中,L、E、F具有不同的數量級。為平衡它們對路徑選擇的影響,必須設置合理的標準化因子。本文采用文獻[18]的方法確定各單目標的標準化因子。假定得到的路徑都是無碰撞路徑,即C=0。分別將ω1、ω2、ω3設為1、0、0,得到單目標L下的最優值Lmin=17.04;分別將ω1、ω2、ω3設為0、1、0,得到單目標E下的最優值Emin=90.96;分別將ω1、ω2、ω3設為0、0、1,得到單目標F下的最優值Fmin=26.14?；贚min計算各目標的標準化因子,得到ω1=Lmin/Lmin=1,ω2=Lmin/Emin=0.19,ω3=Lmin/Fmin=0.65。根據得到的各目標標準化因子,計算得到多目標下L、E、F的最優值分別為17.12、17.91和17.43。這3個目標函數值具有相同的數量級且差異很小,有利于路徑綜合評估。

5.3 海流環境下的路徑規劃仿真

選擇2種海流環境進行模擬并與PSO算法進行比較分析。第一種為固定海流環境,由隨機障礙物和具有固定速度和方向的海流組成;第二種為時變海流環境,由多個黏性Lamb渦流疊加形成的海流和隨機障礙物組成。本文參數都為無量綱量;海域大小為20×10,橫坐標和縱坐標范圍分別為[-10,10]和[-5,5];海流以帶箭頭的線段表示,箭頭方向為海流的方向,線段長短表示海流的大小;黑色圓為障礙物。

5.3.1 固定海流環境

海流速度為2,海流方向與x軸方向的夾角為30°。圓形障礙物的集合為{((xobs,yobs),robs)},包括((-8.8,-2.5),1.3)、((0,-2.0),1.3)、((4.0,2.3),1.5)、((-4.0,-2.3),1.5)、((7.0,-2.3),1.4),其中(xobs,yobs)和robs分別為障礙物的圓心坐標和半徑。USV的速度為2,起點為(-5.0,-4.0),終點為(8.9,4.0) ,USV發動機的額定功率P=4。N=50,w∈[0.40,0.95],c1=c2=2,Tmax=200。

圖4給出了2種算法在固定海流環境下的路徑規劃結果。由圖4和表3可以看出:2種算法在固定海流環境下都能規劃出一條無碰撞的路徑,并且由于設定了USV的安全區域,規劃的路徑都能夠遠離障礙物,保證了航行安全;EOBL-APSO算法的搜索性能較優,規劃出的路徑在路徑長度、能耗和路徑平滑度上都優于PSO算法。

表3 2種算法在固定海流環境下規劃出的最優路徑評價指標對比

圖4 2種算法在固定海流環境下的路徑規劃結果

5.3.2 時變海流環境

時變海流由4個黏性Lamb渦流疊加形成,渦流強度H=20,渦流半徑δ=1。USV起點為(-9.5,4.0),終點為(4.0,-3.2)。圓形障礙物設置及其他參數不變。

圖5給出了2種算法在時變海流環境下的路徑規劃結果。由圖5和表4可以看出:2種算法在時變海流環境下都能規劃出一條無碰撞且遠離障礙物的安全路徑;EOBL-APSO算法規劃出的路徑能夠較好地沿著海流的方向,因此在能耗上優于PSO算法,且路徑更平滑,路徑長度也優于PSO算法。從整體仿真結果看,本文對PSO算法的改進具有明顯的效果,改進算法能夠更好地對多目標進行平衡,從而得到更好的全局最優路徑。

表4 2種算法在時變海流環境下規劃出的最優路徑評價指標對比

圖5 2種算法在時變海流環境下的路徑規劃結果

5.4 實際海域環境的仿真

將本文所提出的方法應用于實際海域環境下的路徑規劃。選取寧波舟山港條帚門航道附近的海域構建仿真環境?；谠摵Ｓ虻娜暗貓D構建200×200像素的海域環境模型,并且利用Lamb渦流模型構建該海域的海流場。

圖6顯示了該海域的路徑規劃結果:路徑與障礙物保持一定的安全距離;規劃路徑避開了逆流,順著海流的方向,減少了USV的能耗;兼顧了其他優化目標,滿足USV的全局路徑規劃要求。

圖6 條帚門航道附近海域的路徑規劃結果

6 結 論

針對海流環境下無人水面艇(USV)的多目標路徑規劃問題,綜合考慮了路徑長度、能耗和路徑平滑度等3個優化目標以及障礙物和海流的影響,構建了USV多目標路徑規劃模型,并且提出了一種改進的粒子群(PSO)算法進行求解。在2種不同的海流環境以及實際海域環境下進行路徑規劃,結果表明改進算法能夠優化多個目標,規劃出一條最優路徑。通過與不同算法的比較,驗證了改進算法具有良好的魯棒性和適用性。