基于ACO-SA算法的變電站巡檢機器人路徑規劃

劉勝，張豪，晏齊忠，張志鑫，申永鵬

(1.鄭州輕工業大學，鄭州 450002；2. 河南中煙工業有限責任公司南陽卷煙廠，河南 南陽 473007)

0 引言

近年來我國在經濟與基礎建設領域發展迅猛，電力工業作為國家發展的支柱，其規模在不斷擴大、自動化程度在不斷提高[1 - 3]，變電站數量也隨之不斷增多，無人或少人值守變電站成為變電站發展的主流趨勢[4]。傳統人工巡檢存在勞動強度大、巡檢效率低、受環境因素限制等問題，已無法滿足當下對供電質量的高要求[5]。引進智能巡檢機器人在滿足安全高效的同時，也克服了傳統人工巡檢的問題與不足。

路徑規劃是實現機器人自動導航的關鍵，進行路徑規劃的目的是在規定約束下為機器人選擇一條盡可能歷程最短、效率最高的無碰撞行動路線[6 - 7]。對于路徑規劃算法的研究，傳統的蒙特卡羅模擬和迪杰斯特拉算法等貪心算法可以確保最優解，但在復雜條件下運算量過大[8 - 11]；隨后人們提出了改進的蟻群算法和遺傳算法此類啟發式算法可以解決運算量過大的問題但仍存在收斂精度低、易落入局部最優解并且迭代復雜的問題[12 - 16]。

針對上述問題，張麗珍等通過建立節點間最優代價函數，設立“虛擬終點”，從而避免了盲目搜索，縮小了搜索空間，但易陷入局部最優[17]。孟冠軍等選擇在蟻群算法中加入全局距離參數，通過在運行過程中不斷交叉操作以得到最快求解速度，該方法雖然降低了算法的運行時間，但所得結果并沒有明顯改進[18]。琚澤立等引入曼哈頓距離、重置信息素揮發機制以及設置蟻群自適應路徑長度改進蟻群算法，得到了很好的路徑結果，但在改進過程中也增加了算法運行的復雜性[19]。劉杰等引入自適應信息素揮發系數，實現了隨機漫游的效果，避免搜索陷入停滯[20]。張凡等引入JPS算法，并優化調點數量，提高搜索效率，但未考慮提高算法運算速度[21]。薛陽等則引入蜂群算法，借助“觀察蜂”和“偵查蜂”的概念完善解的適應度，這樣很好地規避了局部最優的困境[22]。陳志等通過算法初期信息素不均勻分配避免盲目搜索，使用偽隨機狀態轉移規則選擇路徑，同時利用動態懲罰方法解決死鎖問題[23]。

本文結合模擬退火算法與蟻群算法提出了改進的蟻群-模擬退火(ant colony optimization-simulated annealing，ACO-SA)算法，通過提高蟻群前期的全局搜索能力、改善信息素分布與更新、引入回火機制避免局部最優、提高搜索效率。并通過仿真實驗驗證其準確性與有效性。

1 環境模型

本文采用柵格法模擬機器人工作環境，將變電站環境分解為一系列大小相等的網絡單元，單元格大小以巡檢機器人尺寸為標準。

假設巡檢環境為長為L，寬為W的規則場地，將環境平均劃分為m×n個長度、寬度分別為l、w的柵格，用Nxy表示每個小柵格，整個環境空間記為Φ，Φ的表達式如式(1)所示。

Φ=∑Nxy|(x∈[1,m],y∈[1,n])

(1)

每個柵格有無障礙信息表達如式(2)所示。

(2)

式中：Nxy為每個柵格的狀態信息，取值為0表示無障礙區可自由通行，取值為1表示有障礙區禁止通行。在參考了現實變電站布局后，建立多個二值化柵格數組表示機器人巡檢環境，同時設置小柵格為1×1，模型如圖1所示。

圖1 柵格模型Fig.1 Raster model

使用大小相等的柵格劃分柵格空間，并用柵格數組表示運行環境，簡單的建模過程大大降低了模型的復雜度，同時具備區分運動空間與障礙物的能力，滿足路徑規劃的實驗需求。此外，柵格法滿足本文所采用的八叉樹搜索策略，即機器人在搜索過程中可以朝附近8個方向的相鄰柵格之間移動，機器人移動模型如圖2所示。

圖2 巡檢機器人移動模型Fig.2 Mobile model of inspection robot

2 ACO算法和SA算法

ACO算法模擬自然環境中蟻群覓食時的探索過程，是一種尋找最優路徑的啟發式算法[24]。其原理是螞蟻們在探索過程中沿途分泌信息素，隨著蟻群多次往返，信息素不斷積累、揮發，最后信息素濃度最高的路徑即為最短路徑。

信息素濃度是蟻群選擇路徑的關鍵依據，為了加速路徑篩選設定信息素揮發機制，當所有螞蟻完成一次往返后對全局信息素含量進行更新，具體規則見式(3)。

τij(t+1)=(1-ρ)τij(t)+ρΔτij(t)

(3)

