基于改進(jìn)蟻群算法的多AGV泊車(chē)路徑規(guī)劃

郭保青，郝樹(shù)運(yùn)，朱力強(qiáng),b，余祖俊,b

(北京交通大學(xué)a.機(jī)械與電子控制工程學(xué)院；b.載運(yùn)工具先進(jìn)制造與測(cè)控技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京100044)

0 引言

隨著我國(guó)汽車(chē)保有量快速增長(zhǎng)，城市交通擁堵、停車(chē)難等社會(huì)問(wèn)題日益突顯，嚴(yán)重影響了人們的出行質(zhì)量.為解決停車(chē)難問(wèn)題，新技術(shù)不斷涌現(xiàn)，其中基于AGV的平面智能停車(chē)庫(kù)以占地面積少、存車(chē)數(shù)量多、車(chē)輛存取自動(dòng)化程度高等優(yōu)點(diǎn)倍受關(guān)注.

AGV存取車(chē)輛的路徑規(guī)劃是研究平面智能停車(chē)庫(kù)的核心，其任務(wù)是為每臺(tái)AGV從預(yù)存停車(chē)位到目標(biāo)停車(chē)位尋找一條最優(yōu)無(wú)碰路徑，有序完成所有路徑規(guī)劃任務(wù).近年來(lái)，國(guó)內(nèi)外學(xué)者針對(duì)路徑規(guī)劃問(wèn)題做了大量研究.文獻(xiàn)[1]采用雙層模糊邏輯路徑規(guī)劃算法，考慮障礙物距離信息與目標(biāo)角度信息，通過(guò)改變速度提高避碰效率，但不能保證為多機(jī)器人規(guī)劃出全局最優(yōu)路徑；文獻(xiàn)[2]采用多人工魚(yú)群算法在靜態(tài)環(huán)境中規(guī)劃出較優(yōu)路徑，根據(jù)避碰規(guī)則庫(kù)實(shí)現(xiàn)與動(dòng)態(tài)障礙的避碰；文獻(xiàn)[3]提出結(jié)合AGV路徑容量、安全距離的多參數(shù)優(yōu)化控制模型，通過(guò)改進(jìn)的速度控制策略解決沖突.蟻群算法是一種新型仿生算法，憑借并行性、強(qiáng)魯棒性、全局最優(yōu)等優(yōu)點(diǎn)[4]廣泛應(yīng)用于路徑規(guī)劃問(wèn)題[5-7].許多學(xué)者對(duì)基本蟻群算法進(jìn)行了優(yōu)化，文獻(xiàn)[8]將蟻群算法與遺傳算法融合，在蟻群算法中引入改進(jìn)的交叉算子來(lái)避免陷入局部最優(yōu)；文獻(xiàn)[9]提出基于勢(shì)場(chǎng)優(yōu)化的蟻群路徑規(guī)劃算法，用勢(shì)場(chǎng)法路徑預(yù)規(guī)劃獲得的先驗(yàn)知識(shí)構(gòu)造信息素矩陣，采用參數(shù)自適應(yīng)的偽隨機(jī)轉(zhuǎn)移策略?xún)?yōu)化蟻群算法；文獻(xiàn)[10]利用人工勢(shì)場(chǎng)法重構(gòu)啟發(fā)函數(shù)提出的改進(jìn)勢(shì)場(chǎng)蟻群算法收斂速度較快，但容易陷入局部最優(yōu).

針對(duì)基本蟻群算法容易陷入局部最優(yōu)和收斂性差的問(wèn)題，本文提出適用于多AGV路徑規(guī)劃的改進(jìn)蟻群算法.本文根據(jù)典型地下停車(chē)庫(kù)抽象拓?fù)淠Ｐ?，引入螞蟻回退策略?lái)增強(qiáng)算法魯棒性，通過(guò)改進(jìn)啟發(fā)式信息和信息素更新策略提高全局尋優(yōu)能力.針對(duì)多AGV沖突問(wèn)題，通過(guò)改進(jìn)沖突解決策略進(jìn)行局部避碰.仿真結(jié)果驗(yàn)證了單AGV情況下改進(jìn)蟻群算法的性能，并在此基礎(chǔ)上完成了多AGV路徑規(guī)劃算法效率和實(shí)時(shí)性的驗(yàn)證.

