劉二輝,姚錫凡,劉 敏,金 鴻

(1.華南理工大學(xué) 機(jī)械與汽車工程學(xué)院，廣東 廣州 510640； 2.廣州啟帆工業(yè)機(jī)器人有限公司,廣東 廣州 510700； 3.華南農(nóng)業(yè)大學(xué) 工程學(xué)院，廣東 廣州 510642)

0 引言

科技的快速發(fā)展和定制化模式的出現(xiàn)使制造模式從規(guī)模經(jīng)濟(jì)向更多元化的產(chǎn)品組合方向演變[1]，增加了生產(chǎn)系統(tǒng)生產(chǎn)的產(chǎn)品品類，也使工藝流程更加復(fù)雜，由此對制造系統(tǒng)的柔性和制造資源的組織方式提出了更高的要求，作為一種運輸物料的智能化工具，自動導(dǎo)引小車(Automated Guided Vehicle, AGV)主要負(fù)責(zé)工位之間以及物料庫和成品庫與工位之間的物料轉(zhuǎn)運[2]，已經(jīng)廣泛應(yīng)用于現(xiàn)代生產(chǎn)系統(tǒng)，其部署不僅能提高生產(chǎn)系統(tǒng)內(nèi)部物料流的運行效率，還有助于提高生產(chǎn)系統(tǒng)的柔性，因此AGV的運行效率對提高整個生產(chǎn)系統(tǒng)的運行效率和柔性至關(guān)重要。為了提高整個生產(chǎn)系統(tǒng)的生產(chǎn)效率，從而更及時地響應(yīng)市場需求的變化，需要考慮AGV與車間調(diào)度的集成和多AGV的協(xié)調(diào)控制等問題，還需要為每臺AGV規(guī)劃出最優(yōu)路徑[3]。AGV的路徑規(guī)劃目標(biāo)是在AGV的工作空間中，規(guī)劃出一條與障礙物無碰撞的、從起點到目標(biāo)的最優(yōu)或近似最優(yōu)路徑，優(yōu)化的指標(biāo)一般是路徑長度、路徑安全性[4]等。根據(jù)AGV工作空間環(huán)境地圖是否已知，路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃[5]，本文假定環(huán)境地圖已知，著重研究AGV全局路徑規(guī)劃算法的設(shè)計。

AGV路徑規(guī)劃屬于NP-hard問題[6]，設(shè)計高效的路徑規(guī)劃算法仍然是很大的挑戰(zhàn)，大多數(shù)研究著重于智能優(yōu)化算法。例如，Zhou等[7]基于粒子群優(yōu)化(Particle Swarm Optimization, PSO)算法提出改進(jìn)的花授粉算法(Flower Pollination Algorithm, FPA)，并應(yīng)用改進(jìn)FPA求解路徑規(guī)劃問題;Tang等[8]為了平衡PSO的局部開發(fā)和全局搜索能力，提出慣性權(quán)重和加速常數(shù)的自適應(yīng)調(diào)節(jié)策略；為了防止PSO陷入局部極值，提出基于差分進(jìn)化 (Differential Evolution, DE) 算法的改進(jìn)方法；基于上述改進(jìn)策略提出應(yīng)用于AGV路徑規(guī)劃的改進(jìn)PSO算法并證明了其收斂性，缺點是沒有針對AGV路徑規(guī)劃特點設(shè)計鄰域搜索算子。Pan等[9]基于蛙跳算法求解AGV路徑規(guī)劃，缺點是環(huán)境地圖簡單對算法性能測試不夠充分。Liang等[10]為了提高人工蜂群算法(Artificial Bee Colony Algorithm，ABC)的收斂速度采用精英保留策略，為了保證搜索方向的可靠性采用解的共享機(jī)制，為了使解的更新利用種群最新信息采用解的即時更新策略，最后提出改進(jìn)ABC并應(yīng)用于多AGV的在線路徑規(guī)劃，缺點是沒有結(jié)合AGV路徑規(guī)劃的特點設(shè)計提高算法收斂速度的算子。Hidalgo-Paniagua等[11]考慮AGV路徑規(guī)劃中的路徑長度、安全性和路徑光滑程度建立多目標(biāo)規(guī)劃模型，提出求解該問題的多目標(biāo)螢火蟲算法(Firefly Algorithm, FA)，并針對路徑規(guī)劃問題提出路徑長度調(diào)節(jié)算子、路徑安全性算子和路徑光滑程度調(diào)節(jié)算子，基于多目標(biāo)FA求解路徑規(guī)劃問題，證明改進(jìn)策略的有效性，缺點是未涉及路徑片段與障礙物相交的檢查算法;Pakdi等[12]基于遺傳算法求解移動機(jī)器人路徑規(guī)劃，為提高所優(yōu)化路徑的光滑程度，采用分段三次Hermite插值多項式對路徑進(jìn)行光滑處理；為了提高算法求解路徑規(guī)劃時的局部開發(fā)能力，將路徑片段分類并設(shè)計不同的變異算子，最后采用模糊自適應(yīng)控制器使AGV跟蹤優(yōu)化出的路徑。缺點是未與其他智能算法對比來證明改進(jìn)算法的優(yōu)勢。Zhang等[13]針對路徑規(guī)劃的特點提出鄰域變異算子來提高算法的局部開發(fā)能力，設(shè)計了基于可視空間的種群初始化方法來提高初始種群的質(zhì)量，設(shè)計了不可行解修復(fù)算子來提高優(yōu)化過程中可行解的比例，最后將改進(jìn)GA用于求解AGV動態(tài)路徑規(guī)劃問題。Lee等[14]基于有向無環(huán)圖提出改進(jìn)的初始種群生成算法，并基于改進(jìn)GA求解AGV路徑規(guī)劃問題，結(jié)果證明改進(jìn)策略有效提高了初始種群的質(zhì)量，進(jìn)而加快了算法的收斂速度。

