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

音凌一，向鳳紅

（昆明理工大學(xué) 信息工程與自動化學(xué)院，云南 昆明 650000）

路徑規(guī)劃是指，在給定的環(huán)境中，根據(jù)指定的評價標(biāo)準(zhǔn)，規(guī)劃出一條從起點到目標(biāo)點的可行路徑，并保證移動機(jī)器人在不會碰撞障礙物的前提下優(yōu)化路徑[1]。路徑規(guī)劃已在眾多領(lǐng)域得到應(yīng)用，包括移動機(jī)器人[2]、水下機(jī)器人[3]以及自動引導(dǎo)車[4]（Automated Guided Vehicle，AGV）等。然而，目前研究路徑規(guī)劃的算法大多數(shù)都是建立在二維環(huán)境中，忽略了三維環(huán)境的求解，因此，對三維環(huán)境中的路徑規(guī)劃進(jìn)行研究是非常有必要的。

灰狼優(yōu)化算法（Grey Wolf Optimization，GWO）是一種模擬灰狼捕獵行為而得到的新型群智能優(yōu)化算法，較其他群智能算法相比，具有調(diào)整參數(shù)少、易于實現(xiàn)以及有較強(qiáng)的全局搜索能力等優(yōu)點[5]，已經(jīng)在調(diào)度問題[6]、求解約束優(yōu)化問題[7]、高維優(yōu)化問題[8]以及路徑規(guī)劃問題[9]等方面得到成功的應(yīng)用。劉長安[10]等通過設(shè)計基于貪婪思想初始化策略和動靜態(tài)加權(quán)的位置更新公式，改進(jìn)灰狼優(yōu)化算法，并成功應(yīng)用在三維路徑規(guī)劃問題上；姚鵬[11]等將流

0 引 言

體擾動算法和灰狼優(yōu)化算法相結(jié)合，在三維路徑規(guī)劃中具有良好的效果；DEWANGAN[12]等將灰狼優(yōu)化算法運(yùn)用在多機(jī)器人三維路徑規(guī)劃中，并與粒子群優(yōu)化算法、鯨魚優(yōu)化算法及正余弦優(yōu)化算法進(jìn)行對比，表明灰狼優(yōu)化算法有著最優(yōu)的性能。

基于以上研究，本文提出一種基于改進(jìn)灰狼優(yōu)化 算 法（Improved Gray Wolf Optimization，IGWO）的移動機(jī)器人三維路徑規(guī)劃。首先，為提高灰狼優(yōu)化算法的性能，改進(jìn)初始化種群的方法，利用超立方體抽樣提高初始種群的質(zhì)量，提出相對位置的概念，利用個體的相對位置動態(tài)調(diào)整前三狼的比重；其次，為降低三維空間的復(fù)雜度，提出降維-升維的地圖處理方法，通過將三維環(huán)境降維達(dá)到簡化地圖的目的；最后，融合人工勢場法，獲得對未知動態(tài)障礙物避障的能力。仿真結(jié)果證明，相比于遺傳算法、粒子群算法及灰狼算法，改進(jìn)的灰狼算法進(jìn)行路徑規(guī)劃時所需間更短、路徑更優(yōu)且節(jié)點更少。

1 改進(jìn)灰狼優(yōu)化算法

1.1 灰狼優(yōu)化算法原理

在灰狼種群中，種群內(nèi)部一般分為4個等級：第1級是α狼，領(lǐng)導(dǎo)整個種群的個體；第2級是β狼，主要輔助α狼進(jìn)行決策；第3級是δ狼，執(zhí)行偵查和放哨等任務(wù)；第4級是ω狼，是最底層的灰狼，服從前三級狼的指揮。灰狼優(yōu)化算法就是對灰狼種群按等級制度進(jìn)行捕獵行為的數(shù)學(xué)模擬，具體的數(shù)學(xué)描述如下。

1.1.1 包圍獵物

包圍獵物行為可表示為：

