基于改進蟻群算法的機器人路徑規劃研究

姚曉通，李致遠，程 曉

(蘭州交通大學電子與信息工程學院，甘肅 蘭州 730070)

1 引言

目前，機器人在各個領域的應用越來越廣泛，機器人路徑規劃在其中占有很重要的地位。所謂路徑規劃，是機器人從起始位置到目標點位置這兩點之間，以一定的優化準則(如行走路徑最短)，找到一條可以躲避障礙物的最優路徑或次優路徑，指導機器人去逼近找到的路徑，完成任務[1]。對于機器人路徑規劃的研究，涉及很多傳統的全局路徑規劃算法，其中包括A*算法，D*算法，人工勢場法，以及C空間法[2]。但是在面對比較復雜的障礙物環境時，以上算法的效果不佳。隨后，一些研究人員根據自然界生物行為的啟發，又相繼提出了應用在路徑規劃方面的智能算法，如粒子群算法，遺傳算法，神經網絡法，以及蟻群算法[3]。其中，蟻群算法和以上其它智能算法相比，具有信息正反饋，分布式計算及全局求解能力強的特點，所以在機器人路徑規劃領域中，其作為一種很有效的規劃算法，應用很廣泛。

蟻群算法是意大利學者M.Dorigo于20世紀90年代通過對螞蟻覓食行為的觀察研究后，受到啟發，而提出來的一種仿生模擬算法[4]。該算法首先成功的解決了旅行商問題(TSP問題)，在求解旅行商路徑最短問題上取得了比較理想的效果。后續，有學者便將蟻群算法應用到路徑規劃方面，雖然相比于其它智能算法，其具有一定的優勢。但是基本蟻群算法還是存在一定的缺陷和不足，因此許多研究人員對基本蟻群算法進行了改進。文獻[5]提出了將環境中局部的機器人路徑信息引入到蟻群信息素的初始化和路徑選擇概率中，提高了蟻群算法的收斂速度，但路徑質量不是很理想。文獻[6]將遺傳算法算子引入到了蟻群算法中，缺點是運算復雜，效率低。文獻[7]提出了使用混合型信息素更新策略，提高了收斂速度并能夠避免局部最優，但在最優路徑距離上效果不是很好。文獻[8]通過根據螞蟻迭代次數手動設置信息素增強系數去達到提高算法收斂速度的目的，但是容易陷入局部最優。文獻[9]提出了一種基于改進蟻群算法的自適應蟻群算法，該方法針對二維環境的路徑規劃效果較好，在三維環境中收斂緩慢，而且容易陷入局部最優。

上述方法雖然在避免陷入局部最優問題和提高蟻群算法的收斂速度上取得一定的效果，但是仍存在全局路徑效果不佳且搜索到的路徑長度偏長的問題。為了更好地解決這些問題，得到更優質量的路徑。本文提出了改進的蟻群算法，在蟻群狀態轉移策略中引入了基于hocaoglu算法思想的引導函數，引導螞蟻更好地逼近最優解。在信息素更新規則中，設計了一種自適應信息素揮發因子更新方法，避免蟻群陷入局部最優解。

2 基本蟻群算法概述

2.1 蟻群算法的思想

自然界的單個螞蟻的行為比較簡單，但是蟻群整體卻可以體現一些智能的行為。螞蟻在尋找食物的過程中會在經過的路徑上釋放一種被稱作信息素的化學物質，以便其它后來的螞蟻可以感知[10]。在剛開始時，由于路徑上沒有螞蟻經過，不會存在信息素，螞蟻會隨機選擇遇到的路徑。隨著時間的推移，距離短的路徑經過的螞蟻會越來越多，從而會使路徑上累積的信息素濃度越來越高，后續的螞蟻選擇此路徑的概率也會增大，最終螞蟻群會找到一條到達目標點的最優路徑。

2.2 蟻群算法的數學模型

1)狀態轉移概率

螞蟻根據信息素濃度去選擇下一個需要移動的節點。同時，還要受到當前節點與周圍節點之間的期望信息的影響。對于螞蟻的狀態轉移規則如式(1)所示[11]

(1)

2)信息素更新規則

由上可知，禁忌表tabuk用來記錄在當前迭代中螞蟻走過的節點，直到完成本次迭代，否則不能再次訪問禁忌表記錄的節點。當所有螞蟻完成對所有節點的訪問后，在禁忌表中便記錄每只螞蟻所走過的節點，構成路徑的可行解。之后，要對之前的路徑信息素進行削弱，對新引入的信息素進行加強，規則如下

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

(2)

(3)

(4)

3 改進蟻群算法

3.1 改進蟻群算法引導函數

針對基本蟻群算法中螞蟻搜索路徑存在一定的盲目性且逼近目標點的效果不理想的問題，本文提出了一種基于hocaoglu算法思想的引導函數。hocaoglu算法是一種多尺度路徑規劃算法，其原理如圖1所示[12]。

圖1 hocaoglu算法原理圖

在上圖中，s為起始點，e為目標點。顯然可知，從s到e的最短路徑是它們之間的直線段。若在se之間有障礙物，則做se的垂直平分線ab，那么sb、be就是為到達目標點所規劃的路徑。當sb之間也存在障礙物時，繼續做sb的垂直平分線，就可以找到sc、cb、be的可達路徑。以此類推，最后一定可以找到一條不經過障礙物的路徑。可以發現，越靠近se附近的節點，節點與起始點和目標點的距離之和越小，路徑越短，反之，則路徑越長。基于此，本文設計了帶有權重調節因子的引導函數，如式5所示

(5)

(6)

