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

劉加奇, 王泰華, 董 征

(河南理工大學 電氣工程與自動化學院，河南 焦作 454000)

0 引 言

隨著科學技術的不斷發展，移動機器人在生活服務、工業生產等領域得到了廣泛的應用[1]。移動機器人實現自主移動的前提是機器人具有路徑規劃能力，而路徑規劃的好壞，關鍵在路徑搜索算法的選取上[2]。根據路徑搜索算法原理，路徑規劃分為傳統路徑算法(如A*算法[3]、人工勢場法[4]等)和智能路徑算法[5](如遺傳算法(genetic algorithm,GA)[6]、粒子群優化(particle swarm optimization,PSO)算法[7]和蟻群算法(ant colony algorithm，ACA)[8]等)。

蟻群算法自Dorigo M提出以來，在不少領域得到了應用，其中路徑規劃是其中之一[9,10]。不過蟻群算法在路徑規劃過程中，也容易陷入局部最優和收斂性差等問題，針對這些問題，不少學者對蟻群算法進行改進[11]。文獻[12]基于狼群法則對信息素更新方式進行改進，避免螞蟻陷入最優，提高算法搜索路徑長度的最優性。文獻[13]通過改變信息素更新方式，修改信息素揮發系數，在信息素增量更新式子中添加一個動態調節因子，以增大次優路徑上信息素濃度的方法，提高搜索最優路徑的概率。文獻[14]利用鳥群算法對行駛環境進行快速搜索，將規劃的路徑轉化為蟻群算法信息素，對蟻群算法初始信息素進行差異化分配，來提高蟻群算法前期的搜索速度，加快算法的收斂性。文獻[15]結合人工勢場法，增加一個提高全局搜索能力的誘導因子，改進距離啟發函數，提高算法路徑搜索的最優性和收斂速度。

為了改進蟻群算法在路徑規劃上存在的不足，本文通過增加目標點導引修改距離啟發函數和建立判斷可行節點夾角大小的夾角指數啟發函數對狀態轉移概率進行改進，以及采用部分較優路徑信息素增量分段,更新和自適應調節信息素揮發系數對信息素改進的方法，為研究移動機器人靜態全局路徑規劃提供一種參考。

1 環境模型的建立

搭建機器人環境模型，是機器人路徑規劃重要組成部分。柵格法因其直觀和易于實現的特點，在機器人環境建模中得到大量的使用，因此,本文選擇柵格法建立移動機器人二維靜態環境模型。

2 改進蟻群算法

2.1 改進狀態轉移概率

利用蟻群算法進行路徑規劃時，受路徑上初始信息素均勻分布，以及節點啟發性不強的影響，螞蟻在路徑搜索過程中采用一種盲目的方式，導致蟻群算法存在前期搜索速度慢，規劃的路徑非最優問題。本文采用一種離目標點最近的可行節點作為下一節點，通過修改距離啟發函數，增加目標點導引作用，加快蟻群的收斂速度。另外當節點上信息素濃度過大時，會使節點的啟發性不能得到保證的情況，本文基于文獻[8]設計一個新的啟發函數φij(t)，即夾角指數啟發函數。圖1中，夾角θij為可行節點j到目標點E和節點i兩點之間的夾角，根據可行節點j下的路徑1和路徑2可知，夾角θij越大，螞蟻選擇路徑1的期望值越大，因此,建立一個根據節點夾角大小的啟發函數，來保證路徑的最優性。

圖1 節點夾角

由以上分析可知，期望的程度越大，相應的，余弦函數cos(θij)的相反數也就越大；同時，為了能夠增強節點的啟發性，添加一個動態調節因子，建立的夾角指數啟發函數為

φij=exp(-cos(θij))

(1)

則螞蟻選擇下一可行節點的狀態轉移概率公式為

(2)

(3)

式中τij(t)為信息素濃度，α為信息素濃度因子；φij(t)為夾角指數啟發函數，γ為其啟發函數因子；ηiE(t)為可行節點j到目標節點E的啟發函數，d(j,E)為可行節點j到目標點E的歐氏距離，β為距離啟發函數因子；allowedk為螞蟻k下一可行節點集。

2.2 改進信息素更新方式

基本蟻群算法信息素更新是針對到達目標點的螞蟻，算法不僅計算量大，而且螞蟻容易受最差路徑上螞蟻釋放信息素的誤導，使蟻群陷入局部最優，影響蟻群的路徑規劃效果。基于對精英蟻群算法和排序策略[16]的研究，為了更好地區分路徑上信息素濃度，使螞蟻能夠搜索到最優路徑，本文采用一種對路徑長度信息素增量Q差異化的更新方式，即將螞蟻搜索的路徑長度進行分類處理，通過舍棄部分較差路徑上的螞蟻，選擇對搜索到最優路徑的螞蟻信息素增量額外補償，而較優部分螞蟻正常更新的方式，提高路徑規劃長度的最優性。信息素更新改進方法如下

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

(4)

(5)

(6)

系數ε為

(7)

2.3 自適應揮發系數

信息素揮發系數的取值，對蟻群算法的性能起到重要作用，信息素揮發系數過大或過小都將影響蟻群算法規劃的收斂速度和路徑長度。傳統蟻群算法信息素揮發系數采用的是一個定值，不利于螞蟻在路徑長度和收斂速度都保持最優性。基于以上原因，本文研究一種基于等差數列遞減的自適應信息素揮發系數，采取在優先保證蟻群算法收斂性的情況下，對信息素揮發系數采取逐次遞減，后期再增大螞蟻搜索范圍的方式，對信息素揮發系數進行自適應調節。自適應揮發系數為

