改進蟻群算法在AGV路徑規劃上的研究

岳春擂，黃 俊，鄧樂樂

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶郵電大學 信號與信息處理重慶市重點實驗室，重慶 400065)

0 引 言

近年來，隨著物聯網技術的發展，自動引導運輸車(automated guided vehicle，AGV)被廣泛應用于倉儲物流[1]。AGV路徑規劃問題是指在障礙物環境已知的條件下，設計規劃一條從特定位置出發，按照一定的要求，在確保路徑安全情況下到達另一個特定位置的最優路徑[2]。所述最優可以是時間最短、路徑最短以及拐彎次數最少等[3]。路徑規劃算法包括A*算法[4]、Dijstra[5]算法、深度優先搜索(DFS)以及廣度優先搜索(BFS)等。為了滿足現代工業發展需求，學者們開始在將研究重心從傳統算法轉移到智能仿生算法，比如遺傳算法[6]、粒子群算法[7]以及蟻群算法[8]。

蟻群算法(ACO)是由意大利學者Maro Dorigo最早提出的模仿蟻群覓食行為的智能仿生算法，該算法由于高魯棒性、分布式、正反饋、易與其它算法結合等特點被廣泛應用于路徑規劃中[9]。但該算法仍然存在搜索效率低、收斂速度慢、容易陷入局部最優等缺點。文獻[10]將蟻群算法與D*算法結合，利用D*算法改進蟻群算法種的啟發函數，同時使用先驗路徑進行預處理，減少算法處理時間，提高系統時效性。文獻[11]采用多步長，增加算法靈活性并提高算法搜索效率，同時結合最大-最小螞蟻思想，限制信息素濃度，避免算法陷入局部最優。文獻[12]通過將遺傳算法與蟻群算法相結合，利用遺傳算法前期在搜索方面具有全面性和快速性，解決了蟻群算法前期由于缺乏信息素導致的盲目搜索問題，縮短了路徑搜索時間。文獻[13]引入雙向蟻群，提高了算法全局搜索能力，同時結合A*算法改進了初始信息素分布，減小了算法初期搜索盲目性。文獻[14]引入雙種群蟻群，該算法有效避免了蟻群陷入局部最優，提升了算法的收斂速度。

1 基本蟻群算法

蟻群算法通過信息素完成最優路徑的搜索，每只螞蟻從巢穴出發搜尋通往目的地最優路徑過程中，會遺留下信息素，信息素隨著時間揮發，殘留信息素為下一只螞蟻提供尋路引導，通過整個蟻群的搜索，最優路徑的信息素濃度遠高于其它路徑，最終得到最優路徑[15]。

節點狀態轉移：蟻群初始種群規模大小為m， 第k只螞蟻 (k=1,2…m) 從柵格i移動至柵格j的轉移概率與兩大因素有關。分別為柵格i和柵格j之間的信息素濃度以及兩柵格間的距離啟發式函數。如式(1)所示

(1)

(2)

dij表示柵格i和柵格j之間的歐式距離，距離啟發式函數受柵格間距離的影響，如果柵格間距離越大，則距離啟發式函數值越小，選擇該柵格的可能性越小；反之，柵格間距離越小，則距離啟發式函數值越大，選擇該柵格的可能性越大。

信息素濃度更新：蟻群完成一輪迭代后，需要對柵格各段路徑進行信息素濃度更新，便于為下一輪蟻群提供尋路引導，更新方式如下

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

(3)

(4)

(5)

其中，τij(t+1) 表示t+1時刻柵格i和柵格j路徑上的信息素濃度。ρ表示信息素揮發系數， 1-ρ表示信息素殘留程度，τij(t) 表示t+1時刻柵格i和柵格j路徑上的信息素濃度， Δτij(t) 表示在本輪迭代過程中柵格i、j之間累積信息素總量。Q表示信息素強度系數,通常是一個常量，Lk表示第k只螞蟻在本輪迭代中行走路徑總長度。

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