No Free Lunch理論[15]指出任何算法都有自身的局限性，因此近幾年有很多學(xué)者基于一些自然現(xiàn)象啟發(fā)，競相提出新的智能優(yōu)化算法，如灰狼優(yōu)化(Grey Wolf Optimization, GWO)算法[16]、教—學(xué)優(yōu)化(Teach-Learning-Based Optimization, TLBO)算法[17]、FPA[18]、鯨魚優(yōu)化算法(Whale Optimization Algorithm, WOA)[19]、蜻蜓算法(Dragonfly Algorithm, DA)[20]、蝗蟲優(yōu)化算法(Grasshopper Optimisation Algorithm, GOA)[21]等，并用于解決各類復(fù)雜的組合優(yōu)化問題。GWO算法是一種模擬灰狼群圍捕獵物行為而得的新型智能優(yōu)化算法，已經(jīng)有很多學(xué)者應(yīng)用GWO算法求解各種優(yōu)化問題，例如Komaki等[22]應(yīng)用GWO算法求解兩階段裝配車間作業(yè)調(diào)度優(yōu)化問題，與其他算法對比證明了GWO算法跳出局部極小值的概率較高;Lu等[23]應(yīng)用GWO算法求解焊接車間的作業(yè)調(diào)度優(yōu)化問題;Zhang等[24]基于GWO算法求解路徑規(guī)劃問題，并與其他算法對比證明了GWO算法規(guī)劃出的路徑更優(yōu)、效率更高;Mirjalili等[25]基于標(biāo)準(zhǔn)GWO算法提出多目標(biāo)GWO算法，拓展了GWO算法的應(yīng)用范圍；Gupta等[26]研究了GWO算法求解大規(guī)模連續(xù)優(yōu)化問題，結(jié)果證明GWO算法求解大規(guī)模優(yōu)化問題具有較好的性能；Long等[27]基于精英反向?qū)W習(xí)策略和混沌映射提出改進(jìn)GWO算法，并用于求解高維優(yōu)化問題，與其他算法對比證明，改進(jìn)GWO算法能有效平衡全局搜索和局部開發(fā)能力；劉二輝等[28]基于GWO算法中的灰狼層級結(jié)構(gòu)關(guān)系提出改進(jìn)的精英保留策略，有效維持了種群的多樣性，為了提高算法的局部開發(fā)能力提出鄰域變異算子，進(jìn)而提出改進(jìn)GA，并用于求解AGV路徑規(guī)劃問題，證明了改進(jìn)GA求解路徑規(guī)劃的有效性。

基于以上文獻(xiàn),作為一種新型的群智能算法，與GA,PSO等其他智能算法相比,GWO算法能更好地平衡全局搜索和局部開發(fā)能力，然而該算法在AGV路徑規(guī)劃領(lǐng)域研究較少，而且以上文獻(xiàn)均未涉及路徑片段與障礙物相交判斷算法和路徑片段避障算子，更缺少帶有啟發(fā)式規(guī)則的變異算子，因此本文著重針對AGV路徑規(guī)劃的特點研究GWO算法的改進(jìn)策略，并應(yīng)用改進(jìn)GWO算法求解AGV路徑規(guī)劃問題。傳統(tǒng)的判斷路徑片段與障礙物是否相交的方法是，逐次求障礙物的各個邊與路徑片段的交點，然后判斷交點是否在障礙物上，進(jìn)而確定路徑片段是否與障礙物相交。因為計算交點坐標(biāo)需要進(jìn)行較多的乘法和除法運算，還需要多次判斷，因此效率較低。本文提出的改進(jìn)算法可以有效減少交點計算次數(shù)，從而提高算法的運行效率。傳統(tǒng)的種群初始化方法采用完全隨機(jī)的方法，程序每次運行生成的初始種群質(zhì)量差異較大，為了提高初始種群的質(zhì)量，本文提出新的種群初始化方法來有效提高初始解中優(yōu)質(zhì)解的比例。傳統(tǒng)的變異算子缺少啟發(fā)式規(guī)則，導(dǎo)致變異生成優(yōu)質(zhì)解的概率較低，為此本文設(shè)計帶有啟發(fā)式規(guī)則的鄰域變異算子，以提高算法的局部開發(fā)能力。此外，與障礙物空間沒有交集的路徑片段生成效率對算法效率和尋優(yōu)能力的提高同樣至關(guān)重要，本文設(shè)計了新的避障算子以加快路徑片段避開障礙物的速度。為了提高路徑規(guī)劃算法驗證的效率，本文基于MATLAB GUI工具開發(fā)出了基于GWO算法的AGV路徑規(guī)劃仿真原型平臺。

