增強目標啟發信息蟻群算法的移動機器人路徑規劃

郝兆明, 安平娟, 李紅巖, 趙天玥, 王磊, 楊朝旭

(西安科技大學電氣與控制工程學院, 西安 710600)

近年來隨著人工智能的發展以及疫情的暴發,移動機器人開始應用于工農業、航空、商業、醫療服務等行業中。而自主移動機器人的發展離不開路徑規劃,因此近幾年路徑規劃問題成為許多領域的研究熱點[1-2]。目前,在移動機器人路徑規劃中,用到的路徑規劃算法主要有傳統路徑規劃方法Dijkstra算法、A*算法、D*算法、RRT算法等,以及群智能優化算法、粒子群算法、蟻群算法、遺傳算法、模擬退火算法等[3]。

蟻群算法因為其魯棒性強、擁有完善的正反饋機理、高并行分布式計算能力以及易于與其他算法融合等優勢,被廣泛應用于移動機器人路徑規劃中[4]。但是,蟻群算法也存在較容易陷入局部最優、前期路徑搜索盲目性較大、低收斂速度、路線轉彎較多且不均勻等缺陷。因此,研究近幾年蟻群算法以及在改進基礎上進行優化,對移動機器人的路徑規劃有著非常重要的意義[5]。

在移動機器人路徑規劃方面,針對多因素影響路徑規劃,楊立煒等[6]構造了多因子啟發式函數,對初始信息素進行階梯分配,運用最大最小螞蟻策略和信息素揮發因子調整策略,避免算法局部最優。昝新宇等[7]根據多因素綜合指標來分配各路徑上的信息素量,指引螞蟻走向最優路徑。針對算法收斂慢,Miao等[8]引入障礙物排除和角度轉向因子提高轉換概率,采用自適應調整啟發式信息和信息素揮發因子,提高了蟻群算法的收斂性和全局搜索能力。Khaled等[9]通過激發概率選擇下一網格,并基于步長無限的原則采用新的啟發式信息來擴大視野,對信息素更新規則和對蒸發速率的動態調整,加快了算法的收斂速度,擴大了搜索空間。針對路徑安全性,李孟錫等[10]通過限制搜索方向只能在水平和垂直方向上移動,引入自適應期望函數和啟發因子,動態調整狀態轉移概率。在路徑規劃中安全性顯著提高,但是全局限制搜索方向,使得規劃的路徑轉彎次數較多,路徑較長。針對機器人路徑規劃實時性,黃夢濤等[11]在存儲數據中采用二叉排序樹代替順序存儲結構。在機器人經過障礙物柵格的頂點,采用自適應的連接方式該算法規劃效率提升顯著,降低了安全風險,但是規劃的路徑沿著障礙物,路徑長度不是最優。

為使算法收斂速度更快、規劃的路徑安全可靠、效果更好,現通過柵格法對環境建模,合理放大了目標位置對待選節點的影響,在狀態轉移概率中加入啟發式概率,提出正弦自適應調整信息素揮發因子以及刪除冗余節點,進行路徑安全性檢查。最后在兩類不同規模的環境下對本文改進算法、傳統蟻群算法和文獻[6]算法進行仿真對比實驗,以提高收斂速度和路徑規劃效果。

1 模型建立

采用柵格地圖進行環境模型的搭建[12],具體如下:首先構造矩陣G,并將障礙物節點記為元素0,可行節點記為1,也可以隨機設置障礙物。為柵格地圖自定義顏色:如圖1所示。利用sub2ind函數將行列索引轉為線性索引。在正交參考坐標系XOY中,標號i的網格坐標為

黃色代表起點;紅色代表終點;白色為可行區域;黑色為障礙物區域圖1 柵格環境模型Fig.1 Grid environment model

(1)

式(1)中:M為柵格地圖的行數與列數;i為柵格序號;a為柵格的邊長;mod為求余運算;ceil為向上取整運算。

根據以上方法搭建的一個10×10的環境柵格地圖,如圖1所示。

根據柵格地圖的規定,使用改進蟻群算法所生成機器人運動軌跡[13],機器人可以通過左前FL、左L、左后BL、右前FR、右R、右后BR、前F、后B這8個方向進行選擇,如圖2所示。

圖2 機器人運動方向Fig.2 Robot movement direction

2 傳統蟻群算法

傳統蟻群算法是一種求解優化問題的進化智能啟發式搜索算法,主要是根據概率選擇和信息素更新進行路徑規劃,本文研究也主要從這兩方面進行改進。

2.1 狀態轉移

在路徑搜索過程中,根據每條可選路徑上的啟發信息以及信息素濃度來計算狀態轉移概率,計算公式為

(2)

啟發函數為

(3)

式(3)中:dij為節點i與節點j之間的歐氏距離。

2.2 信息素更新