根據上述分析中改進蟻群算法在路徑規劃應用中存在的不足，針對改進蟻群算法存在路徑搜索效率低、收斂速度慢以及路徑規劃缺乏安全性等問題，本文在分析基本蟻群算法當前存在的問題基礎上分別從算法前期、迭代中期以及算法后期3個部分對基本蟻群算法進行改進，確保在尋找全局最優路徑基礎上加快算法整體收斂速度。具體改進包括以下方面：①改進信息素濃度初始化，通過差異化初始信息素濃度，有效避免蟻群前期進行盲目搜索，減少算法迭代次數；②改進啟發函數，綜合衡量當前柵格i與待選柵格j之間的距離 (dij) 以及待選柵格j與目標柵格之間的距離 (djs)， 增強蟻群搜索方向性；③改進信息素重要程度，根據迭代次數設置不同信息素重要程度，增強算法前期搜索可能性同時加快后期搜索收斂性；對每個柵格周圍的8個鄰近柵格進行編號，有效減小AGV行進過程中碰壁情況發生，同時提前避免螞蟻陷入“死角”，增強路徑規劃的安全性及加快算法收斂性。具體改進如下。

2.1 改進環境模型

二維平面地圖建模的方法很多，包括拓撲法、可視圖法以及自由空間法等[16]。本文考慮AGV工作環境多為室內且在障礙物已知的情況下，因此選用柵格法作為二維平面地圖模型。柵格地圖模型易于創建，維護簡單且適應性強，通過簡單修改即可改變模型環境。該模型中白色柵格表示可行區域，用數字0表示，黑色柵格表示靜態障礙物，用數字1表示。

針對目前路徑規劃方法中AGV轉彎安全性問題以及路徑中存在“死角”現象，導致算法不能收斂到最優路徑，本文提出了一種根據鄰近柵格計算出“禁止柵格”的方法，如圖1所示。

圖1 柵格方向標號

如圖1所示，當AGV行進至柵格i時，將柵格i的8個方向的鄰近柵格從左上角開始按順時針方向依次標記為數字1～8。

AGV在室內運動過程中，確保最優路徑避免與靜態障礙物發生碰撞，提高路徑的安全性是AVG路徑規劃的考慮因素之一。如果柵格i的可選柵格中包含標號為奇數的柵格，例如圖1中標號為7的柵格，此時判斷與該路徑方向(西南方向)垂直的兩個鄰近柵格(柵格6，8)是否為障礙物。若兩個鄰近柵格中其中一個為障礙物，則柵格7視為“禁止柵格”。通過該方法可減小AGV與障礙物發生碰撞的可能性。路徑規劃效果如圖2所示。

圖2 避碰效果

圖2中正確行走路徑遠離障礙物邊緣，減小了AGV與靜態障礙物發生碰撞的可能性[16]，提高了AGV室內作業的安全性。

“死角”現象在算法迭代過程中時常發生，影響蟻群搜索效率以及算法最終結果。如圖3所示，圖中實線表示文獻[16]最終路徑規劃效果，虛線表示基本蟻群算法最終路徑規劃效果。由圖可知，基本蟻群算法以及改進算法均只考慮待選柵格與目標柵格之間的距離作為選路的標準，導致AGV行進至柵格i時，仍然將標號為3的柵格列入可選柵格隊列，當AGV行進至柵格3時發現只能向柵格2或者柵格4行走。

圖3 對比算法效果

針對算法迭代過程中出現“死角”現象問題，本文在鄰近柵格的基礎上再向外擴展一層柵格進行計算。如圖4所示。

圖4 防死角原理

柵格i的鄰近柵格中，標號為3的柵格為可行柵格，且與該方向垂直的兩鄰近柵格(柵格2,4)均為可行柵格，因此柵格3滿足路徑安全性準則。但柵格3的鄰近柵格中標號為2，4的柵格為障礙物，此時柵格i移動至柵格3，最終也會向左或者向下移動。因此，對于柵格i而言，柵格3稱為“死角”。對比陷入“死角”現象的蟻群，本文算法通過提前將柵格3標記為“禁止柵格”，直接從柵格i行進至柵格2或柵格4，使得算法在計算量以及最優路徑的轉彎次數、路徑長度方面都有所減少，在尋求全局最優路徑的基礎上加快了算法的收斂速度，同時節省了AGV的運行能耗。

2.2 改進信息素濃度初始化

蟻群算法在迭代初期，由于地圖環境缺乏差異化初始信息素濃度，蟻群在尋路過程中缺乏引導因素，導致蟻群在算法前期盲目搜索，算法收斂速度變慢。因此，本文設計一種基于歐式距離的差異化信息素濃度初值，根據已知的地圖環境模型并圍繞起始點以及目標點生產的“次優路徑”差異化分布初始信息素。如式(6)所示

(6)

