基于蟻群-粒子群算法的巡檢機器人路徑規劃

楊天宇，薛陽，張亞飛

（上海電力學院自動化工程學院，上海200090）

基于蟻群-粒子群算法的巡檢機器人路徑規劃

楊天宇，薛陽，張亞飛

（上海電力學院自動化工程學院，上海200090）

目前，巡檢機器人采用傳統蟻群算法來實現路徑規劃較普遍，但傳統蟻群算法在實現路徑規劃時在收斂速度、效率以及局部最優等問題表現較差，因此提出基于蟻群-粒子群組合優化算法應用到巡檢機器人路徑規劃中，利用柵格法建立機器人工作環境，改善信息素的更新方式和解的多樣性，仿真結果表明相較傳統蟻群算法，采用蟻群-粒子群融合算法更能夠更好地縮小最優路徑的搜索范圍，改善最優解的搜索效率，降低迭代次數，實現最優且無碰撞的全局路徑。

0 引言

如今，變電站巡檢主要是由值班員來人工完成，人工巡檢存在諸如漏巡、漏檢等方面的缺陷。此外，人工巡檢在了解現場設備狀態、發現隱患等方面并不夠及時[1]。隨著智能電網與智能化機器人的大力快速地發展，在未來，人工被智能機器人所取代來完成變電站巡檢已成必然。因此，基于變電站環境下的智能巡檢機器人尤為重要，而路徑規劃是巡檢機器人最核心的技術之一[2]。

目前，巡檢機器人的路徑規劃還是主要通過模仿動物的群集行為，如螞蟻、鳥兒覓食等。蟻群算法（Ant Colony Optimization，ACO）即一種尋找優化路徑的機率型算法[3]。螞蟻識別彼此在各路徑上所留下信息素的強弱來挑選覓食路徑。蟻群算法特別適用于組合優化問題中，其具有精度高、強魯棒性和收斂性等特點。蟻群算法雖然具有上述優勢，但其還有改進之處，如計算量大，搜索較慢，難以擺脫局部最優等。

粒子群算法（Particle Swarm Optimization，PSO）是一種依托種群隨機優化的算法，其在穩定性、收斂速度、全局搜索能力和搜索時間等方面具有明顯優勢，但是在處理組合優化的問題上，粒子群算法依舊存在短板[4]。

因此，鑒于上述蟻群與粒子群優化算法各自的優缺點，為機器人實現路徑規劃時能夠利用各自的優勢，提出了將傳統蟻群算法與粒子群算法組合的方法，即首先采用粒子群算法所具有的較強的全局搜索能力作為基礎，然后利用蟻群算法獲取最優解。

1 蟻群與粒子群算法原理

1.1 蟻群算法（ACO）的基本原理

其中：ηij(t)為啟發式因子，取ηij(t)=1/dij，dij為點i與點j之間的距離；τij(t)為點i與點j兩點間t時刻的路徑上信息素的濃度；allowedk為t時刻螞蟻k所能選擇的點的集合；α為τ相對重要程度；β為η相對重要程度。當螞蟻經過所有點之后，更新存儲在環境中的信息素。

其中：Q為信息素總量；Lk為螞蟻k在經過所有點之后路徑的總長度。當全部螞蟻完成自己的路徑構建，各路徑上信息素的量逐漸增加，計算釋放的信息素濃度，當濃度滿足終止條件（即當迭代次數超過某一設定值）為止，則由螞蟻構建的最優路徑即為所求的最終解[6]。

1.2 粒子群算法（PSO）的基本原理

粒子群算法的初始狀態為一組粒子隨機分布在解區間內，作用是使迭代更加快速有效。通過不斷更新粒子的位置（解的大小）和速度（解變化的步長），不斷比較得到最優或較優解，進而實現路徑最優。公式如下：

其中Vij(t)、Xij(t)分別是該粒子當前速度與位置，C1、C2為學習因子，Pij,Best為到目前為止第（i，j）個粒子搜索到的個體極值，gBest為全局值，rand（）為（0，1）之間的隨機數，ω為加權系數。

