基于改進蟻群算法的全局船舶路徑規劃方法

黃國良,周毅,鄭坤,李萌,蒙學昊

(中海油能源發展股份有限公司采油服務分公司,天津 300452)

路徑規劃算法性能的優劣將直接影響船舶航行的安全和效率。蟻群算法作為最常用的元啟發式算法之一,在路徑規劃問題上取得了不錯的效果,但仍然存在若干缺陷[1]:①容易陷入局部最優,且很難自主跳出;②初始信息素濃度分配方式和信息素更新規則沒有針對性,不必要的探索會降低算法的收斂性。針對蟻群算法的兩個主要問題,學者們提出了各種改進方法[2-8],但目前在船舶路徑規劃問題的求解中,普遍存在算法規劃路徑質量不高、收斂性與隨機性無法保持平衡的問題。因此,考慮結合船舶路徑規劃的任務需求,采用啟發式和融合式策略對蟻群算法進行改進。另外,將路徑長度、安全性和平滑性約束函數融入至信息素更新規則,以保障船舶航行路徑的安全。

1 蟻群算法數學模型

蟻群算法通過信息素濃度與距離啟發函數計算螞蟻選擇路徑的概率。假設蟻群中螞蟻的數量為m,任意兩路徑點間的信息素數值相同。在n時刻,螞蟻l=1,2,3,…,m從當前路徑點i選擇任意路徑點j的概率為

(1)

式中:κ和λ分別是信息啟發式因子和期望值啟發式因子,Hij是距離啟發函數,等于兩路徑點間歐式距離的倒數,Dl為路徑點i下一時刻可選擇的路徑點集合。Iij為路徑點i、j間的信息素數值。

(2)

2 基于人工勢場的改進蟻群算法

2.1 引入人工勢場法

由于人工勢場法具有初始導向性強、計算便捷和魯棒性較強的特點,將人工勢場法引入蟻群算法,提高蟻群算法的初始迭代速度。由于引力勢場函數與本船到目的地的距離G的平方成正比,當G較大時會導致該點的引力值趨于無窮大,增加本船與礙航物發生碰撞的風險。為避免船舶與礙航物發生碰撞事故,設定引力勢場函數影響分界線R。當G≤R時,使引力勢場值與G的平方成正比;當G>R時,使引力勢場值與G成正比,從而降低引力勢場的影響范圍。引力勢場函數改進如下。

(3)

式中:Ka為引力勢場系數。

2.2 偽隨機狀態選擇概率的改進

傳統蟻群算法以路徑中信息素濃度和啟發式信息函數的乘積作為路徑選擇概率。這種選擇方式僅注重對新路徑的搜索,常忽略對當前優秀路徑的選擇,易增加算法的時間復雜度。為此,引入隨機數r與固定參數r0改進算法的選擇概率。當r≤r0時,螞蟻將啟發式信息函數和信息素濃度乘積作為評價值,并選擇使其數值最大的路徑,即強化當前路徑的選擇;當r>r0時,選擇基本蟻群算法的策略作為選擇概率,即探索新路徑。改進后的狀態選擇概率公式可使開發當前路徑和探索新路徑達到平衡,不僅能降低探索新路徑產生的額外時間開銷,還可避免過早的陷入局部最優。改進后的轉移概率為

(4)

式中:r∈[0,1]為隨機數;r0∈[0,1]為固定參數,r和r0的具體取值由人為設定。

2.3 信息素更新規則的改進

傳統蟻群算法更新信息素時僅考慮了路徑長度,而在解決實際船舶路徑規劃問題時,不僅要考慮路徑長度,還要考慮路徑安全性和路徑平滑程度。因此,在信息素更新規則公式中加入路徑的長度、安全性和平滑性目標約束,修改后的信息素公式更新為

(5)

式中:ω1、ω2、ω3是約束函數的權重系數;Il是螞蟻l訪問過的節點;Fl、Fs、Fm分別為路徑長度、路徑安全性和路徑平滑度約束函數。

(6)

式中:t是路徑上節點的總數量;d(i,i+1)為節點i到節點i+1的距離;Si,i+1為前節點與下一節點的路徑安全性程度;θ(i,i+1)為節點i和節點i+1之間的轉向角度。

Si,i+1=

(7)

(8)

式中:SDA(i,i+1)為在路徑點i和i+1之間的船舶安全會遇距離。

3 算法實現

3.1 靜態路徑規劃算法的實現

