基于改進(jìn)灰狼優(yōu)化算法的區(qū)域監(jiān)測(cè)機(jī)器人路徑規(guī)劃

李 靖, 楊 帆,2*

(1.河北工業(yè)大學(xué)電子信息工程學(xué)院，天津 300401；2.河北工業(yè)大學(xué)天津市電子材料與器件重點(diǎn)實(shí)室，天津 300401)

路徑規(guī)劃是機(jī)器人控制領(lǐng)域研究的重點(diǎn)和熱點(diǎn)問(wèn)題，也是機(jī)器人順利完成各項(xiàng)作業(yè)任務(wù)的前提條件。按照算法的基本原理，可以將路徑規(guī)劃算法分為傳統(tǒng)算法、圖形學(xué)算法、群智能算法以及深度學(xué)習(xí)算法。傳統(tǒng)算法主要有人工勢(shì)場(chǎng)法[1]、模糊邏輯算法[2]、禁忌搜索算法[3]等，其缺點(diǎn)在于建模困難，具有一定的局限性。圖形學(xué)算法主要有C空間法[4]、自由空間法[5]、柵格法[6]、voronoi圖法[7]等，其優(yōu)點(diǎn)在于建模簡(jiǎn)單，但其搜索能力不足，對(duì)于大規(guī)模任務(wù)量的路徑搜索具有局限性。群智能算法主要有粒子群算法(particle swarm optimization,PSO)[8]、蟻群算法(ant colony optimization,ACO)[9]、遺傳算法(genetic algorithm,GA)[10]、鯨魚(yú)算法(whale optimization algorithm,WOA)[11]、灰狼優(yōu)化算法(grey wolf optimizer,GWO)[12]等，運(yùn)用自然啟發(fā)的智能仿生學(xué)算法，往往可以解決環(huán)境相對(duì)復(fù)雜的場(chǎng)景，但是其計(jì)算量相對(duì)前兩種會(huì)更高些。此外，還有深度學(xué)習(xí)路徑規(guī)劃算法[13]，其魯棒性最高，但需要大數(shù)據(jù)集的支撐，訓(xùn)練、驗(yàn)證、測(cè)試迭代導(dǎo)致時(shí)間復(fù)雜度大，且需要高要求的硬件支撐，對(duì)小樣本數(shù)據(jù)集無(wú)法進(jìn)行無(wú)偏差的估計(jì)。

針對(duì)大任務(wù)量區(qū)域監(jiān)測(cè)場(chǎng)景，綜合考慮四類(lèi)路徑規(guī)劃算法的優(yōu)缺點(diǎn)，群智能算法更加符合精度與速度的要求。楊桂華等[14]融合了確定性選擇與隨機(jī)性選擇策略，將改進(jìn)蟻群算法用于室內(nèi)移動(dòng)機(jī)器人路徑規(guī)劃算法。黃長(zhǎng)強(qiáng)等[15]改進(jìn)蟻獅算法進(jìn)行航跡規(guī)劃，將混沌調(diào)節(jié)因子引入螞蟻群體，將反調(diào)節(jié)因子引入蟻獅行為中，提高了探索能力和開(kāi)發(fā)能力。余勝東等[16]提出了應(yīng)用混沌螢火蟲(chóng)算法的無(wú)人機(jī)航跡規(guī)劃，引入立方映射混沌算子來(lái)提高了局部搜索能力和魯棒性。

GWO算法自提出以來(lái)，就因其在尋優(yōu)的良好性能，結(jié)構(gòu)簡(jiǎn)單，易實(shí)現(xiàn)等優(yōu)點(diǎn)被廣泛關(guān)注。GWO算法在收斂速度和求解精度上優(yōu)于PSO算法已經(jīng)被驗(yàn)證[12]，但其仍具有提升空間。如王秋萍等[17]采用余弦規(guī)律的搜索因子，引入了動(dòng)態(tài)權(quán)重策略，平衡全局搜索和局部開(kāi)發(fā)能力，提高了GWO算法的求解精度。郭振洲等[18]運(yùn)用指數(shù)函數(shù)衰減搜索因子α，使收斂因子隨著迭代次數(shù)的增加非線性動(dòng)態(tài)變化，在搜索與開(kāi)發(fā)階段尋求平衡，以確保逼近最優(yōu)解。徐松金等[19]引入了隨機(jī)收斂因子以平衡搜索能力，引入了差分變異進(jìn)行個(gè)體更新，以提高算法收斂與精確度。

