張 碩，錢曉明，樓佩煌，武 星，孫 超

(南京航空航天大學(xué) 機(jī)電學(xué)院,江蘇 南京 210016)

0 引言

隨著現(xiàn)代工業(yè)快速發(fā)展，應(yīng)用于智能物流的自動導(dǎo)引小車(Automated Guided Vehicle, AGV)系統(tǒng)已經(jīng)廣泛應(yīng)用于生產(chǎn)制造業(yè)中[1]。以我國某省電能計量器具檢定為例，按照國家規(guī)定，由不同電表生產(chǎn)廠家生產(chǎn)的不同型號的電表在投入實(shí)際使用之前，需要統(tǒng)一在國家電網(wǎng)的省級檢定中心進(jìn)行全檢。特別是近年來，隨著國家智能電網(wǎng)建設(shè)的不斷推進(jìn)，智能電能表每年的檢定量超過千萬只，如此龐大的電能表持續(xù)需求對電表計量檢定的自動化、智能化和信息化提出了更高的要求[2]。電表檢定包括存儲、無人搬運(yùn)、檢定等一系列復(fù)雜環(huán)節(jié)[3]，搬運(yùn)和檢定環(huán)節(jié)集中在自動化無人電表檢定車間中進(jìn)行，檢定中心放置了大量的電表檢定臺體，用以執(zhí)行電表的檢定過程。作為其中搬運(yùn)環(huán)節(jié)的關(guān)鍵載體，AGV因其路徑柔性、能夠有效地提高運(yùn)輸電表的效率，而承擔(dān)了檢定車間中電表在上下垛口與檢定臺體之間運(yùn)輸?shù)娜蝿?wù)。為了應(yīng)對如此龐大的電表檢定任務(wù)量，需要配備多臺AGV共同工作，上位機(jī)系統(tǒng)根據(jù)車間電表檢定狀況，實(shí)時為待檢定電表指派合適的檢定臺體，使用AGV搬運(yùn)電表。這樣一來，大量的電表檢定量和檢定臺體使得檢定車間中多個AGV需要在檢定臺體之間、檢定臺體與上下垛口之間不斷地穿梭運(yùn)動，構(gòu)成了大規(guī)模的AGV運(yùn)輸場景。

路徑規(guī)劃技術(shù)是AGV運(yùn)輸中最關(guān)鍵的問題，即尋找一條從起點(diǎn)到終點(diǎn)的最短路徑，并且需要避開障礙物[4]。傳統(tǒng)的路徑規(guī)劃方法如可視圖法、自由空間法、人工勢場法等，其在較為簡單的路徑規(guī)劃問題上表現(xiàn)優(yōu)秀，往往能找到全局最優(yōu)解，一旦涉及復(fù)雜的場景，傳統(tǒng)方法求解起來費(fèi)時費(fèi)力、成本高且效率低下，難以在可接受的計算時間內(nèi)求解出近似最優(yōu)解，因此智能優(yōu)化算法應(yīng)運(yùn)而生，能在可接受時間內(nèi)求解路徑規(guī)劃問題。針對該問題，國內(nèi)外學(xué)者們提出了很多應(yīng)用在路徑規(guī)劃中的相關(guān)智能求解算法。Liu等[5]基于網(wǎng)格地圖，針對蟻群算法收斂速度問題提出了改進(jìn)的蟻群優(yōu)化算法；Li等[6]提出一種基于遺傳算法重構(gòu)的移動機(jī)器人路徑規(guī)劃算法；Saidi-Mehrabad等[7]提出一種兩階段蟻群算法；Kuo等[8]提出一種改進(jìn)的模糊蟻群系統(tǒng)算法求解路徑；He等[9]通過構(gòu)建MAKLINK無向路徑網(wǎng)絡(luò)以及優(yōu)化蟻群算法中啟發(fā)函數(shù)使AGV路徑達(dá)到全局最優(yōu)路徑，且具有避障的能力。Teymourian等[10]采用局部搜索混合算法和后優(yōu)化混合算法這兩種混合元啟發(fā)式算法，并且進(jìn)一步融合了智能水滴算法和先進(jìn)布谷鳥搜索算法，綜合算法提高了路徑求解的性能；Xiao等[11]對擴(kuò)展布谷鳥搜索算法進(jìn)行調(diào)整用以求解路徑問題；Osaba等[12]提出一種離散演化的螢火蟲算法(Evolutionary Discrete version of the Firefly Algorithm，EDFA)對路徑進(jìn)行求解。這些新興的智能算法易于實(shí)現(xiàn)、代價不高，克服了傳統(tǒng)算法在復(fù)雜場景問題下不易實(shí)現(xiàn)的缺陷，已經(jīng)成功應(yīng)用在各種復(fù)雜應(yīng)用場合的優(yōu)化問題上。如，Khan等[13]提出結(jié)合AGV的蟻群算法及其變體，實(shí)現(xiàn)智能交通管理。Yang等[14]基于擁塞預(yù)防規(guī)則的雙層遺傳算法對自動化集裝箱碼頭的碼頭起重機(jī)、自動導(dǎo)引車、堆場起重機(jī)進(jìn)行了綜合路徑調(diào)度。

粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法是一種群智能算法，屬于新興的演化計算方法，該方法模擬自然界的生物活動規(guī)律，具備仿生的、隨機(jī)的概率搜索方式，通過群體中的協(xié)作機(jī)制尋找最優(yōu)解，一經(jīng)提出便受到學(xué)術(shù)界的廣泛關(guān)注，具有求解速度快，參數(shù)調(diào)整較少的特點(diǎn)。大規(guī)模AGV路徑規(guī)劃問題復(fù)雜度高，是一種NP-Hard問題，無法在多項(xiàng)式時間內(nèi)求出問題的最優(yōu)解，而PSO算法對于這類NP-Hard優(yōu)化問題已被證明具有很強(qiáng)的處理能力，因此已有學(xué)者針對AGV路徑規(guī)劃問題采用PSO算法來求解，目前的研究大部分集中在參數(shù)改進(jìn)、粒子二進(jìn)制編碼、算法公式改進(jìn)以及與其他智能算法的混合等。如Song等[15]提出一種新的多模態(tài)延遲粒子群優(yōu)化算法，為了減少局部陷阱現(xiàn)象的發(fā)生并擴(kuò)大搜索空間，將多模態(tài)延遲信息添加到速度更新模型中；Mandava等[16]提出PSO算法與靜態(tài)障礙物的勢場法和動態(tài)障礙物的勢場法預(yù)測相結(jié)合的路徑規(guī)劃算法；Sadiq等[17]提出了基于D*算法和PSO算法的動態(tài)環(huán)境下的路徑規(guī)劃方法；JIA等[18]提出基于按三角函數(shù)變化的慣性權(quán)重因子和加速因子自適應(yīng)調(diào)整的改進(jìn)PSO的路徑規(guī)劃。分析上述文獻(xiàn)可以看出，路徑規(guī)劃求解算法眾多，但總體趨勢是混合多種算法或?qū)A(chǔ)算法進(jìn)行變種，通常在算例部分采用測試數(shù)據(jù)集，實(shí)際應(yīng)用不廣泛，缺少對大規(guī)模運(yùn)輸實(shí)際應(yīng)用場景下路徑規(guī)劃的研究。

目前，在路徑規(guī)劃問題中，PSO算法的表現(xiàn)依然不盡如人意，算法前期求解速度較慢、粒子群多樣性迅速降低、全局搜索能力不足且容易陷入局部最優(yōu)值，從而導(dǎo)致不能得到最優(yōu)的規(guī)劃路徑。為了克服這些缺陷，文獻(xiàn)[18]提出的方法在一定程度上緩解了粒子群多樣性迅速降低導(dǎo)致全局搜索能力不足的問題，在后期加快了求解速度。本文針對智能車間中的AGV路徑優(yōu)化這一研究對象，特別是結(jié)合車間應(yīng)用實(shí)際，采用改進(jìn)粒子群算法進(jìn)行路徑優(yōu)化求解，基于文獻(xiàn)[18]所提出的改進(jìn)粒子群算法(ωandcParticle Swarm Optimization,WCPSO)，并考慮到傳統(tǒng)的粒子初始化方式具有的盲目性問題和算法更新過程，結(jié)合AGV地圖環(huán)境提出了新的粒子群初始化方式和適應(yīng)度函數(shù)，加快了粒子搜索速度。同時，由于傳統(tǒng)的速度、位置更新公式中粒子群最優(yōu)解容易使粒子群多樣性迅速降低，從而降低全局搜索能力，本文提出了隨三角函數(shù)變化的自適應(yīng)鄰域搜索最優(yōu)解更新方式來改進(jìn)傳統(tǒng)的全局更新方式，保證了粒子群的全局搜索能力，在算法迭代后期使用變異算子增加擾動，以避免陷入局部最優(yōu)位置。工作環(huán)境中存在的運(yùn)動障礙物提高了的路徑規(guī)劃的復(fù)雜度，針對這一問題，提出了避障策略與粒子群算法結(jié)合的路徑規(guī)劃，以實(shí)現(xiàn)動態(tài)環(huán)境下的AGV路徑規(guī)劃。

1 粒子群算法的數(shù)學(xué)理論和AGV運(yùn)行空間描述

1.1 粒子群算法的數(shù)學(xué)理論

粒子群算法最早由Eberhart和Kennedy于1995年提出[19]，其基本概念源于對鳥群覓食行為的研究。在D維粒子搜索空間內(nèi)，有n個代表問題解的粒子組成的種群S={x1,x2,…,xn}，xi=(xi1,xi2,…,xiD)為粒子i(i=1,2,…,n)在D維搜索空間中的解位置；vi=(vi1,vi2,…,viD)為粒子在各個維度上的合成速度，即在各個維度上的位置改變量；pi=(pi1,pi2,…,piD)為粒子i搜索到的歷史最優(yōu)位置；pg=(pg1,pg2,…,pgD)為粒子種群S搜索到的歷史最優(yōu)位置。對于第k+1次迭代，粒子群的問題解位置更新公式為：

(1)

(2)

