融合柵格地圖模型的改進(jìn)AGV路徑規(guī)劃算法研究

顧文斌，陳澤宇，吳亞偉，苑明海

(1.河海大學(xué) 機(jī)電學(xué)院，江蘇 常州 213022；2.常州工程職業(yè)技術(shù)學(xué)院，江蘇 常州 213022)

0 引 言

自動(dòng)引導(dǎo)小車(automated guided vehicle，AGV)最早出現(xiàn)于二十世紀(jì)五十年代，是一種智能化物料自動(dòng)搬運(yùn)設(shè)備，其特點(diǎn)在于自動(dòng)化程度高、易于控制、節(jié)省勞動(dòng)力、提高運(yùn)輸效率、占地空間小等，因此，AGV在眾多生產(chǎn)制造物流行業(yè)中得到了廣泛應(yīng)用。在汽車制造行業(yè)中，物流領(lǐng)域自動(dòng)化設(shè)備應(yīng)用是大勢(shì)所趨，使用AGV替代人力能夠降低汽車制造企業(yè)的運(yùn)輸成本，提升服務(wù)質(zhì)量[1]。對(duì)煙草、醫(yī)藥、食品和化工等行業(yè)而言，業(yè)內(nèi)對(duì)搬運(yùn)任務(wù)有清潔、無排放污染、安全等要求，AGV能夠較好地勝任。在倉儲(chǔ)業(yè)中，AGV使用程度更為廣泛，因?yàn)锳GV有較強(qiáng)自動(dòng)化水平和較高柔性，在倉儲(chǔ)物流行業(yè)中能夠降低人力成本，提高運(yùn)輸效率[2]。在AGV的使用中，進(jìn)行合理的路徑規(guī)劃對(duì)于降低企業(yè)運(yùn)營成本，提高利潤率有重大作用，因此AGV的路徑規(guī)劃問題十分值得研究。

為了計(jì)算得到全局最優(yōu)路徑，目前采用的方法主要有遺傳算法[3-4]、粒子群算法[5-6]、快速擴(kuò)展隨機(jī)樹尋路算法[7]和蟻群算法[8-9]。之后的研究主要針對(duì)這幾種算法進(jìn)行改進(jìn)，文獻(xiàn)[1]提出的改進(jìn)遺傳算法減少了最短路徑的路程，文獻(xiàn)[2]對(duì)傳統(tǒng)遺傳算法進(jìn)行改進(jìn)，提高了算法的收斂速度和效率。文獻(xiàn)[5]提出的改進(jìn)粒子群算法提高了在AGV在規(guī)避障礙時(shí)搜得解的精度。文獻(xiàn)[7]提出的改進(jìn)快速擴(kuò)展隨機(jī)樹尋路算法使得在復(fù)雜環(huán)境下機(jī)器人的運(yùn)行更加平穩(wěn)，且在一定程度上縮短了路徑長度。文獻(xiàn)[8]提出的融合粒子群與蟻群算法提升了蟻群算法的整體性能。對(duì)于傳統(tǒng)蟻群算法收斂性差，容易陷入局部最優(yōu)，結(jié)果不穩(wěn)定的缺點(diǎn)，則考慮在對(duì)螞蟻和迭代質(zhì)量的評(píng)估之后，對(duì)每一次尋路的信息素進(jìn)行區(qū)別更新，有利于擴(kuò)大算法前期的搜索范圍，加強(qiáng)算法后期的收斂性，提高算法的穩(wěn)定性。

以上文獻(xiàn)所用方法是目前解決AGV路徑規(guī)劃問題中普遍認(rèn)可的，較優(yōu)的算法，但是傳統(tǒng)算法存在容易進(jìn)入局部最優(yōu)解，收斂性較差和搜尋結(jié)果穩(wěn)定性差的問題?；诖?，該文提出了改進(jìn)型蟻群算法，使用兩次評(píng)估來合理區(qū)分蟻群，根據(jù)區(qū)分結(jié)果使用不同的信息素更新方式，以此實(shí)現(xiàn)提高算法解的多樣性、收斂性和穩(wěn)定性的目標(biāo)。此外使用蜂巢柵格建立地圖模型，使得模型更加實(shí)際可靠，能提高AGV小車行駛時(shí)的平穩(wěn)性，并降低避險(xiǎn)路徑的長度。

1 環(huán)境模型建立

對(duì)于研究AGV的路徑規(guī)劃問題，建立其空間移動(dòng)環(huán)境模型是基礎(chǔ)，常用的方法有可視圖法[10]、傳統(tǒng)柵格法[11]和人工勢(shì)場(chǎng)法[12]。柵格法(grid method)具有簡(jiǎn)單，易于表達(dá)和靈活等優(yōu)點(diǎn)，所以采用柵格法建立AGV空間環(huán)境模型，并在傳統(tǒng)的柵格基礎(chǔ)上，模擬蜂巢建立起正六邊形的柵格，對(duì)AGV行駛環(huán)境進(jìn)行分割。

