基于改進(jìn)勢(shì)場(chǎng)蟻群算法的自動(dòng)引導(dǎo)小車路徑規(guī)劃研究

王 雨，謝 峰，劉玉磊，朱 翔

（安徽大學(xué) 電氣工程與自動(dòng)化學(xué)院，合肥 230601）

0 引言

自動(dòng)引導(dǎo)小車（Automated Guided Vehicles，簡(jiǎn)稱AGV）是一種無人駕駛的智能運(yùn)輸車，廣泛的應(yīng)用于現(xiàn)代工業(yè)自動(dòng)化物流系統(tǒng)中[1]。AGV是指裝有諸如磁傳感器、攝像機(jī)等導(dǎo)航裝置，能夠行駛在提前規(guī)劃好的路徑，并且在車體上安裝有主控制器、定位裝置、安全保護(hù)裝置、通訊模塊、以及各種物料運(yùn)載的車輛，是一種智能輪式機(jī)器人，被廣泛用于工廠自動(dòng)化生產(chǎn)線、倉(cāng)儲(chǔ)物流、機(jī)場(chǎng)和港口的物料傳送場(chǎng)景[2,3]。AGV路徑規(guī)劃是目前機(jī)器人領(lǐng)域中一個(gè)研究的熱點(diǎn)，即在未知的環(huán)境中，尋找到一條時(shí)間最短、路徑最短的安全無碰撞路徑。目前解決問題的方法主要有人工勢(shì)場(chǎng)法[4,5]、Dijkstra算法[6]、遺傳算法[7]以及蟻群算法[8]等，其中每種方法都存在著自身的優(yōu)點(diǎn)和不足之處。

蟻群算法是由意大利學(xué)者M(jìn)arco Dorigo于1992年提出的，其靈感來源于螞蟻在尋找食物過程發(fā)現(xiàn)路徑的行為。螞蟻在覓食的過程中會(huì)傾向于選擇信息素濃度大的路徑，同時(shí)更新自己的信息素，直到蟻群選擇同一條且信息素濃度最大的最優(yōu)路徑。蟻群算法具有較強(qiáng)的適應(yīng)性和魯棒性，但是也存在著許多問題，如蟻群算法是以螞蟻從當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的距離作為啟發(fā)信息，不利于螞蟻對(duì)動(dòng)、靜態(tài)障礙物的規(guī)避，而且螞蟻尋找目標(biāo)是一個(gè)盲目搜索的過程，這樣就會(huì)產(chǎn)生較多的交叉路徑和螞蟻迷失現(xiàn)象[9]，造成蟻群算法過早的收斂、搜索路徑效率低下等情況。

人工勢(shì)場(chǎng)法是一種局部路徑規(guī)劃算法，它的本質(zhì)是對(duì)AGV運(yùn)行環(huán)境虛擬成一個(gè)抽象的勢(shì)場(chǎng)，在虛擬勢(shì)場(chǎng)中AGV受到障礙物的斥力和目標(biāo)的吸引力形成的合力來確定運(yùn)動(dòng)方向和速度。人工勢(shì)場(chǎng)法可以保證得到一條安全的路徑，但可能并不是最優(yōu)的一條，而且也存在著一些不足之處，該算法易造成目標(biāo)不可以到達(dá)且在目標(biāo)點(diǎn)附近打轉(zhuǎn)，或存在著局部最小區(qū)域，迫使AGV處于暫時(shí)停滯狀態(tài)[10]。

本文根據(jù)蟻群算法和人工勢(shì)場(chǎng)法兩者的優(yōu)缺點(diǎn)，提出了一種改進(jìn)的勢(shì)場(chǎng)蟻群算法。該算法利用AGV所受到人工勢(shì)場(chǎng)力以及到目標(biāo)點(diǎn)的距離來重新構(gòu)造啟發(fā)信息函數(shù)，根據(jù)動(dòng)、靜態(tài)障礙物構(gòu)造不同的勢(shì)場(chǎng)函數(shù)，并且引入障礙物對(duì)AGV的相對(duì)速度和方向，實(shí)時(shí)更新動(dòng)態(tài)障礙物在柵格地圖中的位置，可以做到以較小的代價(jià)提前規(guī)避障礙物；人工勢(shì)場(chǎng)的加入使螞蟻盲目搜索變成有向的搜索，減少了蟻群搜索過程中的“迷失”現(xiàn)象，加快了收斂速度。