式中：ω是慣性權(quán)重系數(shù)，用來保持原來速度的系數(shù)；c1、c2是加速因子，前者是粒子i跟蹤自己歷史最優(yōu)值的權(quán)重系數(shù)，表示粒子本身的自我認(rèn)知，后者是粒子群S中所有粒子跟蹤群體最優(yōu)值的權(quán)重系數(shù)，表示粒子對群體知識的認(rèn)識；ξ、η是[0,1]區(qū)間內(nèi)服從均勻分布的隨機(jī)數(shù)；r是約束因子，控制位置更新(2)時位置變化的幅度，一般取r=1。

1.2 AGV運(yùn)行空間描述

實(shí)際上AGV大部分都工作在二維平面上，因此可以將AGV的運(yùn)動空間映射到如圖1所示的二維坐標(biāo)系R2中。為了求解方便，可以將AGV抽象成一個運(yùn)動質(zhì)點(diǎn)，障礙物尺寸表示為障礙物實(shí)際尺寸與AGV實(shí)際尺寸之和。運(yùn)動空間中存在的障礙物可以抽象表示成具有不同位置和半徑的圓Oj=[xj,yj,rj]，(j=1,2,…,m)，xj表示該障礙物坐標(biāo)系橫坐標(biāo)，yj表示該障礙物坐標(biāo)系縱坐標(biāo)，rj是該障礙物尺寸和AGV尺寸之和表示的半徑。若干個障礙物組成了障礙物空間O=O1∪O2…∪Om，則有

(3)

在求解AGV路徑問題中，從路徑起點(diǎn)到路徑終點(diǎn)的AGV路徑軌跡可以經(jīng)過表示自由空間的圖中空白區(qū)域而不能穿過障礙物。自由空間用Wfree表示。

2 改進(jìn)粒子群算法應(yīng)用到AGV路徑規(guī)劃

下面將有約束條件的AGV無碰撞最短路徑規(guī)劃問題建模成約束優(yōu)化問題，然后應(yīng)用本文提出的改進(jìn)粒子群算法進(jìn)行求解。在粒子群算法中，對于有約束條件的優(yōu)化問題可以采用帶有罰函數(shù)的適應(yīng)度函數(shù)來轉(zhuǎn)化成無約束條件的優(yōu)化問題，然后運(yùn)用粒子群算法求解。因此本文所提出的適應(yīng)度函數(shù)包含路徑總長度函數(shù)和罰函數(shù)。本文提出的基于地圖先驗(yàn)知識的粒子群初始化方式，相比傳統(tǒng)算法粒子群初始化時的隨機(jī)性，可使粒子群快速聚集到最優(yōu)解附近，加快了算法求解速度。標(biāo)準(zhǔn)粒子群算法求解速度快，但是容易陷入局部最優(yōu)，而局部粒子群算法不易陷入局部最優(yōu)但是求解速度慢。局部粒子群算法結(jié)合本文所提的粒子群初始化方式可以克服其求解慢的缺陷，最大程度發(fā)揮出其不易陷入局部最優(yōu)這一優(yōu)勢。在算法后期，粒子種群多樣性迅速降低，粒子難以跳出局部搜索空間，引入變異算子增加粒子群飛往全局最優(yōu)解的可能性，引入避障策略使粒子群算法方便應(yīng)用在動態(tài)環(huán)境中。

2.1 問題描述與適應(yīng)度函數(shù)建立

在路徑規(guī)劃問題中，一個粒子的位置代表一個候選解，其內(nèi)部結(jié)構(gòu)由一個起始點(diǎn)、AGV經(jīng)過的若干節(jié)點(diǎn)和一個終點(diǎn)組成。因?yàn)榱Ｗ觩i=(pi1,pi2,…,piD)，所以pi1表示路徑起點(diǎn)，piD表示路徑終點(diǎn)，pi2,pi3,…,piD-1表示非起終點(diǎn)的路徑節(jié)點(diǎn)，若pij(j=1,2,…,D)∈Wfree，并且將pij依次連接起來，則該粒子可以表示成一條合理的具有D個節(jié)點(diǎn)的AGV可正常行駛路徑。其中pij=(xij,yij)，xij,yij分別表示粒子i在j維度上(第j個節(jié)點(diǎn))在橫、縱坐標(biāo)上的數(shù)值。

適應(yīng)度函數(shù)是衡量粒子位置優(yōu)劣的重要依據(jù)，其設(shè)計是否合理會影響算法的求解速度。在路徑規(guī)劃問題中，通常來說，路徑長度是適應(yīng)度函數(shù)要考慮的一個重要指標(biāo)，對于存在障礙物的AGV工作環(huán)境，路徑合理性等其他因素也同樣重要。本文的路徑規(guī)劃目標(biāo)是求解從路徑起點(diǎn)到路徑終點(diǎn)且不與障礙物碰撞的最短路徑，所以設(shè)計了如式(4)所示的適應(yīng)度函數(shù)，某一粒子位置適應(yīng)度函數(shù)值越小表征該位置所對應(yīng)的路徑序列更佳。

(4)

(5)

式中：fit為適應(yīng)度函數(shù)；G為懲罰因子；L(pj,pj+1)為粒子節(jié)點(diǎn)pj和pj+1連接形成的被稱為路徑片段pjpj+1的長度；m為障礙物總數(shù)；w(j,k)用來衡量路徑片段pjpj+1與障礙物Ok的接觸狀態(tài)，w(j,k)有兩種計算方式，如下所示：

