基于深度強化學習的船舶航線自動規劃

韓志豪， 汪益兵， 張 宇， 郝永志

(1.浙江國際海運職業技術學院， 浙江 舟山 316000；2.浙江大學 舟山海洋研究中心， 浙江 舟山 316000)

隨著全球信息化的不斷發展，船舶智能化應用逐漸普及，在船舶航行過程中，為減少燃油消耗和降低人工成本，確保航行安全可靠，避開航行中的諸多威脅，如禁航區、錨區、淺灘和暗礁等，同時考慮船舶吃水深度、船舶拐彎半徑等，設計一條航行距離較短且最安全的航線，是保證船舶安全、經濟航行的關鍵。

航線設計需要考慮外部環境和船舶自身[1]特性。目前，航線設計有2種方式：由船舶航行專家根據風速、風向、潮汐、水生和天氣等外部環境，結合噸位、吃水深度、船長、船寬、船高和拐彎半徑等船舶自身特性，通過紙質海圖或電子海圖手動繪制航線[2]；借助電子海圖儀，通過設定起點和終點，產生一條沒有障礙物的最近航線，再根據外部環境、船舶自身特性和電子海圖信息修正最近航線。采用這2種方式設計航線不僅非常費時費力，而且在設計時容易遺漏信息，導致船舶在航行時遇到突發狀況，產生難以挽回的損失。

在研究船舶航線自動規劃時，通常采用圖論算法、A*算法和遺傳算法，其中李擎等[3]對A*算法、遺傳算法和圖論算法路徑規劃進行比較，A*算法與遺傳算法規劃的航線優于圖論算法，但A*算法不能結合外部環境、船舶自身特性和電子海圖信息等，遺傳算法收斂速度慢、易陷入局部最優。深度Q網絡(Deep Q Network,DQN)算法結合深度學習與強化學習，巧妙地將深度學習的感知與表達能力融合強化學習的決策與解決問題的能力。DQN廣泛應用在游戲、機器人控制、無人駕駛和機器視覺等領域中。[4]

為解決船舶航線規劃算法不符合航行要求、未依航道航行和未考慮船舶自身拐彎特性等問題，本文結合電子海圖信息，避開錨地、禁航區和沉船等障礙，利用DQN算法自動規劃航線，確保航行的經濟性和安全性。通過仿真測試驗證DQN算法規劃航線擬合船舶航行專家航線的可行性，結果表明，規劃后的航線能依航道航行，拐彎次數較少，解決普通航線規劃算法只求規避障礙的最短路線問題，且其通用性和魯棒性較強。

1 船舶航線規劃框架

利用DQN進行船舶航線規劃，需先輸入船舶航行專家的經驗航線和該航線上的海圖信息，最終目標是找到一條避開所有障礙物的航線，其規劃框架見圖1。

圖1 DQN船舶航線規劃框架

2 基于DQN的自動生成航線方法

2.1 DQN算法

基于值函數DQN算法和深度Q網絡模型，該模型通過圖像和地圖感知并決策控制任務。Q網絡是指Q-Learning強化學習算法而產生的用于決策的Q表[5]，見表1。矩陣中的An為每個動作，如航線規劃中有上、下、左、右等4個動作，Sn為狀態。

表1 用于決策的Q值表動作

表1中的Q值通過試驗，反復調用式(1)進行更新，直至收斂。

Q(St,At)←Q(St,At)+α(Rt+1+

λmaxaQ(St+1,a)-Q(St,At))

(1)

式(1)中:α為學習效率且數值小于1;Rt+1為到達Q(St,At)所獲得的獎勵值;λ為對未來獎勵的衰減值;Q(St,At)為當前在St與At上的Q值;maxaQ(St+1,a)為下一個狀態St+1的最大估計Q值。

當實際問題復雜時，Q表難以承載計算維度。因此，深度Q網絡模型中的深度神經網絡將Q(St,At)近似等于f(s,a)，用深度神經網絡表示Q(s,a,w)，在深度Q網絡模型中，用2個卷積層和2個全連接層，最后輸出每個動作的Q值向量，見圖2[6]。

圖2 DQN動作值函數逼近網絡

在神經網絡的最優化問題中，損失函數是標簽值與網絡輸出的差值，目標是使損失函數最小化。[7]為達到此目標，需要大量標簽數據，進而通過誤差反向傳播梯度下降的方法更新神經網絡參數。通過Q-Learning強化學習算法，可將目標Q值作為標簽，使計算出來的Q值與目標Q值形成損失函數

L(w)=E[(r+γmaxa′Q(s′,a′,w)-Q(s,a,w))2]

(2)

2.2 基于經驗航線的DQN

將船舶航行專家的經驗航線和電子海圖數據直接用于神經網絡訓練數據量太大，訓練速度慢，因此,將船舶航行專家的經驗航線與電子海圖數據圖像融合，并通過顏色特征提取，將圖像處理成單通道編碼方式，以縮短神經網絡訓練時間。在進行航線規劃訓練時，為防止訓練僅能適應熟悉電子海圖場景，而不能適應陌生電子海圖場景并陷入局部最優，采用批量梯度下降法加速收斂，并引入驗證集，當驗證集錯誤率不再下降時，就停止迭代。

