基于改進蟻群算法的智能船舶路徑規劃*

龔銘凡 徐海祥 馮 輝 薛學華

(高性能船舶技術教育部重點實驗室1) 武漢 430063) (武漢理工大學交通學院2) 武漢 430063)

0 引 言

智能船舶由智能機艙、智能船體、智能航行、智能能效管理、智能貨物管理，以及智能集成平臺這六個模塊組成[1].其中路徑規劃是智能航行的重要組成部分，其任務為依照單個或多個優化準則(如距離最優、時間最短、安全性最高等)，找到從初始節點至目標節點避開障礙物的最優或較優路徑[2-3].目前，路徑規劃方法主要有以下三類：傳統路徑規劃方法、基于生物智能和基于強化學習的路徑規劃方法.第一類路徑規劃方法有A*算法[4]，Djikstra算法[5]，人工勢場法[6]等.A*算法在Djikstra基礎上加入啟發式估計，提升了搜索效率，然而面對復雜環境，其效率仍然很低.文獻[7]針對復雜環境A*算法計算時間長，提出時間效率A*算法.文獻[8]通過修改斥力函數，使人工勢場法避免陷入局部最小值而無法跳出，其主要應用場景為目標不可達情況.第二類基于生物智能的方法有粒子群算法[9]、蟻群算法[10]、遺傳算法[11]、神經網絡[12]等.這些群智能算法全局尋優好，不需要建立復雜的環境模型，但參數較多且不確定、收斂速度慢、算法復雜度較高.文獻[13]將粒子群算法與遺傳算法相融合，用于解決自主無人機在三維環境的復雜問題.文獻[14]針對傳統蟻群算法易陷入局部最優的問題，在路徑搜索過程間產生螞蟻，開辟新路徑，增加跳出局部最小值的可能.第三類基于強化學習的方法有Q-leaning算法[15]，Sarsa算法[16]等.與之前的算法相比，強化學習具有學習能力強、復雜未知環境適應度好等優點，但是目前的強化學習中試錯學習、狀態泛化，需消耗大量資源[17].綜上所述，每種算法都有各自的優點與局限，因此，混合算法為路徑規劃提供了一個新的思路，取長補短，從而有效解決實際工程問題.

文中提出的基于勢場啟發式信息的改進蟻群算法，在尋徑過程中，引入船舶受到引力、斥力與其到目標點的間距相結合構建啟發式信息，為算法進行全局路徑規劃提供搜索策略，防止其進入局部最優.改進傳統信息素更新，加入最差蟻群對整個蟻群的負面作用，加快收斂，并對信息素系數進行自適應調節，提升全局搜尋能力.仿真實驗分別比較了傳統算法與本文算法在兩種不同環境下的搜索性能，并對算法中的重要參數進行了敏感性分析.

1 基本蟻群算法

1.1 柵格法環境建模

將障礙物按照船舶的半徑進行適當膨脹，再將未填充滿的柵格補充完整(見圖1)，以確保船舶進行無碰撞運動.蟻群算法對柵格的訪問以一個柵格中心位置為準，不可在柵格的端點或邊界處.柵格標識常見方法有直角坐標法和序號法，且二者可互相轉換.采用序號法，對柵格地圖從上至下、從左至右進行標識，柵格序號集為S={1,2,…,E}.E為右下柵格，對于N1×N2的柵格空間，E=N1×N2.

圖1 障礙物柵格化

1.2 蟻群算法的基本原理

算法中最為重要的兩個步驟為轉移概率選擇以及更新信息素的方式.轉移概率選擇，即一只螞蟻在當下節點前往下一節點是按照一定的幾率去選取.蟻群算法通過輪盤賭的形式選取下一位置，其狀態轉移概率為

(1)

式中：am={1,2,…,n}-Bm為螞蟻可選擇的節點集合；Bm為禁忌表(螞蟻m走過的點)；α為信息素啟發因子，表示之后的螞蟻尋徑時受信息素影響程度；β為期望啟發因子，表示螞蟻受啟發信息影響大??；ηij為啟發函數，表示當前螞蟻領域j到目標E的間距啟發信息,ηij(k)=1/djE.

啟發信息以及信息素濃度大小是螞蟻選取路徑的關鍵依據，由于信息素濃度會跟隨時間增加而慢慢消失，所以算法會更新局部及全局信息素，為

τij(k+1)=(1-λ)τij(k)+τ0

(3)

τij(k+1)=(1-ρ)τij(k)+Δτij(k)

(4)

其中：

(5)

式中：1-λ為局部信息素殘留系數；ρ為全局信息素揮發系數；τij(k)為第k次迭代時節點i、j間信息素；τ0為初始信息素濃度，是一個小的常量；Δτij為蟻群一次迭代后信息素增量；Q為信息素強度；Lm為螞蟻m在本次循環中的路徑長短.

由式(6)可得，節點i，j之間留下的信息素強度和路徑優化程度息息相關，路徑越短，留下信息素濃度越高，而蟻群將跟隨濃度較高的路徑.

2 基于勢場啟發式信息的改進蟻群算法

2.1 改進啟發信息

借鑒人工勢場法的思想，障礙物在其四周的一定范圍內存在斥力場，而目標節點對船舶形成一個引力場，即船舶在整個環境中所受的合力為目標節點的引力與障礙物的斥力相加.

將以上勢場信息與距離信息相結合從而改進啟發信息，使螞蟻向合力方向尋徑，其中勢場合力啟發信息為

ηs(k)=cFtol·cos θ

(7)

式中：c為正常數；θ為勢場合力Ftol與螞蟻可選路徑間的夾角.在此條件下，螞蟻從當前位置到下一節點位置的選擇會趨向于夾角θ較小的方向.該部分啟發信息引入了環境勢場信息，可更有效地使船舶避免與障礙物的碰撞.

