基于改進(jìn)蟻群算法的AGV多目標(biāo)路徑規(guī)劃*

李傳奇，黃衛(wèi)華,b,c，章 政 ,b,c，金 震，張子然

(武漢科技大學(xué) a.機(jī)器人與智能系統(tǒng)研究院；b.冶金自動(dòng)化與檢測技術(shù)教育部工程研究中心；c.信息科學(xué)與工程學(xué)院，湖北 武漢 430081)

0 引言

自動(dòng)導(dǎo)引車(Automated Guided Vehicle，AGV)作為一種自動(dòng)化程度高、靈活性好、抗干擾能力強(qiáng)的移動(dòng)機(jī)器人，廣泛應(yīng)用于現(xiàn)代工業(yè)自動(dòng)化物流倉儲(chǔ)系統(tǒng)[1]。路徑規(guī)劃[2]是AGV調(diào)度系統(tǒng)研究和應(yīng)用的關(guān)鍵問題之一。一般而言，物流倉儲(chǔ)系統(tǒng)具有高效快速的運(yùn)輸需求，合理的路徑規(guī)劃方法對(duì)AGV能夠?qū)崿F(xiàn)有效、安全的自動(dòng)行駛具有重要作用。

常規(guī)AGV路徑規(guī)劃大多是以單個(gè)目標(biāo)作為尋優(yōu)目標(biāo)，如：時(shí)間最少、路徑最短、拐點(diǎn)最少或者目標(biāo)點(diǎn)全遍歷等。文獻(xiàn)[3]以路徑長度為優(yōu)化目標(biāo)，改進(jìn)蟻群算法的啟發(fā)因子及全局信息素分布方式，規(guī)劃AGV行駛路徑；而文獻(xiàn)[4]以最少轉(zhuǎn)折點(diǎn)為目標(biāo)，采用多方位搜索法，避免路徑轉(zhuǎn)折點(diǎn)過多導(dǎo)致AGV配送時(shí)間增加；文獻(xiàn)[5]以最短路徑長度為首要目標(biāo)進(jìn)行規(guī)劃，再從所得路徑中選取轉(zhuǎn)折點(diǎn)最少的作為最終路徑；文獻(xiàn)[6]則以最小化搬運(yùn)完成時(shí)間為目標(biāo)，定義了AGV沖突優(yōu)先級(jí)，提出一種生成無路徑?jīng)_突的規(guī)劃算法，提高AGV的作業(yè)效率。

隨著 “綠色物流”[7]的發(fā)展，基于單目標(biāo)函數(shù)的路徑規(guī)劃方法對(duì)于描述AGV路徑規(guī)劃問題具有一定局限性。除常見規(guī)劃目標(biāo)外，運(yùn)輸安全性、能源消耗等因素也被視為AGV運(yùn)行性能指標(biāo)，實(shí)際運(yùn)行時(shí)，這些因素之間相互影響、制約，存在互斥性，即一個(gè)目標(biāo)的優(yōu)化可能會(huì)導(dǎo)致其他目標(biāo)的退化。例如，最短路徑可能是AGV緊貼著障礙物以降低安全性為代價(jià)的路徑；最安全的路徑可能是拐點(diǎn)最多的路徑，會(huì)導(dǎo)致AGV行駛時(shí)間和能源成本增加。因此，以多個(gè)目標(biāo)作為物流倉儲(chǔ)系統(tǒng)路徑規(guī)劃的準(zhǔn)則，需綜合考慮多種因素的共同影響，實(shí)現(xiàn)AGV在多個(gè)目標(biāo)共同優(yōu)化作用下的自主路徑規(guī)劃。

本文綜合考慮物流倉儲(chǔ)系統(tǒng)路徑規(guī)劃的快速性、穩(wěn)定性和安全性需求，設(shè)計(jì)了一種基于改進(jìn)蟻群算法的AGV多目標(biāo)路徑規(guī)劃算法。首先，構(gòu)建子目標(biāo)函數(shù)，并采用熵權(quán)法確定子目標(biāo)權(quán)值以構(gòu)建路徑評(píng)價(jià)函數(shù)，以最小化評(píng)價(jià)函數(shù)值為總目標(biāo)搭建多目標(biāo)路徑規(guī)劃模型；然后，通過改進(jìn)蟻群柵格轉(zhuǎn)移方式及引入非支配排序算法，提高蟻群多目標(biāo)優(yōu)化能力；最后，基于仿真結(jié)果，證明了本文所設(shè)計(jì)的多目標(biāo)路徑規(guī)劃算法用于動(dòng)靜態(tài)地圖下AGV路徑規(guī)劃的可行性和有效性。

