移動機器人路徑規劃的改進蟻群算法

張 儀 趙苗慧 楊 兵 張 彤

（陜西省可控中子源工程技術研究中心，西京學院理學院，陜西 西安710123）

近年來，由于人工智能的飛速發展，移動機器人的發展也成為人們討論的熱點，同時路徑規劃是移動機器人主要討論的焦點。路徑規劃是指移動機器人在有障礙的環境中尋找一條無碰撞的路徑[1]。路徑規劃的智能優化算法主要有：遺傳算法、模擬退火算法、粒子群算法、免疫算法等。這些算法在移動機器人路徑規劃時能取得很好的結果，但面對復雜環境時依然存在一定的缺陷[2]。

本文將改進的蟻群算法是一種啟發式的隨機搜索算法。蟻群算法來源于自然界螞蟻尋找食物的過程。該算法主要模擬螞蟻群體覓食的過程，螞蟻在尋找食物的過程中，會在所經過的路徑上留下信息素，而在找到食物，且路程較短的路徑上留下較多的信息素，這也給后來尋找食物的螞蟻提供了強有力的方向指引，更多的螞蟻會往信息素濃度高的路徑上走[3]。但傳統的蟻群算法存在收斂速度慢、容易陷入局部最優解等問題[4]。本文將根據傳統蟻群算法所存在的問題提出一種改進蟻群算法。

1 障礙物模型建立

本文將利用柵格法來模擬障礙物環境，黑格表示障礙物，在矩陣中由1 表示，白格表示可行空間，在矩陣中由0 表示。柵格點標號依據從左到右，從上到下的順序依次標號。每個標號代表一個柵格點。每個柵格長度定義為1。坐標原點定義為左上點。并建立XOY 坐標系。坐標點（X,Y）和柵格標號G 對應的關系為式（1）和式（2）所示：

式中，G 是柵格點標號，N 是矩陣的行列數，mod 是進行取余數操作，ceil 是進行朝正向元素方向取整操作。對移動機器人在柵格中的移動規定以下準則:（1）移動機器人只能在白格中移動，并將移動機器人作為質點。（2）移動機器人每次從每個柵格的中心出發，每次只能向周圍八個中心移動，每次移動的距離為1 或1.414。向上下左右移動時的距離為1，向左上、左下、右上、右下移動時距離為1.414。

2 蟻群算法

2.1 傳統蟻群算法

2.2 傳統蟻群算法的不足

2.2.1 迭代次數多。傳統蟻群算法在前期迭代時，每條路徑上的信息素濃度差別不大，就加大了螞蟻尋找最優路徑的范圍，需要更多的時間去搜索路徑，直到找到最優路徑。

2.2.2 易陷入局部最優解。傳統蟻群算法尋找到較優路徑時，就會往這條路徑上釋放更多的信息素，從而引來更多的螞蟻在這條路徑上留下信息素，通過正反饋，令較優解成為了最佳路徑。

2.2.3 參數的大小選擇影響算法尋優能力。參數的選擇直接影響算法的尋優能力，參數選擇不當直接影響算法的可行性。

2.3 改進蟻群算法

通過上述分析的不足，對蟻群算法提出以下改進：

2.3.1 解決陷入U 型陷阱問題。當螞蟻陷入U 型陷阱時，螞蟻只能選擇回退，但上一個節點已經無法回退，此螞蟻就陷入了鎖死狀態。文獻[5]就提出將鎖死的螞蟻丟棄。但此方法并未將螞蟻陷入鎖死時的節點加入禁忌表，沒有為后來出發的螞蟻留下有效信息。本文提出一種新的解決方案，當螞蟻陷入鎖死時，將此節點加入禁忌表中，并將此螞蟻之前路徑上的信息素清零，再令此螞蟻從起始點重新出發。

2.3.2 設計自適應信息素揮發因子ρ。信息素揮發因子ρ 的大小影響著蟻群算法的收斂速度，也影響算法能否找到最優路徑。當ρ 過大時，容易導致信息素揮發過快，減少了較優路徑上的信息素含量，從而導致最優路徑可能被排除。當ρ 過小時，會使各路徑上信息素含量差別不大，從而導致最優路徑不容易被選擇，影響算法的收斂性。本文設計了一種自適應信息素揮發因子。本設計引入Sigmoid 函數作為信息素揮發因子前面的系數。本設計只引入Sigmoid 函數大于0 的部分。改進如式（3）所示。

式中，ρ 和N 為程序初始化設定的參數，信息素揮發因子和迭代次數，Nn為進行到第n 次的迭代。

若取N 為100，則ρ 前面的系數值與迭代次數N 的曲線關系如圖1 所示。

圖1 迭代次數和系數值的關系圖

由圖1 可知該式實現了ρ 的大小隨迭代次數變化而變化的效果。在迭代初期和末期，ρ 的取值最小，初期時，取值越小有利于螞蟻更容易找見最優路勁，末期時，取值越小有利于增快收斂性。當中期取值較大時，能增大信息素的揮發，若陷入局部最優解，就更容易找到更優的解，使螞蟻避免陷入局部最優解。

3 實驗結果與分析

圖2 傳統蟻群算法路徑規劃圖

圖3 改進蟻群算法路徑規劃圖

由圖2 和圖3 對比可知，很直觀地就能看出改進的蟻群算法是有效果的，改進的蟻群算法明顯比傳統蟻群算法少走了許多冤枉路，拐彎次數也少了好多次。再由圖2 和圖3 對比可知，改進蟻群算法所找到的解比傳統蟻群算法所找到的解要更優，所找到的最短路徑長度比傳統的要短11.2%。所用的迭代次數也比傳統蟻群算法要少。傳統蟻群算法與改進蟻群算法對比數據如表1 所示。

表1 傳統蟻群算法與改進蟻群算法性能指標數據對比

4 結論

傳統蟻群算法確實存在容易陷入局部最優解、無法找到最優路徑的問題，基于此問題，設計了一種自適應信息素揮發因子與舍棄鎖死螞蟻路徑信息素但不舍棄螞蟻的方法處理陷入U型障礙鎖死的問題。通過仿真證明改進蟻群算法可以很好地使蟻群避免陷入局部最優解而且能減少迭代次數，提高算法的效率，效果優于傳統蟻群算法。