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

趙嵩郢，陳星燁

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

趙嵩郢1，陳星燁2

(1. 武漢船用電力推進裝置研究所，武漢 430064；2. 渤海造船廠集團有限公司，葫蘆島 125000)

船舶路徑規劃是指在特定的海洋環境下，按照一定的尋優策略，給定出發點和目標點，完成船舶航行所需求的航線規劃。本文依據改進的蟻群算法進行智能船舶路徑規劃，基于對障礙物膨化處理后的柵格地圖，針對經典蟻群算法局部最優問題，加入了狀態自適應調整，信息素自適應更新和拐角處理策略，在提高算法收斂速度的同時保證了所得路徑的平滑性及安全性，實現了智能船舶的安全、經濟航線規劃。

智能船舶 路徑規劃 蟻群算法

0 引言

船舶是水面交通運輸領域最為重要的交通工具，船舶航行安全是世界船舶領域長期的研究課題，其經濟性與社會意義十分重大[1]。船舶航行常規方式是操控人員憑借駕駛經驗，開展航線規劃和船舶操控，其規劃和操控效果往往過度依賴操控人員判斷能力和經驗，出現差錯可能性高且存在潛在風險[2]。

智能化是船舶發展的必然方向，而路徑規劃是船舶智能航行中的重要組成部分[3]。船舶路徑規劃是指在特定的海洋環境下，按照一定的尋優策略，給定出發點和目標點，完成船舶所需求的安全、經濟、可行性高航線規劃[4]。一般來說，路徑規劃主要包括兩個方面: 1）一是已知全局地圖的全局路徑規劃；2）已知局部信息，需動態更新的局部路徑規劃[5]。

本文依據改進的蟻群算法[6-10]進行智能船舶路徑規劃，該算法不依賴于大量的先驗知識，算法結構簡單容易理解并易于實現，對于復雜問題的優化求解具有很強的適應性。基于對障礙物進行膨化處理后的柵格地圖，本文所改進的蟻群規避了蟻群算法局部最優的缺點，主要加入了狀態自適應調整，信息素自適應更新和拐角處理策略，在提高算法收斂速度的同時保證了所得路徑的平滑性及安全性，實現了智能船舶的安全、經濟全局路徑規劃。

1 經典蟻群算法

1.1 柵格建模

柵格法是一種基于柵格構建的地圖建模方法[11]。考慮到智能船舶在有限區域的移動路徑基本服從于二維平面，柵格建模過程中通過將障礙物按照船舶的半徑進行適當膨脹，再將未填充滿的柵格補充完整（見圖1），以確保船舶進行無碰撞運動。即當障礙物未填充整個柵格時，該柵格要作為障礙柵格處理，即障礙物所在的所有柵格均視為障礙柵格，如圖1所示。

圖1 障礙物膨化過程

1.2 經典蟻群算法基本流程

螞蟻尋路過程中會在柵格留下信息素,信息素具有累加效果，同時信息素會逐漸消散，所以迭代過程中需要對路徑上信息素進行更新：

智能照明系統功能能夠在不同的駕駛條件和天氣條件下，增加燈光輸出并通過促動前大燈中各促動器開啟額外燈光源，實現最佳道路照明。尾燈根據相關法規要求，LED燈在白天和夜間具有不同的強度設置，其優勢在于照明功能的亮度足以滿足后方車輛駕駛員正確判斷交通狀況的需要。為更好地了解大燈系統，根據其不同的功能借助相應的原理圖來進一步說明，如圖12所示CAN總線和LIN總線都具有雙向性，即能傳輸又能接收信息。

以智能船舶的全局路徑規劃問題為例，蟻群算法實現步驟如下:

2 改進蟻群算法

2.1 自適應調整的狀態轉移概率策略

蟻群算法是一種隨機啟發式搜索算法[13]，在前期搜索中為提高解得多樣性，會產生大量無意義的交叉路徑，而且螞蟻在尋路時由于禁忌表的限制無法走重復的路徑[14]，螞蟻在前期搜索中容易出現還沒有走到終點就進入“死路”，無法再繼續搜索路徑。這種情況在復雜地圖和規模較大的地圖中表現的更為明顯[15]。故為了使其對目標更有趨向性，盡量減少無用路徑的出現，對于基本蟻群算法以螞蟻所在節點到下一節點的距離反比為期望函數選擇路徑點的概率公式是，本文采用了新的期望函數即以螞蟻能抵達的下一節點到目標點的距離反比：

