基于混合蟻群算法的AGV路徑規劃*

孟冠軍，陳信華，陶細佩，張 偉

(合肥工業大學機械工程學院，合肥 230009)

0 引言

路徑規劃是指在具有障礙物的環境中，移動物依照某一特定的性能指標(如空間距離、時間等)搜索一條從起始位置到目標位置的最優或次優路徑[1]。自動導引運輸車(Automated Guided Vehicle，AGV)路徑規劃主要包含兩個核心問題：地圖信息表達和搜索策略[2]。針對AGV路徑規劃問題，國內外學者進行了長期的深入研究，并相繼提出了多種較為有效的方法，常用的地圖信息表達方法有柵格法[3]、圖論法[4]、可視圖法[5]。搜索策略方面主要包括A*算法[6-7]、dijkstra算法[8]、蟻群算法(Ant Colony Optimization, ACO)[9-10]、粒子群算法[11]等較為常用。文獻[10]采用一種改進蟻群算法，通過自適應的信息素更新機制，算法的全局搜索能力被提高，但算法的收斂速度卻依然較慢。文獻[11]提出了一種將粒子群算法與模擬退火算法、遺傳算法相結合的方法，在一定程度上提高了算法的尋優能力，但算法操作復雜度也相應增加了。本文首先利用可視圖法進行環境建模，而后采用改進蟻群算法進行路徑搜索。針對蟻群算法搜索效率低的缺點，利用A*算法尋優速度快及蟻群算法易于與其它算法相結合的特點，采用A*算法與蟻群算法的混合蟻群算法。即先采用A*算法搜索出一條較優路徑，以這條次優路徑作為蟻群算法迭代搜索的初始路徑，避免了蟻群算法在初期搜索的盲目性，大幅度提升蟻群算法的尋優能力。為了避免使用蟻群算法時陷入局部最優而導致算法停滯，本文對節點轉移概率公式的啟發函數加以改進，引入全局距離參數。同時為了提高算法收斂速度，本文提出一種面向對象的信息素更新規則，只對非最優路徑上的信息素量進行削減。最后，通過實例分析，驗證了本文提出的混合蟻群算法在AGV路徑規劃問題上的有效性。

1 環境建模

本文利用可視圖法建立AGV車間路徑規劃的二維空間模型，環境模型如圖1所示。

圖1 環境模型圖

圖中S、T分別表示AGV的起始點和目標點，黑色區域表示障礙區域，不同障礙區域頂點之間的虛線即可視線如AB。可視圖法將AGV視為一點，將障礙物多邊形的各頂點進行鏈接，并保證這些鏈接線與障礙物均不相交，這樣就形成了一張網絡圖，稱為可視圖[12]。搜索最優路徑的問題便轉化為在可視圖的基礎上利用搜索算法，尋找一條從起始點穿過可視圖中部分可視線到達目標點的最短路徑問題。由于搜索到的路徑是穿過可視線的，即保證了這些路徑均是無碰撞路徑。

2 混合蟻群算法

2.1 算法原理

混合蟻群算法共包括兩個階段，是A*算法和蟻群算法的結合，運用兩種算法的特點和優勢來求解AGV最優運動路徑。

第一階段為A*算法，A*算法是一種啟發式搜索算法，其適用于靜態路網環境。它的根本思想是通過運用啟發式搜索的方式來找尋恰當的啟發函數，其計算和評估各個擴展節點的代價來選擇代價值最優的結點并加以擴展，直到目標節點被找到為止。在路徑搜索問題中，當前節點到目標點的代價值即路徑長度的評估值就通過啟發函數來計算獲得。

第二階段為改進蟻群算法，本文針對傳統蟻群算法存在的缺陷與不足，做出若干改進。

2.1.1 節點轉移規則

本文針對蟻群算法易陷入局部最優導致算法停滯現象的不足，采用新的節點轉移規則，以增強算法的全局搜索能力，便于算法跳出局部最優。

在傳統蟻群算法中，節點轉移概率[13]由兩節點連接路徑上的信息素量τij和啟發函數ηij共同決定，且一般令ηij=1/dij，這樣啟發函數僅由單一的距離參數dij來決定，而dij只能反映節點i周圍的局部信息。在某些情況下，節點i與節點j的距離短，并不意味著節點j到目標點T的距離短。如圖2所示，起始點S到目標點T有兩條路徑，路徑L1上的第一個節點距S較遠，路徑L2上的第一個節點距S較近，如果按照傳統蟻群算法的節點轉移規則，最后搜索到的很可能是路徑L2，但實際上L2的長度是大于L1的長度的。

圖2 節點轉移矢量圖

(1)

其中，i、j為鏈接線上所有點的集合；α為信息素重要程度因子；β為啟發函數重要程度因子；I為螞蟻下一步選擇節點的集合。

2.1.2 信息素更新規則

為了克服傳統蟻群算法收斂速度慢的不足，本文引入一個常數μ，0<μ<1,其作用是減小目前非最優路徑上的信息素增量。于是最優路徑上的信息素增長優勢得到加強，在保證算法全局搜索能力的情況下，加快了算法的收斂速度。新的信息素更新規則如式(2)所示：

