一種改進蟻群算法的路徑規劃研究

劉海鵬,念紫帥

(昆明理工大學 信息工程與自動化學院,昆明 650500)

0 引 言

路徑規劃是機器人研究領域的一個關鍵問題.通常,路徑規劃是指機器人根據已知條件獨立規劃的安全無碰撞的路徑[1].路徑規劃使用的算法有遺傳算法[2]、人工勢場法[3]、粒子群算法[4]、A*算法[5]、RRT算法[6]等.然而,這些算法存在著穩定性差、效率低等問題.與上述算法相比,蟻群算法具有魯棒性強、路徑規劃效果好等優點.但是,在復雜環境下,蟻群算法存在局部最優、搜索時間長等問題.

為此,許多專家學者從信息素更新以及與其他智能算法的結合等方面改進了蟻群算法[7].文獻[8]通過設計一種基于路徑幾何特征的局部優化方法,進一步優化了初始路徑,顯著的提高了算法的收斂速度.文獻[9]通過引入懲罰因子,對死鎖路徑點上的信息素進行懲罰,有效的減少了死亡螞蟻的數量,確保了解的多樣性.文獻[10]通過對路徑進行幾何局部優化,并沿著勢場力的方向擴散信息素,減小了螞蟻的搜索空間.文獻[11]采用進化的思想改進信息素更新策略,使算法的收斂速度得到提高.文獻[12]提出了一種孤狼-蟻群組合策略.采用獨狼視場機制和自適應增強函數來優化蟻群的尋優能力.文獻[13]通過利用零點定理,提出了一種不均衡分配的初始信息素方法,避免了蟻群在搜索過程中過于盲目的情況,使算法的搜索效率得到明顯的提高.文獻[14]通過引入一種動態分組協作算法,該算法同時結合了蟻群系統和最大最小螞蟻系統,形成了一個異構的多種群結構,每個種群可以實現相互進化,相互補充,從而顯著的提高了算法的整體性能.文獻[15]提出了一種具有懲罰性措施的蟻群算法,利用懲罰策略對最壞路徑的信息素濃度進行懲罰,通過信息素的揮發降低螞蟻遍歷最壞路徑的概率,引導螞蟻探索其他未知區域,提升了算法的全局搜索能力.文獻[16]通過在原有算法的基礎上采用了多步搜索策略來代替單步搜索策略的方法,并對信息素更新機制進行重新設計,以及對規劃出的路徑進行平滑處理,使算法的整體性能得到了明顯的提升.

本文對蟻群算法在復雜環境中的問題進行了如下改進:1)通過在啟發函數中引入一種自適應調整的放大因子,使相鄰節點的啟發信息差異得到增大,增加了螞蟻選擇最優路徑的可能性;2)采用一種獎懲機制更新路徑上的信息素,可以在很大程度上提高算法的收斂性;3)對信息素揮發因子采用動態調整的方法來提高蟻群的搜索速度,使算法快速收斂;4)對改進算法生成的路徑進行優化處理,提高了路徑的平滑性.

1 環境模型

在研究路徑規劃的過程中,需要選擇狀態空間描述方法來建立環境模型.本文采用柵格法[7,17]來進行環境建模.柵格法的工作原理是假定機器人運動的環境是在一個二維空間,就可以將這個空間劃分為許多大小相同的單元.可以根據柵格中是否存在障礙物來對柵格的狀態進行判斷.若柵格中存在障礙物,則對應的柵格狀態為1;否則,對應的柵格狀態為0.柵格地圖如圖1(a)所示.白色部分為無障礙物的柵格,機器人可以向其移動,黑色部分為有障礙物的柵格,機器人不能向其移動.如果將機器人看做一個質點,當周圍沒有障礙物存在時,8個方向都可以滿足機器人的運動要求,機器人的運動方向如圖1(b)所示.

圖1 柵格環境模型Fig.1 Raster environment model

2 傳統蟻群算法

蟻群算法是一種比較典型的啟發式搜索算法,螞蟻可以本能地找到從某一點到食物來源的路徑.在t時刻,第k只螞蟻從節點i移動到節點j的概率轉移公式如下:

(1)

(2)

式中,τij(t)為信息素濃度,α為信息素啟發因子,β為期望啟發因子,ηij(t)為啟發函數.allowedk為路徑搜索所有下一可達節點的集合.dij為當前節點i和待選節點j之間的歐氏距離.

在完成一次迭代后,螞蟻會在路徑上留下信息素,路徑上原有的信息素會得到改變.信息素更新公式如下:

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