1 基于熵權(quán)法的AGV多目標(biāo)路徑規(guī)劃建模

考慮到物流倉儲(chǔ)環(huán)境的復(fù)雜性，路徑的低危險(xiǎn)率保證AGV在行駛過程中遠(yuǎn)離障礙物，減少與障礙物碰撞的可能性；更短的避障等待時(shí)間意味著AGV能更快的完成作業(yè)。因此，本文構(gòu)建AGV多目標(biāo)路徑規(guī)劃模型，綜合考慮路徑長度、轉(zhuǎn)角和、危險(xiǎn)率和避障等待時(shí)間作為AGV路徑規(guī)劃的子目標(biāo)，并采用熵權(quán)法確定子目標(biāo)權(quán)重。

1.1 各子目標(biāo)模型的建立

柵格法簡單高效、易于實(shí)現(xiàn)和表達(dá)不規(guī)則障礙物，本文采用柵格法[8]對(duì)倉儲(chǔ)環(huán)境進(jìn)行建模。描述如下：將AGV工作環(huán)境等分為a行a列個(gè)柵格，柵格大小能完全容納機(jī)器人。無障礙物柵格為可行柵格(白色表示)，有障礙物柵格為不可行柵格(黑色表示)，障礙物小于一柵格時(shí)，按一柵格處理。移動(dòng)機(jī)器人在柵格間的移動(dòng)可看作一個(gè)質(zhì)點(diǎn)，并假設(shè)每次都停留在柵格的中心位置。

(1)路徑長度

路徑長度最短能節(jié)約AGV工作時(shí)間及運(yùn)行成本。路徑長度子目標(biāo)函數(shù)f1如下：

(1)

式中，n表示路徑經(jīng)過的總節(jié)點(diǎn)數(shù)(包含起點(diǎn)和終點(diǎn))；xi、yi分別表示節(jié)點(diǎn)i的橫縱坐標(biāo)；L(i,i+1)為節(jié)點(diǎn)i、i+1之間的距離，如圖1所示。

圖1 路徑長度、轉(zhuǎn)角示意圖

(2)轉(zhuǎn)角和

AGV在轉(zhuǎn)彎時(shí)會(huì)減速以避免車速過大導(dǎo)致車體側(cè)翻或甩落所運(yùn)載的貨物。當(dāng)轉(zhuǎn)彎較多時(shí)，AGV頻繁的進(jìn)行減速控制，且轉(zhuǎn)角過大會(huì)增加低速運(yùn)行的時(shí)間。因此選擇轉(zhuǎn)角和作為規(guī)劃子目標(biāo)之一，對(duì)轉(zhuǎn)角和進(jìn)行有效約束能節(jié)約工作時(shí)間、減少轉(zhuǎn)彎導(dǎo)致的輪胎磨損等機(jī)械損耗。轉(zhuǎn)角和函數(shù)f2如下：

(2)

式中，θ(i,i+1,i+2)表示路徑轉(zhuǎn)角，如圖1所示。

(3)危險(xiǎn)率

AGV通過車載的導(dǎo)航傳感器實(shí)時(shí)定位并由環(huán)境傳感器感知周圍障礙物信息。由于傳感器自身精度缺陷易導(dǎo)致AGV所獲得的定位信息和環(huán)境信息間存在一定誤差，特別是距障礙過近時(shí)，測量誤差可能會(huì)造成AGV與障礙物間產(chǎn)生摩擦或碰撞。

AGV與障礙物距離越近，危險(xiǎn)率越高，當(dāng)AGV距離障礙物兩柵格以上時(shí)，受障礙物影響較小可忽略。危險(xiǎn)率函數(shù)f3如下：

(3)

其中，