式中：t是當(dāng)前的迭代次數(shù)，A和C是協(xié)同向量系數(shù)；Xp(t)是獵物的位置向量；X是灰狼的位置 向量。

向量A和C的計算式如下：

式中：a在迭代過程中從2線性減少到0，r1和r2是 [0，1]中的隨機(jī)向量。

1.1.2 狩 獵

狩獵行為的數(shù)學(xué)表示為：

式中：Xα、Xβ和Xδ分別是最優(yōu)解、次優(yōu)解和第三優(yōu)解的位置，Dα、Dβ和Dδ分別是灰狼個體到α狼、β狼和δ狼的距離。

1.1.3 搜尋和攻擊獵物

灰狼群體主要依靠α狼、β狼和δ狼的位置信息來進(jìn)行捕獵，在數(shù)學(xué)描述中主要根據(jù)向量A來控制灰狼是搜尋獵物還是攻擊獵物。當(dāng)|A|＜1，強(qiáng)迫灰狼攻擊獵物；當(dāng)|A|＞1，迫使灰狼遠(yuǎn)離獵物，擴(kuò)大搜索范圍，去尋找下一個獵物。

1.2 改進(jìn)灰狼優(yōu)化算法

1.2.1 拉丁超立方抽樣

傳統(tǒng)GWO算法通常采用隨機(jī)生成的數(shù)據(jù)作為初始種群來求解問題，這種方法建立的初始種群，因為其隨機(jī)性，無法保證種群的多樣性以及種群的均勻分布?，F(xiàn)有的大多數(shù)改進(jìn)是采用Logistic映射來進(jìn)行種群初始化，但具有在[0，0.1]和[0.9，1]區(qū)域取值概率較高及映射遍歷不均勻的缺點。拉丁超立方抽樣用于初始化種群，可以保證全空間填充和抽樣重疊的優(yōu)點。為保持種群的多樣性，使初始種群在迭代開始，盡可能地均勻分布在解空間內(nèi)。因此本文采用拉丁超立方抽樣進(jìn)行種群的初始化。具體過程如下。

（1）確定抽樣規(guī)模H。

（2）將每維變量xi的定義域區(qū)間[xli,xui]劃分成H個相等的小區(qū)間這樣就將原來的一個超立方體劃分成H n個小超立方體。

（3）產(chǎn)生一個H×n的矩陣A，A的每一列都是數(shù)列1，2，…，H的一個隨機(jī)全排列。

（4）A的每行對應(yīng)一個被選中的小超立方體，在每個被選中的小超立方體內(nèi)隨機(jī)產(chǎn)生一個樣本。

圖1是利用超立方體抽樣進(jìn)行種群初始化的結(jié)果，可以明顯看出，個體在解空間中是均勻分布的，同時不存在重復(fù)的個體，說明利用超立方體抽樣進(jìn)行初始化種群是有效的。

圖1 超立方體抽樣種群初始化結(jié)果

1.2.2 動態(tài)權(quán)重

為加快算法的收斂速度，本文提出一種根據(jù)距離比自適應(yīng)調(diào)節(jié)的位置更新公式。在迭代過程中，計算所有灰狼個體分別與α狼、β狼、δ狼之間的距離dji和平均距離dj(j=α、β、δ)，再計算出前三狼平均距離的平均值da。用距離dji與da的比值dji_site來表示個體與前三狼相對位置的遠(yuǎn)近。利用每個迭代中個體距離α、β和δ狼相對位置的不同，來自適應(yīng)調(diào)節(jié)位置更新公式中α、β和δ狼的比重。相關(guān)計算式如下：

式中：dji是第i只灰狼與j狼的距離，Xi是第i只灰狼的位置，Xj是前三狼的位置，dj是前三狼當(dāng)前迭代的平均距離，dji_site是第i只狼與j狼的相對距離，f1、f2和f3分別是所有灰狼個體與前三狼相對距離的求和。

2 環(huán)境建模

2.1 柵格法三維建模