式中，為下一路徑點到目標點的距離。這樣螞蟻選擇路徑就更有導向性，搜索路徑的有效性也有所提高。并且為了進一步提高初始可行解的構造效率，考慮到螞蟻移動采用的是八叉樹策略，如下圖2所示。代表起始點，表示目標點，表示螞蟻現在所在路徑點。可以看出，為了提高螞蟻的搜索速度，那么希望螞蟻在該節點盡可能選擇右下角的三個方向，其中標紅加粗的方向最好。

為此，進一步運用自適應調整的期望函數將節點之間的差值拉大，以保證搜索的針對性，提高算法的運行速度，如下式所示。

2.2 自適應調整的信息素更新策略

2.3 拐點處理策略

在經典蟻群算法的路徑搜索中，通常將路徑長度作為主要的路徑評價標準，為了能更快地找出較優的路徑解，不僅僅在最后評價路徑時考慮拐角，在算法運行中也加入了拐角處理[17]。而在船舶航行的過程中，路徑中多余拐點的產生會影響船舶航行的平滑性和安全性，且對船舶的控制提出了較高的機動性要求[18]。小角度拐角會導致智能船舶的大幅度轉向，不利于船舶的安全航行。因此，需要對規劃得到的路徑進行優化，以減少路徑中不必要的拐點，提高路徑的平滑度。

圖3 多余拐角示意圖

2.4 改進蟻群算法步驟

本文對經典蟻群算法予以改進，添加了自適應啟發因子提高算法收斂速度，對于所得路徑進行小角度拐角處理策略，避免多余拐點的產生，提高了所得路徑的平滑性和安全性。所得的改進算法搜索路徑流程如圖4所示：

圖4 改進蟻群算法示意流程圖

3 仿真結果驗證

3.1 改進蟻群算法驗證

為了驗證改進算法的普遍性，本文以20*20的柵格地圖為例，對改進的蟻群算法與基本的蟻群算法進行對比，其中黑色區域為不可行區域，白色區域為無障礙可行區域。實驗仿真結果如圖5所示：

圖5 對比實驗

通過對智能船舶路徑規劃模塊得到的最優路徑以及算法收斂曲線可以看出，改進蟻群算法所規劃得到的船舶航行路徑的拐點數目明顯少于由經典蟻群算法規劃得到的路徑，并且在蟻群搜索的前期，改進算法收斂速度明顯高于傳統算法，在相同的迭代次數為15時，基本的蟻群算法甚至還未收斂，而改進后的蟻群算法收斂速度已經趨近于結束。結果顯示，改進蟻群算法所獲得的最優路徑長度短且平滑，其收斂速度相比經典蟻群也獲得了較大的提升。

3.2 仿真對比與分析

圖6 路徑規劃算法對比

結果顯示，雖然三種算法均搜索到起始點及終點間的有效移動路徑，但A*算法由于未設置八叉樹搜索策略，相比蟻群算法搜索路徑較長，耗時較多。而兩種蟻群算法都斜向搜索到一條較短的移動路徑，但經典的蟻群算法在搜索區域的范圍上明顯要更大，耗時也更多；本文基于改進的蟻群算法終點趨向性明顯，搜索范圍較小，并且由于加入拐點處理策略，改進算法在大幅度90°拐點的數量上明顯少于傳統算法，路徑的平滑性能提高了很多，具體對比如表1所示。

表1 仿真計算參數表

表中為同一地圖下三種算法經20次運行后的所得結果平均值，拐點平均值取四舍五入結果。由此可得，基于改進蟻群算法搜索得到最優路徑長度相比經典蟻群及A*算法更短，且從多次運行的效果來看，本文改進算法的平均運算時間也比其余兩種常規算法要低。總而言之，相比經典蟻群算法，改進算法避免了路徑中較多拐點的產生，提高了智能船舶路徑規劃的平滑性和安全性，同時相比改進之前，算法收斂速度也有所提升，改進算法的整體有效性及適用性較佳。

4 結果分析