1 AGV工作空間描述

為了方便建模與分析，將AGV工作空間分為障礙物空間和自由空間，由于本文著重研究AGV的路徑規(guī)劃，而AGV運動的形式是平面運動，因此定義：AGV的工作空間W是由R2表示的物理空間，W的子集障礙物空間記為Oobs，AGV與障礙物無碰撞移動的空間為自由空間Cfree，則Oobs∪Cfree=W。

當(dāng)進(jìn)行AGV路徑規(guī)劃算法設(shè)計時，首先要考慮的是環(huán)境地圖的表示方法，網(wǎng)格地圖因容易實施、對障礙物有較好的表示和對障礙物形狀敏感性低等優(yōu)點[29-30]，廣泛應(yīng)用于AGV路徑規(guī)劃的環(huán)境地圖建模，具體方法是將AGV的工作空間劃分為一定數(shù)量的單元格，若單元格屬于障礙物空間，則用黑色表示，反之用白色表示，如圖1所示。單元格尺寸依據(jù)環(huán)境地圖復(fù)雜程度而定，較小的單元格尺寸表示環(huán)境地圖更精確，有利于提高優(yōu)化出的路徑質(zhì)量。

2 基于改進(jìn)灰狼優(yōu)化算法的AGV路徑規(guī)劃

2.1 AGV路徑規(guī)劃模型

為了方便描述，沿用GA用染色體表示一個解的方法，將AGV從出發(fā)點到目的地的一條完整路徑記為一個染色體(如圖2)，染色體上第一個基因和最后一個基因分別表示AGV運動的起始點和目標(biāo)點坐標(biāo)。在自由空間中隨機(jī)產(chǎn)生n-2個點，滿足{p1,p2,…,pn}∈Cfree，這n個點按順序連接起來構(gòu)成一個從起始點到目標(biāo)點的路徑。在優(yōu)化求解過程中，每個染色體的第一個和最后一個基因保持不變[28]，圖1中的黑色實線表示一條包含6個節(jié)點的路徑。

2.2 適應(yīng)度函數(shù)設(shè)計

基于GWO算法求解AGV路徑規(guī)劃的過程中，需要根據(jù)每個染色體的質(zhì)量將種群分為α，β，δ，ω4類個體，然后根據(jù)相應(yīng)策略進(jìn)行解的更新。解的評價方法一般是根據(jù)目標(biāo)函數(shù)設(shè)計適應(yīng)度函數(shù)，本文考慮路徑長度、路徑與障礙物相交的次數(shù)和路徑的光滑程度3個因素，采用加權(quán)的方式先建立目標(biāo)函數(shù)再轉(zhuǎn)化為適應(yīng)度函數(shù)。其中，路徑長度與AGV完成任務(wù)的時間有關(guān)，長度越短運行時間越少；路徑與障礙物的相交次數(shù)與路徑的安全性有關(guān)，在路徑與障礙物相交的鄰域，AGV需要進(jìn)行局部路徑規(guī)劃，若AGV構(gòu)建的環(huán)境地圖偏差較大，則可能導(dǎo)致其與障礙物碰撞，另外局部路徑規(guī)劃也會降低其運行效率；路徑的光滑程度與能耗有關(guān)，由于摩擦，轉(zhuǎn)彎次數(shù)越多，所消耗的能量增加得越多[31]。

(1)路徑長度相關(guān)的子目標(biāo)函數(shù)一

(1)

式中：f1為第一個子目標(biāo)函數(shù);Oobs為障礙物集合;δ為懲罰因子;pipi+1表示點pi和pi+1連接形成的路徑片段[28];

(2)

(2)路徑光滑程度

AGV轉(zhuǎn)彎時速度需要減小，轉(zhuǎn)彎角度越小，AGV的運行速度越大，若優(yōu)化路徑時不考慮AGV的轉(zhuǎn)彎問題，則規(guī)劃出的最優(yōu)路徑不一定能使AGV以最快最安全的狀態(tài)到達(dá)目標(biāo)點，且轉(zhuǎn)彎處的加減速能耗也隨之增加。為此，本文考慮AGV的轉(zhuǎn)彎因素，將路徑光滑程度作為目標(biāo)函數(shù)的一部分，以提高優(yōu)化出的路徑的質(zhì)量。轉(zhuǎn)彎角度的任意一段路徑如圖3所示，路徑光滑程度函數(shù)

(3)