利用柵格法進(jìn)行三維建模，首先需將障礙物進(jìn)行膨脹處理，使不規(guī)則形狀的障礙物膨脹成規(guī)則形狀，然后再對有限的范圍空間進(jìn)行分割，使整個范圍分割成n個立方體，其中障礙物柵格賦值為1，自由柵格賦值為0，每個自由柵格的中點為路徑的節(jié)點。由此可知，在等大空間中，n的值越大，立方體越小，環(huán)境的分辨率越高；n的值越小，立方體越大，環(huán)境的分辨率越低。但n值越大，地圖分辨率越高，算法求解路徑規(guī)劃的效率也就越低；n值越小，地圖分辨率越低，算法的求解精度越低。所以對地圖進(jìn)行預(yù)處理，在保證求解精度的同時，提高求解效率，是很有必要的。

2.2 降維和升維

為了在保證求解精度的同時，降低地圖的復(fù)雜度，提高求解效率，本文提出一種降維-升維的三維建模方法，具體步驟如下。

（1）建立1 000×1 000×250大小的三維坐標(biāo)系，設(shè)置起點（50，950，120）和終點（950，50，10）， 將障礙物膨脹成規(guī)則形狀，其中黑色柵格是障礙物柵格，白色柵格是自由柵格。

（2）從上方俯視整個三維地圖，將整個三維地圖投射到XOY平面上，其中起點為（50，950），終點為（950，50）。

對每個障礙再次進(jìn)行膨脹處理，膨脹的距離是離最近的障礙物距離的一半。

（4）將膨脹后的頂點作為特征點，對兩兩特征點的可視性進(jìn)行判斷，建立鄰接矩陣C，在鄰接矩陣C中進(jìn)行求解，輸出路徑L{P1,P2,P3,…,Pn}。

（5）判斷P1與其他節(jié)點的連線是否經(jīng)過障礙物，若存在節(jié)點Pk與P1的連線不經(jīng)過障礙物，刪除P1與Pk之間的節(jié)點；若不存在Pk點，則對P2點進(jìn)行判斷。重復(fù)以上操作直到Pn-1點。

計算起點到終點的高度差，按照每個節(jié)點之間距離的比值來分配三維空間中移動機(jī)器人上升的 高度。

經(jīng)過降維-升維處理后的路徑如圖2（a）所示，長度為1 331.84 m，算法求解時間為3.23 s；未地圖處理的路徑如圖2（b）所示，路徑長度為1 457.13 m，算法求解時間為9.00 s。對比可知，經(jīng)過降維-升維的處理，路徑優(yōu)化了125.29 m，求解時間優(yōu)化了5.77 s。說明降維-升維的地圖處理方法能有效地加強(qiáng)灰狼優(yōu)化算法求解路徑規(guī)劃問題的效率，縮短最優(yōu)路徑的長度。

圖2 地圖處理對比

2.3 局部動態(tài)障礙物避障

文獻(xiàn)[13]用A*算法與人工勢場法融合，證明與人工勢場法融合可以使A*算法獲得一定的動態(tài)避障能力。為使IGWO算法獲得動態(tài)避障能力，本文把改進(jìn)灰狼算法全局路徑規(guī)劃的節(jié)點作為人工勢場法的臨時節(jié)點，將改進(jìn)灰狼優(yōu)化算法與人工勢場法相結(jié)合，以達(dá)到動態(tài)避障的目的，最后利用仿真驗證融合后的算法的動態(tài)避障性能。

3 仿真實驗

為證明灰狼勢場算法的性能，在Matlab R2018b上進(jìn)行仿真實驗，建立1 000×100×250大小的三維柵格地圖，并與遺傳算法（Genetic Algorithm，GA）、 粒子群算 法（Particle swarm optimization，PSO）及GWO算法對比。其中，設(shè)路徑規(guī)劃起點為（50，950，120），終點為（950，50，10），算法的初始種群N=30，最大迭代次數(shù)tmax=100，GA算法中交叉概率為0.8，變異概率為0.1；PSO算法中學(xué)習(xí)因子c1=c2=2，慣性權(quán)值ωini=0.9，ωend=0.4；人工勢場法靜態(tài)和動態(tài)障礙物影響范圍為15 m。最后，設(shè)置未知動態(tài)障礙物，進(jìn)行動態(tài)避障仿真實驗，以驗證灰狼勢場法的動態(tài)避障能力。