1 問(wèn)題分析及環(huán)境建模

典型地下停車(chē)庫(kù)一般分開(kāi)設(shè)置出入口，由于受建筑附屬設(shè)施影響，部分車(chē)位位于非連通路的端點(diǎn)，即存在部分“死路”.為提高吞吐效率，AGV智能停車(chē)場(chǎng)可將所有出入口規(guī)劃為同時(shí)出入；為增加停車(chē)面積，可將AGV行駛路徑規(guī)劃為雙向單車(chē)道，同時(shí)只允許一個(gè)方向的AGV通行.改造后的AGV停車(chē)場(chǎng)一般具有如下典型特征：

(1)有兩個(gè)同時(shí)出入的出入口；

(2)通道為雙向單車(chē)道，允許多臺(tái)AGV同向行駛，但同時(shí)只能有一個(gè)方向的AGV通行；

(3)有大量位于非連通路端點(diǎn)的車(chē)位；

(4)規(guī)劃的路徑起點(diǎn)或終點(diǎn)必然包含一個(gè)出入口；

(5)各AGV被視為質(zhì)點(diǎn)，每臺(tái)AGV設(shè)有相應(yīng)安全區(qū)域，行駛速度相同，轉(zhuǎn)彎耗時(shí)為常數(shù).

基于以上特征，采用拓?fù)浞▽?duì)某典型地下停車(chē)庫(kù)抽象的AGV停車(chē)庫(kù)模型如圖1所示.該模型由節(jié)點(diǎn)和線段組成，圓節(jié)點(diǎn)代表交叉路口或路徑端點(diǎn)，矩形節(jié)點(diǎn)代表出入口，線段表示停車(chē)庫(kù)中的路徑，虛線為停車(chē)場(chǎng)邊界.AGV運(yùn)行路徑采用有序節(jié)點(diǎn)集合表示，節(jié)點(diǎn)順序表示運(yùn)行方向.多AGV泊車(chē)路徑規(guī)劃既要保證各AGV互不沖突，又要使每臺(tái)AGV行駛時(shí)間最短.

圖1 AGV車(chē)庫(kù)拓?fù)鋱DFig.1 Topological graph of AGV garage

2 基于改進(jìn)蟻群算法的AGV路徑規(guī)劃

2.1 基本蟻群算法

蟻群算法是一種典型的路徑規(guī)劃算法，主要依靠螞蟻之間的信息傳遞來(lái)尋找最優(yōu)路徑.尋路過(guò)程中，螞蟻通過(guò)感知環(huán)境信息，并按照既定規(guī)則來(lái)規(guī)劃路徑，最終以一定的評(píng)價(jià)指標(biāo)找到起止點(diǎn)間的最優(yōu)路徑.

(1)轉(zhuǎn)移概率.

一般情況下，周?chē)h(huán)境是未知的，螞蟻需要根據(jù)轉(zhuǎn)移概率Pij來(lái)確定下一步要走的路徑.設(shè)螞蟻數(shù)量為M，位于節(jié)點(diǎn)i處的螞蟻m(m=1,2,…,M)在t時(shí)刻選擇節(jié)點(diǎn)j的概率為

式中：τij(t)為t時(shí)刻路徑(i,j)上的信息素濃度；ηij(t)為路徑(i,j)在t時(shí)刻的啟發(fā)式信息強(qiáng)度，通常ηij=1/dij，dij為節(jié)點(diǎn)i,j間的距離；α，β分別為信息素濃度和啟發(fā)式信息強(qiáng)度的影響權(quán)重；allowed為下一步允許選擇的節(jié)點(diǎn)集合.

