基于蟻群算法的無人船平滑路徑規(guī)劃

孫鵬娜，張忠民

(哈爾濱工程大學 信息與通信工程學院，黑龍江 哈爾濱 150001)

無人駕駛船(Unmanned Surface Vehicles，USV)與傳統人工駕駛船舶相比，具有高速化、智能化以及模塊化等優(yōu)點[1]。無人船可以代替人工駕駛船舶執(zhí)行某些特殊危險的任務，降低了人力成本。其還能夠長時間航行，有效規(guī)避疲勞駕駛的風險等優(yōu)點，因此具有良好的軍事及經濟價值[2]。在復雜多變的水面環(huán)境中，為了保證無人船能夠安全航行，規(guī)劃一條路徑較短、路線平滑、安全度高的航行路徑至關重要[3-4]。在智能啟發(fā)式算法中，蟻群算法更為穩(wěn)定、可靠，故被廣泛應用于尋找最優(yōu)解。但該算法也存在收斂性差、搜索盲目、易收斂到次優(yōu)解等問題。近些年，國內外對蟻群算法進行改進優(yōu)化并應用于路徑規(guī)劃中，取得了一定的成果。文獻[5]提出了一種融合粒子群和蟻群算法的路徑規(guī)劃算法，有效提高了初期尋徑和全局搜索能力，減少了收斂迭代次數并縮短搜索使用時間。文獻[6]提出基于路程因素、路平滑因素及高度平緩因素的啟發(fā)函數和信息素更新機制，改進算法具有較好的全局搜索能力及收斂性。文獻[7]采用初始信息素不均勻分配、引入權重因子和改進蟻群信息更新規(guī)則，規(guī)劃出平滑的全局路徑。文獻[8]為提高蟻群算法的動態(tài)避障能力，提出了一種基于模糊邏輯和蟻群算法的路徑規(guī)劃策略，搜索路徑較短，獲得了較好的效果。文獻[9]在啟發(fā)函數和信息素更新機制中融合A*算法和狼群分配原則，改進的蟻群算法具有較好的收斂性和可靠性。

結合近些年蟻群算法的改進方法和蟻群算法在規(guī)劃路徑時存在的問題，本文進行了以下改進：提出了基于路徑總長度、路徑轉彎次數以及自適應距離因子的改進啟發(fā)函數；結合路徑平滑性因素和自適應更新策略的信息素的更新標準，引入了障礙物因子的路徑轉移概率，并對輸出的最優(yōu)路徑進行平滑處理，從而提高路徑搜索能力、增加算法的收斂性和路徑的安全性。

1 傳統蟻群算法原理

螞蟻根據啟發(fā)函數的引導、路徑上的信息素濃度強弱以及當前節(jié)點狀態(tài)的轉移概率大小來實現路徑的搜索[10-11]。

1.1 轉移概率的選擇

當螞蟻k位于當前柵格i選擇下一步行進方向時，會根據當前各條路徑上的信息素濃度τi，j(t)及啟發(fā)函數ηi，j(t)來決定下一步路徑，路徑轉移概率為

(1)

式中，α表征信息素重要程度，其值與算法的全局搜索能力有關；β表示啟發(fā)函數重要程度，其值的大小影響螞蟻選擇下一步相鄰柵格；allowedi表示螞蟻k可選擇的下一步可行柵格集合。ηi，j(t)通常與兩柵格中心的歐氏距離成反比。柵格i、j的距離d越小，則選該路徑的啟發(fā)函數就越大。

(2)

1.2 信息素更新方式

螞蟻在行進過程中會留下信息素，用來為其他螞蟻提供指向信息。在蟻群的正反饋機制下，路徑上的信息素濃度強弱與吸引螞蟻數量成正比[12]。

目前蟻群算法中常用的信息素更新機制為蟻周模型，且信息素的分布只于路徑長度有關，更新方式如下

τi，j(t+1)=(1-ρ)τi，j(t)+ρΔτi，j(t，t+1)

(3)

(4)

通常設置初始信息素為

τi，j(0)=C

(5)

式中，ρ是信息素揮發(fā)系數，一般取ρ<1；Q是信息素常數；Lk為螞蟻k在本次迭代中走過的路徑長度；C為常數。下文在此基礎上改進信息素更新方式。

