基于改進(jìn)灰狼算法的數(shù)控車間AGV路徑規(guī)劃研究

李泓坤

（西安工業(yè)大學(xué)，陜西西安，710021）

0 引言

自動(dòng)導(dǎo)引小車 (Automated Guided Vehicle，AGV)屬于輪式移動(dòng)機(jī)器人，其以自動(dòng)導(dǎo)引裝置為核心構(gòu)件，可以按照既定的導(dǎo)航路線平穩(wěn)行駛[1]。在數(shù)控車間等領(lǐng)域內(nèi)，AGV主要被用作配送物料，整體表現(xiàn)出了操作門檻低、構(gòu)造簡(jiǎn)單的特點(diǎn)。但是其在實(shí)踐應(yīng)用中也面臨著一些挑戰(zhàn)，最為棘手的就是AGV路徑規(guī)劃問題。

AGV路徑規(guī)劃直接關(guān)系到AGV的行進(jìn)效率。路徑尋優(yōu)算法是路徑規(guī)劃的核心，依據(jù)理論的不同，AGV路徑規(guī)劃技術(shù)可分為基于采樣的圖搜索算法、基于節(jié)點(diǎn)的搜索算法、基于模型的方法、基于生物啟發(fā)式算法等方法。粒子群算法、模擬退火算法、遺傳算法等都是典型的啟發(fā)式算法。生物啟發(fā)式算法相較于傳統(tǒng)路徑規(guī)劃算法，減少了對(duì)數(shù)學(xué)模型的依賴，全局尋優(yōu)能力強(qiáng)，在AGV規(guī)劃研究中已經(jīng)得到大量的實(shí)際應(yīng)用。

灰狼優(yōu)化 (grey wolf optimization， GWO)[2]算法作為一種生物啟發(fā)算法，具有結(jié)構(gòu)簡(jiǎn)單、需要設(shè)置的參數(shù)少和在實(shí)驗(yàn)編碼中易實(shí)現(xiàn)等優(yōu)點(diǎn)。然而，過去普遍采用GWO算法應(yīng)對(duì)AGV的路徑規(guī)劃問題，此算法與生俱來的一些缺陷難以保證機(jī)器人的運(yùn)動(dòng)效率，會(huì)造成碰撞的可能，這些缺陷主要是易陷入局部極值、全局勘探與局部開發(fā)失調(diào)、初始種群過于單一等。

本課題結(jié)合GWO算法的上述缺陷，提出了一種改進(jìn)灰狼優(yōu)化算法（IGWO），在求解AGV全局路徑規(guī)劃問題時(shí)，通過改良，使得灰狼優(yōu)化算法能夠更好地適應(yīng)數(shù)控車間環(huán)境，并基于此給出穩(wěn)定的路徑尋優(yōu)結(jié)果，這樣就能確保AGV始終選擇最佳路徑行駛，從而保證導(dǎo)航的準(zhǔn)確性，并避免碰撞。

1 灰狼算法

GWO算法屬于新型群體智能優(yōu)化算法，其基本原理是對(duì)灰狼群體在自然界內(nèi)生存時(shí)所存在的捕獵行為和社會(huì)等級(jí)機(jī)制進(jìn)行模擬，對(duì)于此算法而言，灰狼種群內(nèi)任意灰狼都是一個(gè)可能的候選解，群體中包含的的最優(yōu)解、次最優(yōu)解、第三最優(yōu)解分別用α，β，δ表示，其他候選的解都用ω表示。然后我們用D 表示灰狼種群的大小，用D 表示搜索空間，那么就代表第D維空間內(nèi)第i只灰狼的位置。灰狼群體通過式（1）逐漸接近并包圍獵物：

2 改進(jìn)灰狼算法

2.1 基于混沌的種群初始化方法

skew tent映射是一種由簡(jiǎn)單的確定性系統(tǒng)產(chǎn)生的隨機(jī)性序列，混沌映射被用于生成混沌序列。在優(yōu)化領(lǐng)域，混沌映射可以用于替代偽隨機(jī)數(shù)生成器，生成0到1之間的混沌數(shù)。經(jīng)過實(shí)驗(yàn)證明，利用混沌序列進(jìn)行種群初始化、選擇、交叉和變異等操作會(huì)影響算法的整個(gè)過程，而且常常能取得比偽隨機(jī)數(shù)更好的效果。

本文先初始化處理了目標(biāo)種群，具體是基于skew tent映射得到混沌序列實(shí)現(xiàn)的，這樣就可以確保解空間的信息被初始群眾個(gè)體充分利用，同時(shí)確保最終解的完整性，其函數(shù)式如下所示[3]：