式中:m表示一條完整的路徑轉(zhuǎn)彎次數(shù)，φi表示第i個轉(zhuǎn)彎點的轉(zhuǎn)彎角度，f2表示第二個子目標(biāo)函數(shù)。φ越大表示路徑光滑程度越差，當(dāng)φ=0時，路徑為直線。

(4)

式中(xA,yA)，(xB,yB)和(xC,yC)分別是A,B和C3點的坐標(biāo)。

(3)適應(yīng)度函數(shù)

本文設(shè)計如式(5)所示的適應(yīng)度函數(shù)，用于每一次迭代之后評估每個染色體的優(yōu)劣，f1和f2越小，表示路徑長度越短、路徑與障礙物碰撞次數(shù)越少和路徑越平滑，實際應(yīng)用中根據(jù)f1和f2的重要程度不同選擇合適的α和β。

fit=N-αf1-βf2。

(5)

式中：N為足夠大的正數(shù)，fit為適應(yīng)度函數(shù)，α和β分別是f1和f2的權(quán)重系數(shù)。

2.3 獵物搜索階段

用式(6)～式(9)模擬灰狼群捕食過程中前期的圍捕獵物行為(如圖4)：

Z=|H·Xp(t)-X(t)|。

(6)

式中:t為迭代次數(shù)，Xp(t)和X(t)分別為當(dāng)前獵物和狼的位置，H用于調(diào)整搜索方向。

X(t+1)=Xp(t)+V·Z。

(7)

式中V用于調(diào)整搜索半徑，算法迭代前期V的模較大，后期變小。

V=a(2r1-1)。

(8)

式中：a隨著迭代從2線性減小到0;r1為隨機(jī)向量，r1(i)是區(qū)間[0,1]的隨機(jī)數(shù)，i為決策變量的維數(shù)。

H=2r2。

(9)

式中r2為隨機(jī)向量，r2(i)是區(qū)間[0,1]的隨機(jī)數(shù)，i為決策變量的維數(shù)。

其中，式(6)將X(t+1)控制在以Xp(t)為圓心、以V·Z的模為半徑的圓內(nèi)。開始階段V·Z的模較大，用于模擬狼群搜索獵物，為全局搜索階段；隨著迭代V·Z的模變小，進(jìn)入局部信息挖掘階段，即模擬狼群襲擊獵物行為[25]；最后狼群捕獵結(jié)束，算法收斂到全局最優(yōu)解或局部最優(yōu)解。

2.4 捕食階段

為了模擬狼群圍捕獵物的過程，在GWO算法中假設(shè)α，β，δ最接近獵物(最優(yōu)解)，每一次迭代均保存α，β，δ，其他狼在α，β，δ引導(dǎo)下重新調(diào)整位置。式(10)～式(16)表示其他狼在α，β，δ領(lǐng)導(dǎo)下位置更新的數(shù)學(xué)模型，解的更新如圖5所示，其中α，β，δ3個解表示“獵物”的估計位置，隨著算法的迭代，其他狼在α，β，δ的帶領(lǐng)下將“獵物”圍捕在一定區(qū)域內(nèi)等待襲擊(收斂到最優(yōu)解)[25]。

Zα=|H1·Xα(t)-X(t)|;

(10)

Zβ=|H2·Xβ(t)-X(t)|;

(11)

Zδ=|H3·Xδ(t)-X(t)|;

(12)

X1(t+1)=Xα(t)-V1·Zα;

(13)

X2(t+1)=Xβ(t)-V2·Zβ;

(14)

X3(t+1)=Xδ(t)-V3·Zδ;

(15)

X3(t+1)]。

(16)

式中：Xα(t),Xβ(t)，Xδ(t)分別是α,β，δ解的位置，H1(i),H2(i)，H3(i)是區(qū)間[0,2]的隨機(jī)數(shù)，V1(i),V2(i)，V3(i)是區(qū)間[-2,2]的隨機(jī)數(shù)，i是決策變量的維數(shù);X(t)為當(dāng)前解;Zα,Zβ,Zδ分別為當(dāng)前解與α,β,δ解的位置偏差；t為迭代次數(shù)。

2.5 襲擊獵物階段

算法迭代到后期進(jìn)入收斂階段，即灰狼群襲擊獵物階段。建模過程中設(shè)置a隨著算法迭代從2線性遞減到0，使V的模不斷減小。當(dāng)V的模在[0,1]區(qū)間時，迭代后灰狼的位置若在當(dāng)前位置和獵物之間的任何一點，則表示灰狼襲擊獵物(如圖6a)，否則表示灰狼在搜索獵物(如圖6b)[25]。

2.6 路徑微調(diào)算子

基于智能算法求解AGV路徑規(guī)劃一般的缺陷是，由于缺少啟發(fā)式鄰域搜索算子，算法迭代到后期進(jìn)化停滯而陷入局部極小值的概率大大增加。為此，本文基于路徑片段組成的三角形建立啟發(fā)式鄰域搜索算子，以增強(qiáng)算法的局部開發(fā)能力，具體方法如下：

