使用改進(jìn)蟻群算法的AGV路徑規(guī)劃研究

葛志遠(yuǎn)，肖本賢

（合肥工業(yè)大學(xué)電氣與自動化工程學(xué)院，安徽 合肥 230009）

1 引言

近年來，伴隨著倉儲物流自動化快速發(fā)展以及勞動力成本的提高，貨物的運輸方式正在向系統(tǒng)化，智能化的方向發(fā)展。自動導(dǎo)引車（Automated Guided Vehicle，AGV）具有提高生產(chǎn)率和節(jié)約勞動成本等優(yōu)點，因此AGV路徑規(guī)劃成為一項重要內(nèi)容。

目前，針對AGV路徑規(guī)劃問題產(chǎn)生一些群智能優(yōu)化算法，如神經(jīng)網(wǎng)絡(luò)算法[1]、遺傳算法[2]、粒子群算法[3]等。蟻群算法[4]（ACO）具有并行性、正反饋性及良好的擴充性等優(yōu)點，在解決路徑規(guī)劃[5]、TSP[6]等問題都有成功的應(yīng)用。針對蟻群算法耗時長，容易陷入局部最優(yōu)的缺點，文獻(xiàn)[7]提出一種基于蟻群算法的帶時間窗的啟發(fā)式算法，提高了收斂速度。文獻(xiàn)[8]利用遺傳算法對蟻群算法參數(shù)的組合優(yōu)化，但由于遺傳算法計算量大，效果不明顯。

在傳統(tǒng)蟻群算法基礎(chǔ)上，利用改進(jìn)的蟻群算法對AGV路徑規(guī)劃進(jìn)行了研究。

2 空間環(huán)境模型的建立

空間環(huán)境模型的建立是AGV路徑規(guī)劃的基礎(chǔ)。柵格法[9]（grid method）具有簡單高效、易于實現(xiàn)、表達(dá)不規(guī)則障礙物的能力等優(yōu)點，所以采用柵格法建立AGV空間環(huán)境模型。

2.1 環(huán)境建模

利用柵格法將AGV所在的空間環(huán)境劃分為一個M行N列的二維平面空間，如圖1所示。柵格必須完全容納AGV，并預(yù)留安全間距，定義障礙物所占用的柵格為障礙柵格（黑色），無障礙物的柵格為可行柵格（白色），單位長度為1cm且障礙物所占柵格不滿一個柵格按一個考慮，通過直角坐標(biāo)法對每個柵格進(jìn)行標(biāo)識，記為g（x，y）。將障礙柵格組成的集合用Qf表示，可行柵格組成的集合用Qt表示，則AGV路徑規(guī)劃就是在柵格圖中尋找到一條無碰最優(yōu)路徑。

圖1 AGV空間環(huán)境模型Fig.1 AGV Spatial Environment Model

2.2 AGV運動距離函數(shù)

在空間環(huán)境模型中，AGV所在的柵格中一般都有8個運動方向，以水平正方向為 0°基準(zhǔn)，順時針 45°，90°，135°；逆時針 45°，90°，135°，包含后退方向 180°，如圖 2 所示。

圖2 可移動方向示意圖Fig.2 Movable Direction Schematic

通過柵格坐標(biāo) P（x，y）表示 AGV 所處位置，其中 x∈（1，2，…，N），y∈（1，2，…，M），P（x，y）∈Qt。AGV 在 t時刻從起始柵格位置Pt（xt，yt）到t+1時刻下一個柵格位置Pt+1（xt+1，yt+1）的運動距離為d（t），則總路徑長度L為從源地址到目的地址行駛的所有節(jié)點路徑距離之和，d（t）如下式所示。

3 傳統(tǒng)蟻群算法的原理

蟻群算法中螞蟻會根據(jù)信息素的強弱選擇路徑，并在自己走過的路徑上遺留一定的信息素。設(shè)τij（t）表示t時刻在路徑（i，j）連線上殘留的信息素濃度，設(shè)初始時刻τij（t）=C（C為常數(shù)）。（t）表示為在t時刻螞蟻k從地址i轉(zhuǎn)移地址j的概率。

式中：ηij通常作為啟發(fā)因子，取 ηij=1/dij；α—路徑（i，j）上殘留信息的相對重要性；β—啟發(fā)因子的重要程度；allowedk—螞蟻k還未遍歷的地點集合。一次循環(huán)后，計算每一只螞蟻所走過的路徑長度Lk，并比較得出路徑中最短路徑Lmin。

隨著時間的推移，各條路徑上留下的信息素會逐漸減弱，當(dāng)所有螞蟻完成一次循環(huán)以后，根據(jù)式（5）調(diào)整各條路徑上的信息量。

式中：ρ—信息素衰減的程度，ρ∈（0，1）；Δτij—信息素增量。

4 改進(jìn)的蟻群算法

傳統(tǒng)的蟻群算法存在耗時長，搜索效率低等缺點，給出以下幾點改進(jìn)。