式中，D(i)表示節(jié)點(diǎn)i處的危險(xiǎn)率；obj為離節(jié)點(diǎn)i最近的障礙物柵格中心。

(4)避障等待時(shí)間

當(dāng)AGV遇到動(dòng)態(tài)障礙物時(shí)，需暫停運(yùn)動(dòng)并等待障礙物離開。避障等待時(shí)間函數(shù)f4如下：

(4)

式中，b代表總避障次數(shù)，T(o)代表第o次避障等待時(shí)長。

1.2 多目標(biāo)路徑規(guī)劃模型的建立

(5)

理想值均取所有待評(píng)價(jià)路徑中該子目標(biāo)的最小值。

同時(shí)，采用曼哈頓距離描述各子目標(biāo)函數(shù)值與理想值間的接近程度。由式(1)～式(5)構(gòu)建AGV多目標(biāo)路徑規(guī)劃評(píng)價(jià)函數(shù)F為：

(6)

由此AGV多目標(biāo)路徑規(guī)劃模型為：

Y=minF

(7)

其中，Y為路徑規(guī)劃總目標(biāo),目的是求一條從起點(diǎn)到終點(diǎn)的連續(xù)無碰撞且評(píng)價(jià)函數(shù)值最低的路徑。

1.3 基于熵權(quán)法的評(píng)價(jià)函數(shù)權(quán)值確定

熵權(quán)法是客觀的權(quán)值計(jì)算方法，通過信息熵計(jì)算出各指標(biāo)的熵權(quán)，再利用熵權(quán)對(duì)權(quán)值進(jìn)行修正，與其它權(quán)值計(jì)算方法相比評(píng)價(jià)結(jié)果具有較好的客觀性[9]。考慮式(1)～式(4)所示子目標(biāo)對(duì)評(píng)價(jià)函數(shù)影響不完全相同，無法主觀衡量子目標(biāo)間的優(yōu)劣、占比程度，因此選用熵權(quán)法根據(jù)實(shí)際路徑信息計(jì)算式(6)中w1～w4的值，具體步驟如下：

步驟1：構(gòu)建原始數(shù)據(jù)矩陣。由m個(gè)待評(píng)價(jià)路徑，s(1≤s≤4)個(gè)子目標(biāo)構(gòu)成原始數(shù)據(jù)矩陣R′：

(8)

步驟2：標(biāo)準(zhǔn)化處理。旨在消除指標(biāo)間的量綱差異，記標(biāo)準(zhǔn)化處理后的矩陣R=(ruv)m×s。因路徑長度值、轉(zhuǎn)角和、危險(xiǎn)率、避障等待時(shí)間均越小越好，為負(fù)向指標(biāo)，則標(biāo)準(zhǔn)化處理公式為：

(9)

步驟3：計(jì)算第v個(gè)子目標(biāo)的熵值hv。

(10)

其中，

步驟4：確定各子目標(biāo)的權(quán)值大小。

(11)

2 改進(jìn)多目標(biāo)蟻群算法

傳統(tǒng)蟻群算法[10-12]主要對(duì)路徑長度進(jìn)行優(yōu)化，本文對(duì)蟻群算法做出改進(jìn)，將蟻群算法擴(kuò)展至多目標(biāo)函數(shù)優(yōu)化。

2.1 改進(jìn)螞蟻擇路方式

柵格地圖中蟻群運(yùn)動(dòng)可看成從當(dāng)前柵格中心向下一柵格中心轉(zhuǎn)移過程的積累。螞蟻的下一可轉(zhuǎn)移柵格是與當(dāng)前相鄰的八個(gè)柵格，標(biāo)號(hào)如圖2所示，偶數(shù)柵格表示直向轉(zhuǎn)移柵格，奇數(shù)柵格表示斜向轉(zhuǎn)移柵格。若AGV向3號(hào)或5號(hào)柵格轉(zhuǎn)移，可能出現(xiàn)AGV與障礙物柵格頂點(diǎn)摩擦或碰撞的情況，影響AGV正常運(yùn)行。對(duì)下一柵格選取方式改進(jìn)如下：