當(dāng)φ∈(0,1)且x∈[0,1]時(shí)，系統(tǒng)處于混沌狀態(tài)。

2.2 IGWO算法步驟

結(jié)合如上分析，得出下表1所示的高效灰狼優(yōu)化算法（簡(jiǎn)稱IGWO）的詳細(xì)步驟。

算法 1 IGWO 算法begin算法參數(shù)設(shè)置：N-種群大小；t -距離控制參數(shù)a的初始值；a max -最大迭代次數(shù)；ainitial-距離控制參數(shù)a的終止值。基于skew tent混沌初始化得到final灰狼種群對(duì)群體內(nèi)所有個(gè)體的適應(yīng)度進(jìn)行求解，{X i N i , 1,2, ,= …}{f X i N( )i , 1,2,,= …}，然后對(duì)最

優(yōu)個(gè)體、次最優(yōu)個(gè)體、第三最優(yōu)個(gè)體α、β、δ進(jìn)行記錄，用X β表示其對(duì)應(yīng)位置。)d o f o r i=1 t o N d o f o r j=1 t o D d o對(duì)距離控制參數(shù)a的值進(jìn)行求解。代入公式（2）和（3）對(duì)參數(shù)A和C的值進(jìn)行求解。代入公式（6）完成個(gè)體位置的更新。e n d f o r e n d f o r對(duì)群體內(nèi)所有個(gè)體的適應(yīng)度進(jìn)行求解，w h i l e(t＜t m a x{f X i N( )i , 1,2, ,= …}然后對(duì)最優(yōu)個(gè)體、次最優(yōu)個(gè)體、第三最優(yōu)個(gè)體α、β、δ進(jìn)行記錄，用X β表示其對(duì)應(yīng)位置t=t+1;e n d w h i l e e n d

2.3 路徑尋優(yōu)約束條件與適應(yīng)度函數(shù)

選擇最優(yōu)路徑的期間，假設(shè)機(jī)器人的某條行駛路線便是任意灰狼捕獵期間位置更新時(shí)對(duì)應(yīng)的坐標(biāo)集，IGWO算法按照優(yōu)化策略，在路徑集合當(dāng)中選出一條與約束條件高度匹配的路徑，約束條件如下。

(1)路徑連續(xù)性條件

移動(dòng)路徑不能有迂回狀況，即節(jié)點(diǎn)的縱向坐標(biāo)或是橫向坐標(biāo)，相對(duì)于下一個(gè)節(jié)點(diǎn)兩者只能有一個(gè)是在單調(diào)遞增，假設(shè)機(jī)器人由當(dāng)前節(jié)點(diǎn)(x1, y1)移動(dòng)到下一節(jié)點(diǎn)(x2, y2)應(yīng)至少滿足(x2＞x1)或(y2＞y1)。

(2)環(huán)境邊界與障礙物約束條件

移動(dòng)路徑必須限定在固定圖幅邊界的柵格區(qū)域內(nèi)，且移動(dòng)路徑節(jié)點(diǎn)及節(jié)點(diǎn)間的連線禁止穿過障礙物柵格。

(3)目標(biāo)路徑最短條件

在滿足約束條件(1)、(2)下的諸多柵格位置中，第j( j = 1 ,2,...Ny)行柵格應(yīng)選橫坐標(biāo)最小值i( 1 ＜ i＜Nx)作為最終路徑節(jié)點(diǎn)(xi, yi)，以達(dá)到路徑最短條件，即IGWO算法規(guī)劃結(jié)果中適應(yīng)度函數(shù)須取最小值。

數(shù)控車間環(huán)境在路徑尋優(yōu)過程中，以對(duì)角線距離作為適應(yīng)度函數(shù)。

3 AGV運(yùn)行環(huán)境建模

本文采用柵格地圖表示法[5]表示數(shù)控車間環(huán)境，將數(shù)控車間中 AGV 運(yùn)行環(huán)境視為由多柵格組成的矩形，且每個(gè)柵格大小相同。考慮到數(shù)控車間下機(jī)床對(duì)AGV運(yùn)行路徑的影響，對(duì)機(jī)床柵格進(jìn)行膨脹處理。后續(xù)驗(yàn)證采用八方向搜索節(jié)點(diǎn)方法，即AGV可到達(dá)相鄰位置的8個(gè)節(jié)點(diǎn)。

通過以上研究，基于數(shù)字仿真軟件測(cè)試平臺(tái)構(gòu)建了一個(gè)37×23數(shù)控車間柵格地圖。其中黑色為機(jī)床位置，紅色為AGV充電位置，綠色為車間倉庫位置。

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

本文以計(jì)算機(jī)作為仿真實(shí)驗(yàn)平臺(tái)，其CPU型號(hào)為Intel(R) Core(TM) i5-10200H，內(nèi)存為 16GB，處理器主頻為 2.4 GHz，操作系統(tǒng)為 Windows 10，采用 MATLAB R2021b 軟件進(jìn)行仿真操作。

下表1列出了本次實(shí)驗(yàn)的算法參數(shù)，以應(yīng)用路徑規(guī)劃時(shí)對(duì)比算法所需搜索空間和對(duì)比算法所在原文獻(xiàn)為依據(jù)對(duì)種群大小、最大迭代次數(shù)進(jìn)行設(shè)置，以保證所得結(jié)果的準(zhǔn)確性與客觀性。

表1 仿真實(shí)驗(yàn)中的算法參數(shù)設(shè)置

4.1 路徑規(guī)劃仿真

為了驗(yàn)證本文提出的IGWO算法有效性，通過對(duì)柵格地圖設(shè)置不同的AGV初始位置，物料轉(zhuǎn)送位置和最終停車位置，從尋優(yōu)效率、路徑長度等優(yōu)化性能方面橫向?qū)Ρ鹊腉WO算法和IGWO算法的仿真試驗(yàn)結(jié)果，實(shí)驗(yàn)次數(shù)為30。