1.1 蜂巢柵格模型建立

圖1 蜂巢型柵格

1.2 蜂巢型柵格和傳統(tǒng)柵格的對(duì)比分析

圖2 蜂巢柵格移動(dòng)方向

圖3 避險(xiǎn)路徑對(duì)比

圖4 最短路徑對(duì)比

綜上，蜂巢柵格在行駛的平穩(wěn)性和避險(xiǎn)路徑的長度方面都優(yōu)于傳統(tǒng)的正方形柵格，因此后文的改良蟻群算法將在蜂巢柵格的背景下進(jìn)行求解。

2 基于動(dòng)態(tài)分級(jí)制度的改進(jìn)型蟻群算法

2.1 傳統(tǒng)蟻群算法

在傳統(tǒng)的蟻群算法中，螞蟻會(huì)根據(jù)路徑上的信息素濃度選擇自己的路徑，并且根據(jù)路徑的質(zhì)量留下新的信息素，每一次迭代后所有路徑上的信息素都會(huì)消散一部分，使得路徑尋找不會(huì)過早地進(jìn)入局部最優(yōu)。選擇方法如下。

(1)

(2)

(3)

式中，ρ∈(0,1)，為信息素在一次迭代中的揮發(fā)系數(shù)；Δτij為信息素的增量；K為螞蟻總數(shù)；Q為一常數(shù)。

2.2 選擇機(jī)制的改進(jìn)

在傳統(tǒng)的蟻群算法中，路徑啟發(fā)因子ηij(t)是根據(jù)路徑(i，j)所確定的，但是這樣容易陷入局部最優(yōu)解。為了獲得全局優(yōu)解，在改進(jìn)的算法中使用ηij(t)=1/d(i,s)，其中d(i,s)為螞蟻此時(shí)距離目標(biāo)點(diǎn)的距離，同時(shí)將allowedk改為螞蟻k相鄰可選擇的點(diǎn)，將柵格矩陣做鄰接處理，螞蟻k只能選擇所得鄰接矩陣中值不為0的點(diǎn)做下一目標(biāo)點(diǎn)，以減少不必要的計(jì)算。

2.3 對(duì)蟻群進(jìn)行評(píng)估分類

對(duì)于傳統(tǒng)的蟻群算法，信息素的更新完全根據(jù)路徑長度，也有學(xué)者研究了改良的信息素更新規(guī)則[13]來優(yōu)化蟻群算法，但是在算法前期多樣性和后期的收斂性方面還有待提高。針對(duì)這個(gè)問題，文中在考慮螞蟻的動(dòng)態(tài)分級(jí)[9]之上，考慮每一次迭代的質(zhì)量，將每一次的迭代性質(zhì)分為尋優(yōu)和偵察，不同性質(zhì)的迭代采用不同的信息素更新規(guī)則，以提高前期解的多樣性和后期解的收斂性。

具體來說，受到人工蜂群算法[14]的啟發(fā)，先將螞蟻分為偵察蟻和尋優(yōu)蟻。首先根據(jù)該螞蟻在一次迭代中所搜索到的路徑Lk與此次迭代中所搜索到的最短路徑Lmin相比較，得到該螞蟻的屬性值，該值設(shè)置為：Tk=Lmin/Lk。之后設(shè)置屬性值的閾值，記為T0。比較屬性值和閾值來區(qū)分偵察蟻和尋優(yōu)蟻，當(dāng)Tk>T0時(shí)，說明該螞蟻搜得結(jié)果與最優(yōu)解相近，為尋優(yōu)蟻，則該螞蟻在更新信息素時(shí)，將更新的參數(shù)調(diào)整使得余留更多的信息素。反之當(dāng)Tk≤T0時(shí)，說明該螞蟻搜得路徑與最短路徑之間的差距較大，為偵察蟻，則該螞蟻在更新信息素時(shí)，將參數(shù)調(diào)整使得余留更少的信息素。所以T0設(shè)置的值需要重點(diǎn)研究，如果T0太大容易導(dǎo)致更少的螞蟻成為尋優(yōu)蟻而導(dǎo)致算法最終不能很好地收斂，如果T0太小容易使更多的螞蟻成為尋優(yōu)蟻而導(dǎo)致蟻群容易陷入局部最優(yōu)解。經(jīng)過多次仿真，發(fā)現(xiàn)將T0設(shè)置為0.68時(shí)能得到很好的結(jié)果。

2.4 信息素更新規(guī)則