(6)

(7)

式中：r(k)為障礙物Ok的半徑，d(j,k)為障礙物Ok圓心到路徑片段pjpj+1的距離。在適應(yīng)度函數(shù)式(4)中引入懲罰因子G，一般取地圖環(huán)境的最大維度值，可在迭代過程中根據(jù)適應(yīng)度函數(shù)值的突變來判斷相鄰迭代之間是否發(fā)生了路徑碰撞。與式(7)相比，式(6)提出了新的懲罰力度，從式(4)～式(6)中可以發(fā)現(xiàn)，路徑序列總長度越長，適應(yīng)度函數(shù)越大。式(6)表示與障礙物相交的路徑序列片段離障礙物圓心越近，適應(yīng)度函數(shù)以指數(shù)上升的速率增長。相比于式(7)，本算法采用式(6)可以在粒子群算法速度和位置更新的階段盡快地使路徑片段與障礙物避開，減少了不必要的低效率迭代，提高了算法的求解速度。

2.2 基于地圖先驗(yàn)知識的粒子群初始化方法

標(biāo)準(zhǔn)粒子群算法中，初始粒子是隨機(jī)生成的，在本文求解路徑問題中，如果依然采用標(biāo)準(zhǔn)方式隨機(jī)生成某一路徑序列，將會呈現(xiàn)如圖2所示的效果。從圖2a中可以看到，隨機(jī)生成的路徑序列具有盲目性，相鄰路徑片段之間的轉(zhuǎn)角較大，且會出現(xiàn)路徑起點(diǎn)與路徑終點(diǎn)之間來回往復(fù)的現(xiàn)象，這會大大拖慢算法求解速度，也不利于粒子群向全局最優(yōu)位置聚集。

在本文所描述的問題中，一個粒子由包括起始點(diǎn)和終止點(diǎn)的D個位置點(diǎn)構(gòu)成，因此需要構(gòu)造(D-2)個位于自由空間Wfree中的位置點(diǎn)，且這些點(diǎn)應(yīng)該能根據(jù)地圖環(huán)境的變化自適應(yīng)地調(diào)整位置。為此設(shè)計了如下的初始粒子位置生成算法。

(8)

因此，路徑節(jié)點(diǎn)pi是直線Lji上的隨機(jī)任意點(diǎn)，滿足pi∈Lji，i=2,3,…,D-1；至此，某一初始粒子在各個維度上的分量均確定完成，重復(fù)上述過程生成所有粒子，基于地圖先驗(yàn)知識的粒子群初始化就此完成。如圖2b所示，基于地圖先驗(yàn)知識的粒子初始化方法生成的初始路徑序列避免了往復(fù)現(xiàn)象，并可根據(jù)工作環(huán)境疏密狀況自適應(yīng)地改變各路徑節(jié)點(diǎn)的分布，有利于算法的快速求解。

2.3 引入變異算子的改進(jìn)自適應(yīng)領(lǐng)域搜索粒子群算法

在粒子群算法中，每個粒子的速度更新是根據(jù)3個因素來變化的：①粒子自己的歷史最優(yōu)解pid；②粒子群體的歷史全局最優(yōu)解pgd；③粒子前一次迭代的速度vid。

pid使粒子在其附近搜索探查；pgd使得所有粒子向粒子群中已經(jīng)找到的歷史最優(yōu)值靠近；vid使得粒子具有向外界解空間探索的趨勢。由此帶來的一個好處是求解速度很快，但缺陷也很明顯，隨著迭代次數(shù)的增加，所有粒子的更新速度很快降到0的鄰域內(nèi)，導(dǎo)致粒子位置更新幾乎不變，此時如果粒子群還未探索到全局最優(yōu)解，則粒子群已經(jīng)很難依靠自身的力量沖破局部陷阱繼續(xù)探索其他空間。針對粒子群算法過早收斂到局部最優(yōu)值這一缺陷，有學(xué)者通過對參數(shù)ω、c1和c2的研究，發(fā)現(xiàn)相較于一種參數(shù)的改進(jìn)，兩種參數(shù)的同時改進(jìn)在優(yōu)化精度和求解速度上更具優(yōu)勢。本文使用文獻(xiàn)[15]提出的按三角函數(shù)規(guī)律變化的權(quán)重因子ω和加速因子c1,c2，其數(shù)學(xué)表達(dá)式如下：

(9)

式中：kmax表示最大迭代次數(shù)；k表示算法當(dāng)前迭代次數(shù)；ω(k)表示第k次迭代對應(yīng)的慣性權(quán)重因子；ωmax=0.95，ωmin=0.4。

(10)

(11)

式中：ca=1，cb=1.5，cα=1，cβ=1.5。

