基于天牛須搜索算法的多船避碰決策方法

劉 朝 黃立文 張 可 郝國柱

(武漢理工大學航運學院 武漢 430063)

0 引 言

在航海實踐中，駕駛員通常是依靠自身經驗來制定船舶的避碰決策，但當處于比較復雜的多船會遇局面時，駕駛員很難保證可以做出最優的避碰決策[1].因此，許多專家學者應用智能優化算法來研究船舶的避碰策略問題，并取得了很多的成果.文獻[2]將社會情感優化算法應用到船舶轉向避碰的決策中，以便求解出船舶最佳轉向，但系數調節較為復雜.文獻[3]基于改進的免疫粒子群算法，給出了一種求解多船會遇局面下計算最佳轉向幅度的方案.文獻[4]通過結合前景理論和多指標灰關聯決策，建立了考慮駕駛員風險態度的避碰決策優化模型，結果表明：該模型可幫助駕駛員在不同風險偏好下選取最優避碰方案.文獻[5]以船舶最近會遇距離和最近會遇時間建立碰撞危險度模型，綜合考慮轉向幅度和航行時間，構建了避碰決策模型，并提出了一種使用粒子群-遺傳優化算法求解該決策模型的方案.然而，這些算法大多在于模擬動物的群體性活動，無法從個體中獲取有效的決策，求解過程也較為繁瑣.

天牛須搜索(beetle antennae search，BAS)是一種類似于遺傳算法、粒子群算法、模擬退火等算法的智能優化算法[6].該算法不需要知道函數的具體形式，也不需要求解函數的梯度，就可以實現全局高效尋優.相比較粒子群算法，BAS算法僅需要一個個體，極大地降低了尋優過程的運算量.目前該算法已經被應用于機器故障診斷、電網優化調度、選址、圖像修復及路徑規劃等多個領域，并表現出算法在解決優化問題中的有效性及優越性[7-10].本文利用船舶碰撞危險度并考慮船舶在進行避碰操作時的損失函數來確立符合航海實際的避碰決策目標函數，并利用BAS算法研究多船會遇局面下最優避碰轉向幅度以及復航時間，并通過仿真實驗驗證該避碰決策方案.

1 船舶會遇態勢的劃分

海上實踐表明，對會遇態勢的認識不一致是造成船舶間避碰行動不協調乃至碰撞的重要原因之一[11].根據《國際海上避碰規則》對追越、對遇和交叉相遇的定義以及相關規定，以本船為中心，將他船相對于本船的方位劃分為五個區域[12]，見圖1.

圖1 船舶會遇態勢劃分

根據避碰規則，若互見中兩船之間存在碰撞風險，對于E、A區域的來船，本船是讓路船，需要進行相應的避碰操作，一般通常是進行右轉向操作；若來船位于B區域，則本船為讓路船，一般來說本船可以通過降低船速或者是進行左轉向操作進行避碰；若來船處于C、D區域，那么本船為直航船，來船需要進行相應避碰操作.

2 船舶碰撞危險度

船舶碰撞危險度(collision risk index，ICR)是對船舶之間發生碰撞的可能大小的一個度量，其取值范圍是[0,1].目前對于船舶碰撞危險度的計算模型有很多，文中以船舶之間距離(D)、船速比(K)、他船與本船之間相對方位(B)、最近會遇距離(DCPA)，以及最近會遇時間(TCPA)等五個指標為主要參數，并綜合考慮航行水域狀況、能見度情況、操船者技術、船舶操縱性能等因素，確定他船與本船之間的碰撞危險度[13].

設uDi、uKi、uBi、uDCPAi、uTCPAi分別為與本船會遇的目標船i各主要參數的危險隸屬度，取值范圍為[0,1]，i=1,2,…,n.那么本船與目標船i之間的碰撞危險度ICRi即為

ICRi=aDuDi+aKuKi+aBuBi+

aDCPAuDCPAi+aTCPAuTCPAi

(1)