(1)情形一

圖7a所示為路徑片段與障礙物相交，圖7b所示為路徑片段因轉(zhuǎn)彎角度大導(dǎo)致路徑長度過大，因此本文提出路徑微調(diào)算子，通過微調(diào)使路徑片段既變短又能避開障礙物，具體步驟如下：

路徑節(jié)點B沿向量BP方向移動m個單元格到達(dá)B′點，從而既可以使路徑片段避開障礙物(如圖7a)，也可以使路徑片段更短(如圖7b)，則OB′=OB+(mdgrid)BP，其中：向量BP是向量AC法向量的單位向量，O為坐標(biāo)原點。設(shè)B′點坐標(biāo)為(xB′,yB′),

xB′=round

(17)

yB′=round

(18)

式中：dgrid是網(wǎng)格地圖中一個單元格的尺寸；(xA,yA)，(xB,yB),(xC,yC)分別是A，B，C3點坐標(biāo)；round()為四舍五入取整函數(shù)；m=(±1,±2,…,±N)表示路徑節(jié)點B沿AC法向量方向或反方向移動的單元格數(shù)。

向量BP方向的確定方法如下：從圖7a和圖7b可以看出，若BP與BA和BC的夾角均為銳角則BA+BC>B′A+B′C，沿BP方向移動B點有助于點B避開障礙物，也有利于縮短路徑片段；若BP與BA和BC夾角均為鈍角，則BP反向。

(2)情形二

如圖7c所示，Q點是AC的中點，B點沿AC的垂線方向微調(diào)以進(jìn)一步增加路徑轉(zhuǎn)彎角度，此時B點需要沿其與AC中點連線方向微調(diào)才能有效縮短路徑，B點沿向量BP方向移動m個單元格之后記為B′點，則OB′=OB+(mdgrid)BP，其中BP為BQ的單位向量，B′點具體確定方法如下：

(19)

(20)

算法進(jìn)化過程中一般設(shè)置較小的染色體變異概率，因為較大的變異概率會使算法退化為隨機(jī)搜索，為了提高變異生成較優(yōu)解的概率，路徑微調(diào)算法按路徑轉(zhuǎn)彎角度確定變異的優(yōu)先級，按優(yōu)先級確定變異發(fā)生的概率，具體方法如下：

步驟1按圖7中AB和BC所成的角度θ將基因點分為0≤θ≤π/6，π/6<θ≤π/3，π/3<θ≤π/2，θ>π/2四類。

步驟2根據(jù)圖3可見，一個基因點處的θ越小，該點的AGV轉(zhuǎn)彎角度φ越大，對此類基因進(jìn)行變異可以顯著縮短路徑長度并提高路徑光滑程度。θ越小，基因點變異的優(yōu)先級越高，變異的概率越大，因此按優(yōu)先級先處理0≤θ≤π/6的基因點，再依次處理其他3種情形。

2.7 避障算子

為了使路徑片段快速避開障礙物，以提高算法效率和尋優(yōu)能力，本文設(shè)計如圖8所示的避障算子。

從圖中可以看出，為使路徑片段PQ避開障礙物，將P沿PN方向移動到P1或者將Q沿RQ方向移動到Q1，下面以P1為例說明其坐標(biāo)計算方法。P1坐標(biāo)計算如下：

(21)

(22)

式中:(xN,yN),(xP,yP),(xP1,yP1)分別為N,P,P1點的坐標(biāo);dgrid為網(wǎng)格地圖中一個單元格的尺寸;K為常數(shù)，一般設(shè)置為10，r=1,2,…,2K;round()為四舍五入取整函數(shù)。

2.8 初始解生成算法

傳統(tǒng)的初始解生成方法是在自由空間中隨機(jī)產(chǎn)生n-2個點,滿足{p1,p2,…,pn}∈Cfree，然后按順序連接這n個點p1,p2,…,pn-1,pn構(gòu)成一個初始解。這種方法的缺點是缺少啟發(fā)式規(guī)則導(dǎo)致每次迭代生成的初始種群質(zhì)量離散性較大，為此本文提出一種新的啟發(fā)式規(guī)則用于生成較高質(zhì)量的初始解，如圖9所示，其中線段L1,L2,…,Ln-2垂直平分線段p1pn，黑色矩形表示障礙物。具體流程如下：

步驟1在圖9所示的虛線Li上均勻產(chǎn)生m個點。

步驟2判斷路徑片段Li-1Li是否與障礙物相交，若不相交，則將點pi+1作為第i+1個基因，否則選取使路徑片段Li-1Li與障礙物碰撞次數(shù)最少且Li-1Li最短的點pi+1作為第i+1個基因。

2.9 路徑片段與障礙物相交判斷方法

由于傳統(tǒng)的用于判斷路徑片段與障礙物是否相交的算法復(fù)雜且效率較低，求解AGV路徑規(guī)劃時耗時較長，為此本文基于二元函數(shù)梯度建立高效的判斷算法，具體方法如下：