2 改進蟻群路徑規(guī)劃算法

2.1 改進啟發(fā)函數和轉移概率

由式(2)可以看出，傳統蟻群算法中啟發(fā)式函數只與路徑長度有關，而在實際的路徑規(guī)劃過程中，評價路徑優(yōu)劣不能只考慮與路徑長度因素，路徑的平滑程度、自適應距離啟發(fā)因子、算法運行時間等都是路徑的評價標準。因此本文從路徑總長度、路徑的平滑程度、自適應距離啟發(fā)因子等方面對啟發(fā)函數進行改進，改進方法如式(6)所示。

ηi，j(t)=r(i，j，g)+φi，j(t)

(6)

2.1.1 路徑長度因素

傳統蟻群算法的啟發(fā)函數與當前柵格到待走柵格之間的距離有關，本文提出的路徑長度因素與待走柵格到目標柵格以及待走柵格到起始柵格之間的距離因子有關。引入距離函數r(i，j，g)，其定義如下

(7)

(8)

dmax=max{d[m，g]}

(9)

dmin=min{d[m，g]}

(10)

m=1，2，…，card(allowedi)

(11)

式中，dmax、dmin是當前螞蟻k下一步可選擇的所有柵格中心到目標柵格中心的最大、最小距離；μ(s，j，g)表示表示待走柵格j的中心到起始柵格和目標柵格中心的距離啟發(fā)因子；a、b是距離系數；δ是距離啟發(fā)信息系數；d(s，j)和d(j，g)分別表示下一個可行柵格j到起始柵格和目標柵格中心的歐氏距離。

2.1.2 路徑平滑度因素

考慮到無人船的實際行駛情況，當規(guī)劃路徑轉彎次數盡可能少，轉彎角度也盡可能小[13]，且路徑更加平滑時，可提高路徑行駛的安全性。因此，本文引入平滑性啟發(fā)函數，如式(12)所示。

(12)

式中，δ為路徑平滑系數；η是表征直行重要程度的系數；Dv，j(t)表示螞蟻上一步行走的轉向方向；Di，j(t)表示下一步待走的轉向方向。如果當前轉向與上次轉向相同，即當前路徑為直線行走時，平滑性啟發(fā)函數大，從而指引螞蟻沿直線行走，減少了不必要的路徑轉彎次數。

2.2 改進轉移概率

傳統算法中的路徑轉移概率只考慮了待走柵格與目標柵格之間的距離啟發(fā)因子，忽略了待走柵格與障礙柵格之間的距離啟發(fā)信息。因此本文在轉移概率中引入了障礙物啟發(fā)函數，改進后的路徑轉移概率為

(13)

γj，b(t)=1/mind(j，b)，b=1，2，…，card(obsj)

(14)

式中，γj，b(t)表示待走柵格j到鄰接障礙柵格b的歐式距離最小值的倒數。

2.3 改進信息素更新方式

2.3.1 改進信息素更新模型

根據啟發(fā)因子的改進思路，將路徑長度和路徑平滑度作為信息素的更新標準，改進方式如下

τi，j(t+1)=(1-ρ)τi，j(t)+ρΔτi，j(t，t+1)

(15)

(16)

Sk(t)=a×Lk(t)+b×Tk(t)

(17)

(18)

式中，Sk(t)為第t次迭代中螞蟻行走路徑的性能指標，Sk(t)越小，該路徑的信息素分配越高，路徑的綜合性能越好；Lk(t)為當前迭代路徑；Tk(t)為當前路徑的轉彎個數；Lbest為歷史迭代中的最優(yōu)路徑；a、b為常系數；μ為信息素調節(jié)系數。

2.3.2 自適應信息素揮發(fā)系數

蟻群算法的正反饋特性會引導螞蟻傾向于走某一較優(yōu)解，減小了對全局的路徑搜索，導致算法收斂到次優(yōu)解[14]。減小ρ可以增強對路徑的全局搜索但會降低收斂速度[15]。根據信息素揮發(fā)系數的性質，本文提出可以根據不同要求進行動態(tài)調節(jié)的信息素揮發(fā)系數ρ。本文提出的改進為：

(1)設置信息素的上下限閾值，且t=0時，ρ=ρmax；

(2)設定迭代次數閾值M；