基于上述分析，提出了一種基于改進(jìn)灰狼優(yōu)化算法的區(qū)域監(jiān)測(cè)機(jī)器人路徑規(guī)劃方法。首先引入Logistic混沌映射、自適應(yīng)調(diào)整策略、靜態(tài)加權(quán)平均權(quán)重策略改進(jìn)灰狼優(yōu)化算法，隨后將機(jī)器人載電量、路徑長(zhǎng)度短作為約束，引入K-means算法進(jìn)行任務(wù)聚類(lèi)，通過(guò)改進(jìn)的灰狼優(yōu)化算法(improved grey wolf optimizer,IGWO)算法對(duì)模型進(jìn)行離線求解，規(guī)劃出路線，將大任務(wù)量監(jiān)測(cè)作業(yè)自動(dòng)轉(zhuǎn)換成分時(shí)分步作業(yè)，為機(jī)器人自動(dòng)自主區(qū)域監(jiān)測(cè)任務(wù)奠定了基礎(chǔ)。

1 問(wèn)題建模

假設(shè)區(qū)域工作環(huán)境地圖已知，T={T1,T2,…,Tn}為任務(wù)點(diǎn)集合，O為機(jī)器人投放點(diǎn)(起點(diǎn))位置，要求Robot遍歷n個(gè)任務(wù)點(diǎn)，且需回到起點(diǎn)，遍歷路徑為R={O,T1,T2,…,Tn，O}，則路徑長(zhǎng)度L為

(1)

以機(jī)器人電量消耗進(jìn)行約束，機(jī)器人作業(yè)需要消耗電量，機(jī)器人全程作業(yè)任務(wù)消耗到電量為

q=ruL

(2)

式(2)中：ru為機(jī)器人單位距離消耗的電量。

為了機(jī)器人能夠順利完成任務(wù)并能返回出發(fā)地聚集，要求機(jī)器人作業(yè)任務(wù)的電量消耗q，要小于機(jī)器人帶電量Q，可以表示為

q

(3)

以大任務(wù)量巡查監(jiān)測(cè)作業(yè)為背景，通過(guò)機(jī)器人定點(diǎn)巡視，當(dāng)發(fā)現(xiàn)異常點(diǎn)，便調(diào)度臨近的機(jī)器人群到達(dá)指定異常點(diǎn)進(jìn)行檢查，排除故障，實(shí)現(xiàn)自動(dòng)監(jiān)測(cè)，自主完成作業(yè)的目的。首先改進(jìn)傳統(tǒng)灰狼優(yōu)化算法，加強(qiáng)求解能力；隨后通過(guò)改進(jìn)的灰狼優(yōu)化算法求解在電量約束下的問(wèn)題建模模型，遍歷任務(wù)點(diǎn)進(jìn)行監(jiān)測(cè)，發(fā)現(xiàn)異常點(diǎn)派遣臨近機(jī)器人群避障到達(dá)異常點(diǎn)，以便排除故障。

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

2.1 傳統(tǒng)灰狼優(yōu)化算法(GWO)

2.1.1 GWO算法的等級(jí)結(jié)構(gòu)

灰狼優(yōu)化算法[12]是模擬食物鏈頂端的捕食者狼群的捕食行為產(chǎn)生的算法。灰狼大都喜歡群居，且具有非常嚴(yán)格的社會(huì)等級(jí)制度，如圖1金字塔結(jié)構(gòu)的等級(jí)制度所示。

圖1 灰狼的社會(huì)等級(jí)結(jié)構(gòu)Fig.1 Hierarchy of gray wolf

2.1.2 GWO算法的數(shù)學(xué)模型

在GWO算法數(shù)學(xué)建模中，每只灰狼代表種群中 1 個(gè)候選解，將最優(yōu)解視為α，第二、第三個(gè)最佳候選解視分別為β和δ，其余的候選解視為ω。在GWO算法中，搜索(優(yōu)化)由α、β和δ引導(dǎo)，ω狼跟隨這三只狼。

D=|CXp(t)-X(t)|

(4)

X(t+1)=Xp(t)-AD

(5)

式(5)中：t表示當(dāng)前迭代次數(shù);A和C為系數(shù)向量;Xp為獵物的位置向量;D為灰狼個(gè)體與獵物之間的位置關(guān)系向量；X為灰狼的位置向量。A、C計(jì)算公式為

A=2ar1-a

(6)

C=2r2

(7)

式中:r1和r2的模是[0,1]的隨機(jī)數(shù);a為收斂因子，其數(shù)值隨著迭代次數(shù)的增加從2線性減小到0，計(jì)算公式為

(8)

式(8)中:t為當(dāng)前迭代次數(shù);tmax為最大迭代次數(shù)。

