基于海上避碰規則和機器學習的輔助避碰決策方法研究*

馮涂超 鄭 茂 尹奇志 初秀民 謝 朔

(武漢理工大學能源與動力工程學院1) 武漢 430080) (武漢理工大學智能交通中心2) 武漢 430080)

0 引 言

船舶智能輔助避碰決策是船舶智能化研究領域的研究熱點，也是實現船舶智能航行的關鍵技術.近年來，國內外相關領域學者相繼對避碰決策方法開展研究，獲得了大量卓有成效的研究成果[1-3].

基于電子海圖(electronic chart display and information system，ECDIS)及AIS(船舶自動識別系統)的智能避碰決策方法研究.靳祥等[5]通過將AIS信息與專家系統進行融合，解決了避碰決策數據準確性問題.但該類方法主要依靠船載航海信息的采集及交換，其有效性對設備的信息采集精度和準確性有較高要求，主要功能停留在碰撞預警層面，尚未進入輔助避碰決策階段.此外，該方法對《國際海上避碰規則》(COLREGS)(以下簡稱《規則》)運用較少，避碰決策結果未必滿足規則條件.以《規則》為基礎的船舶避碰決策研究，何立居等[6]將避碰經驗、避碰規則等進行融合，建立了避碰數據庫，同時結合CBR(case-based reasoning)和RBR(rule-based reasoning)建立了避碰輔助決策系統.李麗娜等[7]通過將海上避碰規則與專家經驗結合，建立了基于機器學習的船舶擬人動態避碰決策庫，可提供滿足海上避碰規則的避碰決策.這類方法主要基于實際避碰操作，具有很好的實用價值.但由于需要處理大量不同且復雜的船舶會遇場景，數據量大，耗時長.以各種機器學習算法為基礎，結合其他方法如A*算法、規則等的避碰決策研究，孔祥生等[8]基于擴展博弈理論結合避碰規則的約束條件實現了兩船避碰決策，倪生科等[9]利用多種遺傳算法實現了符合避碰規則的避碰決策，沈海青等[10]通過將航行經驗規則與深度競爭Q學習算法和A*算法相結合，縮減了模型訓練時間，使避碰決策符合國際海上避碰決策的要求.該類方法的優點是能根據所設定的條件對求解函數進行優化，缺點在于需獲取大量精確性高的樣本來避免陷入局部收斂問題，同時啟發式搜索無法很好地兼顧《規則》.

目前《規則》是海上航行避碰主要遵循的基本規則，任何避碰決策模型必須遵守規則.根據規則的定義，在不同的船舶會遇態勢下，對船舶間的責任有明確劃分，對船舶如何避碰有指導性的作用.但由于避碰場景的復雜性，規則在部分場景下存在模糊性，一些會遇局面下存在較高的碰撞風險.而有經驗的船長能較為從容地完成船舶在各種復雜態勢下的避碰，若能模擬“船長”的避碰決策，就能提升輔助避碰決策系統的決策性能.因此，本文通過采集船長基于《規則》的決策結果作為數據樣本，結合機器學習方法來建立輔助避碰決策模型.該模型在船舶相遇進入指定距離后，根據本船及目標船的航速，方向角信息對本船避碰操作給出滿足避碰規則的建議.

1 輔助避碰決策系統工作流程及船舶避碰場景建模

1.1 輔助避碰決策系統工作流程

本文所建立的避碰系統由：①船舶避碰場景仿真模塊；②基于航行規則的船舶避碰決策模塊；③機器學習算法建模模塊.整個輔助避碰決策系統工作流程見圖1.

圖1 輔助避碰決策模型工作流程

1.2 船舶避碰場景建模

大型貨運船舶在開闊水域的避碰遵循“用舵不用車”原則[11]，盡量在不改變主機工作狀態的條件下，僅改變航向實現避碰.因此,本文僅研究常規避碰操作，即在船舶巡航航速下依靠改變航向來進行避碰決策.

為采集充足的船舶會遇樣本，首先需建立船舶避碰場景模型，模擬不同的會遇態勢，再通過避碰模型對責任進行判定.從建模方便搞笑的角度出發，本文采用“倒推法”建立避碰場景模型.

首先設立大地坐標系X-O-Y，在本坐標系內設定預期碰撞點，根據碰撞點設置固定坐標系X1-O-Y1，在此坐標系Y1軸負方向上5 nmile處設置本船，本船初始位置設置為固定點，航速設定為標準運營航速10 kn,航向固定為正北方向，依據本船建立固聯坐標系X0-O-Y0.將目標船與預計碰撞點坐標系Y軸正方面的夾角設定為目標船方位角θ，通過設置船舶避碰模型找中的目標船方向角，及目標船船速構建不同的會遇場景，見圖2.為了保證數據的可靠性與準確度，降低隨機性，在所示的0°～360°范圍內，每2°設置為一個目標船初始方位角，目標船航速分別為2，4，6,…,28，30 kn.以此定義2 506個會遇場景，并用船舶避碰決策模塊獲取避碰決策樣本.