(2)信息素更新.

螞蟻經(jīng)過(guò)路徑時(shí)會(huì)留下信息素，隨著時(shí)間推移，信息素會(huì)逐漸揮發(fā)消逝.每代螞蟻完成路徑搜索后，會(huì)按式(2)～式(4)更新信息素.

式中：ρ為信息素?fù)]發(fā)系數(shù)；Δτij(t,t+1)為本次循環(huán)中路徑(i,j)上的信息素增量；Mij為本次循環(huán)中經(jīng)過(guò)路徑(i,j)的螞蟻集合；為第m只螞蟻在路徑(i,j)上產(chǎn)生的信息素增量；Lm為第m只螞蟻在本次循環(huán)中搜索的路徑長(zhǎng)度；Q為常數(shù).

2.2 改進(jìn)蟻群算法

(1)螞蟻回退策略.

螞蟻在搜索路徑時(shí)總是以所處節(jié)點(diǎn)為中心選擇下一節(jié)點(diǎn).由于AGV運(yùn)行環(huán)境有較多不連通路徑，螞蟻在搜索路徑時(shí)可能陷入其中而導(dǎo)致搜索異常終止.為避免此類(lèi)情況，加入螞蟻回退策略來(lái)提高算法魯棒性.如圖2所示，螞蟻搜索從S點(diǎn)到E點(diǎn)的路徑，在搜索過(guò)程中陷入D點(diǎn)，此時(shí)螞蟻未完成路徑搜索而又無(wú)法找到下一節(jié)點(diǎn)，于是采取回退策略將螞蟻置于前一節(jié)點(diǎn)F，并更新禁忌表，使此輪螞蟻無(wú)法再搜索到D點(diǎn).

圖2 螞蟻回退策略示意圖Fig.2 Schematic diagram of fallback strategy

(2)啟發(fā)式信息.

在基本蟻群算法中，螞蟻在搜索路徑時(shí)是以所處節(jié)點(diǎn)與相鄰節(jié)點(diǎn)距離的倒數(shù)為啟發(fā)式信息，路徑搜索盲目性較大.為提高算法尋路速度，本文以螞蟻所處節(jié)點(diǎn)與終點(diǎn)距離的倒數(shù)作為啟發(fā)式信息，提高螞蟻對(duì)終點(diǎn)的可見(jiàn)度，如式(5)所示.

式中：E代表終點(diǎn)；P代表螞蟻所處節(jié)點(diǎn).

(3)信息素更新.

基本蟻群算法搜索路徑時(shí)受非最優(yōu)路徑信息素的干擾可能陷入局部最優(yōu).針對(duì)此問(wèn)題，本文以原有信息素更新策略為基礎(chǔ)，對(duì)每次迭代的最優(yōu)路徑釋放更多信息素，對(duì)最差路徑減少部分信息素.改進(jìn)的信息素更新公式為

式中：Nb和Nw分別為經(jīng)過(guò)本次迭代最優(yōu)和最差路徑的螞蟻數(shù)量；Lb和Lw分別為本次迭代最優(yōu)和最差路徑的路徑長(zhǎng)度.

3 改進(jìn)AGV沖突解決策略

3.1 AGV沖突類(lèi)型

多AGV路徑規(guī)劃是要保證在系統(tǒng)無(wú)沖突情況下為每臺(tái)AGV規(guī)劃出1條最優(yōu)路徑，根據(jù)前面模型，多AGV運(yùn)行過(guò)程中會(huì)出現(xiàn)圖3所示的幾種沖突情況.

圖3 AGV沖突情況Fig.3 AGV conflict situation

圖3(a)中2臺(tái)AGV同時(shí)到達(dá)同一節(jié)點(diǎn)，又分別駛向不同的方向，2臺(tái)AGV會(huì)在節(jié)點(diǎn)處發(fā)生碰撞，稱(chēng)為節(jié)點(diǎn)沖突.