在算法迭代前期，參數(shù)慣性權(quán)重ω和加速因子c1較大，加速因子c2較小，有利于各個粒子盡可能多地探索解空間而不會聚集在某一局部范圍，從而提高找到全局最優(yōu)解的幾率；在算法迭代后期，一定程度上可以認(rèn)為前期已經(jīng)搜索到了全局最優(yōu)解，因此參數(shù)ω和c1較小，c2較大有利于粒子群向全局最優(yōu)解靠攏，加快求解速度，提升算法性能。采取隨迭代次數(shù)變化的參數(shù)控制在一定程度上可以改善標(biāo)準(zhǔn)粒子群算法易早熟的缺陷，這是在參數(shù)層面對標(biāo)準(zhǔn)粒子群算法的改進(jìn)，但為了增大找到全局最優(yōu)解的幾率，除了控制參數(shù)讓單個粒子盡可能多地探索解空間外，依然存在其他方式使得粒子觸及到更多知識，擴(kuò)大搜索范圍，豐富粒子群的多樣性。

本文提出的自適應(yīng)鄰域搜索最優(yōu)解局部粒子群算法通過改變粒子速度更新公式，讓每個粒子的速度更新按照以下3個因素更新：①粒子自己的歷史最優(yōu)解pid；②粒子鄰域內(nèi)所有粒子歷史全局最優(yōu)解pigs(k)d；③粒子前一次迭代的速度vid。

pigs(k)d使得粒子在其鄰域內(nèi)搜索局部最優(yōu)值，并向其鄰域內(nèi)的最優(yōu)位置方向邊移動邊搜索，而不是向整個粒子群最優(yōu)位置靠攏，這樣一來粒子可以觸及到的范圍將大大擴(kuò)大，到達(dá)全局最優(yōu)位置的可能性將大大增加。粒子鄰域隨迭代次數(shù)增加從自身逐漸擴(kuò)大到整個粒子種群。受到隨三角函數(shù)規(guī)律變化的權(quán)重因子和加速因子控制的啟發(fā)，鄰域變化采用按三角函數(shù)變化，其數(shù)學(xué)表達(dá)式為：

(12)

s(k)=smax,αkmax

(13)

式中：s(k)表示粒子鄰域范圍；smin=0，smax=n，n表示粒子群規(guī)模大??；kmax表示最大迭代次數(shù)；α表示迭代控制因子，α∈(0,1)，用來控制粒子群向找到的全局最優(yōu)解靠攏的時機(jī)，本文α=0.5；k表示算法當(dāng)前迭代次數(shù)。

鄰域范圍s(k)隨迭代次數(shù)變化如圖3所示，其中設(shè)迭代次數(shù)為200，迭代控制因子為0.7。將式(9)～式(11)和pigs(k)d代入式(1)和式(2)得：

(14)

(15)

式(14)和式(15)是含有自適應(yīng)參數(shù)的粒子群算法速度、位置更新公式。

當(dāng)算法迭代到后期時，適應(yīng)度函數(shù)值變得平穩(wěn)，此時粒子被困在局部范圍內(nèi)，如果全局最優(yōu)解不在當(dāng)前范圍內(nèi)，需要采取措施來改善這一狀況，使得粒子存在跳出局部陷阱的可能，為此提出粒子位置變異算子。當(dāng)粒子群找到的歷史全局最優(yōu)值連續(xù)多次迭代沒有明顯的變化時，可以認(rèn)為算法已陷入局部最優(yōu)，為解決這一問題，受遺傳算法中變異策略和選擇策略的啟發(fā)，本文通過采用精英選擇策略和傳統(tǒng)輪盤賭相結(jié)合的選擇算子在粒子群中選出一部分適應(yīng)度較好(本文中適應(yīng)度函數(shù)值較小)的粒子進(jìn)行保留，保留粒子個數(shù)為[n×θ]，[·]為向下取整操作，θ∈[0,1]，其余粒子進(jìn)行變異。

fitg=min(fiti),i∈{1,2,…,n}；

(16)

(17)

式中：fiti表示粒子i的適應(yīng)度函數(shù)值；n表示粒子種群規(guī)模大小；B表示相比于適應(yīng)度函數(shù)值足夠大的數(shù)；pi表示輪盤賭算法選擇粒子i的概率。

選擇變異算子操作步驟如下：

步驟1按式(16)選擇出精英粒子保留。

步驟2根據(jù)式(17)和輪盤賭算法選擇[n×θ]-1個粒子保留。

步驟3剩余的n-[n×θ]個粒子進(jìn)行變異操作。

為了豐富粒子群的多樣性，進(jìn)行變異的粒子采取基于地圖疏密程度的初始化方法進(jìn)行重新編碼。然后繼續(xù)進(jìn)行迭代過程，當(dāng)粒子群又聚集到某一局部后，再次進(jìn)行選擇和變異操作，如此循環(huán)直至到達(dá)預(yù)定最大迭代次數(shù)。本文提出的基于改進(jìn)粒子群算法(ωandcLocal Partide Swarm Optimization, WCLPSO)求解AGV路徑規(guī)劃問題流程如圖4所示。

2.4 動態(tài)環(huán)境下的避障策略

針對靜態(tài)環(huán)境，WCLPSO可以有效求解路徑，保證靜態(tài)環(huán)境下路徑序列不會與障礙物相撞，但是在動態(tài)環(huán)境下，即在AGV工作環(huán)境中存在運(yùn)動的障礙物時，如在本文所述的檢定車間中為某一AGV進(jìn)行路徑規(guī)劃時，其余AGV則變成了運(yùn)動中的障礙物，本算法無法保證AGV在運(yùn)行途中不會與運(yùn)動的物體發(fā)生相撞。因此，在靜態(tài)環(huán)境下求出路徑的基礎(chǔ)上，引入實(shí)時避障策略來保證本算法在動態(tài)環(huán)境下的有效求解。