(3)

(4)

(5)

3 蟻群算法改進

3.1 啟發函數的設計

傳統蟻群算法的啟發函數通常只取相鄰節點距離的倒數,由此忽略了待選節點與目標節點之間的距離,這使得螞蟻在進行路徑選擇時傾向于選擇距離當前節點最近的節點.當螞蟻無法搜索到最優路徑時,就會發生死鎖的狀況.于是,本文不僅考慮了待選節點與目標節點的距離,還引入起始節點到待選節點的距離.由于相鄰節點距離差異較小,對整體的啟發信息影響不算明顯.為此,本文采用一種隨迭代次數自適應變化的放大系數.算法前期,使得相鄰柵格的啟發信息差異得到明顯增大,在很大程度上增加了螞蟻選擇最優路徑的可能性.算法后期,可以減小啟發信息帶來的影響,有效的避免了局部最優情況的發生.對應的改進公式如下:

(6)

(7)

式中,djg為待選節點和目標節點之間的歐式距離,dSj為起始節點和待選節點之間的歐氏距離,N為當前迭代次數,Nmax為最大迭代次數.

3.2 改進信息素更新策略

傳統的信息素更新策略是在一次迭代結束后,將那些到達目標點的螞蟻找出來,并在它們所經過的路徑上增加信息素.但是,這種情況下,如果給那些劣質螞蟻走過的路徑增加信息素,就會影響到后續迭代中的螞蟻.于是,本文采用一種獎懲機制[18]來更新路徑上的信息素,即對最優路徑上的信息素采取獎勵的措施,對最差路徑上的信息素采取懲罰的措施,從而使算法快速收斂.對應的信息素更新策略的改進公式如下:

(8)

(9)

式中,Lb和Lw為當前迭代中最優路徑和最差路徑的長度,Lave為當前迭代中的平均路徑長度,Lk為本次迭代第k只螞蟻走過的路徑長度,ψ、φ為權重系數.

3.3 改進信息素揮發因子

由于路徑規劃的特殊性,不同階段對信息素揮發因子ρ的取值要求也不一樣.ρ過大會出現路徑上信息素揮發較快的情況,不利于算法收斂.反之,隨著時間的增加,信息素會被大量積累,就會出現算法陷于局部最優的情況.于是綜合以上情況,本文采用一種動態調整的方法來改進ρ.在算法初始階段,給ρ設定一個較大的值來加大搜索范圍;在后續過程中,采用不斷減小ρ的方式來加快算法的收斂速度.對應的改進公式如下:

(10)

式中,ρmax和ρmin為信息素揮發因子的最大值和最小值.

3.4 路徑優化策略

3.4.1 拐點優化算法

為了減少路徑中的冗余節點,本文引入了一種拐點優化算法,該算法可以在很大程度上將路徑長度和平滑度進行優化.

拐點優化算法的過程如下:在一條起點到目標點的路徑中,節點間的連線不經障礙物,則連接下一節點,直到與障礙物相交,將起點與臨近的那個未穿越障礙物的節點相連接,并將該節點作為新的起點,直至所選節點與目標點重合才算完成整個優化過程.如圖2(a)所示,初始路徑為S→A→B→C→D→G,經過拐點優化處理后的路徑為S→B→C→G.由此可見,經過拐點優化,路徑節點更少,路徑長度更短.

圖2 路徑優化處理Fig.2 Path optimization processing

3.4.2 分段B樣條曲線

為了進一步改善路徑的平滑性,引入分段B樣條曲線[19]對拐點優化算法所生成的路徑進行進一步的優化處理.采用分段B樣條曲線可以更好地滿足機器人在柵格環境下的運動要求,在一定程度上減少了機器人與障礙物發生碰撞的可能性.

由u+1個控制點Hi和一個結點向量n定義的B樣條曲線,公式為:

(11)

式中Fi,k(n)是基于B樣條的函數,下面是遞歸公式:

(12)

(13)

分段B樣條對原始路徑每個轉折點附近的路徑進行平滑處理.分段B樣條處理結果如圖2(b)所示.Li-1→Li→Li+1表示未經處理的路徑,Li為路徑上面的轉折點,Li附近的路徑需要進行平滑處理.

M1Li=M2Li

(14)

在Li-1Li上取一點M1,同時在LiLi+1上面取一點M2,M1M2為優化后的曲線,在這里對轉折點兩側選定同樣長度的線段進行優化處理,具體選取的線段長度根據具體的實驗環境而定.

3.5 本文算法的步驟