圖2 船舶坐標系定義

2 基于航行規則的船舶避碰決策模塊

1977年，國際海事組織(IMO)第一次制定了《國際海上避碰規則》(international regulations for preventing collisions at sea，COLREGs),旨在減少船舶之間的碰撞，包括對不同會遇場景的定義和責任劃分、避碰中聲光預警的要求、瞭望的要求等.

依《規則》，船舶在避碰時需要進行會遇態勢的判斷，進而確定所適用的規則條文，進而確定避讓責任和應采取的行動.在《規則》中，兩船會遇時的態勢被分為三種：①對遇，指兩艘船舶航向相反或近似相反且形成一定碰撞危險時的會遇狀態；②交叉相遇，指兩艘船舶航向交叉且形成一定碰撞危險的會遇狀態；③追越，指一艘船從目標船正橫后方大于22.5°(112.5°～247.5°)的某一方位追趕并超過目標船的會遇狀態.不同會遇態勢下的船舶相對位置具體見圖3.

圖3 船舶會遇態勢圖

因此根據不同的會遇態勢，依照航行避碰規則將兩船間的避讓責任原則按以下角度劃分.

將目標船相對于本船的方位角設為γ，本船速度為speed_A,目標船速為speed_B.

對于大多數對遇、左舷交叉相遇等會遇態勢，可以很明確地根據《規則》做出清晰決策判斷，而對于部分右舷交叉、斜后方交叉等會遇態勢，《規則》并未明確規定避碰責任及方向，因此本文邀請有海上操船經驗的船長，對船舶會遇態勢的基本判定結果進行了確認，從而獲取了避碰場景的規范避碰決策，樣本模型見表1.

表1 基于《規則》的避碰決策樣本模型

本文的研究重點在于機器學習對于人類知識的訓練方法，而上述訓練樣本模型是基于《規則》和船長經驗的理論結果，做了一定程度簡化，僅用于驗證機器學習的有效性，尚無法直接指導實際航海避碰作業.

3 機器學習算法

3.1 BP神經網絡

本次采集了大量基于避碰規則及專家經驗的船舶避碰決策樣本，故采用監督學習算法，其優化算法流程見圖4.

圖4 BP神經網絡優化算法流程

由于輸入數據量綱不一，取值范圍差異大，導致神經網絡收斂慢.取值范圍大的輸入在模式分類中的作用過大，致使取值范圍小的輸入作用過小，從而導致部分信息被淹沒.

因此,對輸入數據進行歸一化處理，使用線性轉換算法為

y=2(x-xmin)/(xmax-xmin)-1

(1)

式中：xmin為x的最小值；xmax為x的最大值；輸入向量為x，歸一化后的輸出向量為y，將所有數據歸一化到[-1,1]區間.

神經網絡輸出層激活函數的值域是有限制的，因此需要將網絡訓練的目標數據映射到激活函數的值域.網絡層數設置為三層，每層節點數為10，激活函數采用對數s形轉移函數為

(2)

3.2 支持向量機SVM

支持向量機SVM是一種二類分類模型，其基本模型定義為特征空間上的間隔最大的線性分類器，其學習策略便是間隔最大化，最終轉化為一個凸二次元規劃問題的求解.

SVM算法最初為二值分類問題而設計，當處理多類問題時，就需要構造合適的多類分類器.：

定義待分類的個數為m，對m個類中的每兩個類都要訓練一個分類器，則總共的二類分類器個數為m(m-1)/2.對于一個需要分類的數據x,它需要經過所有分類器的預測，也同樣使用投票的方式來決定x最終的類屬性.

在船舶實時航行中，會不斷出現新的目標船，形成新的樣本.為防止不必要的重復訓練，本文訓練采用的為“多對多”算法(All-Versus-All AVA)[12]來實現多分類.并通過使用交叉尋優算法[13]及粒子群優化算法(particle swarm optimization,PSO)[14]找到最佳的懲罰參數c和核函數的參數g.算法流程如下.

步驟1將原始問題轉化為凸優化問題：

步驟2凸優化問題求解，首先將原始問題對偶化構建拉格朗日函數，選擇核函數，原始問題轉化為

式中：αi≥0；μi≥0.

步驟3利用KKT條件結合PSO算法求解a*，在向量a*中找到一個向量aj使0

步驟4最后獲得分類決策函數為

4 算法優化結果

4.1 基于神經網絡的避碰策略訓練

通過將采集避碰決策樣本隨機分為兩組，每組包含1 253個樣本.其中一組作為神經網絡的訓練樣本，另外一組作為檢驗樣本.設置四個輸入參數：本船航速、目標船航速、本船方位角、目標船方位角，輸出為三種結果(本船保速保向、本船左轉、本船右轉)的前向網絡.

