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

岳春擂，黃 俊，鄧樂樂

(1.重慶郵電大學(xué) 通信與信息工程學(xué)院，重慶 400065；2.重慶郵電大學(xué) 信號(hào)與信息處理重慶市重點(diǎn)實(shí)驗(yàn)室，重慶 400065)

0 引 言

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

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

1 基本蟻群算法

蟻群算法通過信息素完成最優(yōu)路徑的搜索，每只螞蟻從巢穴出發(fā)搜尋通往目的地最優(yōu)路徑過程中，會(huì)遺留下信息素，信息素隨著時(shí)間揮發(fā)，殘留信息素為下一只螞蟻提供尋路引導(dǎo)，通過整個(gè)蟻群的搜索，最優(yōu)路徑的信息素濃度遠(yuǎn)高于其它路徑，最終得到最優(yōu)路徑[15]。

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

(1)

(2)

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

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

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

(3)

(4)

(5)

其中，τij(t+1) 表示t+1時(shí)刻?hào)鸥駃和柵格j路徑上的信息素濃度。ρ表示信息素?fù)]發(fā)系數(shù)， 1-ρ表示信息素殘留程度，τij(t) 表示t+1時(shí)刻?hào)鸥駃和柵格j路徑上的信息素濃度， Δτij(t) 表示在本輪迭代過程中柵格i、j之間累積信息素總量。Q表示信息素強(qiáng)度系數(shù),通常是一個(gè)常量，Lk表示第k只螞蟻在本輪迭代中行走路徑總長(zhǎng)度。

2 基于改進(jìn)蟻群算法的AGV路徑規(guī)劃

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

2.1 改進(jìn)環(huán)境模型

二維平面地圖建模的方法很多，包括拓?fù)浞?、可視圖法以及自由空間法等[16]。本文考慮AGV工作環(huán)境多為室內(nèi)且在障礙物已知的情況下，因此選用柵格法作為二維平面地圖模型。柵格地圖模型易于創(chuàng)建，維護(hù)簡(jiǎn)單且適應(yīng)性強(qiáng)，通過簡(jiǎn)單修改即可改變模型環(huán)境。該模型中白色柵格表示可行區(qū)域，用數(shù)字0表示，黑色柵格表示靜態(tài)障礙物，用數(shù)字1表示。

針對(duì)目前路徑規(guī)劃方法中AGV轉(zhuǎn)彎安全性問題以及路徑中存在“死角”現(xiàn)象，導(dǎo)致算法不能收斂到最優(yōu)路徑，本文提出了一種根據(jù)鄰近柵格計(jì)算出“禁止柵格”的方法，如圖1所示。

圖1 柵格方向標(biāo)號(hào)

如圖1所示，當(dāng)AGV行進(jìn)至柵格i時(shí)，將柵格i的8個(gè)方向的鄰近柵格從左上角開始按順時(shí)針方向依次標(biāo)記為數(shù)字1～8。

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

圖2 避碰效果

圖2中正確行走路徑遠(yuǎn)離障礙物邊緣，減小了AGV與靜態(tài)障礙物發(fā)生碰撞的可能性[16]，提高了AGV室內(nèi)作業(yè)的安全性。

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

圖3 對(duì)比算法效果

針對(duì)算法迭代過程中出現(xiàn)“死角”現(xiàn)象問題，本文在鄰近柵格的基礎(chǔ)上再向外擴(kuò)展一層?xùn)鸥襁M(jìn)行計(jì)算。如圖4所示。

圖4 防死角原理

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

2.2 改進(jìn)信息素濃度初始化

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

(6)

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

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

圖5 信息素初始化原理

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

2.3 改進(jìn)啟發(fā)函數(shù)

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

(7)

為了避免由于柵格之間的距離差值過小導(dǎo)致啟發(fā)式函數(shù)值對(duì)蟻群尋路過程中引導(dǎo)力弱問題，采用放大距離差值的方法增強(qiáng)待選柵格之間的“優(yōu)劣性”

(8)

(9)

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

啟發(fā)式函數(shù)的最終計(jì)算如式(10)所示

(10)

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

(11)

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

圖6 柵格距離矩陣

2.4 改進(jìn)信息素因子

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

(12)

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

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)準(zhǔn)備

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

表1 實(shí)驗(yàn)參數(shù)

3.2 算法性能對(duì)比

將基本蟻群算法、文獻(xiàn)[16]的改進(jìn)蟻群算法以及本文算法在地圖規(guī)模為20×20的柵格上進(jìn)行對(duì)比實(shí)驗(yàn)。仿真結(jié)果如圖7和表2所示。

圖7 20×20地圖規(guī)模仿真結(jié)果

表2 20×20地圖規(guī)模實(shí)驗(yàn)結(jié)果

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

為進(jìn)一步驗(yàn)證算法可靠性，增加地圖環(huán)境復(fù)雜度，在地圖規(guī)模為30×30的柵格地圖上進(jìn)行對(duì)比實(shí)驗(yàn)。仿真結(jié)果如圖8和表3所示。

圖8 30×30地圖規(guī)模仿真結(jié)果

表3 30×30地圖規(guī)模實(shí)驗(yàn)結(jié)果

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

3.3 特殊路徑規(guī)劃仿真

為了進(jìn)一步驗(yàn)證本文算法在改進(jìn)初始化信息濃度情況下能夠搜索出全局最優(yōu)路徑，本文采用特殊的10×10規(guī)模大小的柵格地圖進(jìn)行實(shí)驗(yàn)對(duì)比分析。實(shí)驗(yàn)結(jié)果如圖9所示。

圖9 10×10地圖規(guī)模仿真結(jié)果

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

3.4 改進(jìn)啟發(fā)式函數(shù)性能對(duì)比

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

圖10 改進(jìn)啟發(fā)式函數(shù)仿真結(jié)果

表4 改進(jìn)啟發(fā)式函數(shù)在20×20地圖規(guī)模實(shí)驗(yàn)結(jié)果

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

4 結(jié)束語

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