3.1 全局靜態(tài)環(huán)境仿真

各算法在相同地圖中求解三維路徑規(guī)劃的結(jié)果如圖3所示。圖3（a）、（b）、（c）、（d）是未經(jīng)過降維-升維處理地圖的求解結(jié)果，可以明顯看出，IGWO算法的求解結(jié)果節(jié)點數(shù)最少，路徑最優(yōu)，說明對傳統(tǒng)GWO算法進(jìn)行提高種群質(zhì)量及動態(tài)權(quán)重的改進(jìn)，有利于改進(jìn)算法的求解精度和質(zhì)量。圖3（e）是經(jīng)過降維-升維處理后IGWO算法的求解結(jié)果，對比圖3（d）可以明顯看出，路徑的節(jié)點數(shù)進(jìn)一步減少，說明降維-升維處理方法優(yōu)化了路徑長度。

圖3 路徑規(guī)劃結(jié)果

表1是各算法在1 000×100×250三維地圖上運(yùn)行20次的平均結(jié)果，可以看出，IGWO算法的求解結(jié)果相比于GA算法、PSO算法和GWO算法，路徑長度上優(yōu)化了208.44 m、91.57 m和58.89 m，節(jié)點數(shù)減少了10個、8個和16個，僅在求解時間上略差于PSO算法，說明超立方體策略和動態(tài)權(quán)重提高了算法求解精度和求解速度；降維IGWO算法求解結(jié)果相比于GA算法、PSO算法、GWO算法和IGWO算法，求解時間減少了11.57 s、5.12 s、8.88 s 和5.77 s，路徑長度優(yōu)化了333.73 m、216.86 m、184.18 m和125.29 m，節(jié)點數(shù)減少了19個、17個、25個和9個，說明降維-升維的地圖處理方法對算法求解路徑規(guī)劃問題的效率及減少路徑長度有著一定積極作用。

表1 20次仿真平均結(jié)果

3.2 局部動態(tài)環(huán)境仿真

在3.1節(jié)的三維環(huán)境中，增加兩個動態(tài)障礙物，再用融合算法進(jìn)行路徑規(guī)劃求解。融合算法的路徑規(guī)劃結(jié)果如圖4所示。

圖4 增加局部動態(tài)障礙物后的規(guī)劃路徑

圖5（a）和圖5（b）分別是路徑在動態(tài)障礙 物1處的放大和路徑在動態(tài)障礙物2處的放大，其中黑色的是動態(tài)障礙物運(yùn)動軌跡?？梢悦黠@看出與人工勢場法的結(jié)合，使IGWO算法成功對未知動態(tài)障礙物進(jìn)行避障，表明算法具有動態(tài)避障能力。

圖5 動態(tài)障礙物放大

4 結(jié) 語

本文對傳統(tǒng)灰狼算法進(jìn)行改進(jìn)，提出超立方體抽樣初始化種群策略和動態(tài)權(quán)重，并與傳統(tǒng)灰狼算法在求解路徑規(guī)劃問題上進(jìn)行對比，證明了改進(jìn)策略能有效地提高灰狼優(yōu)化算法的收斂精度和收斂速度；采用降維-升維地圖處理方法，降低了三維地圖的復(fù)雜性，提高了灰狼優(yōu)化算法求解路徑規(guī)劃問題的效率及精度；利用人工勢場法，成功地對局部未知的動態(tài)障礙物進(jìn)行避障，使改進(jìn)的灰狼優(yōu)化算法擁有一定的動態(tài)避障能力。