(8)

式中ρmax為最大信息素揮發系數，ρmin為最小信息素；t為當前螞蟻迭代次數，T為螞蟻最大迭代次數。

2.4 算法實現步驟

步驟1：利用柵格法建立移動機器人柵格環境模型，布置機器人環境中白色可行柵格和黑色不可行障礙物柵格；步驟2：設置起始點坐標S和目標點坐標E，以及初始化蟻群算法參數；步驟3：將螞蟻m放在起始點位置，螞蟻k按照式(2)選擇路徑下一可行節點，并將螞蟻走過的放進禁忌表tabuk中；判斷節點是否達到目標點，對到達目標點的螞蟻，按照步驟4進行下一步，否則，繼續；步驟4：按照路徑長短進行排序，選取部分較優路徑按照式(4)進行信息素更新；步驟5：判斷是否達到最大循環次數，條件成立輸出全局最優路徑，否則執行步驟2。

3 實驗仿真與分析

為了驗證改進蟻群算法的性能，在MATLAB 2015b仿真平臺上進行測試。設置公式中的參數，其中最大循環次數為100，螞蟻數量為50，信息素濃度α，距離啟發函數β，夾角指數啟發函數γ分別為1，4，2。設置兩種環境模型，與文獻[12]和文獻[16]對比，驗證改進蟻群算法的性能。

3.1 環境1

凹型障礙物是導致路徑搜索長度增加的重要環境模型，本文在搭建環境時，將機器人環境1設置成20×20帶有凹型的環境模型，對文獻[12]、文獻[16]和改進蟻群三種算法進行仿真，得到改進蟻群算法最優路徑和收斂曲線如圖2所示。

圖2 改進蟻群算法最優路徑及收斂曲線

對文獻[12]、文獻[16]和改進蟻群算法各運行20次，算法分別從最優路徑長度、迭代次數、最差路徑長度、平均路徑長度及平均迭代次數上進行比較，統計結果如表1所示。

表1 20×20環境算法性能比較

從表1可知，文獻[16]和改進蟻群算法在最優路徑長度是相等的，并且相比文獻[12]減少了1.94 %；在最優路徑長度下的收斂曲線，文獻[12]和文獻[16]是相等的，改進蟻群算法相比兩個算法減少了80.21 %；在最差路徑長度上，文獻[16]和改進蟻群算法相比文獻[12]分別減少了7 %,7.72 %；從平均路經長度上，文獻[16]和改進蟻群算法相比文獻[12]，分別減少了4.54 %,4.70 %；在平均迭代次數上，文獻[12]和改進蟻群算法均優于文獻[16]，分別減少了20.63 %,87.30 %。通過表1的數據統計結果可知，在搜索的路徑長度上，文獻[16]和改進蟻群算法均優于文獻[12]，并且改進蟻群算法又優于文獻[16]；在收斂曲線上，文獻[12]和改進蟻群算法相比文獻[16]均能較快的收斂，同時改進蟻群算法又較快于文獻[12]，表明改進蟻群算法具有路徑搜索能力強和收斂性快的優點。

3.2 環境2

為進一步驗證改進蟻群算法性能的優越性，本文在文獻[12] 30×30環境的基礎上增加環境的復雜度，將機器人環境2設置成30×30多障礙物和多凹型柵格環境模型，對文獻[12]、文獻[16]和改進蟻群三種算法再次進行仿真比較，得到改進蟻群算法最優路徑和收斂曲線如圖3所示。

圖3 改進蟻群算法最優路徑及收斂曲線

對文獻[12]、文獻[16]和改進蟻群算法各運行20次，算法分別從最優路徑長度、迭代次數、最差路徑長度、平均路徑長度及平均迭代次數上進行比較，如表2所示。

表2 30×30環境算法性能比較

從表2可知，文獻[16]和改進蟻群算法在最優路徑長度上，相比文獻[12]分別減少了8.43 %和9.64 %；在最優路徑長度下的收斂曲線，文獻[12]和改進蟻群算法相比文獻[16]分別減少了25 %,78.79 %；從最差路徑上對比可知，文獻[16]和改進蟻群算法相比文獻[12]分別減少了16.61 %,16.10 %；在平均路徑長度上，文獻[16]和該蟻群算法相比文獻[12]分別減少了13 %,13.89 %；從平均迭代次數上看，文獻[12]和改進蟻群算法又都優于文獻[16]，并且相比文獻[16]分別減少了50.14 %,90.31 %。通過對表1和表2中數據分析可知，改進蟻群算法能夠繞開凹型障礙物，并且在復雜環境下能夠快速搜索到最優路徑，同時具有穩定性強的優點。

4 結 論

針對基本蟻群算法在移動機器人路徑規劃上，搜索的路徑長度和收斂性非最優問題，本文通過對基本蟻群算法的結構進行改進，并將改進蟻群算法應用到柵格環境模型下的移動機器人路徑規劃上，與文獻[12]和文獻[16]仿真對比可知，改進蟻群算法具有路徑規劃能力強，收斂速度快和適用范圍大的優點。