式中：Tau(i,j) 表示可行柵格i與可行柵格j之間的信息素濃度。dsi表示出發柵格s到當前柵格i之間的歐式距離，dij表示當前柵格i到待選柵格j之間的歐式距離dje表示待選柵格j到終點柵格e的歐式距離，dse表示起始柵格到目標柵格之間的歐式距離， min(djm) 表示柵格j距離“次優路徑”的最小歐式距離，dsm、dmn、dne、dme均表示“次優路徑”上的兩個柵格之間的歐式距離。σ表示差異化系數。σ越大，代表初始全局信息素濃度差異越大。

兩點之間直線距離最短，但如果僅將起始柵格與終止柵格之間的連線作為“次優路徑”，不考慮起始柵格與終止柵格之間的靜態障礙物，直接對兩柵格的連線進行信息素濃度初始化反而會誤導蟻群進行搜素。如圖5(a)所示，圖中虛線為全局最優路徑，實線為按照初始信息素尋路結果，由于初始化信息素時未考慮連線間靜態障礙物影響，蟻群尋路至障礙物時需要繼續沿障礙物進行隨機搜索尋找最短路徑，尋路效率低同時很難收斂到全局最優。本文首先確定出“次優路徑”，然后根據歐式距離確定出柵格之間的初始信息素濃度，距離“次優路徑”越短的柵格，初始信息素濃度越高，反之越低。確定“次優路徑”的具體方法如下：首先確定起始柵格與終止柵格之間的連線，當柵格 (s,e) 的連線中有障礙物時，在障礙物處形成斷點。若障礙物位于斷點左邊或右邊，此時將沿障礙物向上、下分別進行搜索，記錄障礙物數量，直至找到可行柵格。比較兩個方向的障礙物數目，選擇障礙物較少的方向的可行柵格作為下一個出發點；若障礙物位于斷點上邊或下邊，此時將沿障礙物向左、向右分別進行搜索，記錄障礙物數量，直至找到可行柵格。比較兩個方向的障礙物數目，選擇障礙物較少的方向的可行柵格作為下一個出發點，直至到達終止柵格，最終找到“次優路線”。如圖5(a)的實線所示，柵格 (s,e) 的連線中存在障礙物，且障礙物位于斷點右側，因此沿障礙物上下搜索，發現向下的障礙物柵格數較少，因此將障礙物下方的可行柵格作為新的出發點繼續搜索，最終形成圖中虛線所示的“次優路徑”；如圖5(b)的虛線所示。柵格j為柵格i的待選柵格,選擇柵格j距離“次優路線”最近的柵格m作為出發點。通過式(6)可以計算得出柵格 (i,j) 之間的初始信息素濃度。

圖5 信息素初始化原理

如圖5所示，當柵格i與柵格j越靠近“次優路線”時，柵格i與柵格j之間的初始化信息素濃度越高，蟻群在尋路過程中，會大概率朝該路徑方向進行搜尋，提高蟻群尋路效率，加快算法收斂，減少算法迭代次數。

2.3 改進啟發函數

在基本蟻群算法中，啟發式函數僅由當前柵格i與待選柵格j之間的距離dij決定。但柵格之間的距離差值較小，蟻群僅通過柵格間距離dij很難從眾多可選柵格中選出最優柵格。例如，當單位柵格寬度為1時，相鄰柵格之間的最小距離為1，最大距離約為1.4；經過基本蟻群算法的距離啟發函數計算后，最近相鄰柵格與最遠相鄰柵格的啟發函數值僅相差約0.3。距離啟發函數對蟻群的尋路效果微弱，蟻群不能綜合利用柵格間的信息素濃度和柵格間的距離。降低了蟻群算法的搜索效率以及最終的尋路效果。因此，本文改進一種啟發式函數，該函數值由當前柵格i到待選柵格j之間的距離dij以及待選柵格j到目標柵格e之間的距離dje共同決定，如式(7)所示

(7)

為了避免由于柵格之間的距離差值過小導致啟發式函數值對蟻群尋路過程中引導力弱問題，采用放大距離差值的方法增強待選柵格之間的“優劣性”

(8)

(9)

