基于改進(jìn)灰狼優(yōu)化算法的自動(dòng)導(dǎo)引小車路徑規(guī)劃及其實(shí)現(xiàn)原型平臺(tái)

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

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

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

No Free Lunch理論[15]指出任何算法都有自身的局限性，因此近幾年有很多學(xué)者基于一些自然現(xiàn)象啟發(fā)，競(jìng)相提出新的智能優(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)化問題，與其他算法對(duì)比證明了GWO算法跳出局部極小值的概率較高;Lu等[23]應(yīng)用GWO算法求解焊接車間的作業(yè)調(diào)度優(yōu)化問題;Zhang等[24]基于GWO算法求解路徑規(guī)劃問題，并與其他算法對(duì)比證明了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)化問題，與其他算法對(duì)比證明，改進(jìn)GWO算法能有效平衡全局搜索和局部開發(fā)能力；劉二輝等[28]基于GWO算法中的灰狼層級(jí)結(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ī)則的變異算子，因此本文著重針對(duì)AGV路徑規(guī)劃的特點(diǎn)研究GWO算法的改進(jìn)策略，并應(yīng)用改進(jìn)GWO算法求解AGV路徑規(guī)劃問題。傳統(tǒng)的判斷路徑片段與障礙物是否相交的方法是，逐次求障礙物的各個(gè)邊與路徑片段的交點(diǎn)，然后判斷交點(diǎn)是否在障礙物上，進(jìn)而確定路徑片段是否與障礙物相交。因?yàn)橛?jì)算交點(diǎn)坐標(biāo)需要進(jìn)行較多的乘法和除法運(yùn)算，還需要多次判斷，因此效率較低。本文提出的改進(jìn)算法可以有效減少交點(diǎn)計(jì)算次數(shù)，從而提高算法的運(yùn)行效率。傳統(tǒng)的種群初始化方法采用完全隨機(jī)的方法，程序每次運(yùn)行生成的初始種群質(zhì)量差異較大，為了提高初始種群的質(zhì)量，本文提出新的種群初始化方法來(lái)有效提高初始解中優(yōu)質(zhì)解的比例。傳統(tǒng)的變異算子缺少啟發(fā)式規(guī)則，導(dǎo)致變異生成優(yōu)質(zhì)解的概率較低，為此本文設(shè)計(jì)帶有啟發(fā)式規(guī)則的鄰域變異算子，以提高算法的局部開發(fā)能力。此外，與障礙物空間沒有交集的路徑片段生成效率對(duì)算法效率和尋優(yōu)能力的提高同樣至關(guān)重要，本文設(shè)計(jì)了新的避障算子以加快路徑片段避開障礙物的速度。為了提高路徑規(guī)劃算法驗(yàn)證的效率，本文基于MATLAB GUI工具開發(fā)出了基于GWO算法的AGV路徑規(guī)劃仿真原型平臺(tái)。

1 AGV工作空間描述

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

當(dāng)進(jìn)行AGV路徑規(guī)劃算法設(shè)計(jì)時(shí)，首先要考慮的是環(huán)境地圖的表示方法，網(wǎng)格地圖因容易實(shí)施、對(duì)障礙物有較好的表示和對(duì)障礙物形狀敏感性低等優(yōu)點(diǎn)[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用染色體表示一個(gè)解的方法，將AGV從出發(fā)點(diǎn)到目的地的一條完整路徑記為一個(gè)染色體(如圖2)，染色體上第一個(gè)基因和最后一個(gè)基因分別表示AGV運(yùn)動(dòng)的起始點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)。在自由空間中隨機(jī)產(chǎn)生n-2個(gè)點(diǎn)，滿足{p1,p2,…,pn}∈Cfree，這n個(gè)點(diǎn)按順序連接起來(lái)構(gòu)成一個(gè)從起始點(diǎn)到目標(biāo)點(diǎn)的路徑。在優(yōu)化求解過(guò)程中，每個(gè)染色體的第一個(gè)和最后一個(gè)基因保持不變[28]，圖1中的黑色實(shí)線表示一條包含6個(gè)節(jié)點(diǎn)的路徑。

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

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

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

(1)

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

(2)

(2)路徑光滑程度

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

(3)

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

(4)

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

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

本文設(shè)計(jì)如式(5)所示的適應(yīng)度函數(shù)，用于每一次迭代之后評(píng)估每個(gè)染色體的優(yōu)劣，f1和f2越小，表示路徑長(zhǎng)度越短、路徑與障礙物碰撞次數(shù)越少和路徑越平滑，實(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)模擬灰狼群捕食過(guò)程中前期的圍捕獵物行為(如圖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 捕食階段

為了模擬狼群圍捕獵物的過(guò)程，在GWO算法中假設(shè)α，β，δ最接近獵物(最優(yōu)解)，每一次迭代均保存α，β，δ，其他狼在α，β，δ引導(dǎo)下重新調(diào)整位置。式(10)～式(16)表示其他狼在α，β，δ領(lǐng)導(dǎo)下位置更新的數(shù)學(xué)模型，解的更新如圖5所示，其中α，β，δ3個(gè)解表示“獵物”的估計(jì)位置，隨著算法的迭代，其他狼在α，β，δ的帶領(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)入收斂階段，即灰狼群襲擊獵物階段。建模過(guò)程中設(shè)置a隨著算法迭代從2線性遞減到0，使V的模不斷減小。當(dāng)V的模在[0,1]區(qū)間時(shí)，迭代后灰狼的位置若在當(dāng)前位置和獵物之間的任何一點(diǎn)，則表示灰狼襲擊獵物(如圖6a)，否則表示灰狼在搜索獵物(如圖6b)[25]。

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

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

(1)情形一

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

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

xB′=round

(17)

yB′=round

(18)

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

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

(2)情形二

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

(19)

(20)

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

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

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

2.7 避障算子

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

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

(21)

(22)

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

2.8 初始解生成算法

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

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

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

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

由于傳統(tǒng)的用于判斷路徑片段與障礙物是否相交的算法復(fù)雜且效率較低，求解AGV路徑規(guī)劃時(shí)耗時(shí)較長(zhǎng)，為此本文基于二元函數(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點(diǎn)的坐標(biāo)。

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

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

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

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

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

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

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

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

(1)界面介紹

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

(2)參數(shù)輸入

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

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

采用如圖12所示的AGV路徑規(guī)劃算法集成仿真原型平臺(tái)，設(shè)計(jì)如圖14、圖16、圖18和圖20所示的4個(gè)地圖情景(稱為Map1，Map2，Map3，Map4)，并采用改進(jìn)GWO算法、單種群GA、多種群GA和改進(jìn)GA 4種算法進(jìn)行求解，對(duì)比求解結(jié)果證明本文設(shè)計(jì)的改進(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ī)劃問題時(shí)，由于搜索能力較差，很快陷入局部極小值，而改進(jìn)GWO算法逐漸收斂到最優(yōu)解，表現(xiàn)出了較好的全局搜索和局部開發(fā)能力。同時(shí)，改進(jìn)GWO算法規(guī)劃出的路徑?jīng)]有明顯的尖角，這是因?yàn)榈捌诒苷纤阕右暂^快的速度使路徑片段避開障礙物，迭代后期帶啟發(fā)式規(guī)則的路徑微調(diào)算子對(duì)路徑進(jìn)行了充分地鄰域搜索，提高了算法的局部開發(fā)能力，使改進(jìn)GWO算法相對(duì)另外3種算法規(guī)劃出的路徑更光滑。

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

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

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

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

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

4 結(jié)束語(yǔ)

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

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

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

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

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

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