根據(jù)上文對(duì)蟻群的評(píng)估結(jié)果，將算法中的螞蟻分為了四種情況，對(duì)于四種螞蟻將采取不同的信息素更細(xì)規(guī)則。

首先對(duì)于尋優(yōu)蟻和偵察蟻，兩者在信息素更新時(shí)，滿足以下關(guān)系：

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

(4)

(5)

(6)

式(5)、式(6)中，ω為螞蟻質(zhì)量系數(shù)，其中ω1>ω2>0，Q為一常數(shù)，Tk為螞蟻的屬性值，T0為螞蟻屬性值的閾值。在此更新規(guī)則下，尋優(yōu)蟻的信息素余留要高于偵察蟻的信息素余留，這樣在進(jìn)行全局搜素時(shí)，確保了較優(yōu)路徑上有高濃度的信息素，但是ω1和ω2之間的差值不能過大，否則容易在算法初期就陷入局部最優(yōu)。經(jīng)過實(shí)驗(yàn)仿真，將ω1設(shè)置為5，ω2設(shè)置為3，能夠有效防止陷入局部最優(yōu)且最后收斂較好。

關(guān)于迭代質(zhì)量，由于在算法初期，螞蟻搜索范圍大，路徑長短參差不齊且相差較大，此時(shí)這一代螞蟻的信息素更新策略采用式(7)。

τij(t+1)=(1-ρ)τij(t)+pm·Δτij,pm≤p0(7)

式中，pm為迭代的質(zhì)量值；Δτij則根據(jù)上述內(nèi)容先判斷該螞蟻是尋優(yōu)蟻還是偵察蟻。

在這種機(jī)制下，算法初期過于發(fā)散的搜尋結(jié)果將不會(huì)留下過濃的信息素，而其中接近最優(yōu)路徑的螞蟻則根據(jù)尋優(yōu)蟻余留更多信息素的特點(diǎn)，將較優(yōu)路徑先行區(qū)分開來，到達(dá)算法后期，一次迭代中大部分螞蟻都是接近最優(yōu)路徑后，則使用式(4)進(jìn)行信息素更新，使結(jié)果收斂于最優(yōu)路徑。

綜上所述，改進(jìn)型蟻群算法信息素更新滿足以下規(guī)則。

(8)

2.5 算法流程

將蜂巢柵格和改進(jìn)的蟻群信息素更新規(guī)則融入傳統(tǒng)蟻群算法，得到的基于蜂巢柵格的改良蟻群算法如下(見圖5):

圖5 改進(jìn)蟻群算法流程

(1)全局初始化，將環(huán)境矩陣鄰接化得到鄰接矩陣，得到初始螞蟻總數(shù)，迭代總數(shù)，起點(diǎn)終點(diǎn)位置。

(2)螞蟻根據(jù)概率公式(1)對(duì)路徑節(jié)點(diǎn)進(jìn)行選擇。

(3)判斷螞蟻是否到達(dá)終點(diǎn)，若是，記錄此路徑長度并對(duì)該螞蟻的屬性進(jìn)行評(píng)估，當(dāng)所有螞蟻執(zhí)行完此步，迭代數(shù)加1。若不是則重復(fù)步驟(2)。

(4)當(dāng)所有螞蟻完成步驟(3),對(duì)迭代質(zhì)量進(jìn)行評(píng)估。

(5)根據(jù)螞蟻屬性和迭代質(zhì)量，對(duì)信息素進(jìn)行區(qū)別更新。

(6)判斷是否到達(dá)最大迭代數(shù)，若是，則輸出最優(yōu)路徑，算法結(jié)束；若不是，則重復(fù)步驟(2)～(5)，直到算法結(jié)束。

3 仿真分析

使用MATLAB軟件對(duì)傳統(tǒng)蟻群算法和改進(jìn)型蟻群算法進(jìn)行仿真。前文已經(jīng)論述了蜂巢柵格的優(yōu)點(diǎn)，所以兩種算法都在25×25的蜂巢柵格的背景下進(jìn)行計(jì)算。各個(gè)參數(shù)設(shè)置為：α=1,β=7,ρ=0.3,Q=1螞蟻數(shù)K=100，迭代數(shù)M=150。算法性能從算法的收斂性、路徑多樣性進(jìn)行證明。

3.1 算法收斂性證明

圖6為根據(jù)改進(jìn)型蟻群算法所得出的最短路徑圖。圖7為兩種算法的最短路徑長度的曲線收斂圖。從圖7的對(duì)比中可以看出，改進(jìn)型算法在前期效果并非十分明顯，因?yàn)橐ＷC初期路徑的多樣性，而到了算法中后期，進(jìn)行有針對(duì)地尋找最優(yōu)路徑時(shí)，改進(jìn)型蟻群算法能體現(xiàn)出良好的收斂性。