其中，φij表示柵格i與柵格j之間的距離放大函數，dje表示待選柵格j與目標柵格e之間的歐式距離，dij表示當前柵格i與待選柵格j之間的距離，dse表示出發柵格與目標柵格之間的歐式距離。ω與λ表示距離放大系數，可根據具體環境進行設置。Dmax，Dmin分別表示當前柵格與可選柵格之間距離的最大值和最小值，0.01為了保證分母不為0。系數q表示放大系數，其取值與待選柵格到目標柵格的距離有關。距離放大函數與當前柵格與待選柵格之間的距離dij以及待選柵格與目標柵格之間的距離dje有關，對于柵格i，在所有待選柵格中，當dij與dje均相對較小時，距離放大函數較大，蟻群選擇柵格j的可能性越大。

啟發式函數的最終計算如式(10)所示

(10)

為了便于啟發式函數計算，建立每個柵格的鄰近柵格距離矩陣Dn2×8， 如式(11)所示

(11)

式中：l表示單位柵格的寬度，G(i)表示柵格i的狀態，其值為0表示可行柵格，為1表示靜態障礙物，j表示待選柵格相對于柵格i的方向標號，i′,i″,i1,i2表示與斜線方向垂直的鄰近柵格。具體如圖6所示。

圖6 柵格距離矩陣

2.4 改進信息素因子

信息素因子決定了螞蟻在尋路過程中螞蟻前往下一個柵格時，受信息素濃度影響的重要程度。算法迭代前期為了增強蟻群的全局搜索能力同時避免蟻群陷入局部最優或者“早熟”現象的發生，信息素因子設置較小，減少信息素對蟻群尋路的引導。隨著迭代次數的增加，蟻群在尋路過程中在較優路徑上累積的信息素增多，較差路徑上的信息素較少，通過增大信息素因子，蟻群跟隨信息素濃度較高的路徑進行搜索，縮小了搜索范圍，加快了算法的收斂速度。如式(12)所示

(12)

式中：NCmax表示最大迭代次數，NC表示當前迭代次數。為了避免算法后期由于信息素重要程度過大造成算法陷入局部最優，設定αmax為信息素重要程度的上界閾值。

3 實驗與分析

3.1 實驗準備

本文所有算法均通過MATLAB R2016b仿真實現。實驗運行PC的操作系統為Windows10，處理器為Intel Core i5-9400F CPU，內存為16 GB。本文采用柵格法進行地圖建模，地圖規模分別為10×10、20×20以及30×30，為避免由于單次實驗造成誤差，分別對不同環境地圖進行30次仿真實驗，并對實驗數據求取平均值。為增加地圖真實性，將靜態障礙物隨機分布在地圖柵格中。在柵格規模為20×20以及30×30,環境下分別對基本蟻群算法，文獻[16]改進蟻群算法以及本文提出的改進蟻群算法進行性能分析，本文算法相關參數見表1。

表1 實驗參數

3.2 算法性能對比

將基本蟻群算法、文獻[16]的改進蟻群算法以及本文算法在地圖規模為20×20的柵格上進行對比實驗。仿真結果如圖7和表2所示。

圖7 20×20地圖規模仿真結果

表2 20×20地圖規模實驗結果

圖7(a)～圖7(c)分別表示基本蟻群算法、文獻[16]算法以及本文算法在柵格地圖規模為20×20的最優規劃路徑。圖7(d)、圖7(e)中，虛線、實線、點畫線分別表示基本蟻群算法、文獻[16]算法以及本文算法路徑長度和轉彎次數，從圖中可以看出，本文算法最優路徑避免了“死角”現象發生，減少了路徑長度和轉彎次數。結合表2可以看出，本文算法在路徑規劃方面較文獻[16]算法減少了10.8%，較基本蟻群算法減少了4.3%；在算法搜索效率(穩定迭代次數減少率)方面較文獻[16]算法減少了30%，較基本蟻群算法減少了43.8%。本文算法在迭代穩定時間方面相較于文獻[16]算法減少了54.2%，較基本蟻群算法減少了32.4%。

為進一步驗證算法可靠性，增加地圖環境復雜度，在地圖規模為30×30的柵格地圖上進行對比實驗。仿真結果如圖8和表3所示。

圖8 30×30地圖規模仿真結果

表3 30×30地圖規模實驗結果