本文針對智能船舶航行過程中路徑規劃的特點，充分考慮到船舶航行的經濟性、安全性以及航行路徑的平滑性。本文所提出面向智能船舶的改進蟻群路徑規劃方法，相比經典蟻群算法，加入了自適應調整的狀態轉移概率策略，信息素自適應更新策略和拐角處理策略，提高算法收斂速度的同時保證了所得路徑的平滑性及安全性，能夠有效完成智能船舶的安全、經濟路徑規劃。本文研究也存在不足之處，即本文的路徑規劃環境為全局靜態，缺乏對動態障礙物及船舶航速等方面的考慮，后續將結合全局地圖信息及局部傳感器信息進行更為全面的智能船舶航行路徑規劃。

[1] Jiang J, Zeng X, Guz zet ti D , et al. Path planning for asteroid hopping rovers with pre-trained deep reinforcement learning architectures[J]. ActaAstronautica, 2020, 171:265-279.

[2] 高天航, 呂靖, 賴成壽. 考慮船舶偏好的海上風險規避路徑規劃研究[J]. 運籌與管理, 2018, 27(11):7.

[3] Jianhua Liu, Jianguo Yang, Huaping Liu, et al. An improved ant colony algorithm for robot path planning[J]. Soft Computing, 2017.

[4] 孟祥杜. 無人船路徑規劃算法研究[D]. 天津理工大學.

[5] 張玉奎. 水面無人艇路徑規劃技術研究[D]. 哈爾濱工程大學, 2008.

[6] Dorigo M, Caro G D . The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances. new ideas in optimization, 1999.

[7] 張松燦, 普杰信, 司彥娜,等. 蟻群算法在移動機器人路徑規劃中的應用綜述[J]. 計算機工程與應用, 2020, 56(8): 10.

[8] 童幫裕, 胡堅堃. 基于改進蟻群算法的船舶冰區航行路徑規劃[J]. 中國航海, 2020, 43(1):5.

[9] Lee S M, Roh M I , Kim K S , et al. Method for a simultaneous determination of the path and the speed for ship route planning problems[J]. Ocean Engineering, 2018, 157: 301-312.

[10] 劉雄, 雷勇, 涂國強. 基于蟻群算法的移動機器人路徑規劃[J]. 計算機仿真, 2011, 28(11): 4.

[11] 康與濤, 朱大奇, 陳偉炯. 船舶避碰路徑規劃研究綜述[J]. 船海工程, 2013, 42(5): 5.

[12] 呂紅光, 尹勇. 基于電子海圖矢量數據建模的無人船路徑規劃[J]. 交通信息與安全, 2019, 37(5):13.

[13] 張海妮. 基于蟻群優化算法的無人船艇航線自動生成及路徑規劃[J]. 艦船電子工程, 2019, 39(3):5.

[14] Xin J, Zhong J, Yang F, et al. An Improved Genetic Algorithm for Path-Planning of Unmanned Surface Vehicle[J]. Sensors, 2019, 19(11):2640-.

[15] 陳立家, 黃立文, 崔梅. 基于改進蟻群算法的船舶多約束最優航線設計[J]. 上海海事大學學報, 2017, 38(4): 5.

[16] Chen Z, Zhang Y, Zhang Y, et al. A Hybrid Path Planning Algorithm for Unmanned Surface Vehicles in Complex Environment With Dynamic Obstacles[J]. IEEE Access, 2019, PP(99): 1-1.

[17] 趙紅. 基于改進勢場蟻群算法的波浪動力滑翔器路徑規劃算法研究[D]. 青島大學.

[18] 張金水, 何立居, 李啟華,等. 蟻群算法和遺傳算法結合的航線生成[J]. 中國航海, 2015(2): 5.

Global Path Planning Method for Intelligent Ship Based on Improved Ant Colony Algorithm

Zhao Songying1, Chen Xingye2

(1. Wuhan Institute of Marine Electric Propulsion, Wuhan 430064, China；2. Bohai Shipyard Group Limited Company, Huludao 125000, China)

TP332

A

1003-4862(2022)08-0072-05

2022-02-15

趙嵩郢（1996-），男，助理工程師。研究方向：智能船舶路徑規劃。E-mail: 15872427429@163.com