圖6 最優(yōu)路徑圖

為了證明算法的穩(wěn)定性，并和傳統(tǒng)算法進(jìn)行對(duì)比，將兩種算法各運(yùn)行10次并統(tǒng)計(jì)數(shù)據(jù)結(jié)果，如表1所示。

表1 算法結(jié)果對(duì)比

從表中可知，傳統(tǒng)算法下搜得最短路徑長度為36，而改進(jìn)型算法下搜得最短路徑為35，并且根據(jù)10次運(yùn)算的平均值和標(biāo)準(zhǔn)差可以看出，傳統(tǒng)的算法搜得最終結(jié)果差別較大，相比之下改進(jìn)型蟻群算法出現(xiàn)此類問題的次數(shù)會(huì)少很多，根據(jù)收斂代數(shù)也可以看出，改進(jìn)型蟻群算法由于信息素更新與傳統(tǒng)蟻群有區(qū)別，所以算法后期收斂性更強(qiáng)。

3.2 路徑多樣性證明

為了證明改進(jìn)型蟻群算法在路徑多樣性方面的優(yōu)越性，和王槐彬等人提出的動(dòng)態(tài)分級(jí)蟻群算法[15]進(jìn)行了實(shí)驗(yàn)數(shù)據(jù)結(jié)果對(duì)比。

在同時(shí)采用蜂巢柵格的基礎(chǔ)上，改進(jìn)型蟻群算法和動(dòng)態(tài)分級(jí)蟻群算法在路徑多樣性方面的對(duì)比如圖8所示。實(shí)驗(yàn)設(shè)計(jì)150次迭代，在前半段迭代中，由于迭代質(zhì)量不佳，螞蟻殘留的信息素濃度根據(jù)更新規(guī)則會(huì)相應(yīng)減少，可以看到改進(jìn)型蟻群算法的路徑多樣性要高于動(dòng)態(tài)分級(jí)蟻群算法，達(dá)到避免進(jìn)入局部最優(yōu)的效果，證明了改進(jìn)型蟻群算法在路徑多樣性方面的優(yōu)越性。并且在算法后半段，迭代質(zhì)量提升，螞蟻逐漸向整體最優(yōu)路徑靠攏，根據(jù)信息素更新規(guī)則留下的信息素會(huì)增加使得蟻群準(zhǔn)確地找到最優(yōu)解。在圖中可以看出，最后改進(jìn)型蟻群算法能夠使大部分螞蟻都找到最優(yōu)解，也證明了改進(jìn)型蟻群算法的收斂性要優(yōu)于動(dòng)態(tài)分級(jí)蟻群算法。

圖8 路徑種類對(duì)比

從每一次迭代結(jié)果的路徑長度標(biāo)準(zhǔn)差分析，如圖9所示，動(dòng)態(tài)分級(jí)蟻群算法整體上能實(shí)現(xiàn)算法前期避免進(jìn)入局部最優(yōu)，后期結(jié)果實(shí)現(xiàn)收斂，但是通過比較可以看出改進(jìn)型蟻群算法在前期的發(fā)散程度和后期的收斂程度都要高于動(dòng)態(tài)分級(jí)蟻群算法。如果考慮標(biāo)準(zhǔn)差到達(dá)一個(gè)閾值可以認(rèn)為蟻群已經(jīng)找到整體最優(yōu)解，那么改進(jìn)型蟻群算法相比于動(dòng)態(tài)分級(jí)蟻群算法能夠更快得到結(jié)果，解決算法效率低的問題，證明改進(jìn)型蟻群算法整體上優(yōu)于動(dòng)態(tài)分級(jí)蟻群算法。

圖9 路徑長度標(biāo)準(zhǔn)差對(duì)比

4 結(jié)束語

對(duì)于AGV的路徑規(guī)劃問題，在傳統(tǒng)的柵格模型上進(jìn)行改變，使用轉(zhuǎn)向角度小，避險(xiǎn)路徑和原路徑比值小的蜂巢柵格對(duì)AGV行駛環(huán)境進(jìn)行模型建立。在算法方面，由于傳統(tǒng)蟻群算法效率低，根據(jù)螞蟻和迭代的評(píng)估值對(duì)其進(jìn)行信息素區(qū)別更新。在新的更新規(guī)則下，根據(jù)仿真結(jié)果可以得出，相比于傳統(tǒng)算法，改進(jìn)型算法在前期的路徑多樣性，后期的算法收斂性方面都更加優(yōu)良，并且最終結(jié)果的準(zhǔn)確性、穩(wěn)定性也要優(yōu)于傳統(tǒng)的蟻群算法，證明了改進(jìn)型蟻群算法整體優(yōu)于傳統(tǒng)蟻群算法。