本文提出的混合蟻群靜態路徑規劃算法(hybrid ant colony static algorithm,HACSA)具體實施步驟如下。

1)步驟1,利用柵格法建立船舶航行環境模型,確定船舶起始點、目的地和礙航物位置。

2)步驟2,對混合蟻群算法中的參數設置初始值,比如,螞蟻數量m,信息素揮發系數δ,初始信息素強度Q,引力勢場系數Ka,人工勢場影響系數R等。

3)步驟3,構建改進蟻群算法禁忌表并對其進行初始化設置。

4)步驟4,根據公式計算各路徑點的信息素濃度。

5)步驟5,根據公式計算船舶所受合力的大小及方向,據公式計算當前位置的轉移概率并確定下一步的移動位置j,并將該位置加入至禁忌表。

6)步驟6,更新完禁忌表后,判斷螞蟻是否到達目的地,若未抵達目的地則繼續執行步驟5,反之,則記錄該螞蟻的路徑長度和路徑信息并進入到步驟7。

7)步驟7,令螞蟻索引l=l+1,并判斷l是否等于m,若不相等則返回步驟4,若相等則更新信息素濃度。船舶碰撞檢測見圖1。

圖1 船舶碰撞檢測

3.2 動態路徑規劃算法的實現

船舶動態路徑規劃算法在靜態路徑規劃的基礎上融入了碰撞危險計算、會遇態勢識別和避碰行動采取。假設任意目標船與本船有個安全會遇半徑Dsafe=SDA,若本船和目標船的船舶最近會遇距離Dcpa

(9)

根據公式判斷出本船與目標船之間的狀態,如果有碰撞可能且具有避讓責任時,本船應采取合適的避讓措施。為簡化運算,本文均采用右轉向實現避讓。在單船會遇情況下,已知本船與目標船的安全圓有2個切點,切點Rp(xRp,yRp)和切點Lp(xLp,yLp),見圖2。

圖2 船舶避讓措施

本文將安全圓的左切點作為船舶避讓導向點,左右切點按照式計算。

(10)

(y-yt)(y-y0)=-(x-xt)(x-x0)

(11)

式中:(x,y)為待求切點坐標;(x0,y0)為本船坐標;(xt,yt)為目標船坐標。

在多船會遇情況下,根據目標船個數分別計算出本船與目標船的左切點和右切點對應的角度。當前局面下存在3個目標船,見圖3。

圖3 多船避讓措施

聯立目標船安全圓公式和可求得本船與目標船的左右切點坐標,針對多目標船會遇局面,重復利用公式-計算出本船與各目標船的左切點角度分別為θAL、θBL、θCL。將選擇目標船切點角度最小的左切點作為避讓導向點,而切點角度θgoal的選擇方法如式所示。

θgoal=min{θAL,θBL,θCL}

(12)

基于上述分析,提出混合蟻群動態路徑規劃算法(hybrid ant colony dynamic algorithm,HACDA),算法具體實施步驟如下。

1)步驟1,采用HACSA規劃出一條初始航行路徑,船舶將沿初始路徑航行。

2)步驟2,計算Tcpa、Dcpa和目標船相對運動方位θT。

3)步驟3,使用公式判斷本船與目標船之間是否存在碰撞危險,若不存在,本船將沿初始路徑繼續航行;反之,則進入步驟5。

4)步驟4,依據θT值判斷本船是否為讓路船,若本船不是讓路船,本船將沿初始路徑繼續航行,若本船為讓路船,判斷Dcpa≤Dsafe和Tcpa≤T是否同時成立。

5)步驟5,若Dcpa≤Dsafe和Tcpa≤T未同時成立,本船將沿初始路徑繼續航行。

6)步驟6,若Dcpa≤Dsafe和Tcpa≤T同時成立,則計算出本船與目標船的左切點角度θAL、θBL、θCL,利用公式求得θgoal,并在開始滿足Dcpa≤Dsafe和Tcpa≤T時采取轉向工作。

7)步驟7,本船轉向避讓后,實時重復步驟2～6判斷本船是否應繼續采取轉向避讓,直至本船到達目的地;若不需避讓,則應用蟻群靜態路徑算法規劃出從當前位置至目的地的航行路徑,本船將沿新路徑航行。

4 仿真實驗

4.1 靜態路徑規劃對比仿真實驗

為驗證HACSA在復雜航行環境中規劃路徑的穩定性,設定仿真環境為50×50(n mile),對比分析傳統蟻群算法、文獻[7]、文獻[8]與HACSA的路徑規劃結果,見圖4、5,表1。