避障策略假設(shè)AGV上配備了能夠檢測障礙物的傳感器，如圖5所示。圖中：va為AGV當(dāng)前的運(yùn)動方向；L為傳感器檢測范圍半徑；si為傳感器檢測扇區(qū)，si取值為0或1，0表示當(dāng)前扇區(qū)內(nèi)沒檢測到障礙物，1表示檢測到障礙物；M為扇區(qū)總數(shù)，其值越大檢測障礙物的分辨率就越高，則AGV采取避障措施規(guī)劃出的新路徑就越精確。則有

S=[s1,s2,…,sM]。

(18)

引入避障策略的動態(tài)路徑規(guī)劃(Path Planning with Obstacle Avoidance,PPOA)算法的流程如下：

步驟1給出參數(shù)，應(yīng)用路徑規(guī)劃算法生成預(yù)行駛路徑。

步驟2AGV根據(jù)預(yù)行駛路徑運(yùn)動，并實(shí)時檢測障礙物。

步驟3判斷是否到達(dá)終點(diǎn)，如果是，則結(jié)束路徑規(guī)劃；否則轉(zhuǎn)步驟4。

步驟4判斷S的取值，如果其中有扇區(qū)取值為1，則轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟2。

步驟5依次計算取值為0的扇區(qū)中心線與傳感器檢測范圍邊緣相交的位置點(diǎn)pi到終點(diǎn)的距離di，滿足si=0,i∈[1,M]。

步驟6AGV運(yùn)動到距離終點(diǎn)最近的位置點(diǎn)pi_min，di_min=min(di)，并實(shí)時檢測障礙物。

步驟7判斷S的取值，如果其中有扇區(qū)取值為1，轉(zhuǎn)步驟5，否則轉(zhuǎn)步驟8。

步驟8判斷是否到達(dá)位置點(diǎn)pi_min，若到達(dá)，則轉(zhuǎn)步驟1;否則轉(zhuǎn)步驟5。

在圖6所示的例子中，S=[1,0,0,1,0,0,1,1]。其中s2=s3=s5=s6=0，s1=s4=s7=s8=1，p2、p3、p5、p6是可行的待選位置點(diǎn)，此時AGV需要根據(jù)避障策略重新規(guī)劃路徑。

值得注意的是，在無人自動化電表檢定車間中運(yùn)動障礙物只是AGV，其運(yùn)動速度一般在固定區(qū)間內(nèi)變動，而不是運(yùn)動狀態(tài)完全隨機(jī)的移動障礙物，因此優(yōu)先使用前文所述動態(tài)避障策略，在碰到本策略無法解決的路徑?jīng)_突問題時，由上位機(jī)中的交通管理系統(tǒng)來介入解決。例如，當(dāng)上位機(jī)交通管理系統(tǒng)檢測到AGV長時間阻塞時，則會協(xié)調(diào)各AGV的運(yùn)動路徑，如有系統(tǒng)無法自行解決的問題，則會報警，期望人工干預(yù)。

3 案例實(shí)驗(yàn)

某省計量中心使用先進(jìn)的多AGV系統(tǒng)作為物流輸送系統(tǒng)，完成各類電表傳輸、檢定等工作，工程的搬運(yùn)規(guī)模和日檢定數(shù)量均屬國內(nèi)最大。雖然AGV在物流領(lǐng)域的應(yīng)用已十分廣泛，但如此大規(guī)模的場地、任務(wù)數(shù)量和任務(wù)要求的應(yīng)用基本沒有。自動化電表檢定車間中每天的電表檢定量達(dá)到萬件，且電表種類繁多、節(jié)奏快，其檢定目標(biāo)如表1所示。由于AGV可以依據(jù)系統(tǒng)指令調(diào)整運(yùn)輸計劃、增加系統(tǒng)柔性，使用AGV作為運(yùn)輸載體可以保證運(yùn)輸效率、降低成本。檢定工藝流程如圖7所示，檢定區(qū)域示意圖如圖8所示，圖8中A區(qū)有1 080個檢測位，用于檢測直接接入式三相電表，每批檢定時長3 h，目標(biāo)日檢定量2 160只。B區(qū)最下面兩排有660個檢測位，用于檢測經(jīng)互感器接入式三相電表，每批檢測時長5 h，目標(biāo)日檢定量660只。B區(qū)其余部分和C區(qū)所有部分共8 820個檢測位，用于檢測單相電表，每批檢測時長90 min，目標(biāo)日檢定量28 800只。AGV參與的環(huán)節(jié)主要是周轉(zhuǎn)箱輸送、在出庫點(diǎn)或裝貨點(diǎn)裝載電表、在卸貨點(diǎn)或入庫點(diǎn)卸載電表。當(dāng)檢定臺空閑時，則呼叫AGV到出庫點(diǎn)運(yùn)送電表到該檢定處；當(dāng)檢定臺完成檢定時，則呼叫AGV到該檢定處運(yùn)送電表到入庫點(diǎn)。檢定臺可以根據(jù)電表類型自動更改檢定程序來應(yīng)對不同的電表。AGV路徑規(guī)劃任務(wù)是從當(dāng)前位置到目標(biāo)點(diǎn)規(guī)劃一條無障礙物碰撞的可供AGV運(yùn)輸電表的可行最短路徑。當(dāng)對某一AGV進(jìn)行路徑規(guī)劃時，其他運(yùn)動AGV可認(rèn)為是運(yùn)動中的障礙物。遇到動態(tài)路徑算法無法自行處理的交通沖突時，系統(tǒng)的交通管理功能會介入解決，沖突解決后繼續(xù)應(yīng)用本策略進(jìn)行路徑規(guī)劃。