圖3(b)中，若 AGV1的速度大于 AGV2，AGV1會(huì)在運(yùn)行過(guò)程中撞到AGV2，稱(chēng)為趕超沖突.

圖3(c)和圖3(d)中2臺(tái)AGV相向行駛并發(fā)生碰撞，稱(chēng)為相向沖突.

3.2 改進(jìn)AGV沖突解決策略

為避免上述沖突，需要制定沖突解決策略.當(dāng)AGV按照各自預(yù)定路徑行駛而遇到?jīng)_突時(shí)，采用對(duì)應(yīng)策略協(xié)調(diào)各自的運(yùn)動(dòng).

(1)停車(chē)等待策略.

對(duì)于節(jié)點(diǎn)沖突及趕超沖突，采用停車(chē)等待策略進(jìn)行解決.當(dāng)發(fā)生沖突時(shí)，1臺(tái)AGV停車(chē)等待，而另一臺(tái)AGV繼續(xù)行駛.而針對(duì)不同沖突，解決方法稍有不同：

對(duì)節(jié)點(diǎn)沖突，可通過(guò)規(guī)定優(yōu)先級(jí)來(lái)解決，當(dāng)多臺(tái)AGV同時(shí)到達(dá)同一節(jié)點(diǎn)時(shí)，優(yōu)先級(jí)高的AGV優(yōu)先通過(guò).

對(duì)趕超沖突，可通過(guò)設(shè)定安全距離來(lái)解決，當(dāng)后方與前方AGV距離小于安全距離時(shí)，后方AGV暫停行駛.

(2)臨時(shí)規(guī)避—重新尋路策略.

對(duì)相向沖突，除避碰問(wèn)題外還要考慮沖突解決的合理性.傳統(tǒng)的重新尋路算法雖能解決相向沖突，但在某些情況下嚴(yán)重影響任務(wù)完成效率，甚至?xí)鹦碌暮罄m(xù)沖突.

為彌補(bǔ)重新尋路算法的不足，本文提出臨時(shí)規(guī)避—重新尋路策略來(lái)解決相向沖突.當(dāng)AGV到達(dá)某一節(jié)點(diǎn)且要行走的下一路徑存在與之相向沖突的AGV時(shí)，當(dāng)前AGV根據(jù)不同情況選擇臨時(shí)規(guī)避或重新規(guī)劃該節(jié)點(diǎn)到終點(diǎn)的路徑.若AGV所處節(jié)點(diǎn)路口數(shù)大于2，且AGV臨時(shí)規(guī)避的等待時(shí)間與原剩余路徑的運(yùn)行時(shí)間之和小于重新規(guī)劃路徑上的運(yùn)行時(shí)間，則選擇臨時(shí)規(guī)避措施；否則，選擇重新規(guī)劃該節(jié)點(diǎn)到終點(diǎn)的路徑.臨時(shí)規(guī)避—重新尋路策略流程如圖4所示.

圖4 臨時(shí)規(guī)避—重新尋路策略流程Fig.4 Temporary avoidance and re-planning strategy flow chart

4 仿真實(shí)驗(yàn)

4.1 單AGV路徑規(guī)劃仿真

(1)主要參數(shù)優(yōu)化.

目前蟻群算法一般通過(guò)經(jīng)驗(yàn)選取參數(shù)，本文通過(guò)在參數(shù)變化范圍內(nèi)設(shè)置不同的參數(shù)組合，并對(duì)每個(gè)參數(shù)進(jìn)行10次仿真，將求得的路徑長(zhǎng)度均值進(jìn)行對(duì)比來(lái)選取最優(yōu)參數(shù).主要測(cè)試參數(shù)為：α∈{0 .0,0.5,1.0,2.0,5.0},β∈{0,5,8,10,15},ρ∈{0.0,0.3,0.5,0.8,1.0} ，其中默認(rèn)值設(shè)為α=1.0，β=10，ρ=0.5，每次實(shí)驗(yàn)只改變1個(gè)參數(shù)，其余為默認(rèn)值，結(jié)果如表1所示.