1 蟻群算法和人工勢(shì)場(chǎng)法的基本原理

為了更好地利用勢(shì)場(chǎng)蟻群算法解決自動(dòng)化車間環(huán)境下AGV路徑規(guī)劃問題，本文將AGV工作環(huán)境視為二維空間，并采用柵格法建立柵格地圖，根據(jù)AGV小車的大小尺寸來進(jìn)行柵格地圖網(wǎng)格大小的劃分，黑色表示障礙物，白色表示自由柵格，AGV作為一個(gè)質(zhì)點(diǎn)運(yùn)動(dòng)，對(duì)障礙物進(jìn)行膨脹處理，如占據(jù)局部柵格，按照整個(gè)柵格處理，以防止發(fā)生碰撞。AGV路徑規(guī)劃算法如下。

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

傳統(tǒng)的蟻群算法來決定螞蟻在t時(shí)刻行走路徑的原理是：某螞蟻（m）在第i個(gè)節(jié)點(diǎn)選擇下一個(gè)節(jié)點(diǎn)j的概率是根據(jù)柵格環(huán)境中各路徑上的信息素ij(t)和當(dāng)前的啟發(fā)信息ij(t)的大小決定的，如式(1)所示。

螞蟻經(jīng)過的路徑會(huì)留下信息素，但隨著時(shí)間的流逝會(huì)揮發(fā)一定的數(shù)量，需要對(duì)其按照式(2)進(jìn)行局部更新：

蟻群算法完成一次迭代后，可找出當(dāng)前螞蟻尋找到的最短、最優(yōu)路徑，并對(duì)信息素通過式(3)和式(4)進(jìn)行全局更新。

式中：Q為常量，ρ表示信息揮發(fā)參數(shù)，Lm表示螞蟻建立的最短路徑。

1.2 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法的實(shí)質(zhì)是對(duì)機(jī)器人運(yùn)行環(huán)境虛擬一個(gè)抽象勢(shì)場(chǎng)，障礙物對(duì)機(jī)器人產(chǎn)生斥力Frep，目標(biāo)點(diǎn)產(chǎn)生引力Fatt，合力Ftot指引機(jī)器人運(yùn)動(dòng)。

假設(shè)AGV在M點(diǎn)，目標(biāo)對(duì)其引力勢(shì)場(chǎng)函數(shù)為Uatt(i)，如式(5)所示，障礙物對(duì)其斥力勢(shì)場(chǎng)函數(shù)為Urep(i)，如式(6)所示[11～13]。

式中：η和ξ分別是斥力勢(shì)場(chǎng)常量、引力勢(shì)場(chǎng)常量；d（M，O）為當(dāng)前點(diǎn)到障礙物點(diǎn)的距離；d（M，G）為當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的距離；dO表示斥場(chǎng)作用半徑。AGV在M點(diǎn)所受的引力和斥力分別為式(7)、式(8)所示。

根據(jù)幾何疊加原理得到所受合力為Ftot=Frep+Fatt，nMG為當(dāng)前點(diǎn)到目標(biāo)點(diǎn)的單位矢量。

2 勢(shì)場(chǎng)蟻群算法的改進(jìn)

2.1 改進(jìn)的人工勢(shì)場(chǎng)法

自動(dòng)化車間環(huán)境經(jīng)常會(huì)有人來回的進(jìn)行走動(dòng)，形成了動(dòng)態(tài)的障礙物，人工勢(shì)場(chǎng)對(duì)于動(dòng)態(tài)障礙物的環(huán)境，存在著躲避不及的問題，因此需在人工勢(shì)場(chǎng)法的基礎(chǔ)上加以改進(jìn)，對(duì)勢(shì)場(chǎng)函數(shù)不僅要考慮其相對(duì)位置，還要考慮它們之間的相對(duì)速度。如圖1所示，以AGV小車為參照物，通過kinect視覺傳感器感知環(huán)境，得到障礙物t0到t1時(shí)間段的位置信息和移動(dòng)角度，然后抽象為速度矢量三角形計(jì)算它們的相對(duì)速度大小v和方向。

圖1 求取障礙物相對(duì)速度示意圖