表1 檢定目標(biāo)

3.1 靜態(tài)環(huán)境實(shí)驗(yàn)

本實(shí)驗(yàn)選用PSO算法與上文提到的帶有慣性因子和加速因子自適應(yīng)調(diào)節(jié)的粒子群算法(WCPSO)進(jìn)行對照實(shí)驗(yàn)來驗(yàn)證本文所提出改進(jìn)粒子群算法(WCLPSO)的可行性與有效性。

3.1.1 靜態(tài)環(huán)境

為了驗(yàn)證算法的有效性，考慮隨機(jī)、任意布置靜態(tài)障礙物的環(huán)境，如圖9所示，分別采用PSO、WCPSO、WCLPSO求解靜態(tài)工作環(huán)境下的AGV路徑問題，其中圓形表示環(huán)境中的障礙物。算法參數(shù)設(shè)置相同，如表2所示，為了保證實(shí)驗(yàn)結(jié)果的可靠性，三種算法設(shè)置表2中的參數(shù)并且分別進(jìn)行30次獨(dú)立實(shí)驗(yàn)，并計算適應(yīng)度函數(shù)的平均值和方差用來作為衡量算法性能的依據(jù)，其中一次實(shí)驗(yàn)路徑優(yōu)化對比結(jié)果如圖9a、9b、9c所示，圖中虛線代表粒子群中各粒子所對應(yīng)的路徑序列。

由圖9可以看到，WCLPSO優(yōu)化出的路徑比WCPSO和PSO求出的路徑更平滑，且路徑總長度更小，結(jié)果更優(yōu)。在算法前期，PSO與WCPSO相比于WCLPSO求解速度更快，主要是因?yàn)閃CLPSO在算法前期探索了更大的解空間，花費(fèi)的時間較多，但往往能比前兩者找到更優(yōu)的路徑。多次獨(dú)立實(shí)驗(yàn)平均值、方差統(tǒng)計結(jié)果如表3所示，最優(yōu)解對比如圖10所示，WCLPSO經(jīng)常能求出比另外兩種算法求出的路徑更優(yōu)的路徑，方差更小，求解性能更穩(wěn)定，而PSO、WCPSO則往往被困在了局部最優(yōu)解附近，求解性能不穩(wěn)定。經(jīng)過多次實(shí)驗(yàn)表明，WCLPSO可以有效穩(wěn)定地解決AGV的路徑規(guī)劃問題。

表2 算法求解AGV路徑參數(shù)設(shè)置

表3 實(shí)驗(yàn)統(tǒng)計結(jié)果

3.1.2 檢定車間靜態(tài)環(huán)境

前文已經(jīng)給出了檢定車間的整體布局圖，為了更清楚地顯示算法給出的路徑且不影響對算法的討論，在本小節(jié)中只給出檢定車間局部圖，如圖11所示。其中圓形表示檢定臺體對應(yīng)的裝、卸電表位置。因此，檢定車間實(shí)際局部圖可以抽象成如圖12所示的局部靜態(tài)障礙物分布情況，圖中各種圖形指代暫存架、掛表機(jī)器人、檢定臺體、分布在檢定車間內(nèi)的各種設(shè)備和各種車間建筑設(shè)施例如柱子等AGV物理不可達(dá)的位置。分別采用PSO、WCPSO、WCLPSO求解如圖11所示檢定車間環(huán)境下的AGV路徑問題。算法參數(shù)設(shè)置相同，為了保證結(jié)果的可靠性，3種算法按表4所示參數(shù)設(shè)置進(jìn)行多次實(shí)驗(yàn)，并計算適應(yīng)度函數(shù)的平均值和方差，以作為衡量算法性能的依據(jù)，其中一次實(shí)驗(yàn)路徑對比結(jié)果如圖12所示。

表4 參數(shù)設(shè)置

由圖12可以看出，PSO算法無法得到有效路徑，WCPSO可以得到可行路徑，但路徑長度不是最優(yōu)，WCLPSO可以得到最優(yōu)路徑。多次獨(dú)立實(shí)驗(yàn)平均值、方差統(tǒng)計結(jié)果如表5所示，最優(yōu)解對比如圖13所示，在復(fù)雜檢定車間環(huán)境下，PSO多次無法得到可行路徑，WCPSO可行但結(jié)果往往不是最優(yōu)，WCLPSO得到的路徑長度更優(yōu)、方差更小，其性能更穩(wěn)定。實(shí)驗(yàn)表明，改進(jìn)算法可以有效地解決復(fù)雜檢定車間中路徑規(guī)劃問題。

表5 實(shí)驗(yàn)統(tǒng)計結(jié)果