表1 參數(shù)優(yōu)化結(jié)果Table 1 Parameter optimization result

由表1可以看出：α最優(yōu)值在1.0附近，β最優(yōu)值在10附近，ρ對(duì)算法影響較小，在0.8附近最優(yōu).基于以上結(jié)果，本文對(duì)基本蟻群算法和改進(jìn)蟻群算法進(jìn)行仿真測(cè)試時(shí)，各參數(shù)設(shè)置如下：迭代次數(shù)k=100，螞蟻數(shù)量M=50，α=1.0，β=10，ρ=0.8.

(2)尋路成功率對(duì)比.

由于不連通路徑會(huì)導(dǎo)致尋路失敗，可以通過(guò)尋路成功率來(lái)比較算法性能.圖1拓?fù)鋱D共有46個(gè)節(jié)點(diǎn)，其中2個(gè)為出入口，44個(gè)為交叉路口或路徑端點(diǎn).現(xiàn)分別以2個(gè)出入口為AGV任務(wù)的起點(diǎn)或終點(diǎn)，44個(gè)節(jié)點(diǎn)分別為另一點(diǎn)，對(duì)比兩種算法的尋路成功率，結(jié)果如表2所示，其中尋路成功率計(jì)算公式為

表2 尋路成功率比較Table 2 Comparison of path finding success rate

表2基本蟻群算法中，以S1分別為起點(diǎn)和終點(diǎn)的尋路成功率為59%和64%；以S2分別為起點(diǎn)和終點(diǎn)的尋路成功率為64%和70%.而無(wú)論何種情況，改進(jìn)蟻群算法的尋路成功率均為100%.由此可見(jiàn)，改進(jìn)蟻群算法有較高的魯棒性.

(3)尋路質(zhì)量及算法收斂性比較.

為了全面客觀地驗(yàn)證改進(jìn)蟻群算法的性能，本文在基本蟻群算法中加入回退策略(稱(chēng)為回退蟻群算法)，與改進(jìn)蟻群算法進(jìn)行尋路質(zhì)量及算法收斂性比較.本文通過(guò)在停車(chē)庫(kù)隨機(jī)選取3個(gè)內(nèi)部節(jié)點(diǎn)與出入口組成3組路徑任務(wù)進(jìn)行仿真.圖5為兩種算法得到的最終路徑和平均路徑長(zhǎng)度收斂曲線，實(shí)線和虛線分別代表回退蟻群算法和改進(jìn)蟻群算法.表3列出了兩種算法得到的具體路徑數(shù)據(jù)和算法耗時(shí)，由圖5及表3可以看出改進(jìn)蟻群算法得到的路徑更短，收斂速度更快.

表3 尋路質(zhì)量及算法收斂性比較Table 3 Comparison of path quality and algorithm convergence

(4)算法復(fù)雜度分析.

算法復(fù)雜度主要包括時(shí)間和空間復(fù)雜度.時(shí)間復(fù)雜度是指算法執(zhí)行基本操作的次數(shù)，由于本文對(duì)蟻群算法的改進(jìn)主要在啟發(fā)式信息、信息素更新和增加回退及避碰策略上，改進(jìn)和基本蟻群算法在時(shí)間復(fù)雜度上都為T(mén)(n)=O(k?n2?M)，具有相同的量級(jí).因此，本文采用算法編譯運(yùn)行時(shí)間來(lái)評(píng)估算法時(shí)間復(fù)雜度，由表3的耗時(shí)可以看出，改進(jìn)算法有較高的執(zhí)行效率.

