基于改進蟻群算法的AGV路徑規劃

李任江，滕智鵬

（長春工業大學 機電工程學院，吉林 長春 130012）

0 引言

自動引導小車AGV作為調節和聯系離散型物流系統，被廣泛運用于自動化立體倉庫中，常用的路徑規劃方法有柵格法［1］、A＊算法［2］、Dijkstra算法［3］、遺傳算法［4］、蟻 群 算 法［5］、粒 子 群 算 法［6］等。 在 這 些 方 法中，遺傳算法有著較強的搜索能力，通過引入自適應的參數，能夠找到全局最優解［7］，但是局部尋優能力差；粒子群算法參數少，能夠快速收斂，但易于陷入局部最優解；蟻群算法具有很強的魯棒性和適應性，但是還存在一些問題，如不具備自主避障能力、信息素的更新機制不完善等，有待進一步研究。

本文基于改進蟻群算法進行AGV路徑規劃，首先引入方向系數，并采用局部、全局結合的信息素更新方式，達到快速尋優的目的；其次引入安全距離判斷策略，提高AGV運行路徑的安全性。仿真結果表明，改進算法具有較好的避障能力，收斂速度快，能夠運用于復雜運輸環境。

1 構造AGV運行環境

為規劃AGV運行路徑，首先要建立能夠使AGV識別的運行環境，通常情況下，AGV的運行環境為二維有界空間，為了便于研究，進行如下假設：①將行駛的AGV看作質點；②AGV行駛過程中主方向為x軸，且行駛速度v不變；③黑色方格為障礙物柵格；④每一條路徑節點之間的連續不能穿過障礙物。

用M表示AGV的運動空間，建立笛卡爾坐標系xoy，以橫向為坐標軸x，縱向為坐標軸y，原點位于M區域左下角，起點S位于原點，終點E位于M 區域右上角。x、y軸上的最大值分別為Xmax、Ymax，基于行駛速度v完成x、y對柵格的劃分，每行的柵格數為Nx＝個柵格的序列號滿足如下關系式：

其中：i為序列號；n為每一行柵格數；int為取整運算；mod為求余運算。

基于以上描述及設定，本文建立20×20的AGV運行環境，如圖1所示。

2 傳統蟻群算法

蟻群算法是一種模擬螞蟻覓食的仿生算法，螞蟻根據轉移概率選擇一條路徑留下信息素，積累的信息素濃度越大，路徑被選擇的概率越大，螞蟻會根據留下的信息素找到最優路徑。根據傳統蟻群算法設定，某時刻t螞蟻k從節點i移動到節點j的概率為：

其中：pij（k）（t）為轉移概率；τij（t）為t時刻節點i與節點j之間的信息素強度；α為信息素重要度因子；ηij（t）為節點i到節點j的期望啟發函數，ηij（t）＝，dij為節點i到節點j的歐幾里得距離；β為期望程度因子。

螞蟻完成一次循環后更新每條路徑上的信息素：

其中：τij（t＋1）為更新后節點i和j之間的信息素強度；ρ為信息素揮發系數；Δτij（t）為路徑節點i到節點j上的信息素增加量，設初始時刻Δτij（0）＝0；m為蟻群的數量；Q為信息素加強系數；Lk為螞蟻k所走過路徑的總長度。

3 改進的蟻群算法

3.1 啟發函數改進

傳統蟻群算法中，由于初始時刻各條路徑上的信息素含量較少，為了使路徑規劃初期AGV的路徑選擇具有一定的指向性，本文引入方向系數（即方向啟發因子）μ來判斷AGV運行過程中當前節點與下一節點的角度，避免角度過大而造成路徑搜索時間的浪費。某時刻AGV運行引導原理如圖2所示。

圖1 AGV運行環境

圖2 AGV運行引導原理

AGV連續經過節點i、j、a、b，當前 AGV運行路徑為節點i到節點j，節點a和節點b為下一步的出發點和到達點，θ1、θ2分別為AGV處于節點a和節點j時與運動邊界形成的角度。Δθ越小，AGV運行方向越靠近終點b，從而縮短運行距離。設ηij＊為改進后的期望啟發函數，Δθ和ηij＊的計算公式如下：

其中：dij為i與j之間的距離；μ為方向啟發因子，且μ＞0。