灰狼追蹤獵物位置的數(shù)學(xué)模型描述如式(9)～式(11)所示：

{Dα=|C1Xa-X|

Dβ=|C2Xβ-X|

Dδ=|C3Xδ-X|

(9)

{X1=Xα-A1Da

X2=Xβ-A2Dβ

X3=Xδ-A3Dδ

(10)

(11)

式中：C1、C2、C3為隨機(jī)向量；Dα、Dβ和Dδ分別為α狼、β狼和δ狼與狼群其他成員之間的距離；Xα、Xβ、Xδ分別為α狼、β狼和δ狼的位置；X為當(dāng)前狼的位置。狼群中ω狼的位置由α狼、β狼和δ狼共同決定。

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

2.2.1 基于Logistic映射的種群初始化

混沌具有隨機(jī)性、遍歷性和規(guī)律性的特點(diǎn)。引入混沌序列，可以使初始種群個(gè)體盡可能地利用解空間的信息，改善全局搜索能力，由于Logistic映射[20]簡(jiǎn)單混沌且遍歷均勻性較好，因此在種群初始化時(shí)，使用Logistic映射產(chǎn)生混沌序列，對(duì)狼群進(jìn)行種群位置初始化。Logistic映射的表達(dá)式如式(12)所示：

xn+1=axn(1-xn)

(12)

式(12)中：xn∈[0,1]為混沌變量；a=4。設(shè)x0=0.428 8。圖2為30個(gè)種群Logistic映射種群初始化后的氣泡圖。

圖2 基于Logistic映射的種群初始化氣泡圖Fig.2 Population initialization bubble diagram based on Logistic Mapping

2.2.2 控制參數(shù)自適應(yīng)調(diào)整策略

a對(duì)GWO算法全局搜索及局部開(kāi)發(fā)能力具有平衡作用，它隨著迭代次數(shù)的增加不斷地從2線性衰減到0，而迭代收斂的過(guò)程并不是線性的，因此，提出了一種非線性控制參數(shù)自適應(yīng)調(diào)整策略，如式(13)所示。通過(guò)調(diào)整a的自適應(yīng)值來(lái)平衡GWO算法的搜索能力和開(kāi)發(fā)能力，在迭代初期全局搜索時(shí)，a較大，非線性變化速率快，全局搜索能力強(qiáng)，避免局部最優(yōu)，在迭代后期a較小，非線性變化速率慢，則在某個(gè)區(qū)域內(nèi)尋求最優(yōu)解，開(kāi)發(fā)能力強(qiáng)，收斂速度加快。

(13)

式(13)中：t為當(dāng)前迭代次數(shù)；Tmax為最大迭代次數(shù)；n∈[1,2]為非線性調(diào)制指數(shù)；ainitial為控制參數(shù)a的初始值，ainitial=2。a的非線性衰減對(duì)比如圖3所示。

圖3 控制參數(shù)a對(duì)比Fig.3 Contrast chart of control parameter a

2.2.3 靜態(tài)加權(quán)平均策略

加權(quán)平均策略的主要思想是為三個(gè)頭狼分配配重，以顯示金字塔的層次結(jié)構(gòu)，這里引入文獻(xiàn)[17]的靜態(tài)加權(quán)平均策略，分配給α狼的權(quán)重為0.5，β狼的權(quán)重為0.3，則δ狼的權(quán)重為0.2，如式(14)所示：

(14)

3 問(wèn)題建模求解

3.1 K-means算法

K-means算法[21]是無(wú)監(jiān)督聚類(lèi)算法，不需要有任何的先驗(yàn)知識(shí)，其原理思想是基于一種劃分的思想，以距離作為數(shù)據(jù)間相似性度量的標(biāo)準(zhǔn)，數(shù)據(jù)間的距離越小，則表明相似性越高，則可以歸為一個(gè)類(lèi)簇。

根據(jù)問(wèn)題建模可知任務(wù)點(diǎn)樣本集T={T1,T2,…,Tn}，假設(shè)聚類(lèi)集合為μ={μ1,μ2,…，μk}

距離函數(shù)為

(15)

式(15)中：Tm為第m個(gè)任務(wù)；μi表示第i類(lèi)到聚類(lèi)中心。

聚類(lèi)中心更新公式為

(16)

準(zhǔn)則函數(shù)為

(17)

式中：xj表示第j類(lèi)樣本中的數(shù)據(jù)。

3.2 約束條件下IGWO算法模型求解

考慮機(jī)器人電量約束，通過(guò)檢查行駛路徑機(jī)器人所消耗的電量q是否大于機(jī)器人的載電量，如果qQ，需要對(duì)任務(wù)點(diǎn)進(jìn)行聚類(lèi)，將任務(wù)劃分成k個(gè)子任務(wù)，分別在子任務(wù)內(nèi)進(jìn)行IGWO算法求解規(guī)劃路徑，即轉(zhuǎn)換成類(lèi)旅行商問(wèn)題(traveling salesman problem，TSP)，并分別判斷子任務(wù)內(nèi)電量約束是否滿(mǎn)足qQ的情況，便重新對(duì)任務(wù)進(jìn)行k+1類(lèi)聚類(lèi)，在子任務(wù)類(lèi)內(nèi)進(jìn)行路徑規(guī)劃及電量判斷，直到子任務(wù)(k+2，k+3,…,k+m)內(nèi)路徑規(guī)劃對(duì)應(yīng)的行駛電量滿(mǎn)足q

圖4 問(wèn)題建模求解流程圖Fig.4 Flow chart of problem model solving

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

實(shí)驗(yàn)仿真環(huán)境為處理器Intel Corei7 CPU @1.8 GHz 2.0 GHz，內(nèi)存16 G，操作系統(tǒng)WIN10，64位，仿真軟件為MATLAB 2019a進(jìn)行仿真。

4.1 IGWO算法測(cè)試仿真

為了驗(yàn)證改進(jìn)灰狼優(yōu)化算法的性能，選取了國(guó)際上6個(gè)經(jīng)典基準(zhǔn)測(cè)試函數(shù)進(jìn)行測(cè)試，其中Sphere函數(shù)、Rosenbrock 函數(shù)、Schwefel’s 2.22函數(shù)為單峰測(cè)試函數(shù)、Rastrigin函數(shù)、Griewank函數(shù)和Ackley函數(shù)為多峰測(cè)試函數(shù)，測(cè)試函數(shù)的維數(shù)、定義域如表1所示。分別對(duì)PSO算法，GWO算法及IGWO算法進(jìn)行了仿真測(cè)試，其測(cè)試結(jié)果對(duì)比如圖5所示，對(duì)比平均值及標(biāo)準(zhǔn)差如表2所示。其中，種群規(guī)模設(shè)置為30，最大迭代次數(shù)設(shè)置為500次。

Sphere 函數(shù)：

(18)

Schwefel’s 2.22函數(shù)：

(19)

Rosenbrock函數(shù)：

(20)

Rastrigin函數(shù)：

(21)

Ackley函數(shù)：

(22)

Griewank函數(shù)：

(23)

表1 測(cè)試函數(shù)Table 1 Test function

圖5 基準(zhǔn)測(cè)試函數(shù)測(cè)試結(jié)果Fig.5 Benchmark function test results

表2 基準(zhǔn)測(cè)試函數(shù)優(yōu)化結(jié)果對(duì)比Table 2 Optimization comparison of test functions

實(shí)驗(yàn)結(jié)果表明，對(duì)于單峰測(cè)試函數(shù)，IGWO算法的收斂速度及精度略高于GWO算法。而對(duì)于多峰測(cè)試函數(shù)，IGWO算法的收斂速度遠(yuǎn)遠(yuǎn)高于PSO算法及GWO算法，效果更佳明顯。

4.2 基于IGWO算法的區(qū)域搜索機(jī)器人路徑規(guī)劃仿真

假設(shè)環(huán)境地圖為1 000×1 000的區(qū)域內(nèi)，模擬隨機(jī)生成50個(gè)任務(wù)點(diǎn)與100個(gè)任務(wù)點(diǎn)兩種情況進(jìn)行算法仿真(圖6～圖8)。起點(diǎn)坐標(biāo)設(shè)置為(0,0)，一個(gè)機(jī)器人從起點(diǎn)坐標(biāo)逐一巡視任務(wù)點(diǎn)，且能在任務(wù)完成后，回到起點(diǎn)坐標(biāo)處。

圖6 50個(gè)任務(wù)點(diǎn)路徑規(guī)劃效果Fig.6 Results of path planning for 50 task points

圖7 適應(yīng)度對(duì)比Fig.7 Comparison of fitness values

圖8 100個(gè)任務(wù)點(diǎn)路徑規(guī)劃效果Fig.8 Results of path planning for 100 task points

圖6為50個(gè)任務(wù)點(diǎn)仿真效果，通過(guò)GWO算法和IGWO算法對(duì)多任務(wù)點(diǎn)一次性遍歷的路徑長(zhǎng)度分別為7 782.746 3、8 709.361 4 m，IGWO算法比GWO算法規(guī)劃路徑長(zhǎng)度縮短了926.615 1 m，效率提升了10.64%。圖7為50個(gè)任務(wù)點(diǎn)GWO 算法與IGWO 算法的最優(yōu)適應(yīng)度值曲線對(duì)比，可以清晰地看出IGWO算法比GWO算法收斂更快，對(duì)模型的求解能力更強(qiáng)。在機(jī)器人最大載電量的限制下，規(guī)劃長(zhǎng)度遠(yuǎn)遠(yuǎn)大于已有機(jī)器人最大行走長(zhǎng)度 3 500 m，因此需要將任務(wù)點(diǎn)進(jìn)行聚類(lèi)，將任務(wù)分時(shí)分步處理，任務(wù)點(diǎn)聚類(lèi)成2類(lèi)時(shí)，滿(mǎn)足已有機(jī)器人最大路徑長(zhǎng)度(電量)約束，將搜索任務(wù)分成2次處理，第一次遍歷27個(gè)任務(wù)點(diǎn)進(jìn)行搜索，路徑為0—32— 41— 40—11— 43—35—36—29—24— 45— 8—3—39— 6—1— 44—7—20— 42—28—13—10—30—31— 49— 47—50—0，路徑長(zhǎng)度為3 485.164 2 m，第二次遍歷23個(gè)任務(wù)點(diǎn)進(jìn)行搜索，路徑為：0—34—21—26—2— 46—22—19—25— 4—27—18— 48—38—15—5—16—17—33—37—23—14—12—9—0，路徑長(zhǎng)度為3 489.207 6 m，兩次路徑長(zhǎng)度合計(jì)為6 974.371 8 m，比傳統(tǒng)GWO算法一次性直接遍歷路徑規(guī)劃長(zhǎng)度縮短了19.92%，比IGWO算法未任務(wù)點(diǎn)聚類(lèi)一次性規(guī)劃長(zhǎng)度縮短了10.39%，且滿(mǎn)足了機(jī)器人電量約束。

圖8為100個(gè)任務(wù)點(diǎn)測(cè)試結(jié)果，此時(shí)2聚類(lèi)不能滿(mǎn)足電量約束條件，繼續(xù)進(jìn)行3聚類(lèi)，才能滿(mǎn)足約束，從而得到圖8(d)路徑規(guī)劃結(jié)果。如表3所示，100任務(wù)點(diǎn)路徑規(guī)劃總長(zhǎng)度由傳統(tǒng)GWO算法的20 342.147 2 m 縮短到IGWO算法的19 378.594 8 m，再在機(jī)器人電量約束的條件下，進(jìn)行任務(wù)點(diǎn)3聚類(lèi)，其路徑長(zhǎng)度縮短為10 965.772 8 m，縮短比例為53.91%。由此可見(jiàn)，在大任務(wù)量作業(yè)的場(chǎng)景中，本文算法路徑規(guī)劃優(yōu)勢(shì)更佳明顯。

表3 路徑規(guī)劃測(cè)試結(jié)果Table 3 Test results of path planning

5 結(jié)論

針對(duì)大任務(wù)量監(jiān)測(cè)作業(yè)，提出基于改進(jìn)灰狼優(yōu)化算法區(qū)域監(jiān)測(cè)機(jī)器人路徑規(guī)劃算法。該算法選取尋優(yōu)性能良好且穩(wěn)定的灰狼優(yōu)化算法，并對(duì)其進(jìn)一步改進(jìn)，以Logistic混沌映射加強(qiáng)種群多樣性，以控制參數(shù)自適應(yīng)調(diào)整策略平衡灰狼優(yōu)化算法的搜索和開(kāi)發(fā)能力，以靜態(tài)加權(quán)平均權(quán)重策略，更新種群位置，加快收了斂速度，從而增強(qiáng)了算法的模型求解能力。根據(jù)任務(wù)量規(guī)模及機(jī)器人載電量約束，引入K-means算法任務(wù)聚類(lèi)，并通過(guò)IGWO算法進(jìn)行路徑求解，將大規(guī)模任務(wù)量自動(dòng)自主的轉(zhuǎn)化成分時(shí)分步任務(wù)。實(shí)驗(yàn)結(jié)果表明，IGWO算法無(wú)論是在單峰函數(shù)還是多峰函數(shù)的測(cè)試上收斂效果均有提高，特別在多峰函數(shù)更佳明顯。基于改進(jìn)灰狼優(yōu)化算法的區(qū)域監(jiān)測(cè)機(jī)器人路徑規(guī)劃在大規(guī)模任務(wù)量的場(chǎng)景更能體現(xiàn)出優(yōu)越性，任務(wù)規(guī)模越大，路徑縮短比例更高。