式中：aD，aK，aB，aDCPA，aTCPA為五個主要參數的危險隸屬度的權重，取值范圍為[0,1]，且滿足

aD+aK+aB+aDCPA+aTCPA=1

(2)

船舶之間的距離越小，碰撞危險度就越大.船舶之間距離的隸屬度函數為

(3)

式中：D1為最晚避讓距離；D2為可采取避讓措施距離，由航行水域狀況、能見度，以及人為因素等決定.取值為

D1=H1×H2×H3×DLA

(4)

D2=H1×H2×H3×Ri

(5)

Ri=1.7cos(Bi-19°)+

(6)

式中：H1取決于能見度；H2由航行水域狀況決定；H3取決于操船者經驗、技術、反應能力等人為因素，DLA為最晚施舵距離，通常取12倍的船舶長度.

(7)

式中：W為常數，這里取值為2；C為碰角(0°≤C≤180°).

(8)

(9)

式中：d1為船舶碰撞距離；d2為船舶注意距離.

(10)

d2=2d1

(11)

(12)

式中：t1為船舶碰撞時間；t2為船舶注意時間，并且

(13)

(14)

式中：vri為目標船i與本船之間相對速度.

3 基于天牛須搜索算法的多船避碰決策方法

3.1 天牛須搜索算法基本原理

天牛須搜索也被稱為甲殼蟲須搜索，搜索過程的簡化模型見圖2.

圖2 天牛搜索過程簡化模型

那么該簡化模型的尋優策略即為

1) 天牛的左右兩須應位于天牛質心的兩邊；

2) 天牛行動的步長step與左右兩須之間的距離d0比值應該是一個固定的常數，即step=c·d0，其中c為常數.也可以理解為體型較大的天牛(兩須之間的距離長)行走的步長較大，體型較小的天牛行走的步長較小.

3) 天牛每次行動之后，它的頭部朝向應該是隨機的.

3.2 BAS算法建模

假設要求解一個n維的空間中目標函數f的最小值，現設天牛的質心坐標為x，左須坐標為xl，右須坐標為xr，左右兩須之間的距離為d0.由尋優策略(3)可知，天牛的頭部朝向是隨機的，所以由右須指向左須的向量的方向也是隨機的，在此用隨機向量dir=rands(n,1)來表示右須指向左須的向量.對其進行歸一化處理，即

(15)

由此，可以得到

xl-xr=d0×dir

(16)

(17)

對于目標函數f，首先求取天牛當前位置左右兩須的值，即fl=f(xl)，fr=f(xr).

如果fl

x=x+step×dir

(18)

如果fl>fr，為了尋找目標函數的最小值，此時天牛應該朝著右須的方向飛行step的距離，即

x=x-step×dir

(19)

為了簡化形式，使用符號函數sign對式(18)和(19)進行簡寫

x=x-step×dir×sign(fl-fr)

(20)

此外，對于天牛行動的步長，本文將使用變步長的方式代替固定步長.在每次的迭代過程中，將步長設置為step=eta·step，其中：eta∈[0,1]且接近于1，這里取eta=0.95.

3.3 避碰決策目標函數

當船舶之間存在碰撞危險時，一般來說，常用的避碰操作是采取變速、轉向或者同時進行轉向和變速等方式.由文獻[13]可知，通常情況下，即使是處于多船避碰的局面，船舶也可以通過一次轉向或者變速來實現避碰，并且轉向避讓是使用頻率最高的一種方法，很少會同時進行轉向和變速操作.所以，本文將主要研究船舶避碰操作中的轉向避碰操作.

當會遇的船舶之間存在碰撞危險時，需要根據本船與他船之間的會遇態勢，合理的選取轉向幅度，此時應滿足：

1) 轉向后，應使得會遇船舶之間的碰撞危險度盡可能的減小.

2) 在滿足避碰規則“大幅度”要求的前提下，轉向幅度應盡可能的小，以減少資源的損耗.

3) 船舶轉向后，在保證航行安全的前提下，在新航向上的航行時間要盡可能的短，以降低復航的難度.