4.1 蟻群算法概率公式的改進(jìn)

傳統(tǒng)蟻群算法中ηij與路徑（i，j）的距離成反比，這樣容易使螞蟻陷入局部最優(yōu)，故修改啟發(fā)因子與當(dāng)前地址到目標(biāo)地址的歐式距離成反比，距離目標(biāo)地址越近則概率越大，具體如式（5）所示。

式中：aroundk—當(dāng)前地址i周圍8個地址的集合，啟發(fā)因子ηiT=1/diT—地址j到目標(biāo)地址T的歐式距離，由式（5）可知，當(dāng)螞蟻尋找路徑時會朝著離目標(biāo)地址近的方向移動，提高了搜索效率，有利于螞蟻尋找最優(yōu)路徑。

4.2 優(yōu)勝劣汰機制

為加快蟻群算法的收斂速度，節(jié)省搜索時間，使搜索范圍限定在優(yōu)勢路徑中。每次循環(huán)后，差別更新最優(yōu)路徑與最差路徑信息素，使螞蟻的關(guān)注點較集中在優(yōu)勢路徑，盡可能使螞蟻在優(yōu)勢路徑附近尋找最優(yōu)路徑，如式（6）～式（8）所示。

式中：c（r，s）—路徑調(diào)整參數(shù)；Lbest_jT—最優(yōu)路徑中節(jié)點地址j到目標(biāo)地址T的歐式距離；Lworst_jT—最差路徑中地址j到目標(biāo)地址T的歐式距離。

對于最優(yōu)路徑，前期距離較遠(yuǎn)，信息素增益低，有利于前期路徑選擇多樣性，而后期距離目標(biāo)越近，則信息素增益越大，越有利于提高搜索效率；同理，對于最差路徑，前期路徑信息素衰弱較少，防止路徑信息素過少被忽略，后期路徑距離越近，信息素衰減越多。因此，在最優(yōu)與最差路徑上的每一段路徑上的信息素改變都不一樣，擴大了最優(yōu)與最差路徑之間的差異。

4.3 全局信息量調(diào)整

蟻群每次循環(huán)后，只根據(jù)最優(yōu)路徑和最差路徑進(jìn)行信息素的更新，會在一定程度有利于加快收斂速度，但在算法初期，螞蟻過早的集中在幾條次優(yōu)路徑上，使可能的最優(yōu)路徑容易被忽略，不利于尋找到最優(yōu)路徑。因此，針對除最優(yōu)路徑與最差路徑以外的路徑，采取以下改進(jìn)規(guī)則。

式中：n—在Lk上行走的螞蟻總數(shù)；Lk—第k只螞蟻在本次循環(huán)中的路徑長度；ω—信息素擴大系數(shù)。由式（9）可知，若Lk與Lbest的差異越大，則該路徑的信息素增益越低，只有與Lbest較為接近的保留下來。若算法前期出現(xiàn)次優(yōu)路徑，則與次優(yōu)路徑接近的路徑也會較多，全局調(diào)整信息素調(diào)整的范圍較廣，保證了搜索空間范圍，因此聯(lián)合式（6）與式（9）使信息素集中表現(xiàn)在最優(yōu)路徑與次優(yōu)路徑中，提高了螞蟻資源利用效率，有利于蟻群搜索出最優(yōu)路徑。

4.4 信息素濃度限制

經(jīng)過上述蟻群算法的改進(jìn)，提高了蟻群算法的收斂速度，但是為了防止部分路徑上的信息素過多，降低了路徑選擇的多樣性，導(dǎo)致蟻群算法出現(xiàn)早熟現(xiàn)象，所以引入最大最小螞蟻系統(tǒng)對每條邊上的信息素濃度進(jìn)行限制，具體方法，如式（10）所示。

通過將信息素值限定在［τmin，τmax］之間，可以使得路徑之間的信息素濃度之間差距限定在合理的范圍內(nèi)，從而解決了在不同路徑上，由于信息素濃度差異過大從而導(dǎo)致蟻群算法最終出現(xiàn)次優(yōu)的情況。

4.5 死鎖策略

當(dāng)AGV尋找最優(yōu)路徑時，可能會出現(xiàn)死鎖現(xiàn)象[10]，使AGV在當(dāng)前柵格中無法執(zhí)行下一步動作，如圖3所示。

圖3 移動死鎖問題示意圖Fig.3 Mobile Deadlock Problem Diagram

針對上述出現(xiàn)的死鎖現(xiàn)象，提出當(dāng)AGV運動時無法找到除起始地址柵格以外的其他柵格地址時，可執(zhí)行回歸動作，返回到前一地址，并將該地址從可行柵格Qt中剔除，加入到障礙柵格Qf，使得后續(xù)螞蟻避免在死鎖地址消耗時間，有效解決死鎖問題。

5 改進(jìn)蟻群算法的路徑規(guī)劃步驟

綜上所述，改進(jìn)后具體步驟如下：