AGV工作空間網(wǎng)格地圖及路徑如圖10所示，其中，路徑片段pipi+1與障礙物Ob1相交，其直線方程為

(yi-yi+1)x-(xi-xi+1)y+xiyi+1-xi+1yi=0。

(23)

式中(xi,yi)和(xi+1,yi+1)分別是pi和pi+1點的坐標(biāo)。

假設(shè)一個二元函數(shù)

f(x,y)=(yi-yi+1)x-(xi-xi+1)y+

xiyi+1-xi+1yi。

(24)

函數(shù)f(x,y)的梯度

gradf(x,y)=(yi-yi+1,xi+1-xi)。

(25)

式中g(shù)radf(x,y)表示函數(shù)f(x,y)的梯度。

直線pipi+1將平面分成直線的兩側(cè)和直線pipi+13部分，對于直線pipi+1上的任意點(xt,yt),有f(xt,yt)=0。由多元函數(shù)微分學(xué)可知，沿梯度方向的函數(shù)值增加，反之減小，因此對于在gradf(x,y)指向一側(cè)的任意點(x,y),f(x,y)>0；對于在-gradf(x,y)指向一側(cè)的任意點(x,y)，f(x,y)<0。據(jù)此設(shè)計矩形障礙物與路徑片段pipi+1相交的判斷方法流程如下：

首先判斷f(xA,yA)和f(xB,yB)，若二者同號，則點A和點B在直線pipi+1的同一側(cè)；否則，計算直線AB與直線pipi+1的交點坐標(biāo)，若交點坐標(biāo)在點A和點B之間，則路徑片段pipi+1與障礙物相交。

判斷路徑片段是否與障礙物有交集的傳統(tǒng)算法，需要先計算路徑片段與障礙物各邊界的交點坐標(biāo)，然后根據(jù)交點坐標(biāo)判斷交點是否在障礙物空間，進(jìn)而判斷路徑片段與障礙物是否有交集，整個過程需要多次進(jìn)行乘法和除法計算，效率較低；而本文改進(jìn)算法只需進(jìn)行較少的乘法和f(x,y)的符號判斷，因此計算簡單、效率較高。隨著障礙物數(shù)量的增加，改進(jìn)算法的計算量顯著減少，算法運行效率明顯提高。

2.10 灰狼優(yōu)化算法求解AGV路徑規(guī)劃的解的修復(fù)方法

基于改進(jìn)GWO算法求解AGV路徑規(guī)劃過程中，每一次迭代生成的解未必是可行解，為了提高種群優(yōu)質(zhì)解的比例，加快算法的收斂進(jìn)程，本文設(shè)計如圖11所示的路徑染色體修復(fù)算法。

3 AGV復(fù)雜環(huán)境路徑規(guī)劃仿真實驗與結(jié)果分析

3.1 AGV路徑規(guī)劃算法仿真原型平臺開發(fā)

為了驗證本文所提改進(jìn)GWO算法求解AGV路徑規(guī)劃的有效性并提高算法驗證的效率，采用MATLAB 2014b軟件GUI工具開發(fā)出基于智能優(yōu)化算法的AGV路徑規(guī)劃集成仿真原型平臺，如圖12所示。

(1)界面介紹

新建地圖操作方法是先在“地圖網(wǎng)格數(shù)”輸入網(wǎng)格數(shù)，然后點擊“新建地圖”新建一張空白的地圖并顯示網(wǎng)格。繪制障礙物的步驟是，先點擊“設(shè)置障礙物”，然后依次選中矩形障礙物左下角點和右上角點完成障礙物繪制?！案倪M(jìn)GA”、“改進(jìn)GWO算法”、“多種群GA”和“單種群GA”可以選擇不同路徑規(guī)劃的求解算法，以對比幾種算法的性能，并快速驗證改進(jìn)策略的優(yōu)勢。“路徑光滑處理”用于去除路徑的一些尖角，以提高路徑的光滑程度，進(jìn)而提高AGV運行的效率。圖12中的粗虛線是算法優(yōu)化出的路徑，細(xì)點畫線是點擊“路徑光滑處理”之后生成的路徑。“保存地圖”可以將當(dāng)前繪制的地圖保存成.mat格式文件，下次進(jìn)入該平臺點擊“加載地圖”即可載入歷史地圖數(shù)據(jù)。

(2)參數(shù)輸入

“種群個數(shù)”一般設(shè)置為30～80；“編碼長度”用于設(shè)置染色體的長度，一般設(shè)置為5～20；“地圖網(wǎng)格數(shù)”用于輸入原始地圖要劃分的網(wǎng)格數(shù)，該參數(shù)越大表示網(wǎng)格致密度越高，其大小根據(jù)地圖復(fù)雜程度而定，初始值一般設(shè)置為1；“迭代次數(shù)”作為迭代終止條件，一般設(shè)置為100～300；交叉概率較大會對種群擾動過大，從而破壞優(yōu)質(zhì)解，較小時會導(dǎo)致算法進(jìn)化停滯，變異概率太小導(dǎo)致算法易陷入局部最小值，太大對種群擾動較大，使算法退化為隨機(jī)搜索，因此根據(jù)染色體的信息熵確定變異和交叉概率，以避免單一變異和交叉概率導(dǎo)致算法魯棒性差的缺陷?！白畲笞儺惛怕省?、“最小變異概率”、“最大交叉概率”和“最小交叉概率”用于根據(jù)染色體信息熵自適應(yīng)計算染色體的變異和交叉概率[28]。