(2)

(3)

其中，Q為常數，表示螞蟻循環一次所釋放的信息素總量；dij表示節點i與節點j之間的距離。

2.2 算法流程

綜合上述描述得到混合蟻群算法，算法流程圖如圖3所示。

圖3 算法流程圖

首先采用可視圖法建立AGV運動環境模型，并運用A*算法在環境模型中搜索出一條較優路徑；然后將其作為改進蟻群算法的初始路徑，同時根據新節點轉移公式尋找蟻群運動節點，直至到達目標點；最后在迭代次數到達限定后輸出算法求得的最優路徑。

3 案例應用及分析

3.1 問題描述

將某車間AGV的工作環境作平面化處理，得到一個100 m×100 m的二維空間，該二維空間分布了一些障礙物，將這些障礙物進行區域劃分，得到4個障礙區域，現需為AGV規劃出一條從起始點S到目標點T避開障礙物且盡可能短的路徑。S、T以及障礙區域的位置可通過測量得知。

3.2 仿真環境及環境模型

為了驗證混合蟻群算法在AGV運動規劃方面的優越性及有效性，采用MATLAB軟件進行仿真。仿真環境：利用MATLAB R13a,在Intel(R) Core(TM) i5-3210M CPU @ 2.50GHZ、4.00GB內存、Window 7操作系統下進行仿真驗算。建立適當的平面直角坐標系，測得S、T以及障礙區域頂點的坐標，利用可視圖法，在MATLAB R13a上進行環境建模，如圖4所示。

圖4 環境模型圖

圖4中虛線L1，L2，……,L16為可視圖鏈接線，鏈接線上的“*”為該鏈接線的中點，黑色區域即障礙區域。

3.3 A*算法規劃較優路徑

采用可視圖法建立環境后，在MATLAB上運用A*算法搜索較優路徑，為降低算法運算的復雜度，以可視圖各鏈接線的中點作為A*算法路網中的擴展節點，圖5為利用A*算法得到的搜索結果。

圖5 環境模型圖

圖中粗虛線即搜索到的較優路徑，該路徑從起始點S出發，依次經過L1、L2、L3、L4、L9、L10、L14、L15的中點，最后到達目標點T，該路徑總長度為107.4 m。

3.4 改進蟻群算法搜索最優路徑

以A*算法得到的上述路徑作為改進蟻群算法的初始路徑，并進行最優路徑搜索。同時針對原AGV路徑規劃問題，用同樣的方法進行環境建模，再利用傳統蟻群算法進行路徑尋優。傳統蟻群算法和混合蟻群算法求得的最優路徑比較如圖6所示。

圖6 路徑搜索結果對比圖

為了便于分析將兩種算法的迭代曲線求出并放在一起進行比較，如圖7所示。

圖7 算法迭代結果

圖6和圖7中細實線代表混合蟻群算法的結果，粗實線則代表傳統蟻群算法的結果。

3.5 結果分析

將以上兩種方法得到的路徑規劃結果的相關數據進行統計，具體見表1所列。

表1 算法結果對比

上述統計結果表明，本文提出的混合蟻群算法搜索到的最優路徑比傳統蟻群算法在路徑長度上得到了明顯改善，符合本文AGV路徑規劃問題的目標要求。并且經過改進后的蟻群算法在大約第98次循環迭代之后，就開始達到最優路徑，而傳統蟻群算法在大約第252次循環迭代之后，才開始趨于最優路徑。即本文的混合蟻群算法不僅搜索的路徑更優，在算法收斂速度方面也具有明顯優勢。為了更好的比較傳統蟻群算法和混合蟻群算法的性能，將兩種算法在同樣的實驗條件下運行5次，得到的結果見表2所列。

表2 算法結果對比

由表2數據可知，傳統蟻群算法求取的最優路徑長度穩定在95 m左右，相較之下混合蟻群算法求取的最優路徑長度則在83 m左右。且混合蟻群算法所需的迭代次數要遠遠小于傳統蟻群算法。此外由于本文提出的AGV路徑規劃問題沒有對環境作限制，沒有明確規定障礙物的位置，因而具有現實的普適意義，從而證明了本文混合蟻群算法在解決AGV路徑規劃問題方面的有效性。

4 結論

文章提出了一種基于混合蟻群算法的AGV路徑規劃研究方法。在傳統蟻群算法的基礎上，對算法中的節點轉移概率公式以及信息素更新方式加以改進，并利用A*算法尋優速度快的優點將其與蟻群算法相結合，彌補了傳統蟻群算法收斂速度慢且易陷入局部最優導致算法停滯的不足。基于此方法在MATLAB軟件中對實際案例進行實驗仿真，得出如下結論：混合蟻群算法可使AGV在運行過程中有效避開障礙物，并找尋出一條無碰優化路徑；相較于傳統蟻群算法，混合蟻群算法規劃的路徑長度和質量明顯優于前者；通過算法迭代圖和多次對比試驗，表明混合蟻群算法具有較好的收斂性和較高的搜索效率等優點。