2.2.1顏色特征提取初始化數據

由于船舶航線規劃是在電子海圖軟件中實現的，為區分顏色，對電子海圖軟件的海圖顯示和圖像渲染進行二次開發，以區分航線、航道和轉向點等特征。

顏色特征提取方法是尋找某像素點與周圍連續像素點之間的顏色直方圖差異，只有差異大于指定閾值，才可確定該像素點與其周圍像素有可識別的特征。

本文的船舶航線規劃算法的環境是基于正式的電子海圖，以300×300的每個像素為單位進行柵格化處理，帶有陸地、沉船和障礙物。通過對電子海圖進行顏色特征提取和輪廓識別后，將圖像轉換成單通道灰度圖像，以減少訓練時間，原始電子海圖見圖3，輪廓識別后電子海圖見圖4，采用紅綠藍(Red Green Blue,RGB)值為(255,0,0)標示已識別的輪廓。電子海圖經驗航線見圖5，其中:RGB值為(0,255,0)的2×2像素點為航線的起始點;RGB值為(0,0,255)的2×2像素點為航線的終點;RGB值為(0,0,0)的為經驗航線，為避免在強化學習時路徑出現小范圍振蕩，將路徑寬度設為1個像素。

圖3 原始電子海圖

圖4 輪廓識別后電子海圖

圖5 電子海圖經驗航線

圖5中淺灰色區域為可行區域，其他不規則區域為不可行區域。對于每個像素點，其上、下、左、右，左上、左下、右上和右下等8個相鄰的方格為可達區域。試驗目標是自動規劃的航線能較好地擬合經驗航線，從航線的起點到航線的終點用較少的拐彎點，并規避障礙的較短航線。在輪廓識別的電子海圖中，當智能體從航線起點開始向周圍點探索時，經多組獎勵方案測試后，最終選定如下獎勵方案，以防止陷入局部最優：遇到經驗航線獎勵1.0；遇到障礙獎勵-0.5，結束此次周圍探索；拐彎獎勵-0.4；遇到終點獎勵2.0，并結束周圍探索。

2.2.2存儲經驗池和雙神經網絡

強化學習本身是無監督學習，強化學習算法有噪聲、稀疏和延遲的獎勵，而深度學習本身是監督學習，但在DQN訓練[8]過程中，價值函數對動作的估計將不斷優化，輸出動作也逐步優化，繼而影響訓練樣本的分布。因此，先采用存儲經驗池的方式存儲一部分樣本，然后隨機采樣。

本文的船舶航線規劃基于船舶經驗航線，在智能體Agent向上、下、左、右、左上、左下、右上和右下等8個方向探索時，采用ξ-greedy選擇航行方向，ξ=0.1，即隨機選擇方向的概率為0.1；采用貪婪策略的概率為0.9，其中貪婪策略為

arg maxQ(st+1,a)

(3)

根據當前狀態計算，試探的8個方向，并取最大的獎勵方向作為下一狀態航線規劃的方向。通過ξ-greedy產生的經驗，存儲在經驗池開辟的空間中，存儲格式為(st,at,rt,st+1)，其中:st為當前狀態;at為當前航行方向;rt為當前獎勵;st+1為下一個狀態。在該船舶航線規劃系統中，采用2個神經網絡分別作為當前神經網絡和目標神經網絡，二者結構相同，但數據不同，達到打亂數據間的相關性的目的。當累積經驗數據至1 000步后，將當前神經網絡參數拷貝至目標神經網絡，之后每100步將當前神經網絡參數拷貝至目標神經網絡，降低當前Q值與目標Q值的相關性。當前的Q值與目標的Q值之間通過均方差更新網絡參數，其誤差函數為

L(θi)=Esars[(Yi-Q(s,a|θi))2]

(4)

對θ求偏導，得到的梯度為

?θL(θi)=Esurrit[(Yi-Q(s,a|θi))?θiQ(s,a|θi)]

(5)

通過上述方法增加數據采樣次數，提高數據使用效率，同時避免從連續數據中學習效率低下、前后樣本相關度高的問題。當實際訓練時，也可能出現當前的參數決定最大獎勵動作方向為向右，此種情況下樣本多數來自右邊，然后右邊樣本再訓練，這樣訓練可能出現惡性循環，參數出現局部收斂，甚至發散。采用經驗池的方式，數據多個狀態會被平均，使訓練過程平滑，避免局部收斂與發散。

2.3 基于經驗航線的深度強化學習

依據第2.2.2節概述，DQN的船舶航線規劃系統算法流程見圖6。

在算法訓練過程中，使用經驗池存儲當前神經網絡處理得到的轉移樣本，有

et=(st,at,rt,s′)

(6)

在每個100步后，將智能體與電子海圖環境得到的轉移樣本存儲到經驗池D={e1,…,et}中。在訓練過程中，每次從經驗池D中隨機抽取小批量轉移樣本，同時采用隨機梯度下降算法更新神經網絡參數。

圖6 DQN的船舶航線規劃系統算法流程