斜向擇路時(shí)，驗(yàn)證AGV當(dāng)前位置與下一斜向柵格中心連線的垂線上的兩個(gè)最近柵格是否有障礙物，若有，則將斜向柵格標(biāo)記為不可轉(zhuǎn)移柵格。如圖2所示，可將3號(hào)和5號(hào)柵格標(biāo)記為不可轉(zhuǎn)移柵格。

圖2 蟻群擇路柵格模型

2.2 改進(jìn)信息素播撒機(jī)制

由于信息素濃度只受路徑長度影響，其它子目標(biāo)對(duì)蟻群指引作用較小，蟻群多目標(biāo)尋優(yōu)能力不足。本文利用非支配排序算法對(duì)每次迭代的可行路徑分層，層數(shù)越靠前，表明該層路徑至少在一個(gè)或多個(gè)子目標(biāo)上很優(yōu)，給予該層中的路徑更多的信息素增量，從而使多個(gè)目標(biāo)共同指引蟻群尋優(yōu)。

非支配排序算法的核心思想便是支配比較。將路徑支配的概念描述如下：路徑A、B均為可行路徑，若A在某個(gè)子目標(biāo)上優(yōu)于B，且其余子目標(biāo)上均不弱于B(可以相等)，則稱路徑A支配路徑B；否則路徑A與B是非支配關(guān)系。由一系列不被其他路徑所支配的路徑組成最優(yōu)路徑集合。

利用非支配排序?qū)β窂椒謱樱襟E如下：

步驟1：每次迭代結(jié)束后，將可行路徑存入集合G中，并保存路徑子目標(biāo)函數(shù)值。

步驟2：對(duì)于G中的任一路徑p，都與其余路徑進(jìn)行支配關(guān)系比較，統(tǒng)計(jì)支配路徑p的路徑數(shù)目np、被p所支配的路徑集合Sp。若np=0，則表示路徑p不受其它任何路徑支配，將其分入T1層。

步驟3：對(duì)于T1中的路徑p，將Sp集合中的每一個(gè)成員q的支配計(jì)數(shù)nq減1。若nq=0，則表示路徑q除了受T1層路徑支配外，不再受其它路徑支配，將q分入T2層。

步驟4：依步驟3方式，將對(duì)應(yīng)路徑分入T3層。

步驟5：剩余路徑分入T4層。

劃分完畢后，有如下關(guān)系：同層路徑之間相互非支配；對(duì)Tl+1(l=1,2,3)層中的任一路徑，在Tl層中至少存在一條支配它的路徑。

前層路徑更優(yōu)，應(yīng)給與更多的信息素增量以加強(qiáng)對(duì)后續(xù)螞蟻的指引作用，同時(shí)弱化后層路徑信息素增量，改進(jìn)如下：

(12)

其中，

3 多目標(biāo)路徑規(guī)劃算法流程

綜上所述，本文所設(shè)計(jì)的基于改進(jìn)蟻群算法的多目標(biāo)路徑規(guī)劃步驟如下：

步驟1：采用柵格法對(duì)物流倉儲(chǔ)環(huán)境建模。

步驟2：確定子目標(biāo)函數(shù)及多目標(biāo)路徑規(guī)劃模型。

步驟3：初始化參數(shù)。初始化蟻群參數(shù)及最優(yōu)路徑集合Q，Q用于存放最優(yōu)路徑。

步驟4：蟻群迭代。開始此次迭代，依據(jù)改進(jìn)的螞蟻擇路方式確定可行柵格，利用輪盤賭法選出下一個(gè)節(jié)點(diǎn)，直至終點(diǎn)或螞蟻“死亡”。

步驟5：非支配排序。依據(jù)式(1)～式(4)計(jì)算可行路徑子目標(biāo)函數(shù)值。利用非支配排序算法對(duì)路徑分層。

步驟6：信息素更新。依據(jù)式(12)更新信息素。

步驟7：更新最優(yōu)路徑集合Q。對(duì)于排序后T1層中的路徑p，如果p對(duì)于集合Q來說是非支配的，則加入集合Q，并刪除Q中被p所支配的路徑。

步驟8：迭代次數(shù)更新。迭代次數(shù)d=d+1，當(dāng)?shù)螖?shù)最大時(shí)，結(jié)束迭代，否則返回步驟4。