式中：τij(t)為返途中螞蟻在節點i到節點j之間的路徑上所留下的全局信息素含量；ρ為信息素揮發因子，ρ∈(0,1)代表信息素在自然條件下的揮發情況，1-ρ為信息素殘留因子；Δτij(t)為本次往返途中螞蟻k在節點i到節點j之間的路徑上所留下的信息素含量，其數學表達式如式(4)所示。

(4)

式中m為環境地圖最大柵格數。

螞蟻對于路徑的選擇不僅與信息素濃度有關，在選擇下一節點時會優先考慮相鄰的節點，對此定義螞蟻在兩節點間的啟發函數ηij以表達螞蟻從所在節點i到達下一節點j的期望程度，詳見式(5)。

(5)

(6)

式中：dij為節點i與節點j直接的歐幾里得距離；ix、iy、jx、jy分別為兩節點的橫縱坐標。

(7)

式中：A為螞蟻下一步可訪問的節點集合；τij(t)為節點i與j之間的信息素含量；ηij為啟發函數；α為信息素啟發因子，α值越大則在選擇路徑時信息素的影響就越大，螞蟻們就越傾向于選擇較多螞蟻走過的路徑；β為期望因子，β值越大則在選擇路徑時啟發式信息的影響就越大，螞蟻們更傾向于移動至相鄰最近的節點；C為該時刻未訪問的節點集合；S為集合C中的一節點。

根據以上條件，利用經典蟻群算法在本文所建立的柵格環境(圖1)中進行路徑規劃，其結果如圖3—4所示。

圖3 經典蟻群算法規劃路線Fig.3 Classic ant colony algorithm for route planning

結合圖3和圖4可知，傳統蟻群算法在迭代至30次左右時陷入局部最優導致算法處于死鎖狀態，之后迭代冗余無法得到最優結果。

圖4 經典蟻群算法收斂曲線Fig.4 Convergence curve of classical ant colony algorithm

模擬退火算法模擬熱力學中金屬退火過程[25]，隨著溫度由高降低(退火過程)，粒子隨機運動概率逐漸降低，并最終達到穩定熱平衡狀態。

運用模擬退火算法進行路徑規劃實際上是一個組合優化的過程，即從所有可行解中挑選出最優狀態下的解。首先設定Ω={S1,S2,…,Sn}代表所有可行解構成的解空間，用C(Si)代表解Si所對應的目標函數的值，最終最優解S*應滿足對于所有Si∈Ω都能滿足C(S*)≤C(Si)。

隨機生成一組可行解 記為初始解狀態，并計算得到該解的目標函數值C(Si),隨后采用Metropolis抽樣法獲取新的可行解S′,計算目標函數的增量，并以如下標準判斷是否接收S′作為新的當前解，數學表達式如式(8)所示。

(8)

式中：P為隨機數，P∈[0,1]；Pt為接收概率，與時間t成反比，如式(9)所示。

(9)

之后重復操作迭代500次后降低溫度，在新的溫度條件下尋求新解，當滿足終止條件后，結束退火過程并輸出最優解。其中t時刻下溫度T=αtT0，T0為初始溫度。

3 改進算法

3.1 啟發函數的改進

傳統蟻群算法在設定啟發式信息時僅用節點間距離的反比來構建啟發函數，以此模擬螞蟻選擇最短距離路徑的效果，這樣在理論上確保了螞蟻們會優先選擇段距離路徑，但是未考慮當前節點與下一節點的位置關系，同時在后期搜索過程中啟發信息的影響程度將遠低于信息素，為此我們重新定義啟發函數如式(10)所示。

(10)

(11)

式中：djb為節點j到終點b的歐幾里得距離；Lmax為最大迭代次數；?為使啟發函數動態變化而引入的參數，其值隨著迭代次數的增加由大變??；L為當前迭代次數。由于前期增大了啟發函數的比重，避免了螞蟻搜索路徑的盲目性，加快收斂速度，同時不會干擾后期路徑選擇的準確性。在其他參數不變的情況下，僅改變啟發函數完成10組對照實驗，實驗結果如圖5所示。

圖5 改進啟發函數驗證Fig.5 Verification of improved heuristic function

由圖5可知，我們在同一柵格環境進行10次重復試驗，可以看出在運用改進啟發函數后，迭代次數明顯下降。

3.2 初始信息素改進

在經典蟻群算法中，初始時全局信息素處于同一水平，這使得螞蟻們前期處于盲目搜索狀態，導致算法運行時間增加。為了提高算法收斂速度，本文給出了初始信息素的確定公式，如式(12)所示。

(12)

式中：a、i、j、b分別表示起始點、當前節點、下一節點、終點；dab、dai、dij、djb為各點之間的歐幾里得距離；λ為平衡系數。20×20柵格環境中初始信息素濃度如圖6所示。

圖6 初始信息素濃度Fig.6 Initial pheromone concentration

以顏色深度表示初始信息素濃度，從圖6可以看出，初始信息素濃度是以始末連線為中心，沿中垂線向外呈正態分布且濃度逐漸降低。這使得初始條件下各節點由于位置不同信息素分布不均勻，避免了螞蟻在初期盲目探索，提高了搜索效率。