空間復(fù)雜度是指算法執(zhí)行時(shí)間內(nèi)占用的存儲(chǔ)單元.改進(jìn)算法中的數(shù)據(jù)包括用來(lái)描述問(wèn)題和實(shí)現(xiàn)算法功能的輔助數(shù)據(jù)，空間復(fù)雜度為S(n)=O(n2)+O(n?M).實(shí)際應(yīng)用中，停車(chē)場(chǎng)環(huán)境信息使用數(shù)據(jù)文件存儲(chǔ)，數(shù)據(jù)格式非常簡(jiǎn)單，占用存儲(chǔ)空間很少，空間復(fù)雜度很低.

圖5 路徑任務(wù)和算法收斂曲線Fig.5 Pathing task and algorithm convergence curve

4.2 多AGV路徑規(guī)劃仿真

將改進(jìn)沖突解決策略與沖突判別條件相結(jié)合編制成多AGV路徑規(guī)劃算法.為了驗(yàn)證算法性能，本文以相向沖突為例對(duì)3個(gè)AGV進(jìn)行仿真，并與重新尋路算法進(jìn)行比較.仿真前，用改進(jìn)蟻群算法為每臺(tái)AGV規(guī)劃出起止點(diǎn)間的最優(yōu)路徑.為方便觀察路徑?jīng)_突情況，以時(shí)間窗來(lái)表示AGV路徑占用情況.設(shè)AGV同時(shí)從各自起點(diǎn)開(kāi)始行駛，仿真結(jié)果如圖6所示.

圖6結(jié)果分別表示避碰前、重新尋路和本文避碰算法3種情況下3臺(tái)AGV的路徑圖及對(duì)應(yīng)時(shí)間窗，其中AGV1運(yùn)行在1→17的路徑上，AGV2運(yùn)行在40→2的路徑上，AGV3運(yùn)行在2→43的路徑上.圖6中，初始路徑在(28,29)上發(fā)生相向沖突；為避免沖突，重新尋路算法以節(jié)點(diǎn)29為起點(diǎn)重新規(guī)劃到終點(diǎn)的剩余路徑；本文算法則將AGV2臨時(shí)?？吭诼窂?29,30)且靠近節(jié)點(diǎn)29的29(P)位置.3種方法的對(duì)比如表4所示，原始路徑由于存在相向沖突，無(wú)法完成相應(yīng)任務(wù)，故表4中任務(wù)時(shí)間和算法耗時(shí)均為空；重新尋優(yōu)算法雖然能夠?qū)崿F(xiàn)沖突后路經(jīng)的重新規(guī)劃，但任務(wù)時(shí)間較長(zhǎng)；而本文算法在任務(wù)完成時(shí)間和算法耗時(shí)上都由于重新尋優(yōu)算法，不僅能有效避免沖突，規(guī)劃的新路徑也更合理，算法效率更高.

表4 多AGV路徑規(guī)劃算法性能比較Table 4 Multi-AGV path planning algorithm performance comparison

圖6 多AGV路徑及時(shí)間窗Fig.6 Multi-AGV path and time windows diagram

5 結(jié) 論

針對(duì)智能停車(chē)庫(kù)多AGV泊車(chē)路徑規(guī)劃問(wèn)題，本文提出了基于改進(jìn)蟻群算法的多AGV泊車(chē)路徑規(guī)劃算法.仿真實(shí)驗(yàn)表明，本文算法在效率和性能上相比基本蟻群算法均有提高，不僅能為單AGV規(guī)劃出1條無(wú)碰優(yōu)化路徑，而且能在多AGV同時(shí)運(yùn)行的情況下避免沖突，滿(mǎn)足AGV存取車(chē)路徑規(guī)劃的需要.下一步計(jì)劃在此基礎(chǔ)上研究停車(chē)位優(yōu)化布局方法和AGV數(shù)量與停車(chē)效率的關(guān)系，為智能AGV停車(chē)場(chǎng)設(shè)計(jì)提供指導(dǎo).