步驟1.柵格法建模,并對算法中所用到的各個參數進行初始化設置;

步驟2.將m只螞蟻放在起始點,并將該點加入禁忌表;

步驟3.利用式(6)計算啟發函數并用轉輪賭法來選擇下一節點,并更新禁忌表;

步驟4.若螞蟻抵達目標點,則進入步驟5,否則回到步驟3;

步驟5.若螞蟻達到m只,則進入步驟6,否則回到步驟2;

步驟6.利用式(8)更新路徑上的信息素;

步驟7.若滿足N=Nmax,則進入步驟8,否則回到步驟2;

步驟8.利用拐點優化算法和分段B樣條曲線對規劃出的初始路徑進行平滑處理,輸出最終結果.

4 仿真與分析

為了充分驗證本文算法的有效性,選用了3種不同規模的地圖來進行機器人路徑規劃的仿真實驗,分別是20×20規模、30×30規模和40×40規模的柵格地圖.考慮到本文所研究的算法與其他文獻中的算法在參數的數值設置方面存在著一定程度上的差異,為此這里直接引用原始文獻中的實驗數據來進行仿真實驗上的對比分析[20].并且考慮到算法運行時間這個指標在很大程度上與計算機所對應的處理器的性能有關聯,這里引用文獻[21]實驗中不同實驗設備等效耗時的思想,將原文文獻中的時間與本文算法中的運行時間進行比例換算,即根據原文文獻設備得出的算法運行時間,通過換算得到原文文獻在本文設備中的算法運行時間.通過這種方法有效的解決了不同實驗設備在時間指標上存在差異的情況,在一定程度上使實驗的數據結果變得真實可靠.同時為了便于實驗的對比分析,4.1、4.2和4.3所用到的實驗參數會與公共參數存在略微差異,這里為了使Nmax和m這兩個實驗參數盡可能的與原文文獻保持一致,最大程度上保證實驗上的嚴謹性,后面實驗中就不再對修改實驗參數這項進行更多的說明.實驗運行環境為:Windows11 64 bit;Matlab R2021a;處理器Intel(R)Core(TM)i5-1135G7 @ 2.40GHz;內存16GB.本文實驗設計中所用的公共參數是根據許多次的的實驗分析所得出的,這里采用多次實驗的方式來找出滿足實驗最優結果的最佳參數值.實驗公共參數如表1所示.

表1 實驗公共參數Table 1 Experimental public parameters

4.1 20×20仿真環境

在20×20規模的地圖環境下,將本文算法與傳統蟻群算法,文獻[22]算法進行仿真實驗.實驗參數:m=30,其他參數與表1相同.3種算法規劃的路徑如圖3(a)所示,其中帶圓圈標記的細實線為傳統蟻群算法規劃的路徑,細實線為文獻[22]算法規劃的路徑,粗實線為本文算法規劃的路徑;收斂曲線對比如圖3(b)所示;實驗結果對比如表2所示.從實驗結果可以看出,本文算法的路徑長度要優于其他兩種算法,可見本文算法具有很強的搜索能力,能夠搜索到較優的路徑.并且本文算法的路徑更加平滑,表明在經過拐點優化算法與分段B樣條曲線的優化處理后,路徑的平滑性有了進一步的提高.通過圖3(b)可以很明顯的看出,本文算法要比其他兩種算法更快的找到最優路徑,收斂于最優解.在程序運行時間方面,本文算法和文獻[22]算法差別不大,相比傳統蟻群算法則有著較大的改進.顯然,本文的改進算法在20×20規模的地圖環境下,相比較其他兩種算法路徑更優,算法的收斂性更強,搜索路徑的效率更高.

表2 實驗結果對比Table 2 Comparison of experimental results

圖3 路徑規劃結果Fig.3 Path planning results

4.2 30×30仿真環境

在30×30規模的地圖環境下,利用兩個不同的地圖環境,進行兩組不同的對比實驗.

4.2.1 實驗1