3 試驗與分析

本節介紹系統試驗仿真平臺測試Demo、優化參數，進而將試驗參數應用于真實電子海圖環境中，評估訓練結果的好壞。

3.1 仿真結果分析

本文采用的基于經驗航線的DQN規劃船舶航線，在PC上基于Python3.6.5環境進行仿真驗證。使用的Python模塊包括PyQt5、tensorflow、pandas、numpy和matplotlib，模擬電子海圖環境，采用廣度優先搜索算法(Breadth First Search,BFS)模擬船舶經驗航線，目標是通過智能體規劃最接近經驗航線的航線。

仿真平臺首先生成10 000張10×10矩陣的地圖，作為DQN的訓練樣本，見圖7，并對每張地圖生成隨機障礙，用實心正方形表示；在障礙區域以外的區域，隨機生成路徑起始點，用正方形內嵌菱形輪廓表示；在障礙區域與起始點以外的區域，隨機生成路徑終點，用正方形內嵌圓形輪廓表示；用BFS生成8個方向的最短路線，模擬真實電子海圖的專家經驗航線，用實心三角形表示；智能體在搜索路徑時，用實心圓形表示。

通過路徑指引，在10 000張隨機地圖中，由智能體搜索每張地圖的路徑，損失函數的收斂速度較接近，見圖8和圖9，但基本在1 000次訓練后，損失函數趨于0。因此,在訓練時，設定每張圖的訓練步數為1 000步。

由于使用ξ-greedy選擇航行方向，因此對于每張地圖的訓練步數與損失圖，由隨機選擇方向概率帶來的影響會略有不同。以示例地圖2為例，當隨機選擇方向概率為0.5時，其訓練步數與損失圖見圖10；當隨機選擇方向概率為0.9時，其訓練步數與損失圖見圖11。隨機選擇方向概率越大，擾動越大，但與其損失衰減無關。

圖7 深度強化學習訓練隨機地圖

a)示例地圖1 b)訓練步數與損失圖

a)示例地圖2 b)訓練步數與頻失圖

圖10 示例地圖2隨機方向概率為0.5

圖11 示例地圖2隨機方向概率為0.9

當訓練完成10 000張隨機地圖訓練樣本后，隨機生成100張無經驗航線的地圖作為測試樣本。測試樣本生成航線與經驗航線擬合率均值為71.18%，測試樣本生成航線擬合經驗航線概率分布圖見圖12。

3.2 試驗結果分析

在真實電子海圖系統中，采用105張經驗船長規劃的實際航線作為訓練樣本，如圖5所示，經過單通道灰度處理后作為訓練樣本，直接輸入模型中，樣本為300×300像素的圖像，包含起點、終點、路徑、航道和障礙數據。

在訓練樣本時，單張圖的損失與訓練步數見圖13。損失值收斂在400步以上，且與仿真平臺相比損失值較發散。

圖12 測試樣本生成航線擬合經驗航線概率分布圖

圖13 電子海圖經驗航線

當訓練105張電子海圖經驗航線訓練樣本后，100張無經驗航線的電子海圖作為測試樣本。測試樣本生成航線與經驗航線擬合率均值為65.09%，測試樣本生成電子海圖航線與經驗航線擬合率的散點圖見圖14，概率分布圖見圖15，能基本滿足基于經驗航線的航線規劃需求。

圖14 電子海圖測試樣本擬合經驗航線概率散點圖

圖15 電子海圖測試樣本

以測試樣本的第71條航線為例，航線從舟山蝦峙門至山野鴨山錨地，分別通過經驗航線、遺傳算法規劃航線與DQN規劃航線在電子海圖上繪制航線對此見圖16。蝦峙門—野鴨山經驗航線表見表2，總長為28.57 n mile，拐彎6次，依航道航行，用帶箭頭的實線表示如圖16所示，依航道航行率為86.16%；A*算法規劃航線見表3，總長為26.78 n mile，拐彎14次，部分依航道航行，用帶箭頭的點線表示如圖16所示，依航道航行率為52.88%；以DQN規劃航線后，自動規劃航線的航點見表4，總長為27.06 n mile，拐彎5次，基本依航道航行，但未完全靠右航行，用帶箭頭的虛線表示如圖16所示，依航道航行率為69.14%。

圖16 經驗航線與自動規劃航線對比圖

表2 蝦峙門—野鴨山經驗航線表

表3 蝦峙門—野鴨山A*算法規劃航線表

表4 蝦峙門—野鴨山DQN規劃航線表

4 結束語

本文提出基于經驗航線的船舶航線規劃方法，同時采用DQN算法，在真實的電子海圖環境中實現經驗航線規劃功能。試驗表明：DQN算法可基于經驗航線進行電子海圖航線規劃，大大減少手動繪制航線的時間，可避免部分由于經驗不足導致航線規劃錯誤的問題，對今后基于經驗航線的航線規劃算法具有指導作用。本文已實現在電子海圖上基于經驗航線的船舶航線規劃，但依航道比率還有提升空間，且數據運算效率較低，下一步將對系統參數進行優化，并將其用于實際船舶航行中。