結合表3，實驗結果表明：本文最優路徑長度在基本蟻群算法基礎上減少了5.1%，在文獻[16]算法基礎上減少了5.6%，通過在算法前期設置信息素初值，蟻群算法搜索效率(穩定迭代次數減少率)在基本蟻群算法的基礎上減少了65%，在文獻[16]改進蟻群算法基礎上減少了35.7%；本文算法在拐彎次數上稍遜于文獻[16]算法，但相較于基本蟻群算法卻減少了18.8%；本文算法在迭代穩定時間方面相較于文獻[16]算法減少了66.5%，較基本蟻群算法減少了11.1%。結合兩種不同大小規模的柵格地圖仿真實驗可以看出，本文算法在滿足尋找全局最優路徑的情況下，保持極快的收斂速度，且經過少數迭代次數后算法便趨近穩定；而另外兩種算法在前期迭代過程中極其不穩定，收斂速度過慢。因此，在綜合衡量最優路徑各方面性能都較好時，本文算法優勢明顯。

3.3 特殊路徑規劃仿真

為了進一步驗證本文算法在改進初始化信息濃度情況下能夠搜索出全局最優路徑，本文采用特殊的10×10規模大小的柵格地圖進行實驗對比分析。實驗結果如圖9所示。

圖9 10×10地圖規模仿真結果

圖9(a)～圖9(c)分別表示基本蟻群算法、文獻[16]算法以及本文算法在柵格地圖規模為10×10的最優規劃路徑。由上圖分析可以看出，基本蟻群算法在迭代初期并未進行信息素濃度初始化，蟻群在算法前期進行隨機搜索，且搜索過程中判定待選柵格的“優劣性”標準單一，因此未收斂到全局最優路徑；文獻[16]算法僅根據待選柵格距離障礙物的距離進行信息素初始化，距離障礙物遠的柵格初始信息素濃度高，距離障礙物近的柵格初始信息素濃度低，并未充分根據目標柵格進行有方向性的設置信息素濃度，最終也難以收斂到全局最優路徑；本文算法在初始化信息素濃度時，遇到障礙物就沿障礙物進行上下左右搜索，尋找下一個出發點，最終得到一條“次優路徑”，并根據“次優路徑”進行信息素濃度初始化。實驗結果表明，本文算法收斂速度較快、穩定性較強，且能夠收斂到全局最優。

3.4 改進啟發式函數性能對比

為了進一步驗證本文算法在改進啟發式函數后能夠快速搜索出全局最優路徑，采用地圖規模為20×20大小的柵格地圖進行實驗對比分析。為保證實驗的有效性，對比算法為將本文算法的啟發式函數替換為基本蟻群算法的啟發式函數；為保證實驗數據的可靠性，在相同實驗環境下進行30次仿真實驗，并對實驗數據求取平均值。實驗結果如圖10和表4所示。

圖10 改進啟發式函數仿真結果

表4 改進啟發式函數在20×20地圖規模實驗結果

圖10(a)～圖10(c)分別表示對比算法與本文算法在柵格地圖規模為20×20的路徑規劃。由圖10(a)可以看出，對比算法終止柵格對目標柵格的引導力弱，同時柵格間距離太小，導致蟻群難以尋找出全局最優路徑。結合表4，實驗結果表明：本文算法在路徑長度方面較對比算法減少了13.5%，在迭代穩定次數以及迭代穩定時間分別減少了30.8%和27.7%。本文算法通過改進啟發式函數，適當放大柵格間距離，同時結合當前柵格與待選柵格距離以及待選柵格與終止柵格距離，增強蟻群尋路效率的同時尋找全局最優路徑。

4 結束語

改進蟻群算法在構建二維平面地圖時初始化信息素濃度并改進啟發式函數，提升了蟻群算法的整體性能。如提高算法收斂速度、尋找全局最優路徑以及增強算法穩定性。通過為每個柵格引入“方向編號”,避免“死角”現象發生，同時引入“拐角”機制，合理加大了最優路徑與障礙物之間的距離，提高了AGV行走路徑的安全性和可靠性。通過引入動態信息素因子，避免算法前期發生“早熟”現象以及后期陷入局部最優。仿真實驗和結果數據表明，本文算法可以在減少路徑長度和拐彎次數之間獲得最優比例，為AGV規劃出安全、可靠的最優路徑。與其它算法相比，本文算法在收斂性、穩定性以及尋找最短路徑方面表現優異，得到了性能較好的蟻群算法。本文算法在考慮AGV行走路徑的安全性基礎上規劃出全局最優路徑，在提高算法收斂速度的同時增強了算法的穩定性。在今后的研究工作中，可結合粒子群算法進行參數優化，規劃更加智能的路徑，同時引入滑動窗口方法，使AGV在動態環境下，實現動態避障功能。