上式中ω表示加權系數，通過控制當前速度影響后一個速度的方式，可以得到新的空間，通過不斷迭代，ω值逐漸變小，不斷更新全局值與個體極值，以獲得全局最優[7]。

2 蟻群-粒子群融合優化算法

針對文中上述蟻群與粒子群算法各自優劣勢，故采取蟻群算法與粒子群算法相互融合[8]的策略，發揮二者的優勢來優化巡檢機器人路徑規劃。在處理組合優化問題時，蟻群算法優勢顯著，因其包含較好的并行性、精度高、反饋良好，強魯棒性和收斂性等特點。粒子群算法優勢在于其較快的收斂速度、較好的全局搜索以及搜索時間短等。因此巡檢機器人路徑優化可先通過粒子群算法具有的較好的全局搜索來的特點，實現粗略搜索以獲取路徑上足夠的信息素;再通過蟻群算法的正反饋特點來精確搜索[9]。

蟻群-粒子群組合算法步驟如下:

（1）參數初始化;

（2）采用PSO對全局粗略搜索;

（3）利用粗略搜索得到次優解;

（4）更新信息素，改善ACO搜索能力;

（5）通過ACO在次優路徑上精確搜索;

（6）最終獲得問題的最優解。

圖1 蟻群-粒子群組合算法原理圖

3 仿真結果

3.1 仿真環境建模

為了表明蟻群-粒子群算法的有效性與可行性，分別構建結合傳統蟻群算法與蟻群-粒子群融合算法下巡檢機器人的路徑全局規劃[10]，并在MATLAB軟件和VC++6.0的環境下進行仿真。如圖1所示:用一個全局靜態10×10柵格矩陣表示，黑色柵格和白色柵格分別表示障礙物與可行柵格[11]，這個區域內分布了形狀不同、大小不等的障礙物。Start、End分別表示機器人的起點與終點位置。

算法參數初始化為:螞蟻數量m=80，α=1，β=2，信息素 ρ=0.05，迭代數為100。

3.2 試驗結果與分析

圖2和圖3表示傳統的蟻群算法與優化的蟻群-粒子群組合算法在試驗工作環境下巡檢機器人的路徑規劃。如圖2所示，在搜索過程中，采用傳統蟻群算法的路徑規劃存在很多的缺陷，如易陷入局部最優，易早熟，沒有很好地找到全局最優的路徑。

圖3表示蟻群-粒子群組合算法的路徑規劃，改善了信息素的更新方式，用巡檢機器人所在的位置到終點的距離優化啟發因子，加入粗略搜索，減少了搜索最優路徑的時間，通過更新信息素濃度分布，精確搜索次優路徑，從而完成全局從起點到終點的最優路徑。

為了更加全面地闡述文中的蟻群改進算法在路徑規劃中的有效性和最優執行效率，在以上仿真的基礎上，分別在不同的測試環境中進行仿真對比試驗，重新改變仿真環境，包括改變障礙物的分布情況，設置5個不同的試驗環境，參數初始化保持。

不變，更改障礙物的體積和個數等，每種環境下各測試25次，每次試驗循環100次，試驗搜索最優解所需迭代次數如下表。

從表1中可以看出，參數設置保持不變的前提下，在不同的試驗環境下，蟻群-粒子群融合算法通過利用粗搜索得到次優解進而獲取次優路徑，更新次優路徑上的信息素分布，能夠有效加快機器人全局尋優的速度，相比傳統蟻群算法，算法融合之后可有效地將最優路徑搜索次數降低了約34%，縮短了收斂時間，改善了算法的執行效率。

表1 搜索最優解的迭代次數

4 結語