規(guī)定AGV移動(dòng)逆時(shí)針為正，順時(shí)針為負(fù)，則障礙物移動(dòng)的相對(duì)角度和距離為式(9)所示：計(jì)算出安全避碰最小角度和安全距離，并據(jù)此建立新的勢(shì)場(chǎng)函數(shù)。所改進(jìn)的引力勢(shì)場(chǎng)函數(shù)和斥力勢(shì)場(chǎng)函數(shù)分別為式(10)和式(11)：

由此可求出障礙物和AGV的碰撞角

式中η和ξ是速度常數(shù)，v是AGV到障礙物的相對(duì)速度，vO為AGV到目標(biāo)點(diǎn)的相對(duì)速度。

那么，AGV在此處受到的斥力和引力分別如式(12)和式(13)所示。

2.2 啟發(fā)信息的改進(jìn)

螞蟻在柵格地圖上移動(dòng)，傳統(tǒng)蟻群算法中螞蟻受到信息素濃度和距離的作用，當(dāng)路徑短時(shí)，使螞蟻往返一次時(shí)間短，重復(fù)頻率快，每次行走都會(huì)留下信息素，吸引更多的螞蟻，增加路徑上的信息素濃度，這樣越來越多的螞蟻都聚集在最短路徑上。但在路徑規(guī)劃初期，信息素濃度較弱時(shí)，螞蟻搜索的隨機(jī)性較大，收斂速度變慢。而在傳統(tǒng)的人工勢(shì)場(chǎng)法中，螞蟻是通過所受勢(shì)場(chǎng)合力來進(jìn)行路徑規(guī)劃，定義的啟發(fā)信息為：

式中，α為常數(shù)，θ為螞蟻行走方向和勢(shì)場(chǎng)合力方向的夾角。在啟發(fā)信息的作用下，螞蟻選擇θ最小的邊行走，有利于避免碰撞和有效的選擇最接近目標(biāo)點(diǎn)路經(jīng)行走。但當(dāng)勢(shì)場(chǎng)合力為零時(shí)，AGV將會(huì)處于局部最小點(diǎn)，引力和斥力等價(jià)，陷入局部最優(yōu)位置陷阱，為此，本文結(jié)合兩種算法的優(yōu)點(diǎn)構(gòu)成算法的啟發(fā)信息為：

式中，Nmax和N分別為最大迭代次數(shù)和當(dāng)前迭代次數(shù)。從式(17)可以看出在勢(shì)場(chǎng)蟻群算法初期，信息素濃度較低，主要靠勢(shì)場(chǎng)力啟發(fā)信息使螞蟻快速找到目標(biāo)點(diǎn)。隨著迭代次數(shù)的增加，降低了勢(shì)場(chǎng)力啟發(fā)信息的作用，加強(qiáng)了信息素的作用，使螞蟻主要集中在信息素濃度強(qiáng)的路徑上，從而增強(qiáng)了對(duì)最優(yōu)路徑的搜索。最后還可以保障在人工勢(shì)場(chǎng)合力為零的情況下仍有效的進(jìn)行到目標(biāo)的最優(yōu)路徑搜索，進(jìn)而避免失去搜索方向。

2.3 路徑規(guī)劃步驟

步驟1：確定柵格地圖長(zhǎng)度，障礙物的位置，AGV的起始點(diǎn)和終點(diǎn)；

步驟2：初始化勢(shì)場(chǎng)蟻群算法的參數(shù)，例如螞蟻數(shù)量、信息啟發(fā)因子、引力和斥力增益、信息素強(qiáng)度等；

步驟3：將螞蟻放在起點(diǎn)，判斷行走過程中有沒有動(dòng)態(tài)障礙物，如果存在動(dòng)態(tài)障礙物，算出安全距離和角度，更新柵格地圖中的障礙物位置，按照式(1)和勢(shì)場(chǎng)合力方向選擇下一個(gè)節(jié)點(diǎn)。當(dāng)螞蟻到節(jié)點(diǎn)j后的，按式(2)對(duì)走過的路進(jìn)行局部信息素更新，并刪除跟新的柵格地圖；若不存在動(dòng)態(tài)障礙物，按照傳統(tǒng)勢(shì)場(chǎng)合力方向選擇下一個(gè)節(jié)點(diǎn)j，并將節(jié)點(diǎn)j加入禁忌表；

步驟4：重復(fù)步驟3，直到螞蟻到達(dá)目標(biāo)點(diǎn)，保存所有螞蟻搜索到的路徑長(zhǎng)度，并選擇最優(yōu)路徑；