(3)當迭代次數Nc等于M后取常數ρ0。ρ0值可根據不同環(huán)境進行調節(jié)，當迭代次數Nc不等于閾值M時，信息素揮發(fā)系數ρ減小并與信息素閾值下限進行比較，取兩者間較大值，即

(19)

式中，λ為遞減常數，λ<1。

2.4 路徑平滑處理

傳統蟻群算法沒有考慮路徑轉向時的轉彎半徑，而在實際行駛過程中，需要考慮轉向能耗并且避免轉向過程中發(fā)生側翻。因此本文在改進蟻群算法規(guī)劃航行路徑的基礎上，通過B樣條插值法對路徑進行平滑處理，從而確保船舶行駛的穩(wěn)定性[16]。圖1為簡易無人船簡化模型。

圖1 無人船轉向簡化模型Figure 1. Simplified steering model of USV

假設無人船在航行過程中某一時刻處于(x，y)位置，此時無人船的航向為θ，船舶中軸與轉向方向的偏移角為φ，無人船的轉向角度具有機械特性的約束[17]，即

|φ|≤φmax

(20)

因此，無人船行駛的最小轉彎路徑為

Rmin=L×cotφmax

(21)

式中，L是船舶的中軸距離差。為保證轉向的安全性，需要滿足轉彎路徑大于最小轉彎路徑。

路徑平滑處理中一般使用插值法進行路徑擬合。常用的插值法有貝塞爾曲線、多項式曲線以及B樣條曲線等。貝塞爾曲線插值容易，但改變某個關鍵點時整個曲線隨之變化。多項式曲線在高次插值時可能會出現龍格現象[18]。B樣條曲線是通過逼近關鍵點產生的，可以局部控制曲線，具有凸包性、保凸性、變差減小性等優(yōu)點[19]。因此對輸出的最優(yōu)路徑提取關鍵節(jié)點，對拐點進行B樣條插值處理。

圖2 平滑處理前后路徑對比Figure 2. Comparison chart of path smoothing and unsmoothing

平滑處理結果如圖2所示。未進行平滑處理時，路徑拐點明顯，某些轉向角度達到了π/2，不符合實際航行需求。而平滑處理后的路徑可以有效滿足轉向時安全轉向角和最小轉彎路徑的要求。

2.5 改進算法流程

本文改進蟻群算法的運行流程如圖3所示。

圖3 改進算法運行流程Figure 3. Flow chart of the improved algorithm

3 算法仿真及分析

為了驗證改進蟻群算法在路徑規(guī)劃中的可行性，本文使用MATLAB軟件在不同柵格環(huán)境下進行仿真。

3.1 20×20柵格環(huán)境仿真

建立較為簡單的20×20柵格環(huán)境，對本文改進的蟻群算法進行了仿真。設置對角線型的起始柵格與目標柵格，并對仿真參數進行設置。多次仿真后的結果如圖4所示。

(a)

(b)

(c)圖4 20×20柵格最優(yōu)路徑及路徑平滑優(yōu)化(a)改進算法最優(yōu)路徑仿真 (b)平滑處理后的路徑 (c)路徑綜合性能及平均綜合性能迭代Figure 4. Optimal path and path smoothing in 20×20 grid map(a)Optimal path simulation of improved algorithm (b)Optimal path simulation after path smoothing (c)Iterative graph of path comprehensive and average comprehensive performance

從圖4(a)可以看到，為了有效避免與障礙物的邊角相撞，保障路徑的安全性，改進算法規(guī)劃的路徑犧牲了一部分路徑長度并且增加了轉彎個數，但是路徑的可行性有明顯提高，說明該改進算法能較好地對環(huán)境的進行全局路徑規(guī)劃。圖4(b)為平滑處理后的路徑，能夠較好地處理拐點信息，轉向角度更加符合無人船實際行駛情況。下文中改進算法仿真結果都為路徑平滑處理后的路徑。由圖4(c)中可以看出該改進算法具有較好的收斂性，迭代曲線整體呈下降趨勢并且收斂速度較快，算法后期的收斂性較為穩(wěn)定，沒有出現收斂到次優(yōu)解和陷入局部最優(yōu)解的情況。通過仿真分析可知，本文的算法改進較為符合預期結果。

