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

音凌一，向鳳紅

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

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

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

0 引 言

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

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

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

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

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

1.1.1 包圍獵物

包圍獵物行為可表示為：

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

向量A和C的計(jì)算式如下：

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

1.1.2 狩 獵

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

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

1.1.3 搜尋和攻擊獵物

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

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

1.2.1 拉丁超立方抽樣

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

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

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

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

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

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

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

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

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

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

2 環(huán)境建模

2.1 柵格法三維建模

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

2.2 降維和升維

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

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

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

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

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

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

計(jì)算起點(diǎn)到終點(diǎn)的高度差，按照每個(gè)節(jié)點(diǎn)之間距離的比值來(lái)分配三維空間中移動(dòng)機(jī)器人上升的 高度。

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

圖2 地圖處理對(duì)比

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

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

3 仿真實(shí)驗(yàn)

為證明灰狼勢(shì)場(chǎng)算法的性能，在Matlab R2018b上進(jìn)行仿真實(shí)驗(yàn)，建立1 000×100×250大小的三維柵格地圖，并與遺傳算法（Genetic Algorithm，GA）、 粒子群算 法（Particle swarm optimization，PSO）及GWO算法對(duì)比。其中，設(shè)路徑規(guī)劃起點(diǎn)為（50，950，120），終點(diǎn)為（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；人工勢(shì)場(chǎng)法靜態(tài)和動(dòng)態(tài)障礙物影響范圍為15 m。最后，設(shè)置未知?jiǎng)討B(tài)障礙物，進(jìn)行動(dòng)態(tài)避障仿真實(shí)驗(yàn)，以驗(yàn)證灰狼勢(shì)場(chǎng)法的動(dòng)態(tài)避障能力。

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

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

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

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

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

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

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

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

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

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

4 結(jié) 語(yǔ)

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