基于優化蟻群算法的AGV路徑規劃研究

張志軍, 董學平, 甘 敏

(1.合肥工業大學 電氣與自動化工程學院,安徽 合肥 230009; 2.福州大學 數學與計算機科學學院,福建 福州 350108)

0 引 言

自動導引車(automated guided vehicle,AGV)是一種無人駕駛的運輸車輛。由于近幾年我國倉儲物流行業的迅速發展以及人力成本的提高,傳統的倉儲物流運輸方式越來越不適應人們的需求[1]。AGV工作穩定可靠,可以大大提高工作效率,節省人力成本,將人們從某些危險的工作環境中解放出來,在倉儲物流運輸中扮演著越來越重要的角色,因此高效的AGV路徑規劃已經成為一個重要的研究課題。

對于AGV的路徑規劃問題,國內外學者做了大量的研究工作,提出了多種AGV路徑規劃方法,其中智能路徑規劃方法有遺傳算法[2]、粒子群算法[3]、人工蜂群算法[4]以及蟻群算法[5]等。蟻群算法是意大利學者Dorigo受到自然界中真實螞蟻群體的覓食行為啟發而提出的一種元啟發式算法[6],它具有良好的正反饋性、并行性以及較高的魯棒性,具有全局搜索能力,在解決AGV路徑規劃問題上得到了廣泛的應用[7-9]。文獻[10]將蟻群下一步可達節點的范圍擴大到整個地圖空間,并且通過設置跳點,使搜索到的蟻群最短路徑長度得到了優化,但該方法運行耗時比較長;文獻[11]在精英蟻群算法的基礎上引入了獨狼搜索機制,采用獨狼逃跑策略在螞蟻視場內設定天敵,從而避免路徑上的信息素趨于穩定,改善路徑停滯問題,使最短路徑解的質量得到了提升,但該算法的收斂速度還需要進一步改善;文獻[12]針對復雜凹形障礙環境下的路徑規劃問題,提出了雙蟻群完全交叉算法,將蟻群2的路徑解和蟻群1的路徑解相交,以優化蟻群1的路徑解,從而得到高質量的路徑,但該算法2個蟻群的迭代次數和迭代方式相同,內存占用比較大且耗時較長。

本文針對上述問題,提出了一種優化蟻群算法。首先,在基本蟻群算法中引入輔助蟻群,利用輔助蟻群的方向優勢優化主蟻群初始信息素的分配,使主蟻群前期路徑搜索更具有針對性,提高了搜索效率,且輔助蟻群和主蟻群的迭代次數和迭代方式有很大區別,因此優化蟻群算法占用內存較小且運行耗時較短。其次,偽隨機狀態轉移策略的引入,增加了路徑選擇的多樣性,避免了算法早熟。最后利用蟻群的當前最優解、主蟻群一代蟻群中的最優解、最差解對路徑上信息素進行有區別地獎懲,提高路徑搜索的質量。仿真結果表明,優化蟻群算法的收斂速度和最短路徑質量均得到了提升。

1 環境建模

1.1 柵格環境

在對AGV的路徑規劃研究中,建立AGV的運動環境是一個很重要的步驟,常用的環境建模方法有可視圖法、柵格法和拓撲法[13]。本文采用柵格法作為環境建模方法,將運動環境抽象為由m×n個網格單元組成的二維平面環境地圖,使得AGV在該環境下的運動過程視作質點運動[14]。一個5×5的柵格環境如圖1所示,以環境左下角為坐標原點,向上為Y軸正方向,向右為X軸正方向,建立平面直角坐標系,選擇網格單元長度為1 cm。在柵格環境中,將環境中的障礙物在環境地圖中用陰影柵格表示,不足1個柵格的按1個柵格計算,可行柵格用白色柵格表示。

將柵格環境按從左到右、從上到下的順序標示每個柵格的序號,在m×m的柵格環境中,序號S與所在柵格的坐標(x,y)一一對應且對應關系為:

(1)

其中:mod為求余運算;ceil為向上取整運算。因此,AGV的行走路線可以用一系列序號數組的形式表示出來[15]。

圖1 AGV柵格環境

AGV運動方向如圖2所示,除邊緣柵格外,每個柵格一般有左上、上、右上、左、右、左下、下、右下8個運動方向,分別將它們用1、2、3、4、5、6、7、8數字進行編號。

圖2 AGV運動方向圖

1.2 柵格環境處理