訓練函數采用梯度下降自適應學習率訓練函數，神經網絡配置參數設置如下：神經網絡訓練的目標誤差0.01，顯示中間結果的周期為50，最大迭代次數1 000，學習率設為0.01.經過訓練后的網絡以檢驗組為測試樣本，見圖5.由圖5可知，在訓練198次時，決策誤差已趨于收斂，決策準確率達到(1 210/1 253)96.329%.

對測試樣本錯誤決策數進行統計，各場景下樣本決策錯誤率見圖6.

由圖6可知，使用BP神經網絡算法分類的輔助避碰決策系統均有較高的決策正確率，而進一步將避碰決策錯誤樣本場景標注在船舶態勢會遇圖中，見圖7.由圖7可知，決策錯誤場景樣本主要集中在對遇(355°～5°)場景及右舷交叉場景(5°～112.5°)中.而在其中大量的錯誤樣本主要集中在對遇態勢與左舷交叉態勢的邊界處，即355°角度附近.

圖5 神經網絡訓練

圖6 不同會遇態勢下決策錯誤率

圖7 決策錯誤樣本圖

4.2 基于支持向量機(SVM)的避碰策略訓練

同理將樣本分成對訓練及測試兩組.每組數據均隨機抽取1 254條數據，經過SVM交叉尋優后，決策準確率達到98.403 8%，通過交叉尋優找到最佳懲罰因子和核函數，見圖8.

圖8 SVM尋找最優策略流程圖

通過對結果進行分析可發現在1 253組測試樣本中通過SVM算法訓練后的決策模型能準確對其中1 232組樣本進行決策.而基于PSO優化的SVM算法能準確對1 241組樣本進行決策.測試樣本誤差見圖9.

圖9 對照誤差圖

而進一步對出現決策誤差的場景進行統計，發現不同會遇場景下的決策錯誤率見圖10.

圖10 不同會遇態勢下決策錯誤率

由圖10可知，基于SVM算法分類的輔助決策系統在追越及交叉相遇場景中均有較高的決策成功率，而由于對遇場景的樣本較少未能達到充分訓練的效果，因此本決策方法給出的對遇場景決策錯誤率較高.

同時將所有決策失敗的場景中的目標船標注在會遇態勢圖上，見圖11.由圖11可知，決策失敗的場景主要集中在大角度右舷交叉相遇(67.5°～112.5°)與對遇(355°～5°)場景中，在這兩種會遇態勢下存在更高的碰撞危險.后續將著重研究對遇及大角度右舷交叉兩種會遇場景，擴充會遇場景庫及專家決策樣本.

圖11 決策錯誤樣本圖

4.3 驗證效果

為了進一步驗證本輔助系統的決策效果，隨機設計50個會遇場景，其中對遇場景10個、交叉相遇30個、追越10個.在所有會遇場景中本船船速均設置為運營船速，本船方位角為0°；目標船速度為8～20 kn中隨機值，將輔助避碰系統決策結果與基于航行規則的專家決策進行對比，結果見表2.

表2 輔助避碰決策驗證

由此可以說明本決策系統在各種會遇態勢下均能做到較精準的給出避碰建議，但根據相關仿真測試可以發現，在交叉相遇態勢下由于存在相對方位角跨度較大問題，若能持續采集大量專家決策樣本進行訓練，提高輔助避碰決策系統的準確性.

5 結 論

1) 本文設計了一種結合了航行避碰規則與機器學習的船舶航行輔助避碰決策系統，通過模擬船舶碰撞場景，獲得基于航行避碰規則的船舶避碰決策樣本.通過對樣本進行處理，根據關鍵特征參數，即距離預計碰撞點一定距離內本船及目標船的方位角和船速，應用兩種不同的機器學習算法進行分類，獲得一種判斷成功率較高的輔助避碰決策系統.

2) 采取了BP神經網絡與支持向量機SVM兩種算法對決策系統進行分類.由樣本測試結果可以看出，在相同樣本數的情況下，由SVM算法優化的輔助決策系統有著更為精準的輔助避碰決策，能基本滿足任何會遇態勢下的避碰決策輸出.由于SVM在樣本個數較大的情況下，求解的矩陣階數過高將耗費大量的計算及訓練時間，影響分類準確性.而采用BP神經網絡訓練的輔助決策系統對大量樣本數據擁有著更好的泛化性能，其識別率隨著樣本量增大并沒有較大的波動.

3) 建議在將輔助避碰決策系統應用到不同船舶時，能獲取較多避碰實例的船舶(如內河繁忙水域的船舶)采用基于BP神經網絡優化的輔助避碰，而在樣本量相對較少的情況下(如沿海或遠洋船舶)采用基于SVM算法優化的輔助避碰.