3.2 求解結(jié)果分析與討論

采用如圖12所示的AGV路徑規(guī)劃算法集成仿真原型平臺，設(shè)計如圖14、圖16、圖18和圖20所示的4個地圖情景(稱為Map1，Map2，Map3，Map4)，并采用改進(jìn)GWO算法、單種群GA、多種群GA和改進(jìn)GA 4種算法進(jìn)行求解，對比求解結(jié)果證明本文設(shè)計的改進(jìn)策略的優(yōu)越性。算法參數(shù)和流程分別如表1和圖13所示，其中改進(jìn)GA采用文獻(xiàn)[28]的算法。

表1 改進(jìn)GWO算法求解AGV路徑規(guī)劃參數(shù)設(shè)置

續(xù)表1

從圖14和圖15可以看出，傳統(tǒng)單種群GA、多種群GA和改進(jìn)GA求解路徑規(guī)劃問題時，由于搜索能力較差，很快陷入局部極小值，而改進(jìn)GWO算法逐漸收斂到最優(yōu)解，表現(xiàn)出了較好的全局搜索和局部開發(fā)能力。同時，改進(jìn)GWO算法規(guī)劃出的路徑?jīng)]有明顯的尖角，這是因為迭代前期避障算子以較快的速度使路徑片段避開障礙物，迭代后期帶啟發(fā)式規(guī)則的路徑微調(diào)算子對路徑進(jìn)行了充分地鄰域搜索，提高了算法的局部開發(fā)能力，使改進(jìn)GWO算法相對另外3種算法規(guī)劃出的路徑更光滑。

為了進(jìn)一步驗證本文所提改進(jìn)策略對GWO算法尋優(yōu)能力的影響，設(shè)計復(fù)雜程度不同的環(huán)境地圖Map2，Map3，Map4，采用改進(jìn)GWO算法、改進(jìn)GA等算法對3種情形環(huán)境地圖的路徑規(guī)劃結(jié)果如圖 16、圖18和圖20所示，目標(biāo)函數(shù)收斂曲線如圖17、圖19和圖21所示。從圖16、圖18和圖20可以看出，改進(jìn)GWO算法和改進(jìn)GA優(yōu)化出的路徑較優(yōu)，單種群GA和多種群GA規(guī)劃出的路徑較長且尖角較多，并過早地陷入局部極小值。從圖17、圖19和圖21可以看出，目標(biāo)函數(shù)收斂曲線前期下降較快，后期緩慢下降，說明改進(jìn)GWO算法和改進(jìn)GA前期對解空間進(jìn)行了充分探索，快速鎖定最優(yōu)解可能存在的區(qū)域，后期依賴算法較好的局部開發(fā)能力對上述區(qū)域進(jìn)行了充分地鄰域搜索，種群中的個體不斷聚集到最優(yōu)解鄰域內(nèi)，算法進(jìn)入收斂階段，而傳統(tǒng)單種群GA和多種群GA缺少對AGV路徑規(guī)劃問題有感知能力的遺傳算子，導(dǎo)致算法迭代到中后期不能充分挖掘鄰域信息，致使算法很快陷入局部極小值而停滯進(jìn)化。幾種不同復(fù)雜程度環(huán)境地圖路徑規(guī)劃結(jié)果對比證明，改進(jìn)GWO算法求解復(fù)雜環(huán)境地圖中的路徑規(guī)劃時，搜索性能有較大提高，并且規(guī)劃出的路徑比較光滑，有助于提高AGV行駛的速度，從而更好地滿足實際應(yīng)用。進(jìn)一步分析可以看出，隨著環(huán)境地圖復(fù)雜程度的增加，改進(jìn)GWO算法與改進(jìn)GA的尋優(yōu)優(yōu)勢越發(fā)明顯。

為了更加深入研究“2.8路徑片段與障礙物相交判斷方法”對改進(jìn)算法效率的影響，采用4種算法求解較復(fù)雜的環(huán)境地圖Map3和Map4所示的AGV路徑規(guī)劃問題，改進(jìn)前后算法求解時間對比如表2所示，可見改進(jìn)的檢測算法效率提高30%左右。算法效率的提高有助于提高AGV的避障性能和運行速度，進(jìn)而提高涉及AGV的生產(chǎn)系統(tǒng)內(nèi)部的物料流效率。

表2 改進(jìn)的路徑片段與障礙物相交檢測算法效率對比 s

