基于優(yōu)化蟻群算法的AGV路徑規(guī)劃研究

張志軍, 董學平, 甘 敏

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

0 引 言

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

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

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

1 環(huán)境建模

1.1 柵格環(huán)境

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

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

(1)

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

圖1 AGV柵格環(huán)境

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

圖2 AGV運動方向圖

1.2 柵格環(huán)境處理

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

圖3 柵格環(huán)境處理前后地圖

2 基本蟻群算法

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

(2)

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

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

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

(3)

(4)

(5)

3 優(yōu)化蟻群算法

3.1 優(yōu)化信息素的初始分配

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

(6)

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

圖4 輔助蟻群工作原理

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

(7)

(8)

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

(9)

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

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

3.2 優(yōu)化的狀態(tài)轉(zhuǎn)移策略

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

(10)

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

3.3 優(yōu)化的信息素更新策略

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

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

(11)

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

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

(12)

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

(13)

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

3.4 優(yōu)化蟻群算法的實現(xiàn)步驟

優(yōu)化蟻群算法的路徑尋優(yōu)流程圖如圖5所示。

具體實現(xiàn)步驟如下:

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

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

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

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

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

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

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

(9) 輸出最優(yōu)路徑,程序結(jié)束。

圖5 優(yōu)化蟻群算法路徑尋優(yōu)流程圖

4 仿真實驗及結(jié)果

對2種算法均進行20次獨立實驗,仿真后的統(tǒng)計數(shù)據(jù)見表1所列。

圖6 文獻[16]蟻群算法最優(yōu)路徑軌跡及仿真結(jié)果

圖7 優(yōu)化蟻群算法最優(yōu)路徑軌跡及仿真結(jié)果

表1 2種算法2次運行結(jié)果統(tǒng)計數(shù)據(jù)

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

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

5 結(jié) 論

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

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