在柵格環境中,當一個可行柵格的上、下、左、右4個方向中至少有3個方向有障礙柵格存在時,就構成了一個凹形障礙物。本文針對此類凹形障礙物中的可行柵格做了優化處理,這是因為這類可行柵格不但會增加不必要的路徑,而且還有可能導致螞蟻在搜索路徑的過程中無路可走而無法到達終點,即發生死鎖現象,降低了蟻群路徑搜索質量。柵格環境處理前后地圖如圖3所示。從圖3a可以看出,由網格14到網格16處,經過網格9的長度比網格15的路徑長度長;由網格24到網格36處,經過網格29的長度比網格30的路徑長度長,而且在網格29處螞蟻如果向網格28、27移動,那么會造成死鎖。本文算法會檢測可行柵格上、下、左、右4個方向柵格的可行狀態,若出現3個及3個以上的柵格不可行時,則會把該柵格標記為障礙柵格,整個柵格持續重復檢測標記,直到障礙柵格的數目不再增加為止,實現效果如圖3b所示。

圖3 柵格環境處理前后地圖

2 基本蟻群算法

基本蟻群算法中,人工螞蟻在尋找路徑時,和真實螞蟻相似,會根據路徑上信息素的濃度選擇運動方向,濃度越高,選擇該運動方向的概率就越大。假設螞蟻k在t時刻從節點i到節點j的路徑上的信息素為τij(t),則從節點i到j的轉移概率為:

(2)

其中:α反映了信息素在路徑選擇時的重要程度,α越大,螞蟻就更傾向于選擇高信息素濃度的節點;啟發值ηij=1/djG,表示為從節點j到終點G的歐式距離的倒數;β反映了啟發信息在路徑選擇時的重要性,β越大,螞蟻就更傾向于選擇距離終點較近的柵格節點;D為節點i可選的下一個可達節點的集合。

基本蟻群算法中,螞蟻利用信息素尋找路徑的同時,也會在路徑上釋放信息素,當一代螞蟻中所有的螞蟻都完成了路徑搜尋,全局信息素更新方式為:

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

(3)

(4)

(5)

3 優化蟻群算法

3.1 優化信息素的初始分配

基本蟻群算法初始信息素的設置都是相同的量,會導致算法在初期搜索時具有一定的盲目性,增加了搜索路徑的時間成本。本文中的優化蟻群算法提出了一種使用輔助蟻群來協助主蟻群進行初始信息素分配的方法。輔助蟻群利用其在搜索路徑上的方向優勢,這種方向優勢可以讓輔助蟻群較基本蟻群快速規劃出可行的較優路徑。輔助蟻群工作原理如圖4所示，假設起點在序號為1的柵格處,記為B;終點在序號為25的柵格處,記為G,由于從B到G有一定的方向性,最優路徑一般會出現在AGV由右、右下、下3個運動方向到達的節點組成的路徑中。因此在輔助蟻群中,規定螞蟻k在節點i處最多只有3個轉移方向,即右、下和右下,從節點i到可轉移節點j的轉移概率為:

(6)

其中:jx、jy分別為節點j的橫、縱坐標值;ix、iy分別為節點i的橫、縱坐標值;D′為節點i在右、下、右下3個方向可達節點的集合。由(6)式可知,螞蟻在右、下、右下方向的轉移概率分別為1/4、1/4、1/2,因此輔助蟻群更偏向于往右下方向移動,有利于減少搜索路徑長度。

圖4 輔助蟻群工作原理

輔助蟻群的每一代螞蟻中,只對找出該代中最短路徑的螞蟻的信息素進行更新,全局信息素更新方式為:

(7)

(8)

其中:n為一代中最優路徑上的螞蟻數;Lbest′為該代中的最優路徑長度;路徑(i,j)為該代最優路徑。為避免某一路徑較其他路徑上的信息素濃度過高,造成主蟻群過早收斂,引入最大最小螞蟻系統,利用下式對輔助蟻群迭代完成后的信息素進行限制，即

(9)

其中:τmax′、τmin′分別為設置的輔助蟻群信息素的最大值和最小值。

設置輔助蟻群的初始信息素,待蟻群迭代完成后,將輔助蟻群信息素傳遞給主蟻群,作為主蟻群的初始信息素。由于輔助蟻群每代最優路徑上的信息素較其他路徑多,能夠引導主蟻群沿著這些路徑移動,從而提高主蟻群前期搜索的路徑質量;將輔助蟻群當前搜索到的最優路徑傳遞給主蟻群,幫助主蟻群優化搜索策略。此外,輔助蟻群在類似于圖1的環境中會找不到從起點到終點的通路,此時輔助蟻群路徑上的初始信息素只會隨著迭代而揮發,而沒有信息素的增量。迭代結束后,輔助蟻群將揮發后的信息素傳遞給主蟻群,同時將當前最優路徑長度設置為無窮大,此時主蟻群仍然能正常工作。

3.2 優化的狀態轉移策略

對于主蟻群,針對基本蟻群算法中螞蟻從一個節點到下一個節點的狀態轉移為單獨的輪盤賭方式,很容易造成螞蟻較快集中到某一路徑而導致搜索到的最優路徑不為全局最優的情況,提出了一種偽隨機狀態轉移策略為:

(10)