步驟9：權(quán)值計(jì)算。輸出最優(yōu)路徑集合Q，利用熵權(quán)法計(jì)算子目標(biāo)權(quán)值。

步驟10：輸出最終路徑。依據(jù)式(6)計(jì)算路徑評(píng)價(jià)函數(shù)值，取最小評(píng)價(jià)值路徑為最終輸出路徑。

4 實(shí)驗(yàn)結(jié)果與分析

4.1 靜態(tài)環(huán)境下實(shí)驗(yàn)結(jié)果與分析

物流倉儲(chǔ)環(huán)境下貨物分布較為規(guī)整，構(gòu)建如圖3所示的柵格地圖，柵格行列數(shù)a=30；起點(diǎn)坐標(biāo)(0.5,0.5)，終點(diǎn)坐標(biāo)(29.5,29.5)。設(shè)置蟻群最大迭代次數(shù)Nmax=50，蟻群數(shù)量M=100。地圖中無動(dòng)態(tài)障礙物，暫不考慮避障等待。利用本文改進(jìn)多目標(biāo)蟻群算法得到最優(yōu)路徑集合Q，Q中的路徑如圖3所示，路徑信息如表1所示。

圖3 靜態(tài)環(huán)境改進(jìn)蟻群路徑圖

表1 靜態(tài)環(huán)境改進(jìn)蟻群路徑信息表

由圖3和表1可以看出，改進(jìn)的多目標(biāo)蟻群算法得到的路徑1～4分布范圍較廣，有沿著地圖中部斜向指向終點(diǎn)的路徑1、4，也有沿著地圖邊緣的路徑2、3，各路徑之間相互非支配，優(yōu)勢均不相同，路徑2轉(zhuǎn)角和最小，路徑3危險(xiǎn)率最低，路徑4長度最短，路徑1性能最均衡。

路徑1、4因?yàn)槎嘈毕蛐凶?，路徑長度較其它兩條路徑更小，但受地圖中心障礙物影響，轉(zhuǎn)角較多，平滑性較其它兩條路徑有所下降；同時(shí)，路徑2前半段緊貼障礙物，危險(xiǎn)率在4條路徑中最高。

上述結(jié)果表明：靜態(tài)環(huán)境下，本文改進(jìn)的蟻群算法對(duì)各子目標(biāo)均能有所優(yōu)化，能引導(dǎo)蟻群多目標(biāo)尋優(yōu)，實(shí)現(xiàn)AGV多目標(biāo)路徑規(guī)劃。

在相同的蟻群參數(shù)、柵格環(huán)境及擇路方式下，利用傳統(tǒng)蟻群算法尋路，結(jié)果如圖4所示，路徑信息如表2所示。

圖4 靜態(tài)環(huán)境傳統(tǒng)蟻群路徑圖

表2 靜態(tài)環(huán)境傳統(tǒng)蟻群路徑信息表

由于傳統(tǒng)蟻群算法中路徑長度對(duì)尋優(yōu)起主導(dǎo)作用，圖4中路徑5斜向行駛至終點(diǎn)。與改進(jìn)的多目標(biāo)蟻群算法路徑1～4相比：路徑5較路徑1在長度上減小了5.96%，轉(zhuǎn)角和增加了35.76%，危險(xiǎn)率增加了16.15%；較路徑2在長度上減小了9.84%，轉(zhuǎn)角和增加了137.5%，危險(xiǎn)率增加了5.59%；較路徑3在長度上減小了6.25%，轉(zhuǎn)角和增加了90.06%，危險(xiǎn)率增加了30.17%；較路徑4在長度上增加了1.13%，轉(zhuǎn)角和增加了5.59%，危險(xiǎn)率增加了16.15%。

可以看出，路徑5相比于改進(jìn)的多目標(biāo)蟻群算法路徑1～3，小幅縮短了路徑長度，但是轉(zhuǎn)角和、危險(xiǎn)率上都有所上漲，路徑5在提升路徑長度的同時(shí)，損失了路徑的平滑性和安全性；且路徑5各方面性能均比路徑4差。

