李 靖, 楊 帆,2*

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

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

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

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

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

1 問題建模

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

(1)

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

q=ruL

(2)

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

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

q

(3)

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

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

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

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

灰狼優(yōu)化算法[12]是模擬食物鏈頂端的捕食者狼群的捕食行為產(chǎn)生的算法?；依谴蠖枷矚g群居，且具有非常嚴格的社會等級制度，如圖1金字塔結(jié)構(gòu)的等級制度所示。

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

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

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

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

(4)

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

(5)

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

A=2ar1-a

(6)

C=2r2

(7)

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

(8)

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

灰狼追蹤獵物位置的數(shù)學模型描述如式(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為隨機向量；Dα、Dβ和Dδ分別為α狼、β狼和δ狼與狼群其他成員之間的距離；Xα、Xβ、Xδ分別為α狼、β狼和δ狼的位置；X為當前狼的位置。狼群中ω狼的位置由α狼、β狼和δ狼共同決定。

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

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

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

xn+1=axn(1-xn)

(12)

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

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

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

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

(13)

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

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

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

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

(14)

3 問題建模求解

3.1 K-means算法

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

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

距離函數(shù)為

(15)

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

聚類中心更新公式為

(16)

準則函數(shù)為

(17)

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

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

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

圖4 問題建模求解流程圖Fig.4 Flow chart of problem model solving

4 實驗仿真及結(jié)果分析

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

4.1 IGWO算法測試仿真

為了驗證改進灰狼優(yōu)化算法的性能，選取了國際上6個經(jīng)典基準測試函數(shù)進行測試，其中Sphere函數(shù)、Rosenbrock 函數(shù)、Schwefel’s 2.22函數(shù)為單峰測試函數(shù)、Rastrigin函數(shù)、Griewank函數(shù)和Ackley函數(shù)為多峰測試函數(shù)，測試函數(shù)的維數(shù)、定義域如表1所示。分別對PSO算法，GWO算法及IGWO算法進行了仿真測試，其測試結(jié)果對比如圖5所示，對比平均值及標準差如表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 測試函數(shù)Table 1 Test function

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

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

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

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

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

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

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

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

圖6為50個任務(wù)點仿真效果，通過GWO算法和IGWO算法對多任務(wù)點一次性遍歷的路徑長度分別為7 782.746 3、8 709.361 4 m，IGWO算法比GWO算法規(guī)劃路徑長度縮短了926.615 1 m，效率提升了10.64%。圖7為50個任務(wù)點GWO 算法與IGWO 算法的最優(yōu)適應(yīng)度值曲線對比，可以清晰地看出IGWO算法比GWO算法收斂更快，對模型的求解能力更強。在機器人最大載電量的限制下，規(guī)劃長度遠遠大于已有機器人最大行走長度 3 500 m，因此需要將任務(wù)點進行聚類，將任務(wù)分時分步處理，任務(wù)點聚類成2類時，滿足已有機器人最大路徑長度(電量)約束，將搜索任務(wù)分成2次處理，第一次遍歷27個任務(wù)點進行搜索，路徑為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，路徑長度為3 485.164 2 m，第二次遍歷23個任務(wù)點進行搜索，路徑為：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，路徑長度為3 489.207 6 m，兩次路徑長度合計為6 974.371 8 m，比傳統(tǒng)GWO算法一次性直接遍歷路徑規(guī)劃長度縮短了19.92%，比IGWO算法未任務(wù)點聚類一次性規(guī)劃長度縮短了10.39%，且滿足了機器人電量約束。

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

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

5 結(jié)論

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