其中:j1為i節點處隨機選擇的下一個可達節點;j2為采用(2)式選擇的下一節點;q為0～1之間的隨機數;q0為偽隨機轉移策略選擇的切換值,q0=1/(N+1),為自適應動態變量,隨著迭代次數的增加而減少;N為優化蟻群算法主蟻群的迭代次數。前期q0能取到較大的值,增加搜索路徑的多樣性;后期q0較小,螞蟻將會集中在信息素較多的路徑上,加快收斂速度。

3.3 優化的信息素更新策略

本文采用全局信息素更新策略,即當一代螞蟻中所有個體都完成了路徑搜索后才更新路徑信息素。

將輔助蟻群更新后的信息素和當前搜索到的最優路徑傳遞給主蟻群,幫助主蟻群完成路徑規劃。主蟻群每代螞蟻搜索完路徑后,根據主蟻群一代螞蟻中最差路徑Lworst、一代螞蟻中最優路徑Lbest及當前主蟻群和輔助蟻群所找到的最優路徑LbestALL,利用(3)式、(4)式、(11)式更新全局信息素,即

(11)

懲罰一代中的最差路徑可以減少后代蟻群在該路徑上的數目,對當前路徑上的信息素進行有差別的獎勵,使螞蟻集中在較優路徑附近,提高螞蟻搜索路徑解的質量,加快收斂速度。

在路徑搜索過程中,可能會出現某代螞蟻中出現了當前最優路徑,但由于路徑上的信息素比較低而在后代螞蟻中丟失的現象,降低了找到全局最優解的概率。為了確保當前最優路徑不會丟失,若Lbest和LbestALL在一代螞蟻中不相等,即該代螞蟻沒有搜索到LbestALL所在路徑時,在該代螞蟻路徑信息素更新完畢后,則根據(3)式、(12)式增加當前最優路徑LbestALL的信息素為:

(12)

為了避免由于某一路徑上信息素濃度過高導致算法的停滯,對路徑上的信息素進行限制，即

(13)

其中:τmax為限制的信息素的最大值;τmin為限制的信息素的最小值。

3.4 優化蟻群算法的實現步驟

優化蟻群算法的路徑尋優流程圖如圖5所示。

具體實現步驟如下:

(2) 柵格環境處理。當一個可行柵格的上、下、左、右4個方向中至少3個方向有障礙柵格存在,將該柵格標記為障礙柵格。

(3) 輔助蟻群利用其方向優勢尋找路徑,迭代完成后將當前最優路徑和更新后的信息素傳遞給主蟻群作為初始信息素。

(4) 主螞蟻k通過主蟻群狀態轉移策略選擇移動到下一地址。

(5) 判斷螞蟻k是否陷入死鎖,若陷入,則丟棄該只螞蟻,并立刻啟動下一螞蟻,轉步驟(4)。

(6) 判斷螞蟻k是否到達終點,若到達,則記錄該路徑并啟動下一螞蟻,轉步驟(4)。

(7) 判斷一代中m只螞蟻是否都完成了路徑搜索;若是,則對該代中的螞蟻根據主蟻群信息素更新策略、更新信息素,迭代次數加1;否則轉步驟(4)。

(8) 重復步驟(4)～步驟(7),直到達到主蟻群最大迭代次數。

(9) 輸出最優路徑,程序結束。

圖5 優化蟻群算法路徑尋優流程圖

4 仿真實驗及結果

對2種算法均進行20次獨立實驗,仿真后的統計數據見表1所列。

圖6 文獻[16]蟻群算法最優路徑軌跡及仿真結果

圖7 優化蟻群算法最優路徑軌跡及仿真結果

表1 2種算法2次運行結果統計數據

從圖6、圖7可以看出,本文的優化蟻群算法和文獻[16]蟻群算法的最優路徑相同,但是由表1可知,本文算法20次仿真實驗中的最優路徑都為全局最優路徑,而文獻[16]算法有一定概率搜索到的最優路徑為全局次優路徑,同時本文算法達到最優路徑的平均迭代次數相比文獻[16]算法有了顯著提高。

以上實驗結果表明,相較于文獻[16]算法,本文算法通過引入輔助蟻群,使主蟻群前期路徑搜索時更具有針對性;通過引入偽隨機狀態轉移策略,增加了搜索過程中路徑的多樣性;通過優化信息素更新策略,保證了路徑解的質量,從而提高了蟻群算法的搜索效率,加快了蟻群算法的收斂速度,提升了最優路徑解的質量,表明了本文算法的優越性。

5 結 論

在基本蟻群算法的基礎上,本文提出了一種優化蟻群算法,對柵格環境做了優化處理,利用輔助蟻群設置主蟻群的初始信息素,減少前期主蟻群搜索路徑的盲目性,并且對基本蟻群算法的狀態轉移策略以及信息素的更新策略做了相應優化。

MATLAB仿真結果表明,該優化蟻群算法提高了蟻群搜索效率,加快了收斂速度,提升了最優解的質量,表明該優化蟻群算法在AGV路徑規劃尋優問題上是行之有效的。