PSO算法沒無法在全局內(nèi)搜索最優(yōu)路徑，而且路徑尋優(yōu)收斂效率較低，期間還出現(xiàn)了搜索停滯的現(xiàn)象（陷入局部極值導(dǎo)致）。在迭代前期，GA算法有著十分可觀的收斂速度，但與其他啟發(fā)式算法相比，其也出現(xiàn)了局部收斂的問題，而且比較頻繁；SA算法也有著理想的收斂速度，全局路徑規(guī)劃表現(xiàn)較好，但仍存在多次實(shí)驗(yàn)所得最優(yōu)路徑值不穩(wěn)定等問題；GWO算法不但在初始階段擁有理想的收斂速度之外，中后期搜索還協(xié)調(diào)了局部開發(fā)。由此可見，本文提出的IGWO算法有效彌補(bǔ)了傳統(tǒng)GWO算法優(yōu)化方面的缺陷，具有十分理想的搜索能力和收斂能力。

從表2得出：相較于傳統(tǒng)GWO算法，本文提出的IGWO算法平均路徑長度更短且得到穩(wěn)定性更強(qiáng)的結(jié)果，算法同時(shí)具有理想的收斂速度，因此尋優(yōu)耗時(shí)也變相縮短了。

表2 環(huán)境1中30次實(shí)驗(yàn)的算法性能對(duì)比

5 結(jié)論

本文對(duì)灰狼算法進(jìn)行改進(jìn)，以求解數(shù)控車間AGV全局路徑規(guī)劃問題，基于路徑規(guī)劃仿真實(shí)驗(yàn)結(jié)果，得到幾點(diǎn)結(jié)論，具體如下：

（1）本文提出的IGWO算法通過引入Tent混沌映射來保證灰狼種群初始化的均勻性，這樣就能很好地克服傳統(tǒng)GWO算法初始群眾分布不均的問題，同時(shí)還能使得算法在路徑尋優(yōu)初期的收斂速度得以提升，在路徑尋優(yōu)期間，此算法在綜合勘探和避障方面的表現(xiàn)十分出色，一定程度上彌補(bǔ)了傳統(tǒng)GWO算法全局算法與局部開發(fā)不協(xié)調(diào)的缺陷，使得算法在路徑尋優(yōu)最后階段能較為準(zhǔn)確地鎖定全局最優(yōu)解。

（2）全局路徑規(guī)劃仿真實(shí)驗(yàn)表明，在數(shù)控車間場(chǎng)景下，IGWO算法計(jì)算所得的路徑有效、合理。相對(duì)比于傳統(tǒng)GWO算法、GA算法、SA算法、PSO算法，本文IGWO算法在路徑尋優(yōu)能力、收斂效率、尋優(yōu)結(jié)果穩(wěn)定性等方面具有一定的優(yōu)越性。

（3）本文提出的IGWO算法相較于傳統(tǒng)啟發(fā)式算法具有結(jié)構(gòu)簡(jiǎn)單、計(jì)算復(fù)雜度較小、全局搜索能力較強(qiáng)等優(yōu)勢(shì)。本文所提的各項(xiàng)改進(jìn)策略可為其他啟發(fā)式群智能算法的優(yōu)化改進(jìn)以求解全局路徑規(guī)劃問題提供參考。