變電站巡檢機器人路徑規劃是電力相關單位研究的重點，如何快速有效地搜索出一條起點與終點間無碰撞且最短路徑的算法是研究目的。機器人路徑規劃若采用傳統蟻群算法，則會存在執行效率低迭代次數多等缺點。提出了一種基于蟻群-粒子群融合算法的巡檢機器人路徑規劃，在傳統蟻群算法的基礎上加入粒子群算法，改進信息素的更新方式，增加解的多樣性。仿真結果表明采用蟻群-粒子群融合算法可以減小路徑最優的搜索范圍，改善最優解的搜索效率，降低迭代次數，實現全局路徑最優且無碰撞的路徑。

圖2 傳統蟻群算法巡檢機器人路徑規劃

圖3 蟻群-粒子群組合算法的巡檢機器人路徑規劃

[1]周立輝,張永生,孫勇,等.智能變電站巡檢機器人研制及應用[J].電力系統自動化,2011,35(19):85-88.

[2]陳瑤,陳阿蓮,李向東,等.變電站智能巡檢機器人全局路徑規劃設計[J].山東科學,2015,28(1):114-119.

[3]劉雄,雷勇,涂國強.基于蟻群算法的移動機器人路徑規劃[J].計算機仿真,2011,28(11):185-188.

[4]黃太安,生佳根,徐紅洋,等.一種改進的簡化粒子群算法[J].計算機仿真,2013,30(2):327-330.

[5]鄭慧君,陳俞強.基于改進蟻群的路徑導航算法[J].控制工程,2016,23(4):608-612.

[6]邱莉莉,鄭建立.基于改進蟻群算法的機器人路徑規劃[J].信息技術,2015(6):150-152.

[7]孫凱,吳紅星,王浩,等.蟻群與粒子群混合算法求解TSP問題[J].計算機工程與應用,2012,48(34):60-63.

[8]簡毅,張月.移動機器人全局覆蓋路徑規劃算法研究進展與展望[J].計算機應用,2014,34(10):2844-2849.

[9]Che H,Wu Z,Kang R,et al.Global Path Planning for Explosion-Proof Robot Based on Improved Ant Colony Optimization[C].Intelligent Robot Systems.IEEE,2016:36-40.

[10]Ren C M,Zhang J X.Robot Path Planning Based on Improved Ant Colony Optimization[J].Computer Engineering,2008,34(15):1-3.

[11]周東健,張興國,馬海波,等.基于柵格地圖-蟻群算法的機器人最優路徑規劃[J].制造業自動化,2014,12(5):1-3.

楊天宇（1990-），男，湖北武漢人，碩士研究生，研究方向為圖像處理、機器視覺、機器人路徑規劃

薛陽（1977-），男，江蘇無錫人，博士后，副教授，研究方向為機器人控制、微電網控制

張亞飛（1993-），男，江蘇連云港人，碩士研究生，研究方向為機器人技術、圖像處理

Path Planning;Inspection Robot;Ant Colony Algorithm;Particle Swarm Optimization Algorithm;Optimal Path

Path Planning of Inspection Robot Based on Ant Colony-Particle Swarm Optimization Algorithm

YANG Tian-yu，XUE Yang，ZHANG Ya-fei

（College of Automation Engineering，Shanghai University of Electric Power，Shanghai 200090）

At present,the inspection robot using the traditional ant colony algorithm to realize path planning are common,but the traditional ant colo?ny algorithm in path planning in the convergence speed and the efficiency of local optimization and poor performance,therefore is proposed based on ant colony particle swarm optimization algorithm is applied to the combination of robot path planning,the establishment of the working environment of the robot using grid method.Diversity to improve the information update in the settlement,the simulation results show that compared with the traditional ant colony algorithm,the ant colony particle swarm fusion algorithm can better reduce the optimal path search range,improve the search efficiency of the optimal solution,reduce the number of iterations,the global optimal and collision free path.

路徑規劃；巡檢機器人；蟻群算法；粒子群算法；最優路徑

國家自然科學基金資助項目（No.61040013）

1007-1423（2017）29-0048-04

10.3969/j.issn.1007-1423.2017.29.012