利用熵權(quán)法對(duì)5條路徑的信息進(jìn)行計(jì)算，得到各子目標(biāo)權(quán)值如表3所示，最終評(píng)價(jià)函數(shù)值如表4所示。

表3 靜態(tài)環(huán)境子目標(biāo)權(quán)值表

表4 靜態(tài)環(huán)境評(píng)價(jià)函數(shù)值表

從表4可以看出，較傳統(tǒng)蟻群算法路徑5，路徑1～4的評(píng)價(jià)函數(shù)值更小，路徑更優(yōu)，且路徑3評(píng)價(jià)函數(shù)值最小，僅為1.85，最趨近于理想值，為靜態(tài)環(huán)境下的最優(yōu)路徑?？傻贸觯o態(tài)環(huán)境下，本文改進(jìn)的蟻群算法能進(jìn)行有效的多目標(biāo)路徑尋優(yōu)，較傳統(tǒng)蟻群算法所得路徑綜合性能更優(yōu)。

4.2 動(dòng)態(tài)環(huán)境下實(shí)驗(yàn)結(jié)果與分析

物流倉儲(chǔ)環(huán)境中可能出現(xiàn)人員走動(dòng)、貨物擺放位置臨時(shí)改變等動(dòng)態(tài)情況，在上述靜態(tài)環(huán)境中添加動(dòng)態(tài)障礙物以研究本文改進(jìn)蟻群算法所得路徑在動(dòng)態(tài)環(huán)境中的適應(yīng)能力。為方便研究，對(duì)動(dòng)態(tài)障礙物作如下設(shè)計(jì)：在如圖5所示的每個(gè)黃色方框內(nèi)隨機(jī)產(chǎn)生一個(gè)動(dòng)態(tài)障礙物；其大小能被1柵格完全容納；動(dòng)態(tài)障礙物活動(dòng)范圍即為黃色方框區(qū)域；動(dòng)態(tài)障礙物隨機(jī)產(chǎn)生，沿水平方向勻速直線運(yùn)動(dòng)，觸碰到活動(dòng)邊界時(shí)沿鏡面反射方向折返。

圖5 動(dòng)態(tài)障礙物活動(dòng)范圍圖

AGV分別沿路徑1～5前進(jìn)，每次避障等待時(shí)間為5 s。最終各子目標(biāo)信息如表5所示。

表5 動(dòng)態(tài)環(huán)境路徑信息表

從表5可得，路徑1、2、5均遭遇一次動(dòng)態(tài)障礙物，進(jìn)行了一次避障等待，路徑4避障2次，路徑3避障0次。權(quán)值計(jì)算如表6所示，路徑評(píng)價(jià)值如表7所示。

表6 動(dòng)態(tài)環(huán)境子目標(biāo)權(quán)值表

表7 動(dòng)態(tài)環(huán)境評(píng)價(jià)函數(shù)值表

由表7可以看出，路徑3評(píng)價(jià)值為1.48，最趨近于理想值路徑，為最優(yōu)路徑；傳統(tǒng)蟻群算法所得的路徑5評(píng)價(jià)值最大，路徑綜合性能最差。路徑4雖然比路徑5多一次避障等待，但評(píng)價(jià)值較路徑5更低，路徑更優(yōu)。可以得出，若地圖中出現(xiàn)了少量動(dòng)態(tài)障礙物，本文改進(jìn)的多目標(biāo)蟻群算法所得路徑仍然具有更強(qiáng)的適應(yīng)性，且其綜合性能、整體評(píng)價(jià)較傳統(tǒng)蟻群路徑更優(yōu)。

5 結(jié)論

根據(jù)AGV運(yùn)行需求選取子目標(biāo)，提出一種基于改進(jìn)蟻群算法的AGV多目標(biāo)路徑規(guī)劃方法，該方法改變柵格選取方式、利用非支配排序算法改進(jìn)信息素增量、利用熵權(quán)法確定權(quán)值。仿真結(jié)果表明動(dòng)靜態(tài)環(huán)境下本文設(shè)計(jì)算法能有效進(jìn)行多目標(biāo)路徑尋優(yōu)，所得路徑分布廣、性能高，綜合評(píng)價(jià)更優(yōu)。