孫鵬娜，張忠民

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

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

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

1 傳統(tǒng)蟻群算法原理

螞蟻根據(jù)啟發(fā)函數(shù)的引導(dǎo)、路徑上的信息素濃度強(qiáng)弱以及當(dāng)前節(jié)點(diǎn)狀態(tài)的轉(zhuǎn)移概率大小來(lái)實(shí)現(xiàn)路徑的搜索[10-11]。

1.1 轉(zhuǎn)移概率的選擇

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

(1)

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

(2)

1.2 信息素更新方式

螞蟻在行進(jìn)過(guò)程中會(huì)留下信息素，用來(lái)為其他螞蟻提供指向信息。在蟻群的正反饋機(jī)制下，路徑上的信息素濃度強(qiáng)弱與吸引螞蟻數(shù)量成正比[12]。

目前蟻群算法中常用的信息素更新機(jī)制為蟻周模型，且信息素的分布只于路徑長(zhǎng)度有關(guān)，更新方式如下

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

(3)

(4)

通常設(shè)置初始信息素為

τi，j(0)=C

(5)

式中，ρ是信息素?fù)]發(fā)系數(shù)，一般取ρ<1；Q是信息素常數(shù)；Lk為螞蟻k在本次迭代中走過(guò)的路徑長(zhǎng)度；C為常數(shù)。下文在此基礎(chǔ)上改進(jìn)信息素更新方式。

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

2.1 改進(jìn)啟發(fā)函數(shù)和轉(zhuǎn)移概率

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

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

(6)

2.1.1 路徑長(zhǎng)度因素

傳統(tǒng)蟻群算法的啟發(fā)函數(shù)與當(dāng)前柵格到待走柵格之間的距離有關(guān)，本文提出的路徑長(zhǎng)度因素與待走柵格到目標(biāo)柵格以及待走柵格到起始柵格之間的距離因子有關(guān)。引入距離函數(shù)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是當(dāng)前螞蟻k下一步可選擇的所有柵格中心到目標(biāo)柵格中心的最大、最小距離；μ(s，j，g)表示表示待走柵格j的中心到起始柵格和目標(biāo)柵格中心的距離啟發(fā)因子；a、b是距離系數(shù)；δ是距離啟發(fā)信息系數(shù)；d(s，j)和d(j，g)分別表示下一個(gè)可行柵格j到起始柵格和目標(biāo)柵格中心的歐氏距離。

2.1.2 路徑平滑度因素

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

(12)

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

2.2 改進(jìn)轉(zhuǎn)移概率

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

(13)

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

(14)

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

2.3 改進(jìn)信息素更新方式

2.3.1 改進(jìn)信息素更新模型

根據(jù)啟發(fā)因子的改進(jìn)思路，將路徑長(zhǎng)度和路徑平滑度作為信息素的更新標(biāo)準(zhǔn)，改進(jìn)方式如下

τ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次迭代中螞蟻行走路徑的性能指標(biāo)，Sk(t)越小，該路徑的信息素分配越高，路徑的綜合性能越好；Lk(t)為當(dāng)前迭代路徑；Tk(t)為當(dāng)前路徑的轉(zhuǎn)彎個(gè)數(shù)；Lbest為歷史迭代中的最優(yōu)路徑；a、b為常系數(shù)；μ為信息素調(diào)節(jié)系數(shù)。

2.3.2 自適應(yīng)信息素?fù)]發(fā)系數(shù)

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

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

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

(3)當(dāng)?shù)螖?shù)Nc等于M后取常數(shù)ρ0。ρ0值可根據(jù)不同環(huán)境進(jìn)行調(diào)節(jié)，當(dāng)?shù)螖?shù)Nc不等于閾值M時(shí)，信息素?fù)]發(fā)系數(shù)ρ減小并與信息素閾值下限進(jìn)行比較，取兩者間較大值，即

(19)

式中，λ為遞減常數(shù)，λ<1。

2.4 路徑平滑處理

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

圖1 無(wú)人船轉(zhuǎn)向簡(jiǎn)化模型Figure 1. Simplified steering model of USV

假設(shè)無(wú)人船在航行過(guò)程中某一時(shí)刻處于(x，y)位置，此時(shí)無(wú)人船的航向?yàn)棣龋爸休S與轉(zhuǎn)向方向的偏移角為φ，無(wú)人船的轉(zhuǎn)向角度具有機(jī)械特性的約束[17]，即

|φ|≤φmax

(20)

因此，無(wú)人船行駛的最小轉(zhuǎn)彎路徑為