步驟5：按照式(3)對(duì)最短路徑進(jìn)行信息素的全局更新，清空禁忌表；

步驟6：判斷是否達(dá)到最大迭代次數(shù)，若達(dá)到則終結(jié)，否則重復(fù)步驟3到步驟4。

3 AGV路徑規(guī)劃實(shí)驗(yàn)驗(yàn)證

為了驗(yàn)證本文所提的路徑規(guī)劃算法的可行性，在Matlab環(huán)境下對(duì)該算法進(jìn)行仿真，加以和常規(guī)的蟻群算法比較。本文用20×20的柵格環(huán)境和不同的障礙物設(shè)置來模擬真實(shí)環(huán)境，每個(gè)柵格的大小為一個(gè)單位長(zhǎng)度。AGV起點(diǎn)設(shè)置為（1，20），終點(diǎn)設(shè)置為（20，1），黑色表格為障礙物，白色表格表示自由柵格。設(shè)定參數(shù)螞蟻數(shù)量為30，迭代次數(shù)為100，信息素濃度啟發(fā)因子α=1，能見度啟發(fā)因子β=5，信息素?fù)]發(fā)系數(shù)ρ=0.7，信息素強(qiáng)度Q=1，引力系數(shù)η=2，斥力系數(shù)ζ=2，斥力作用半徑d0=2，可調(diào)參數(shù)ψ=0.1。

通過圖2可以看出，在復(fù)雜的自動(dòng)化車間環(huán)境下，傳統(tǒng)蟻群算法沒有搜索到一條最優(yōu)的路徑，而是找到了一條較長(zhǎng)的路徑，因?yàn)槊つ克阉骱退训絾l(fā)信息的影響，在中心復(fù)雜的環(huán)境中，螞蟻偏向于遠(yuǎn)離障礙物，造成了較長(zhǎng)的行走路徑，由于信息素的作用，以后的蟻群也會(huì)較大幾率選擇此路。改進(jìn)的算法在勢(shì)場(chǎng)合力和信息素濃度的雙重作用下加快算法的收斂速度，并且避免了上述問題。從收斂曲線看，蟻群算法用了56次迭代收斂到34.549，本文改進(jìn)的勢(shì)場(chǎng)蟻群算法只用了30次迭代就收斂到最優(yōu)路徑30.364。

圖2 蟻群算法

圖3 改進(jìn)勢(shì)場(chǎng)蟻群算法

圖4 動(dòng)態(tài)障礙物的路徑規(guī)劃

對(duì)于動(dòng)態(tài)障礙物，改進(jìn)的人工勢(shì)場(chǎng)可以實(shí)時(shí)更新局部環(huán)境，根據(jù)計(jì)算得到的安全距離和角度來填充柵格地圖障礙物的位置。從上圖可以看出當(dāng)運(yùn)行到（8，14）時(shí)，有動(dòng)態(tài)障礙物實(shí)時(shí)更新柵格地圖，從（8，12）開始添加障礙物，然后根據(jù)改進(jìn)人工勢(shì)場(chǎng)算法在局部柵格地圖重新計(jì)算路徑。從圖4可以看出路徑變得更加復(fù)雜，用37次迭代收斂到31.269。

4 結(jié)論

本文針對(duì)復(fù)雜的自動(dòng)化車間環(huán)境的路徑規(guī)劃問題，采用人工勢(shì)場(chǎng)算法和蟻群算法融合的辦法。將AGV在運(yùn)動(dòng)中受到的虛擬勢(shì)場(chǎng)合力作為螞蟻尋找目標(biāo)點(diǎn)的部分啟發(fā)信息，引導(dǎo)AGV感知周圍障礙物，進(jìn)行有效的避障和目標(biāo)搜索。在感知到運(yùn)動(dòng)目標(biāo)時(shí)，及時(shí)的在局部地圖上更新障礙物，在改進(jìn)的新勢(shì)場(chǎng)函數(shù)引導(dǎo)下進(jìn)行有效的避障，尋找到最優(yōu)的安全避障距離和角度，結(jié)束后恢復(fù)原柵格地圖。通過仿真結(jié)果表明，本文所提出的改進(jìn)勢(shì)場(chǎng)蟻群算法對(duì)自動(dòng)化車間環(huán)境下路徑規(guī)劃的效果比較好，對(duì)動(dòng)態(tài)障礙物也有很好的躲避效果。