基于以上三點，在多船會遇時，船舶的避碰決策目標函數為

minf(x)=w1f1(xi)+w2f2(xi)

(21)

式中：f1(xi)為目標船i與本船之間的碰撞危險目標函數，f2(xi)為航程損失的目標函數，w1、w2為權重系數，為了便于尋優計算，w1取0.7，w2取0.3.

碰撞危險目標函數為

(22)

式中：n為目標船個數.

航程損失的目標函數為

(23)

式中：xi為轉向幅度，航程損失函數的取值范圍為[0,1].同理，損失函數的值越小，轉向幅度和復航時間應越短.

4 仿真分析

假設在開闊水域中能見度良好，駕駛者技術水平良好，船舶的操縱性能良好，即H1=1，H2=1，H3=1.本文以三船會遇局面為仿真對象，本船的初始位置為(0,-4)，航速為16 kn，航向為0°；目標船1的初始位置為(2,1.5)，航速為16 kn，航向為220°；目標船2的初始位置為(2,-3)，航速為17 kn，航向為300°.船舶間的初始會遇態勢見圖3.

圖3 船舶間初始會遇態勢

由船舶間的初始會遇態勢，以及表1中船舶間的相關參數可知，本船與目標船1、目標船2之間的碰撞危險度都很大，存在很高的碰撞風險.根據避碰規則，此時兩目標船為直航船，本船應及早采取合適的避碰行動，以降低本船與兩目標船之間的碰撞風險.同時對于目標船2和目標船1來說，兩船之間也存在碰撞風險，根據避碰責任，目標船2也要采取合適的避碰操作來降低與目標船1之間的碰撞風險.因此，對于圖3的會遇局面，本船需要選取合適的轉向幅度以降低與兩目標船之間的碰撞風險；而目標船2也要找到最優的轉向幅度.

表1 初始會遇船舶間相關數據

在圖3的多船會遇局面中，使用BAS算法為本船規劃一個合適的避碰方案，以降低碰撞風險.使用BAS算法對式(21)的目標函數進行尋優計算，同時為了避免計算結果的偶然性，對該尋優過程進行10次重復操作，每次的迭代次數均為100次，最終求得平均最優轉向幅度為32.185 6°本船恢復原航向的時間約為8.34 min.即本船的最佳轉向幅度是右轉向32.185 6°，在該航向上航行大概8.34 min之后可以完成避碰操作.同時為了驗證BAS算法的有效性，使用粒子群算法對避碰決策目標函數進行求解.算法的尋優過程見圖4.

圖4 本船的PSO和BAS算法迭代過程

使用BAS算法對目標船2的轉向幅度進行尋優求解.在經過10次重復計算之后，得到的平均最優轉向幅度為43.090 3°，恢復航向使用的時間為11.14 min.算法的迭代過程見圖5.

圖5 目標船2的PSO和BAS算法迭代過程

表2將BAS算法對多船會遇局面避碰策略的求解結果與粒子群算法進行了簡單的對比.從表中可以看出，BAS算法的收斂速度快，求解出來的最優轉向幅度比粒子群算法要小，但復航時間要稍微長一點，這與實際情況是相符合的.同時本文所用的碰撞危險度模型綜合考慮了船舶的操縱性能、人為因素、航行環境等因素，使得BAS算法求得的結果也更符合航海實際.

表2 算法對比

5 結 束 語

本文通過分析船舶的會遇態勢，結合避碰規則對避碰責任進行了劃分，在綜合考慮航行水域情況、能見度、操船者技術、船舶操縱性能等因素的基礎上，使用船舶之間距離、船速比、方位角、最近會遇距離以及最近會遇時間等五個指標確定了比較符合航海實際的碰撞危險度模型，通過對避碰操作過程中轉向幅度的分析，建立了避碰策略目標函數，利用BAS算法的全局搜索能力強、尋優速度快、魯棒性強的特點，求得了多船會遇下最優避碰轉向幅度以及復航時間.通過三船會遇的仿真實驗，驗證了算法的有效性.