將本文算法與傳統蟻群算法,文獻[13]算法進行仿真實驗.3種算法規劃的路徑如圖4(a)所示,其中帶圓圈標記的細實線為傳統蟻群算法規劃的路徑,細實線為文獻[13]算法規劃的路徑,粗實線為本文算法規劃的路徑;收斂曲線對比如圖4(b)所示;實驗結果對比如表3所示.從實驗結果可以看出,本文算法搜索到的路徑長度更短,路徑更加平滑,搜索到的路徑也更加符合機器人的行走路線,而傳統蟻群算法和文獻[13]算法路徑長度還需要得到進一步的優化,特別的就傳統蟻群算法而言,由于算法搜索路徑的效率較低,以及路徑搜索中難以避免的陷入局部最優解的情況,所生成的路線過于差,不能很好的滿足機器人的行走要求.程序運行時間方面,本文算法要稍遜于文獻[13]算法,相比較傳統蟻群算法仍然存在著明顯的提高.根據圖4(b)可以很明顯的看出,本文算法在收斂速度上要優于另外兩種算法,并且所對應的收斂曲線并沒有存在什么波動,整體更加平穩,同時根據收斂曲線可以很清楚地看出,本文算法要更早的達到穩定效果.至于與文獻[13]算法在時間方面的不足可以進行舍棄,以得到路徑長度和收斂速度上的提升.綜合以上可以得出,本文算法得到的的路徑相對于其他兩種算法而言,路徑更優,同時收斂速度更快.

圖4 路徑規劃結果Fig.4 Path planning results

4.2.2 實驗2

將本文算法與傳統蟻群算法,文獻[23]算法進行仿真實驗.實驗參數:Nmax=150,m=100,其他參數與表1相同.3種算法規劃的路徑如圖5(a)所示,其中帶圓圈標記的細實線為傳統蟻群算法規劃的路徑,細實線為文獻[23]算法規劃的路徑,粗實線為本文算法規劃的路徑;收斂曲線對比如圖5(b)所示;實驗結果對比如表4所示.從實驗結果可以看出,由于本文算法高效的搜索能力以及拐點優化算法和分段B樣條曲線先后兩次優化處理,使得本文算法在路徑長度上優于文獻[23]算法和傳統蟻群算法.根據圖5(b)可知,傳統蟻群算法和文獻[23]算法都存在著較明顯的波動,而本文算法基本沒什么波動,整體來看較為平穩.同時,本文算法在收斂速度上相對于另外的兩種算法明顯更快.表明,本文算法的改進策略可以使算法的收斂速度得到明顯的提高.因此,本文算法相比其他兩種算法,具有搜索能力強和快速收斂的特點.

表4 實驗結果對比Table 4 Comparison of experimental results

圖5 路徑規劃結果Fig.5 Path planning results

4.3 40×40仿真環境

在40×40規模的地圖環境下,將本文算法與文獻[23]算法,傳統蟻群算法進行仿真實驗.實驗參數:Nmax=400,m=100,其他參數與表1相同.3種算法規劃的路徑如圖6(a)所示,其中帶圓圈標記的細實線為傳統蟻群算法規劃的路徑,細實線為文獻[23]算法規劃的路徑,粗實線為本文算法規劃的路徑;收斂曲線對比如圖6(b)所示;實驗結果對比如表5所示.從實驗結果可以看出,本文算法經過前期的改進以及后面拐點優化算法和分段B樣條曲線的優化處理,所規劃的路徑更加平滑,也符合機器人的行走路線.文獻[23]算法和傳統蟻群算法的路徑長度要高于本文算法,整體上還需要進一步的提高.從圖6(b)可知,傳統蟻群算法在前期存在十分明顯的波動情況,只是隨著迭代的增加這種波動情況開始逐漸減小,直至穩定.文獻[23]算法同樣前期存在著較大的波動,后面才得到明顯的降低,迭代到一定程度才穩定下來.而本文算法幾乎沒有存在波動的情況,整體比較平穩,說明本文算法的收斂效果較為明顯.由此可見,本文算法在規模大,環境復雜度高的地圖中,仍然存在著很大的優勢.

表5 實驗結果對比Table 5 Comparison of experimental results

圖6 路徑規劃結果Fig.6 Path planning results

5 結 論

本文提出了一種改進蟻群算法的路徑規劃研究方法,來解決機器人在復雜環境下的路徑規劃問題.該方法在啟發函數中引入動態調整的放大因子,來增大相鄰節點的啟發信息差異,從而增加螞蟻選擇最優路徑的概率;采用一種獎懲機制更新路徑上的信息素,使算法的收斂速度得到加快;通過動態調整信息素揮發因子,加快了算法的收斂速度;在最優路徑的基礎上進行路徑優化,改善了路徑的平滑性,更好的滿足機器人在柵格環境下的運動要求.實驗研究表明,本文改進的算法能夠應用在規模性大,復雜度高的地圖環境中,并且在一定程度上有著較高的實用意義.由于本文研究主要是在靜態環境下進行的,下一步研究可以將路徑規劃應用在動態環境領域.