當路徑中殘留的信息元素含量過多時,啟發式信息就可能被完全覆蓋。因此在每只螞蟻抵達目標地點或者進行下一次迭代時,對時間路線中的所有殘留數據都要進行更新。其中,t時刻路徑中的信息素也可按如下方法進行更新處理。其中,t+n時刻路徑(i,j)上的信息素的更新公式[14]為

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

(4)

(5)

(6)

式中:ρ為螞蟻在路徑上的信息素揮發速度,取值為[0.2,0.6];1-ρ為路徑上的信息素殘留因素;Δτij(t)為所有螞蟻存留在路徑i、j上的信息素增量累計和;Q為信息素強度,可經過大量實驗得到最優取值;Lk(t)為第k只螞蟻迭代一次計算得到的路徑長度。

3 改進蟻群算法

傳統蟻群算法主要是根據啟發函數、狀態轉移概率和信息素更新進行路徑規劃,本文研究也主要從這三方面進行改進。

3.1 改進啟發函數

啟發函數ηij表示從i～j的能見度,兩地距離越短,信息素濃度越大的路徑越容易被選擇。近幾年大量學者對啟發函數進行了改進,公式為

(7)

式(7)中:djE為節點j與目標位置節點E的距離。

蟻群進行路徑搜索時,路徑搜索主要根據每條路徑上的信息素濃度以及啟發函數進行選擇。但是在算法早期階段,每條路徑的初始信息素濃度相同,路徑的不同選擇主要在以距離為指標的啟發式函數上。當啟發函數分母越大,即dij與djE之和對啟發函數的影響較小,從而使蟻群算法前期搜索盲目,蟻群會遠離目標位置進行搜索,消耗大量的時間,降低了搜索的速度。

針對該問題,為了增強目標位置對啟發函數的影響,提出一種新的增強啟發式公式,在式(7)的基礎上減去起點到目標點的距離,使公式的分母變小,反過來就是將目標位置對下一個待選柵格節點的影響進行放大,從而對蟻群前期搜索進行方向指引。

(8)

式(8)中:ε為任意常數,ε>0,參數ε用于保證分母不為零;σ為距離增益系數,取值為(0,1),用于調整啟發式信息的強度。

在式(8)中,引入節點和目標節點的啟發式信息來增大節點i與相鄰節點j之間的距離。

對于兩個待選節點1和節點2,根據式(8)中節點1方向上更靠近目標位置,被選擇的概率更高,因此路徑主要沿著斜角線進行規劃,如圖3所示。

圖3 下一待選柵格節點Fig.3 Next grid node to be selected

3.2 狀態轉移概率的改進

在計算路徑轉移概率時,引入帶有權重的距離啟發因子,構建了新的啟發式概率分布,在算法進入迭代后期,避免陷入局部最優,降低了啟發函數的影響。改進后的狀態轉移概率公式如式(9)～式(12)所示,再根據輪盤賭法選擇下一個要訪問的柵格節點。

(9)

MAX=max{d(allowed,E)}

(10)

MIN=min{d(allowed,E)}

(11)

(12)

式中:MAX為下一個待選柵格節點到目標節點的最大距離;MIN為下一個待選柵格節點到目標節點的最小距離;φij(t)為待選柵格節點到目標節點修正距離啟發函數;f為當前迭代次數;fmax為最大迭代次數;δ為可調參數;μ為距離修正系數;λ為距離啟發因子。

改進后的算法在螞蟻搜索路徑時,方向上更接近目標位置的柵格節點被選中的概率更高。因此,螞蟻將以大概率向目標位置進行搜索,從而提高搜索效率。

3.3 正弦自適應信息揮發因子

信息素揮發因子ρ對整個算法的全局搜索能力影響較大。若ρ較小,信息素存留在路徑上的濃度較高,但是隨著時間的累積會限制整體的全局搜索能力,使算法陷入局部最優[15];若ρ較大,路徑上存留的信息素濃度較少,雖然在早期能夠提高全局搜索能力,但是在一定程度上會減弱信息素的引導能力,整體進入盲目的搜索的狀態。因此為提高螞蟻的搜索能力,使用正弦自適應調整策略對信息素揮發因子進行調整,公式(13)如下:

(13)

式(13)中:ρmax和ρmin為信息素揮發因子的最大值與最小值。

在算法初期,信息素揮發因子較小,信息素殘留因子較大,從而螞蟻具有較強的局部搜索能力。在算法中期,隨著正弦函數的變化特性,信息素揮發速度變大,路徑上的信息素濃度變小,螞蟻開始進行全局搜索。而在算法后期,信息揮發因子又變小,螞蟻尋找該區域的最優解,及全局最優解[16]。

3.4 路徑剪枝

路徑避障尋優中存在轉彎次數過多,路徑過于曲折等特點。對于室內低速機器人可以完全按照路徑行走;對于中高速機器人,可以考慮對路徑進行剪枝,從而縮短路徑長度,使路徑更平滑,提高計算效率。