為了更加全面地證明改進(jìn)GWO算法求解AGV路徑規(guī)劃問題的優(yōu)化能力，選取較復(fù)雜的環(huán)境地圖Map4作為優(yōu)化對象，同一種群條件下每個算法對同一個環(huán)境地圖求解30次，最優(yōu)解、最差解和平均解對比如表3所示，求解過程中除種群參數(shù)外其他參數(shù)同表1。通過對比可以看出，種群數(shù)太小時由于對優(yōu)化空間不能提供足夠多的信息，導(dǎo)致算法早熟，隨著種群參數(shù)的增加，種群可以充分覆蓋解空間，算法的搜索能力不斷提高，種群參數(shù)增加到一定值后算法尋優(yōu)能力趨于穩(wěn)定，種群參數(shù)在60～70附近時算法綜合性能較優(yōu)，隨著種群數(shù)的繼續(xù)增加，算法尋優(yōu)能力變化較小，但是計算耗時增加較快，因此種群參數(shù)設(shè)置在60～70范圍內(nèi)比較合適。從表3可以看出，在幾種種群大小情況下，改進(jìn)GWO算法優(yōu)化出的最優(yōu)解、最差解和平均解均優(yōu)于改進(jìn)GA，進(jìn)一步分析最優(yōu)解和最差解的差值可以看出，改進(jìn)GWO算法優(yōu)化出的結(jié)果離散性更小，說明改進(jìn)GWO算法有較好的穩(wěn)定性。進(jìn)一步分析表2以及環(huán)境地圖Map1，Map2，Map3，Map4的路徑規(guī)劃結(jié)果可以證明，隨著環(huán)境地圖復(fù)雜度的增加，改進(jìn)GWO算法的尋優(yōu)能力和效率均優(yōu)于其他算法。AGV的實際運行環(huán)境充滿較多動態(tài)性和不確定性，因此有較高效率和尋優(yōu)能力的改進(jìn)GWO算法有助于提高AGV的運行效率和安全性。

表3 不同種群條件下幾種算法優(yōu)化出的路徑對比(環(huán)境地圖Map4)

4 結(jié)束語

針對AGV路徑規(guī)劃問題特點，本文主要從進(jìn)化算子、種群初始化算法和算法效率3方面對傳統(tǒng)GWO算法進(jìn)行改進(jìn)，并與其他智能算法對比，證明改進(jìn)算法求解AGV路徑規(guī)劃問題的有效性，創(chuàng)新點如下：

(1)進(jìn)化算子方面，根據(jù)路徑片段組成的三角形建立啟發(fā)式變異規(guī)則，進(jìn)而提出帶啟發(fā)式規(guī)則的路徑微調(diào)算法，克服了傳統(tǒng)GWO算法求解AGV路徑規(guī)劃問題容易陷入局部極小值的缺陷，有效提高了算法的局部開發(fā)能力，防止算法迭代到后期因局部搜索能力較差而導(dǎo)致進(jìn)化停滯。另一方面，為了提高路徑片段避開障礙物的效率，設(shè)計了新的避障算子，有效提升了種群中優(yōu)質(zhì)解的比例，進(jìn)而加快算法的收斂進(jìn)程。

(2)種群初始化方面，傳統(tǒng)的種群隨機(jī)初始化方法缺少啟發(fā)式規(guī)則，每次求解時易造成初始種群質(zhì)量差異較大，本文提出新的種群初始化方法有效提高了初始種群的質(zhì)量，進(jìn)而提高了算法的穩(wěn)定性。

(3)算法效率方面，傳統(tǒng)的路徑片段與障礙物相交判斷算法復(fù)雜且效率較低，本文基于二元函數(shù)梯度設(shè)計出更加高效的判斷算法，改進(jìn)前后算法的求解時間對比證明，新的判斷算法顯著提高了路徑規(guī)劃算法的效率。

(4)為了提高算法測試效率，基于MATLAB GUI開發(fā)了基于多種智能算法的AGV路徑規(guī)劃集成仿真原型平臺，并采用單種群GA、多種群GA、改進(jìn)GA和改進(jìn)GWO算法求解4種不同復(fù)雜程度環(huán)境地圖中的路徑規(guī)劃問題，證明了改進(jìn)GWO算法求解AGV路徑規(guī)劃問題的優(yōu)勢，進(jìn)一步以種群參數(shù)為自變量對比每個算法優(yōu)化出的最優(yōu)路徑長度。綜合分析證明，隨著環(huán)境地圖復(fù)雜度的增加，本文所提改進(jìn)GWO算法在優(yōu)化能力和效率方面均優(yōu)于改進(jìn)GA等算法。

本文主要研究基于改進(jìn)GWO算法的AGV靜態(tài)環(huán)境的路徑規(guī)劃問題，而AGV實際的工作環(huán)境具有較多的動態(tài)性，因此未來將研究GWO算法在AGV動態(tài)路徑規(guī)劃求解中的應(yīng)用和新的種群初始化方法，同時開展其他新型智能優(yōu)化算法在AGV路徑規(guī)劃中的應(yīng)用研究。