3.3 初始信息素改進

在經典蟻群算法中信息素揮發因子通常為常數，這使得信息素的更新無法滿足我們對算法收斂速度與全局最優的要求。對此本文給出信息素動態揮發因子見圖7，此時ρ的值隨著迭代次數的增加而減小。ρ的數學表達式如式(13)所示。

圖7 兩種ρ函數對比Fig.7 Comparison of the two ρ functions

ρ=ce-t1/2

(13)

式中：t為算法運行時間；c為平衡系數，其值可變以確保函數可進行自適應變化。

改進后的信息素更新機制前期ρ值較大可以擴大搜索范圍，后期ρ值較小以便快速篩選出優勢路徑。為驗證改進的可行性，在其他條件不變的前提下，使用不同信息素揮發因子進行對照實驗，實驗結果如圖8所示。

圖8 改進信息素揮發機制驗證Fig.8 Verification of improved pheromone volatilization mechanism

3.4 初始信息素改進

為了避免局部最優我們引入模擬退火算法中的回火機制，螞蟻選擇下一節點j時的選擇函數見式(14)。

(14)

(15)

4 改進算法

為驗證改進算法的有效性，使用MATLAB R2016a進行計算機仿真實驗，具體實驗環境為Windows 10操作系統，CPU為core i5 8th gen，8 G內存。為驗證ACO-SA算法的優越性，將仿真結果與經典蟻群算法進行比較。

4.1 算法實現

仿真實驗參數如表1所示。同時由于模擬過程若設定Tmin=0則需要過長時間運行，迭代次數過多使精度和時間上產生矛盾。因此設定的終止條件為T<0.000 1或最優解保持不變。

表1 參數配置Tab.1 Parameter configuration

按圖9流程進行算法仿真。

圖9 ACO-SA算法流程Fig.9 Flow chart of ACO-SA algorithm

步驟1：構建柵格地圖，設定初始參數，即螞蟻數量N、降溫系數、初始溫度、回火次數、迭代次數。

步驟2：設定不均勻初始信息素濃度，并設定啟發函數。

步驟3：派出螞蟻探索全圖，根據信息素濃度及啟發函數前往下一節點，所有螞蟻完成一次往返或無法行走時本次迭代結束。

步驟4：歷次迭代完成后，接受最短路徑，并更新全局信息素濃度。

步驟5：采用回火機制，與前一溫度時刻比較，若當前解(最短路徑長度)優于上一解則接受新解，對于劣解根據公式得到接受概率，同時產生隨機數Y(取值范圍為[0,1])，若Y

步驟6：更新當前溫度，當迭代次數或當前溫度滿足結束條件時退出循環，否則進入下一次迭代循環。

步驟7：輸出解集中的最優解為最終路徑。

4.2 結果分析

根據上述算法步驟，本文分別建立場景1(20×20)、場景2(25×25)、場景3(30×30)柵格地圖，并逐步增加地圖環境復雜程度，檢驗算法的普適性。為了更直觀地驗證ACO-SA算法的可行性，將文獻[20]的改進蟻群算法與本文提出的融合算法進行對比。場景1、2、3的實驗結果分別如圖10—12所示。

圖10 場景1實驗結果Fig.10 Experimental results of scenario 1

圖11 場景2實驗結果Fig.11 Experimental results of scenario 2

圖12 場景2實驗結果Fig.12 Experimental results of scenario 2

ACO-SA算法、文獻[20]算法在3個場景中關于最優路徑長度、算法運行時間、迭代次數的對比結果如表2所示。

表2 結果對比Tab.2 Comparison of results

結果顯示，在3個場景中相較于文獻[20]算法，ACO-SA路徑長度減少了8.44%、9.97%和10.27%，運算時間分別縮短了29.17%、35.45%和37.71%，迭代次數縮減了64.71%、22%和16.28%，由于采用新的信息素更新機制，ACO-SA算法的最優路徑長度較經典算法有明顯改進，并且轉移概率中增大啟發函數的作用，將隨機性選擇和確定性選擇相結合，使收斂速度更快，更穩定。

5 結論

針對傳統蟻群算法在路徑規劃中存在的優化能力差，收斂速度慢，易陷入局部最優的問題，本文提出一種改進的ACO-SA算法，主要結論如下。

1)改進啟發函數，結合初始情況下蟻群選擇的隨機性與準確性，避免了前期的盲目搜索，加快了收斂速度。

2)采用不均勻的初始信息素分布策略，初始信息素濃度呈散落式分布，減少了路徑中的冗余抉擇，提高了搜索效率。使用動態函數重新定義信息素揮發因子，確保了后期的快速迭代。

3)引入模擬退火算法中的“回火”機制，借助Metropolis抽樣法增加優勢的篩選范圍，避免陷入局部最優的困境。

4)在柵格環境中與多種算法進行對比驗證，在結果、速度、效率等方面均優于其他算法，證明了ACO-SA算法的可行性。

未來將深入研究巡檢機器人面對動態障礙及優先到達情況下的協調算法，助推變電站巡檢機器人的實踐應用。