當搜索到一條新路徑時,從起點開始依次遍歷路徑中的其他節點,根據不相鄰的兩個節點連接不受障礙物阻擋來判斷是否存在多余節點。如果節點相連的直線沒有經過障礙物,則二者之間部分節點多余,刪除多余中間節點。考慮到在實際應用中,機器人尺寸的問題以及新的路徑可能經過障礙物頂點,因此對得到的新的路徑進行安全性檢查,將軌跡推離障礙物。最后對軌跡進行調整,得到最終機器人路徑。路徑剪枝前后對比如圖4所示。

圖4 路徑剪枝仿真示意圖Fig.4 Schematic diagram of path pruning simulation

3.5 改進蟻群算法的流程

改進后的蟻群算法步驟如圖5所示。

4 算法仿真與分析

為了驗證改進算法的路徑規劃效果,在Win10操作系統;Inteli5-7200U CPU;8 GB DDR4,MATLAB R2018a仿真平臺上進行測試。

為消除對地圖環境因素的干擾,構建出了兩類規模不同的環境障礙物仿真地圖:一類是規模復雜的障礙物環境圖(30×30),另一種是規模較大的環境地圖(100×100),將本文改進算法、傳統蟻群算法和文獻[6]方法進行了20次仿真比較研究,以證明了本文方法的可行性和優越性。

4.1 實驗參數設置

公共參數初始值經過本文研究的大量實驗以及參考其他學者的研究得到,相關參數設置如表1所示。

表1 參數初始化設置Table 1 Parameter initialization settings

4.2 環境1:30×30柵格地圖

為了驗證算法能否在復雜環境下快速規劃出機器人運動路徑,搭建了30×30的柵格地圖,如圖6所示。進行3種算法對比,得到了機器人收斂曲線變化圖,如圖7所示。3個算法的綜合指標進行了對比如表2所示。

表2 30×30柵格地圖三種算法對比結果Table 2 Comparison results of three algorithms for 30×30 grid map

圖6 30×30路徑規劃圖Fig.6 30×30 path planning diagram

圖7 30×30 路徑長度收斂曲線圖Fig.7 30×30 path length convergence curve

由圖6、圖7和表2可知,對于障礙物復雜的環境1:傳統蟻群算法在迭代60次左右才能收斂,雖然能找到一條最優路徑,但收斂速度較慢。文獻[6]算法在17代左右即可搜索到全局最優路徑,收斂速度較快,但從整體路徑軌跡來看,轉彎次數較多。而本文改進算法在8代左右即可搜索到全局最優路徑,收斂速度相對較快。在路徑長短上,3種算法相差不大,但本文算法的路徑是最短的,沒有刪除冗余點前為44.56,刪除冗余點后路徑長度為42.04。并且在轉彎次數顯著減少,路徑更加平滑。

在搜索時間上,本文算法比傳統算法搜索時間縮短了46%,比文獻[6]算法搜索時間縮短了20%。通過圖6的路徑規劃圖可知,在經過障礙物頂點時能夠保持安全距離,并且在障礙物復雜環境下能夠快速搜索到最優路徑,同時具有穩定性強的優點。

4.3 環境2:100×100柵格地圖

為了驗證算法能否在規模較大的環境下快速規劃出機器人運動路徑,搭建了100×100的柵格地圖,如圖8所示。進行3種算法對比,得到了機器人收斂曲線變化圖,如圖9所示。3個算法的綜合指標進行了對比如表2所示。

圖8 100×100 3種算法路徑規劃圖Fig.8 100×100 3 algorithms path planning diagram

圖9 100×100 3種算法收斂曲線圖Fig.9 100×100 convergence curves of three algorithms

由圖8、圖9以及表3可知,相比文獻[6]算法,本文改進算法搜索速度快,改進算法的路徑長度比文獻[6]算法減少了21%,比傳統蟻群算法減少了23%。對于傳統蟻群算法搜索盲目性大,在路徑搜索時轉彎次數較多,遠離目標位置行走,導致搜索的路徑長度增加。而改進蟻群算法通過引入目標位置啟發函數,規劃的路徑靠近目標位置,路徑最短。在搜索時間上,改進算法比傳統算法縮短了14.2%,比文獻[6]縮短了5%。3種算法對比,改進蟻群算法通過引入正弦自適應調節信息素揮發因子,以及刪除冗余點。使其在規模大的環境中搜索時間較短,路徑比較平滑,轉彎次數較少,因此該算法具備較好收斂速度和路徑規劃效果。

表3 100×100柵格地圖3種算法對比結果Table 3 Comparison results of three algorithms for 100×100 grid map

5 結論

由于目前改進蟻群算法不能滿足移動機器人的安全性和實時性,通過將目標位置對下一個待選柵格節點的影響進行合理放大,采用正弦自適應揮發因子策略以及路徑剪枝,提高了蟻群算法的全局搜索能力和收斂速度。與傳統蟻群算法和文獻[6]改進算法對比可知,本文改進蟻群算法規劃的路徑更短更平滑更安全。