3.2 30×30柵格環(huán)境仿真

為了驗證本文改進蟻群算法在路徑規(guī)劃的可靠性，使用30×30柵格環(huán)境對本文改進蟻群算法、傳統蟻群算法以及文獻[6]提出的改進算法進行仿真。

表1 30×30柵格環(huán)境下3種算法仿真結果

(a)

(b)

(c)圖5 30×30柵格環(huán)境下3種算法仿真結果(a)3種算法最優(yōu)路徑對比圖 (b)3種算法最優(yōu)路徑長度收斂圖 (c)3種算法最優(yōu)路徑轉彎次數收斂圖Figure 5. Simulation results of three algorithms in 30×30 grid map(a)Optimal path comparison graph of three algorithms (b)Optimal path length convergence graph of three algorithms (c)Path steering times convergence graph of three algorithms

從圖5可以看出，點線表示的傳統蟻群算法歷代路徑收斂波動較大，迭代性能不夠穩(wěn)定，并且從圖5(c)中可知傳統算法在轉彎次數達到最優(yōu)之后，反而收斂到一條轉彎次數較多的路徑；點劃線表示的文獻[6]改進蟻群算法和實線表示的本文改進算法在路徑長度和轉彎次數的迭代曲線整體呈下降趨勢。表1仿真結果顯示，本文改進算法與傳統蟻群算法、文獻[6]算法相比，在迭代初期、各代最優(yōu)路徑以及最后輸出的最優(yōu)路徑在收斂性、最優(yōu)路徑長以及轉彎次數方面都具有明顯優(yōu)勢，并且在第10次迭代左右就收斂到了最優(yōu)結果，算法運行時間高于傳統算法優(yōu)于文獻[6]的改進算法。

3.3 50×50柵格環(huán)境仿真

為了進一步驗證本文改進算法具有較優(yōu)的全局搜索性和較高的路徑規(guī)劃優(yōu)化能力，設置了更為復雜的50×50的柵格環(huán)境進行仿真。由于在30×30柵格環(huán)境中，傳統蟻群算法規(guī)劃的路徑在路徑長度和轉彎次數以及算法收斂性等方面都明顯劣于文獻[6]改進蟻群算法和本文改進蟻群算法，因此在50×50的柵格環(huán)境下只對本文改進算法和文獻[6]改進算法進行仿真。

表2 50×50柵格環(huán)境下兩種算法仿真結果比較

(a)

(b)

(c)圖6 50×50柵格環(huán)境下兩種算法仿真結果比較(a)兩種算法最優(yōu)路徑對比圖 (b)兩種算法最優(yōu)路徑迭代收斂圖 (c)兩種算法最優(yōu)路徑轉彎次數收斂圖Figure 6. Simulation results of two algorithms in 50×50 grid map(a)Optimal path comparison graph of two algorithms (b)Optimal path length convergence graph of two algorithms (c)Path steering times convergence graph of two algorithms

如表2和圖6所示，在較為復雜的仿真環(huán)境中，點劃線表示的文獻[6]算法迭代變得不夠穩(wěn)定，而實線表示的本文改進蟻群算法的迭代曲線整體呈下降趨勢。迭代初期、各代最優(yōu)路徑以及最后輸出的最優(yōu)路徑在收斂性、最優(yōu)路徑長以及轉彎次數方面都具有明顯優(yōu)勢，并且在第13次迭代后期收斂到了最優(yōu)路徑。本文改進算法后期的收斂性較穩(wěn)定，且穩(wěn)定性較好，沒有出現收斂到次優(yōu)解的情況。

4 結束語

本文針對無人駕駛船舶在航行環(huán)境復雜，傳統算法不能滿足路徑長度、路徑平滑度、路徑安全等多方面的要求，根據無人船航行的特點和要求，對傳統蟻群算法進行了優(yōu)化改進，使之符合實際船舶的航行需求。本文在啟發(fā)函數中加入了路程長度、平滑度等因素的影響，引入了障礙物對轉移概率的影響并對信息素更新方式進行了改進，從而設計出一條各方面都較優(yōu)的路徑。根據仿真結果，本文改進的蟻群算法有效解決了傳統蟻群算法存在的問題，規(guī)劃的路徑在航程、路徑平滑度、安全性等方面都有較好的表現。