基于柵格地圖環境的機器人路徑規劃算法

劉琳琳

（武漢軟件工程職業學院機械工程學院，湖北武漢430205）

0 引言

移動機器人技術是未來全球高新產業發展的基礎技術之一。21世紀以來，隨著計算機和電子技術水平的不斷提高，移動機器人技術也進入了快速發展的黃金階段。

路徑規劃問題是移動機器人技術研究領域的熱點問題之一。移動機器人路徑規劃是指機器人通過自身傳感器獲取環境信息，在工作空間內自行規劃出一條安全的運行路線，同時高效完成作業任務[1]。路徑規劃算法有多種，學者們針對機器人路徑規劃問題已做了大量研究，本文在前沿路徑規劃問題的研究基礎上，將改進的蟻群算法運用于基于柵格地圖環境的機器人路徑規劃方案中進行研究。

1 基本蟻群算法

意大利學者Marco Dorigo通過對自然界中蟻群覓食進行分析模擬，于1992年首次提出了蟻群算法（ACO）。蟻群算法用于機器人路徑規劃時，在初始狀態下，各條路徑上的信息素濃度往往相等，螞蟻在進行第一次路徑搜索時，通常根據周圍路徑長短進行選擇，搜索的路徑不一定是全局最優路徑。由于算法的正反饋特征，更多的螞蟻將集中在此路徑上，導致算法過早收斂[2]。本文針對蟻群算法進行路徑規劃時效率低、局部最優以及收斂性差等缺點，提出改進措施。

2 環境建模

假設機器人的工作環境為二維空間，障礙物靜止且大小不變。本文將二維的規劃空間進行離散化，采用柵格法構建環境空間，采用序號法進行柵格的標識，如圖1所示。

圖1 地圖的柵格化處理

3 基于柵格地圖環境路徑規劃的蟻群算法

為了克服蟻群算法在路徑規劃中易陷入局部最優解的缺陷，避免早熟現象的發生，本文改進路徑點的搜索方式，重建信息素濃度更新機制，對可行柵格的可到達程度以及最優程度建立評價體系，以提高算法的整體性能。

3.1 柵格地圖環境的預處理

當環境空間比較復雜時，如圖2（a）所示，當機器人運動至M時，無法向周圍任何區域移動，此時陷入死鎖狀態[3]。

本文從柵格地圖環境入手，避免“凹”區域對路徑搜索過程的干擾。采用基于并查集思想的連通區域判斷的方法，將連接在一起的障礙區域視作一個障礙物；將單個障礙物中的“凹”區域進行填充，如圖2（b）所示。

圖2 柵格地圖環境的預處理

3.2 優勢路徑點的提取

螞蟻在預處理后的環境空間中進行路徑搜索時，其部分最優路徑通常會經過障礙物的“凸點”，本文將這些最優路徑點定義為“優勢路徑點（DPP）”。如圖3所示，網狀線標記的柵格區域即為優勢路徑點。

圖3 優勢路徑點實例

本文采用基于幾何特征的模板匹配方法提取優勢路徑點。該方法是將待識別的路徑點與事先構造好的模板進行比對，從而確定優勢路徑點，本文采用的模板如圖4所示。

圖4 優勢路徑點提取策略

根據圖4（a），當障礙柵格的8鄰域范圍內1-2-4區域為自由區域時，1柵格即為當前障礙柵格的“凸”點（SPUL），如圖4（b）所示；同理，（c）（d）（e）中3、6、8柵格分別表示當前障礙柵格的“凸”點（SPUR、SPDL、SPDR）。這些“凸”點集合即為優勢路徑點（DPP）。

3.3 蟻群算法的改進

3.3.1 信息素濃度更新方式的改進

為了使螞蟻搜索到的路徑集中在最優路徑附近，改進的算法將信息素濃度更新函數進行改進，通過加強最優路徑上的信息素濃度，對求解到的全局最優路徑給予獎勵。“優勢路徑點”對全局最優路徑有著明顯的貢獻，本文將搜索到的包含優勢路徑點路徑上的信息素濃度進行增強。改進的信息素濃度更新方式如式（1）所示：

式中，ω表示優勢路徑點對信息素濃度的貢獻參數；L′表示本次循環中包含優勢路徑點的路徑長度。

3.3.2 信息素閾值的限定

為了提高蟻群算法的全局搜索能力，抑制算法過早地收斂，保證算法具有良好的多樣性和隨機性，在信息素濃度不斷進行更新的同時，要對其濃度強度τ進行限制。濃度強度閾值按公式（3）進行限定[4]：

4 基于柵格地圖環境機器人路徑規劃的算法步驟

（1）采用柵格法對機器人的運行環境進行環境建模，設置機器人起始點Start、目標點End，對螞蟻數量、信息啟發算子α、期望啟發算子β、貢獻參數ω等進行初始化，確定最大迭代次數N。

（2）對柵格地圖環境進行預處理。

（3）提取環境中全部的優勢路徑點。

（4）螞蟻開始搜索路徑，根據公式（4）找出螞蟻下一步可以到達的柵格。

（5）判斷螞蟻是否在規定的步數內到達目標點，若是，則記錄下來螞蟻走過的路徑及長度；否則，將此螞蟻從螞蟻序列里剔除。

（6）更新信息素濃度，根據公式（1）（3）更新已搜索到的路徑上的信息素濃度。

（7）判斷是否達到最大迭代次數，若達到，則輸出當前搜索到的路徑中最短的路徑，程序結束；否則，重復步驟（4）～（7）。

5 仿真實驗及分析

5.1 仿真環境

用MATLAB構建仿真平臺，設置仿真環境如圖5所示，地圖環境為10×10的柵格矩陣，障礙柵格用黑色填充，自由柵格用白色填充，機器人起點為Start，終點為End，蟻群算法的初始化參數為：螞蟻數量m=50，最大迭代次數N=100，信息啟發算子α=1，期望啟發算子β=7，貢獻參數ω=1.5，信息素強度Q=100，信息素揮發系數ρ=0.7。

圖5 仿真環境

5.2 實驗結果分析

對本文算法與基本蟻群算法在圖5的環境地圖上進行仿真實驗，仿真結果如圖6及表1所示。

圖6 柵格地圖環境下的規劃路徑

從圖6及表1可以看出，基本蟻群算法并未找到全局最優解，迭代次數較多，搜索時間較長；本文的算法提高了路徑搜索質量以及算法效率。仿真結果證明了本方法能夠較為有效地解決機器人路徑規劃問題。

6 結語

本文研究了基于柵格地圖環境的移動機器人路徑規劃方法。針對蟻群算法在機器人路徑規劃過程中出現的路徑質量差、搜索效率低等缺陷，本文通過對柵格地圖環境進行預處理，提取優勢路徑點，改進信息素濃度更新機制，限制信息素濃度強度的方式對蟻群算法進行了改進。仿真實驗證明，本文提出的算法方案能夠有效地避免蟻群算法的早熟問題，提高路徑質量以及算法效率。