趙嵩郢，陳星燁

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

趙嵩郢1，陳星燁2

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

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

智能船舶 路徑規(guī)劃 蟻群算法

0 引言

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

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

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

1 經(jīng)典蟻群算法

1.1 柵格建模

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

圖1 障礙物膨化過程

1.2 經(jīng)典蟻群算法基本流程

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

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

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

2 改進蟻群算法

2.1 自適應(yīng)調(diào)整的狀態(tài)轉(zhuǎn)移概率策略

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

式中，為下一路徑點到目標(biāo)點的距離。這樣螞蟻選擇路徑就更有導(dǎo)向性，搜索路徑的有效性也有所提高。并且為了進一步提高初始可行解的構(gòu)造效率，考慮到螞蟻移動采用的是八叉樹策略，如下圖2所示。代表起始點，表示目標(biāo)點，表示螞蟻現(xiàn)在所在路徑點?？梢钥闯?，為了提高螞蟻的搜索速度，那么希望螞蟻在該節(jié)點盡可能選擇右下角的三個方向，其中標(biāo)紅加粗的方向最好。

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

2.2 自適應(yīng)調(diào)整的信息素更新策略

2.3 拐點處理策略

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

圖3 多余拐角示意圖

2.4 改進蟻群算法步驟

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

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

3 仿真結(jié)果驗證

3.1 改進蟻群算法驗證

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

圖5 對比實驗

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

3.2 仿真對比與分析

圖6 路徑規(guī)劃算法對比

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

表1 仿真計算參數(shù)表

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

4 結(jié)果分析

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

[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] 高天航, 呂靖, 賴成壽. 考慮船舶偏好的海上風(fēng)險規(guī)避路徑規(guī)劃研究[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] 孟祥杜. 無人船路徑規(guī)劃算法研究[D]. 天津理工大學(xué).

[5] 張玉奎. 水面無人艇路徑規(guī)劃技術(shù)研究[D]. 哈爾濱工程大學(xué), 2008.

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

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

[8] 童幫裕, 胡堅堃. 基于改進蟻群算法的船舶冰區(qū)航行路徑規(guī)劃[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] 劉雄, 雷勇, 涂國強. 基于蟻群算法的移動機器人路徑規(guī)劃[J]. 計算機仿真, 2011, 28(11): 4.

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

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

[13] 張海妮. 基于蟻群優(yōu)化算法的無人船艇航線自動生成及路徑規(guī)劃[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] 陳立家, 黃立文, 崔梅. 基于改進蟻群算法的船舶多約束最優(yōu)航線設(shè)計[J]. 上海海事大學(xué)學(xué)報, 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] 趙紅. 基于改進勢場蟻群算法的波浪動力滑翔器路徑規(guī)劃算法研究[D]. 青島大學(xué).

[18] 張金水, 何立居, 李啟華,等. 蟻群算法和遺傳算法結(jié)合的航線生成[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-），男，助理工程師。研究方向：智能船舶路徑規(guī)劃。E-mail: 15872427429@163.com