3.2 動態(tài)環(huán)境實(shí)驗(yàn)

3.2.1 動態(tài)環(huán)境

為驗(yàn)證所提避障策略在動態(tài)障礙物環(huán)境下的有效性，本小節(jié)設(shè)計了在動態(tài)環(huán)境下的AGV路徑規(guī)劃實(shí)驗(yàn)，求解路徑算法參數(shù)如表2所示，引入了一些按照線性或圓周規(guī)律運(yùn)動的障礙物，參數(shù)設(shè)置如表6和表7所示。按照動態(tài)路徑規(guī)劃算法得到的一部分AGV關(guān)鍵避障時刻狀態(tài)如圖14所示，如在圖14c中，傳感器檢測到障礙物3后AGV開始進(jìn)行實(shí)時避障，在圖14e中，當(dāng)確認(rèn)范圍內(nèi)無障礙物后按照路徑規(guī)劃的路線運(yùn)動。圖中左下角延伸到右上角的曲線代表AGV的歷史運(yùn)動軌跡，可以看到AGV實(shí)現(xiàn)了從起點(diǎn)到終點(diǎn)的無碰撞運(yùn)動，證明了本策略能夠有效地解決動態(tài)環(huán)境下AGV路徑規(guī)劃問題。

表6 直線運(yùn)動參數(shù)設(shè)置

表7 圓周運(yùn)動參數(shù)設(shè)置

3.2.2 檢定車間動態(tài)環(huán)境

由于AGV運(yùn)行環(huán)境是無人自動化檢定車間，運(yùn)動障礙物只可能是其余AGV，為了提高AGV執(zhí)行避障策略的概率，并驗(yàn)證所提避障策略的有效性，在圖12所示靜態(tài)障礙物環(huán)境的基礎(chǔ)上設(shè)計了運(yùn)動AGV，如圖15所示，圖中箭頭下方的較小圓形圖標(biāo)指代其余運(yùn)動中的AGV，讓其在如圖所示環(huán)境中往復(fù)橫向編隊勻速運(yùn)動。AGV運(yùn)輸電表的起終點(diǎn)如表4所示，應(yīng)用本策略進(jìn)行AGV的路徑規(guī)劃和實(shí)時避障，關(guān)鍵時刻狀態(tài)如圖15所示。圖15b和圖15c顯示了AGV在遭遇其他AGV時脫離預(yù)定行駛路徑，執(zhí)行了避障流程，圖15d顯示了避障結(jié)束后上位機(jī)系統(tǒng)重新為其規(guī)劃路徑。可以看到，AGV實(shí)現(xiàn)了從出庫口裝貨處到檢定臺卸貨處的無碰撞運(yùn)動，證明了在檢定車間這一復(fù)雜環(huán)境中應(yīng)用本策略進(jìn)行AGV路徑規(guī)劃的可行性。

4 結(jié)束語

求解大規(guī)模運(yùn)輸場景下AGV路徑規(guī)劃時，存在搜索精度低，易陷入局部陷阱而造成搜索停滯的問題，因此本文提出一種新的改進(jìn)粒子群算法。提出了新的基于AGV工作環(huán)境結(jié)合輪盤賭策略的粒子群初始化方式，與隨機(jī)初始化方式相比，可根據(jù)地圖環(huán)境動態(tài)自適應(yīng)生成初始粒子群，有利于加快前期求解速度和提高搜索精度。設(shè)計了新的適應(yīng)度函數(shù)，使得路徑片段加速避開障礙物。在調(diào)節(jié)算法各參數(shù)的基礎(chǔ)上，引入了在算法前期隨三角函數(shù)變化的自適應(yīng)鄰域搜索更新方式和算法后期變異算子，增強(qiáng)了算法的全局和局部搜索能力，避免陷入局部最小值。提出的實(shí)時避障策略和路徑規(guī)劃實(shí)現(xiàn)了動態(tài)環(huán)境下的AGV路徑規(guī)劃。采用Python開發(fā)出AGV路徑規(guī)劃平臺，實(shí)現(xiàn)了地圖環(huán)境的繪制、基于3種粒子群算法的路徑求解、算法求解過程中粒子實(shí)時位置和路徑最優(yōu)解的動態(tài)觀測、結(jié)合實(shí)時避障策略的路徑規(guī)劃，有助于理解算法在各個時間節(jié)點(diǎn)上的運(yùn)行表現(xiàn)，方便了算法的進(jìn)一步改進(jìn)。案例中的AGV路徑規(guī)劃對比實(shí)驗(yàn)表明，應(yīng)用在自動化千萬級電表檢定車間的AGV路徑規(guī)劃對比實(shí)驗(yàn)表明，本文所提出的路徑規(guī)劃策略在求解大規(guī)模AGV路徑規(guī)劃問題上具有較為優(yōu)異的性能，從而證明了其應(yīng)用價值。大規(guī)模AGV系統(tǒng)在運(yùn)行過程中積累了大量數(shù)據(jù)，如何利用這些數(shù)據(jù)并基于大數(shù)據(jù)和機(jī)器學(xué)習(xí)對AGV路徑規(guī)劃中的參數(shù)進(jìn)行優(yōu)化還有待進(jìn)一步探索。