表1 復雜環境下不同算法的仿真結果

由圖4可知,除了傳統蟻群算法,其他三種方法均可收斂得到各自的最優路徑。在復雜環境下HACSA得到路徑最短,距離為74.6 n mile。

圖5中,HACSA的收斂速度最快。盡管船舶航行環境更復雜,HACSA仍在第8次迭代完成收斂,而文獻[8]卻在20次迭代以后才完成收斂,所以復雜環境幾乎不會影響HACSA的運行效率。

圖5 復雜環境下算法的迭代收斂

另外,文獻[8]也加入了船舶安全性約束函數。由表1可知,相比于文獻[8]中的方法,復雜環境幾乎不會影響HACSA規劃路徑的安全性。所以無論是在復雜環境還是簡單環境,HACSA均取得了相對最優的運行結果。

4.2 動態路徑規劃算法仿真實驗

4.2.1 單目標船動態路徑規劃

為驗證HACDA算法在靜態障礙物和單一目標船環境下船舶動態路徑規劃的實用性,設計船舶航行區域為20×20(n mile),本船航行起點柵格序號為1,航行終點柵格序號為400。設定本船航向為45°、航速為20 kn,目標船的柵格起始序號為180、航向為180°、航速為16 kn。見圖6。

圖6 單目標船動態路徑規劃

由圖6a)可知,在航行初始階段,HACDA首先規劃出一條自起點至終點的安全初始航行路徑(避開靜態和動態障礙物的初始位置),此后本船沿著初始路徑航行。判斷出兩船之間存在碰撞危險,本船為讓路船,且兩船間的Dcpa和Tcpa值均小于規定值。避讓過程中仍使用HACDA實時規劃出自當前位置至目的地的局部新路徑,見圖6b)。一旦避碰過程結束,本船將沿局部新路徑航行,若避碰過程未結束本船將繼續進行避讓。當本船航行到252號柵格時,本船與目標船的碰撞危險解除,見圖6c)。此時本船將沿著更新后的局部新路徑繼續航行,最終抵達航行目的地。由圖6(d)可知,在整個航行過程中,本船能識別動態障礙物并完成避讓過程。

4.2.2 多目標船動態路徑規劃

為驗證HACDA在靜態障礙物和多運動目標船環境下船舶動態路徑規劃的穩定性,設計船舶航行區域大小為20×20(n mile),本船航行起點柵格序號為1,航行終點柵格序號為400,本船航向為45°、航速為20 kn;目標船1(TS1)起點柵格的序號為257、航向為180°、航速為16 kn;目標船2(TS2)起點柵格的序號為138,航向為225°,航速為10 kn;目標船3(TS3)起點柵格的序號為81,航向為315°,航速為10 kn。見圖7。

圖7 多目標船舶動態路徑規劃

首先采用HACDA規劃一條初始路徑,見圖7a)。在圖7b)中,當本船行駛至290號柵格時,可計算出本船與TS1的Dcpa值為0.94 n mile,θT值為18.65°,兩船相距6.07 n mile,相對運動速度vR1為36 kn,Tcpa的值為10.4 min。由HACDA可判斷出本船與TS1之間存在碰撞危險,且兩船間的Dcpa和Tcpa值均小于約定值,本船右轉實現以避讓。

當本船行駛至274號柵格時,本船與TS1解除碰撞危險并將沿局部新路徑向目的地航行,見圖7b)。此時,由HACDA判斷出本船與TS2之間存在碰撞危險,且兩船間的Dcpa和Tcpa值均小于規定值,本船將采取右轉向避讓。隨后本船與TS2結束對遇局面并將沿更新后的局部新路徑駛向目的地,最終本船順利抵達航行目的地。

5 結論

為提高船舶路徑規劃的安全性與經濟性,提出一種改進的蟻群算法用于船舶路徑規劃。針對蟻群算法迭代速度慢、易陷入局部最優等問題,通過在算法迭代初始階段引入人工勢場法,有效改善了算法的迭代速度和尋優能力。同時,為進一步使所規劃路徑符合實際情況,將路徑長度、安全性、平滑性約束條件融入至信息素更新規則,并綜合考慮航行規則約束。仿真實驗證明,所提出算法的可行、有效。主要分析靜態環境下的船舶路徑規劃,針對動態環境,僅實現了簡單多船環境下船舶路徑規劃。然而,動態環境下的影響因素更多,如何實現更為復雜環境下的船舶動態路徑規劃是后續研究方向。