Rmin=L×cotφmax

(21)

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

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

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

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

2.5 改進(jìn)算法流程

本文改進(jìn)蟻群算法的運(yùn)行流程如圖3所示。

圖3 改進(jìn)算法運(yùn)行流程Figure 3. Flow chart of the improved algorithm

3 算法仿真及分析

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

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

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

(a)

(b)

(c)圖4 20×20柵格最優(yōu)路徑及路徑平滑優(yōu)化(a)改進(jìn)算法最優(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)可以看到，為了有效避免與障礙物的邊角相撞，保障路徑的安全性，改進(jìn)算法規(guī)劃的路徑犧牲了一部分路徑長(zhǎng)度并且增加了轉(zhuǎn)彎個(gè)數(shù)，但是路徑的可行性有明顯提高，說(shuō)明該改進(jìn)算法能較好地對(duì)環(huán)境的進(jìn)行全局路徑規(guī)劃。圖4(b)為平滑處理后的路徑，能夠較好地處理拐點(diǎn)信息，轉(zhuǎn)向角度更加符合無(wú)人船實(shí)際行駛情況。下文中改進(jìn)算法仿真結(jié)果都為路徑平滑處理后的路徑。由圖4(c)中可以看出該改進(jìn)算法具有較好的收斂性，迭代曲線整體呈下降趨勢(shì)并且收斂速度較快，算法后期的收斂性較為穩(wěn)定，沒(méi)有出現(xiàn)收斂到次優(yōu)解和陷入局部最優(yōu)解的情況。通過(guò)仿真分析可知，本文的算法改進(jìn)較為符合預(yù)期結(jié)果。

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

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

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

(a)

(b)

(c)圖5 30×30柵格環(huán)境下3種算法仿真結(jié)果(a)3種算法最優(yōu)路徑對(duì)比圖 (b)3種算法最優(yōu)路徑長(zhǎng)度收斂圖 (c)3種算法最優(yōu)路徑轉(zhuǎn)彎次數(shù)收斂圖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可以看出，點(diǎn)線表示的傳統(tǒng)蟻群算法歷代路徑收斂波動(dòng)較大，迭代性能不夠穩(wěn)定，并且從圖5(c)中可知傳統(tǒng)算法在轉(zhuǎn)彎次數(shù)達(dá)到最優(yōu)之后，反而收斂到一條轉(zhuǎn)彎次數(shù)較多的路徑；點(diǎn)劃線表示的文獻(xiàn)[6]改進(jìn)蟻群算法和實(shí)線表示的本文改進(jìn)算法在路徑長(zhǎng)度和轉(zhuǎn)彎次數(shù)的迭代曲線整體呈下降趨勢(shì)。表1仿真結(jié)果顯示，本文改進(jìn)算法與傳統(tǒng)蟻群算法、文獻(xiàn)[6]算法相比，在迭代初期、各代最優(yōu)路徑以及最后輸出的最優(yōu)路徑在收斂性、最優(yōu)路徑長(zhǎng)以及轉(zhuǎn)彎次數(shù)方面都具有明顯優(yōu)勢(shì)，并且在第10次迭代左右就收斂到了最優(yōu)結(jié)果，算法運(yùn)行時(shí)間高于傳統(tǒng)算法優(yōu)于文獻(xiàn)[6]的改進(jìn)算法。

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

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

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

(a)

(b)

(c)圖6 50×50柵格環(huán)境下兩種算法仿真結(jié)果比較(a)兩種算法最優(yōu)路徑對(duì)比圖 (b)兩種算法最優(yōu)路徑迭代收斂圖 (c)兩種算法最優(yōu)路徑轉(zhuǎn)彎次數(shù)收斂圖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所示，在較為復(fù)雜的仿真環(huán)境中，點(diǎn)劃線表示的文獻(xiàn)[6]算法迭代變得不夠穩(wěn)定，而實(shí)線表示的本文改進(jìn)蟻群算法的迭代曲線整體呈下降趨勢(shì)。迭代初期、各代最優(yōu)路徑以及最后輸出的最優(yōu)路徑在收斂性、最優(yōu)路徑長(zhǎng)以及轉(zhuǎn)彎次數(shù)方面都具有明顯優(yōu)勢(shì)，并且在第13次迭代后期收斂到了最優(yōu)路徑。本文改進(jìn)算法后期的收斂性較穩(wěn)定，且穩(wěn)定性較好，沒(méi)有出現(xiàn)收斂到次優(yōu)解的情況。

4 結(jié)束語(yǔ)

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