其中Dis為當前節點與起始節點的距離，die為與目標節點的距離。引導函數的值與節點到目標點的距離和到起始點的距離之和有關，也和節點與目標點的距離有關。由式(5)可知，在se附近的節點且越靠近目標點的節點，且引導函數的值越大，相應的路徑距離越小。同時，對引導函數設置調節因子λ，在搜索前期λ大于0.5，更偏向于se附近的節點，在搜索后期λ小于0.5，更側重于靠近目標點的節點，這樣有助于螞蟻在后期更快的找到目標點。Ns為當前節點所在節點的次序，Nm為搜索的中期節點的次序。所以改進后的算法的狀態轉移規則如式7所示

(7)

γ為啟發引導因子，表示引導函數的重要程度。

3.2 自適應信息素揮發因子的設計

相比于其它參數，信息素揮發因子ρ對算法性能的影響最大。當ρ過小時，信息素揮發慢，導致路徑上的信息素濃度差異小，螞蟻會充分搜索地圖上的每條路徑，但是收斂速度會變慢[13]；而ρ過大時，路徑上的信息素揮發速度過快，之前信息素濃度低的路徑，信息素濃度會更低，信息素濃度差異變大，會出現強烈的正反饋效果，這樣雖然會加快算法的收斂速度，但是很容易陷入局部最優。面對信息素揮發因子很難找到一個特定的值去適應螞蟻搜索迭代的整個周期，本文提出了一種自適應的信息素揮發因子的方法。對于ρ的區間范圍為[0，1]，將ρ的初始值設置為0.95，若連續10次迭代中相鄰兩次最優解的差值小于等于0.1%時，ρ自動調節為原來的0.9倍；當ρ小于0.2時，強制設置ρ為0.2，表達式如式8所示

(8)

式(8)中，約束條件的設定，某種程度上可以防止螞蟻在搜索過程中陷入局部最優，同時既可以信息素 揮發因子過大，又可以防止過小，對算法性能產生壞的影響。基于以上，改進后的蟻群算法流程圖如圖2所示。

圖2 改進后的蟻群算法流程圖

4 實驗結果與分析

為了驗證改進算法的有效性，本文在matlab2016a環境下搭建仿真地圖并進行對比實驗。相比于可視圖法、節點法和自由空間法，柵格法具有規劃空間表達一致，便于計算機建模、存儲、處理更新和分析等優點，故采用柵格法對環境地圖進行建模。為了排除地圖環境因素的影響，建立了兩種不同的障礙物仿真地圖：一種是簡單的障礙物環境地圖(規格為10*10)，另一種是復雜障礙物環境地圖(規格為20 *20)。由于蟻群算法參數較多，采用控制變量，利用單一參數對算法性能的影響來確定最佳參數值，其它參數的選取則都是在已經確定的之前參數的最佳值的基礎上進行實驗的。本文對最佳參數的選取(以平均路徑長度和平均迭代次數為評判準則)，進行了10次實驗，每次迭代的次數為100，然后再取10次實驗最佳值的平均值。最終參數確定如下：螞蟻數目m=35，信息啟發因子α=4，期望啟發因子β=5，引導啟發因子γ=3，信息素強度系數Q=100，路徑初始信息素濃度τ0=0.3，信息素揮發因子ρ=0.95，最大迭代次數NCmax=100。

路徑規劃的兩種地圖環境模型，它們的起始點都為(1，1)，目標點分別為(10，10)，(20，20)，其中黑色為障礙物，白色為可規劃路徑地圖。在簡單環境地圖模型下，基本蟻群算法和改進后的蟻群算法路徑規劃仿真運行圖，如圖3、4所示，它們的迭代收斂曲線圖，如圖5、6所示。

圖3 基本蟻群算法路徑規劃圖

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

圖5 基本蟻群算法收斂圖

圖6 改進蟻群算法收斂圖

由圖3、圖4、圖5和圖6可知，改進蟻群算法規劃的最優路徑的長度明顯小于基本蟻群算法規劃的路徑距離，本文改進算法的收斂長度為15.95，且在第28代就開始收斂；而基本蟻群算法的路徑收斂長度為19.32，收斂代數為52代，顯然改進蟻群算法在最優路徑長度和收斂速度要優于傳統蟻群算法。

圖7、圖8為另一種復雜環境地圖下蟻群算法的路徑規劃仿真運行圖。

圖7 基本蟻群算法路徑規劃圖

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

圖9、10為復雜地圖環境下基本蟻群算法和改進蟻群算法的收斂曲線圖。

圖9 基本蟻群算法收斂圖

圖10 改進蟻群算法收斂圖

由圖9、圖10分析可知，在復雜障礙物環境下，改進蟻群算法的性能也是要優于基本蟻群算法的。改進蟻群算法在42代就收斂到最優路徑，路徑長度為30.56，而基本蟻群算法最優路徑長度為34.23，收斂的代數為68。在兩種地圖環境下，可以看出改進蟻群算法通過引入引導函數，加強精英螞蟻的路徑信息素濃度和對信息素揮發因子的自適應調節使其全局尋優能力和收斂速度都好于基本蟻群算法，使螞蟻的尋優效率更高，更有目的性，而且不易陷入局部最優。

5 結論

本文提出了一種基于改進蟻群算法的機器人路徑規劃方法。針對傳統蟻群算法路徑規劃中存在的一些問題，提出了相應的改進。首先，在蟻群狀態轉移策略中引入基于hocaoglu算法思想的引導函數并對其設置調節因子；其次，在蟻群信息素更新規則中采用自適應的信息素揮發因子；最后在matlab環境下對所提方法進行仿真驗證，結果表明改進的蟻群算法在尋優能力和收斂速度上具有明顯優勢，求解最優解更有目的性，在提高收斂速度的同時又可以避免陷入局部最優，能找到更優質量的路徑，具有實際工程意義。