（1）初始化最大迭代次數(shù)Nmaxc，當(dāng)前迭代次數(shù)Nc為0；設(shè)置在起始地址與終點地址。

（2）對螞蟻k根據(jù)改進(jìn)的蟻群算法概率公式移動至下一個地址。

（3）判斷螞蟻k是否陷入死鎖狀態(tài)，如果是，則進(jìn)入回歸策略，否則繼續(xù)執(zhí)行。

（4）當(dāng)螞蟻k完成路徑搜索后，記錄螞蟻k到達(dá)目標(biāo)地址時的路徑長度Lk。

（5）循環(huán)（2）、（3）、（4），直到 m 只個螞蟻都移動至目標(biāo)地址。

圖4 改進(jìn)蟻群算法流程圖Fig.4 Improved Ant Colony Algorithm Flow Chart

（6）通過 Lk（k=1，2，…，m）計算出最優(yōu)路徑 Lbest與最差路徑Lworst，并根據(jù)改進(jìn)的信息素更新方法更新路徑軌跡信息素，并置Nc←Nc+1。

（7）對計算過的各個邊的信息素濃度，利用最大最小螞蟻系統(tǒng)公式進(jìn)行判斷與限制。

（8）若每個螞蟻搜尋的最優(yōu)路徑相同，則直接跳出循環(huán)。

（9）若迭代次數(shù)Nc＜Nmaxc時，則跳轉(zhuǎn)到（2）。當(dāng)達(dá)到最大迭代次數(shù)Nmaxc時，則跳出循環(huán)，輸出最短路徑，程序結(jié)束。

6 仿真實驗

利用MATLAB對基本蟻群算法和改進(jìn)蟻群算法分別進(jìn)行仿真，并比較它們的仿真結(jié)果。

各個參數(shù)設(shè)置分別為：α=1，β=4，m＝50，ρ=0.2，ω=10，Q=1000，Nmaxc=200，傳統(tǒng)的蟻群算法和改進(jìn)的蟻群算法最優(yōu)路徑長度與仿真結(jié)果分別，如圖5、圖6所示。并通過運行兩種算法，對死鎖問題以及最優(yōu)解比例進(jìn)行統(tǒng)計，結(jié)果如表1所示。

由圖5～圖6可知，改進(jìn)的蟻群算法一開始的搜索效率優(yōu)于傳統(tǒng)的蟻群算法。在迭代次數(shù)上優(yōu)勢不大，但改進(jìn)的蟻群算法搜尋的最優(yōu)路徑明顯優(yōu)于傳統(tǒng)的蟻群算法，且改進(jìn)的蟻群算法后期的收斂速度比傳統(tǒng)的蟻群算法更快。

由表1可知，傳統(tǒng)的蟻群算法容易出現(xiàn)死鎖問題，而通過改進(jìn)蟻群算法的死鎖策略，可以有效的避免螞蟻運動時陷入死鎖狀態(tài)，使改進(jìn)的蟻群算法中螞蟻最終全部達(dá)到最優(yōu)解。

分析實驗結(jié)果得出，傳統(tǒng)的蟻群算法搜索效率較低，耗時長，且容易出現(xiàn)次優(yōu)路徑，通過改進(jìn)的蟻群算法提升了搜索效率，縮短了搜索時間，提高了尋優(yōu)的準(zhǔn)確性，且有效的避免了死鎖現(xiàn)象。

圖5 傳統(tǒng)蟻群算法最優(yōu)路徑圖和仿真結(jié)果Fig.5 The Optimal Path Map and Simulation Results of Traditional Ant Colony Algorithm

圖6 改進(jìn)蟻群算法最優(yōu)路徑圖和仿真結(jié)果Fig.6 Optimal Path Map and Simulation Results of Improved Ant Colony Algorithm

表1 傳統(tǒng)蟻群算法與改進(jìn)蟻群算法性能比較Tab.1 Comparison of System Ant Colony Algorithm and Improved Ant Colony Algorithm

7 總結(jié)

提出了利用改進(jìn)的蟻群算法對AGV進(jìn)行路徑規(guī)劃的方法。傳統(tǒng)蟻群算法具有耗時長，算法的搜索效率較低，容易出現(xiàn)次優(yōu)現(xiàn)象的缺點，提出將根據(jù)與目標(biāo)地址的歐式距離作為啟發(fā)因子，使螞蟻具有目的性尋優(yōu)，提高了搜索效率，并通過優(yōu)勝劣汰機制調(diào)整最優(yōu)路徑與最差路徑信息素濃度，給出了全局信息素調(diào)整方案及限制，有利于螞蟻集中關(guān)注于最優(yōu)路徑和次優(yōu)路徑中，提升了路徑的收斂速度，對多樣性也有一定的保證，提高了搜索的準(zhǔn)確性，同時也對死鎖現(xiàn)象問題的處理，有效避免了AGV陷入死鎖狀態(tài)，仿真結(jié)果證明了方法的可行性和有效性。