由式（7）可知，若角度過大則會使η＊ij的值減少，可以減少角度較大的柵格被選擇的概率。結合式（7）和式（2）可得到改進后的蟻群算法轉移概率計算公式：

3.2 信息素更新機制改進

傳統蟻群算法對信息素的更新方式較為單一，當算法進入下一循環時并沒有充分利用上一循環中最短路徑上的信息素。本文采用的信息素更新方式如下：當螞蟻進行一次循環時，對所到達的每個節點上的信息素根據式（4）進行局部更新；經過n個時刻螞蟻完成一次循環后，對最優、最差路徑上的信息素根據式（9）進行全局更新：

其中：Lgb為當前最優路徑長度；Tu為當前最優路徑上所有節點的集合；Lgw為當前最差路徑長度；Tv為當前最差路徑上所有節點的集合。

采用上述更新方式，可以使每個循環中的信息素充分利用，提高較好路徑被選擇的概率，從而提高算法的性能，避免陷入局部最優解。

3.3 路徑安全距離判斷策略

算法對AGV進行路徑規劃的過程中，會出現與障礙物邊緣碰撞的路徑，這樣會影響AGV運行的安全性。本文在對AGV路徑規劃過程中引入安全距離，以提高AGV運行路徑的安全性。圖3為引入安全距離前、后的AGV運行路徑，路徑uv、ij分別為引入安全距離前、后的規劃路徑。

圖3 引入路徑安全距離

根據本文的設定，AGV運動方向為x軸，假設障礙物右上尖角點e的坐標為（x，y），取ce為250mm，點c的坐標為（x，y＋250）。某時刻AGV運行到點c，點c與障礙物尖角e以及路徑終點j產生一個角度θ，由此可以計算出線段lde的長度，并將線段lde的長度稱為安全距離：

其中：lce為線段ce的長度；θ為ce與cd的夾角，且θ∈（0，90°］。

路徑規劃過程中，AGV經過障礙物時路徑節點的選擇與點c一致，可以滿足安全距離且安全距離∈（0，250］。若AGV經過障礙時主運動方向為y軸，則判斷障礙物右下尖角與AGV的安全距離。

4 仿真實驗及結果分析

在圖1環境下，對傳統蟻群算法和改進蟻群算法進行仿真實驗，并對兩種算法規劃出的結果進行對比分析。仿真中各項參數的設定為：螞蟻數量m＝50；信息素重要度因子α＝1；期望程度因子β＝8；信息素揮發系數ρ＝0.1；信息素加強系數Q＝15；最大迭代次數N＝100。圖4為傳統蟻群算法和改進后的蟻群算法的收斂曲線。從圖4中可以看出，改進蟻群算法比傳統蟻群算法更快達到收斂。

圖5為傳統蟻群算法、改進蟻群算法和改進蟻群算法引入安全距離（取安全距離為250mm）后進行路徑規劃的結果。通過比較圖5（a）和圖5（b）可以看出，改進蟻群算法得到的最優路徑更短。再比較圖5（b）和圖5（c）可以看出，引入安全距離后AGV在靠近障礙物時會控制與障礙物的距離為設定的安全距離。傳統蟻群算法在路徑規劃初始時刻路徑的選擇具有隨機性，而改進后的蟻群算法在引入方向啟發因子之后在路徑選擇上避免了平移的出現，同時也能夠根據安全距離自主避碰。

對以上仿真得到的最優路徑長度、平均收斂代數和平均收斂時間以及拐點數進行比較分析，見表1。由表1可以看出：引入方向啟發因子和安全距離后，AGV的運動更具有指向性，產生的路徑上的拐點數比傳統蟻群算法更少，從而產生的路徑長度更短且搜索耗時也明顯減少；AGV會在障礙物附近判斷當前安全距離同時保證路徑最短，使直行路徑變成拐角，所以路徑長度也會有所增加，更符合實際情形。

圖5 算法路徑仿真結果

表1 算法性能對比

5 結語

本文提出一種適用于復雜運輸環境下AGV路徑規劃的改進蟻群算法。采用柵格法建立運行地圖，通過引入方向系數、安全距離判斷策略和改進信息素更新機制，提高算法運行效率和收斂速度，避免陷入死鎖，保證了AGV運輸路徑的安全性。實驗結果表明，本文提出的算法比傳統蟻群算法更快達到收斂，且規劃的最優路徑距離更短，引入安全距離之后AGV的運行路徑與引入前相比更安全。