綜合距離啟發信息式(2)得：

(8)

由于人工勢場本身會存在引力與斥力相抵，即合力為0的情況，此時會陷入局部最小值，若僅采用勢場力作為啟發信息，就會陷入局部最小值而無法逃脫.而綜合蟻群算法本身的啟發信息，即使勢場合力為零，仍擁有距離信息作為啟發信息，引導船舶跳出局部最優，繼續尋找最優路徑.

2.2 改進信息素更新

修改全局信息素更新機制，加入最差蟻群的影響，對殘留信息素與當前信息素加權，其更新規則為

τij(k+1)=g(1-ρ)τij(k)+(1-g)Δτij(k)

(9)

(10)

(11)

(12)

式中：ρmin為揮發系數閾值.由式(12)可見，揮發系數會越來越小直至到達最小值.

2.3 算法步驟

改進算法流程圖見圖2.

圖2 改進算法流程圖

3 仿真結果與分析

蟻群算法中的參數的最優選取目前還沒有嚴謹的理論支撐，主要取決于統計數據以及經驗.但算法中的重要參數，如啟發式因子、蟻群數量等，都會對路徑規劃的結果優劣產生重要影響，因此對參數進行敏感性分析具有重要意義.

文中設置兩個路徑規劃環境分別為：20×20個柵格，較少障礙物；30×30個柵格，較多障礙物，見圖3.

圖3 算法運行環境

3.1 啟發式因子的影響

信息素啟發式因子α的大小表示遺留信息素對蟻群尋徑影響大小，而期望啟發式因子β的高低體現啟發函數于尋徑中重要程度.圖4為信息素啟發因子對應的最優距離.由圖4可知，不論是簡單、復雜環境，還是算法改進前后，曲線整體大致都是隨著α的增加而下降直至穩定.除此以外，改進算法比原算法更容易尋得最優路徑且在長度上占優.結合改進后的兩種環境曲線變化，選取α=0.8，路徑相對最短，此時觀察期望啟發式因子的變化.

圖4 信息素啟發式因子α對應最優距離

圖5為期望啟發因子對路徑長度的影響，圖中的曲線趨勢均為遞減，即β越大，最佳路徑長度越短.由圖5可知，相對于基本蟻群算法，本文提出的改進勢場蟻群算法尋得路徑更短、更為穩定，并且環境越復雜，路徑長度差異越大.通過簡單、復雜環境曲線，選擇β=4，使兩者路徑長度均最優.因此，最佳的啟發式因子組合為α=0.8，β=4.

圖5 期望啟發式因子β對應最優距離

3.2 螞蟻數量的影響

螞蟻數量對算法得到的最優路徑影響見圖6.相較于原算法曲線的大波動，改進蟻群算法得到的曲線更為平滑.在簡單環境中，當M=50時，本文算法得到最優解，且蟻群數量增加，路徑長度不變；復雜環境下，螞蟻數量為70時，路徑最短，且隨著數量加大，所得解在其上下微小波動.考慮到時間復雜度及迭代收斂速度，選取蟻群數量為60最為適宜.

圖6 蟻群數量M對應最優距離

3.3 最優參數下路徑規劃仿真分析

運用傳統蟻群算法和改進蟻群算法在仿真平臺進行實驗.參數設置：螞蟻數量M=60，迭代次數K=60，初始信息素揮發系數ρ=0.4，啟發式因子α=0.8，β=4.圖7為船舶在兩種不同環境下，通過改進算法得到了全局最優路徑.

圖7 改進算法路徑規劃

兩種算法對比結果見表1.由表1可知，在兩種算法均各自收斂至最優后，時間上，本文算法為0.9,和9.8 s，與基本蟻群算法的3.5和16.6 s相比有顯著提升；路徑上，在簡單環境下路徑相差不大，但在復雜環境情況下差距明顯，本文算法路徑長度為45.9 m，較基本蟻群算法減少了7 m左右.因此，本文算法在路徑長度及時間成本上更優.

表1 兩種算法對比結果

兩種環境下的迭代收斂曲線見圖8.由圖8可知，兩種環境下，原算法均收斂較為緩慢且一直在振蕩，而本文算法均循環12次左右收斂至最優且較為穩定.

圖8 兩種環境下的迭代收斂曲線

由于蟻群算法規劃的節點均為柵格中心，使得計算出擁有較多轉折點及一些不必要的路徑，因此，對算法生成的曲線進行平滑處理.若路徑連續三個點連接不過障礙物，則將中間點剔除；反之，路徑保持不變.以此類推，保留必需點，剔除多余點，獲得路徑長度分別為28，45 m，由此可得，縮減后的路徑更為平滑且長度更短，見圖9中虛線部分.

圖9 路徑縮減之后的路徑規劃

4 結 束 語

文中提出了一種改進蟻群算法適用于全局靜態的路徑規劃.利用勢場合力作為啟發函數的一部分，讓船舶有效規避障礙物且不斷靠近目標節點，結合距離啟發信息，使船舶更快尋得最近路線.針對原算法復雜度高、收斂速度較慢且消耗時間長等問題，加入最差路徑蟻群影響，修改全局信息素更新機制，增加收斂速度，降低算法時間.針對基本蟻群算法及改進蟻群算法中重要的參數采用單因素法，分析其對路徑規劃的路程及時間的影響.在最優參數的基礎上，將兩者進行分析比較.仿真結果證實了改進后算法的有效性及可行性.最后采用路徑縮減，將獲取的路徑曲線進行優化處理.本文的仿真環境為全局靜態，后續將結合未知環境及動態障礙物進行局部路徑規劃研究.