基于改進(jìn)蟻群算法的變電站巡檢機(jī)器人路徑規(guī)劃研究

謝志文，汪 政，王 銳，周 原

(廣東電網(wǎng)有限責(zé)任公司電力科學(xué)研究院，廣東 廣州 510080)

電網(wǎng)輸電工作的正常運(yùn)行需要開(kāi)展變電站巡檢工作。最常見(jiàn)變電站巡檢工作是借助人力資源，該巡檢方式消耗大量人力，人長(zhǎng)期在變電站環(huán)境中開(kāi)展巡檢工作，經(jīng)常受到電磁輻射與復(fù)雜環(huán)境侵害，對(duì)于人體健康危大[1-3]。隨著科學(xué)技術(shù)的不斷進(jìn)步，機(jī)器人技術(shù)逐漸進(jìn)入變電站巡檢工作中，路徑規(guī)劃研究是機(jī)器人巡檢工作中至關(guān)重要的一部分。

在機(jī)器人系統(tǒng)內(nèi)部安裝所需巡檢的環(huán)境地圖，目的地確定下來(lái)以后，機(jī)器人沿著算法規(guī)劃完成的路徑自主運(yùn)行，在機(jī)器人內(nèi)部安裝超聲傳感器與光視覺(jué)傳感器，以此檢測(cè)出運(yùn)行前方的靜止障礙物或者運(yùn)動(dòng)障礙物[4-6]。有學(xué)者提出以生物認(rèn)知作為基礎(chǔ)的機(jī)器人路徑規(guī)劃方法[7]，該方法計(jì)算過(guò)程復(fù)雜，實(shí)現(xiàn)路徑規(guī)劃需要經(jīng)過(guò)系統(tǒng)復(fù)雜計(jì)算，降低機(jī)器人反應(yīng)時(shí)間；還有學(xué)者將離散灰狼算法作為基礎(chǔ)規(guī)劃?rùn)C(jī)器人的巡檢路徑[8]，該方法由于路徑規(guī)劃以路徑最短為目標(biāo)，造成巡檢過(guò)程中多次出現(xiàn)漏巡檢的情況。

蟻群算法對(duì)螞蟻尋找食物的過(guò)程進(jìn)行模擬，提出多種假設(shè)形成一種智能模式[9-10]。為變電站機(jī)器人巡檢規(guī)劃更加合理的路徑，提出了改進(jìn)蟻群算法的變電站機(jī)器人巡檢規(guī)劃方法。

1 巡檢機(jī)器人路徑規(guī)劃方法

1.1 巡檢地圖構(gòu)建

變電站中機(jī)器人巡檢地圖通過(guò)柵格法被劃分成眾多小柵格，一個(gè)二值表示一個(gè)小柵格，最終使用二值表示全部柵格，由此實(shí)現(xiàn)全區(qū)域空間在地圖上使用二值表示。實(shí)驗(yàn)開(kāi)展時(shí)地圖使用一個(gè)矩陣來(lái)表示，如果地圖中某一個(gè)障礙物的位置出現(xiàn)變化，對(duì)某個(gè)二值做出調(diào)整就能重新獲取地圖結(jié)構(gòu)[11-13]。地圖構(gòu)建完成以后才可以通過(guò)改進(jìn)后的蟻群算法尋找最為安全、最為準(zhǔn)確也是最短的巡檢路徑。

1.2 用于規(guī)劃?rùn)C(jī)器人巡檢路徑的改進(jìn)蟻群算法

1.2.1 蟻群算法數(shù)學(xué)模型

使用式(1)表示t時(shí)刻下，某個(gè)螞蟻從巡檢點(diǎn)i至j的概率：

(1)

式中，τij(t)與dij={i，j=1，2，…，n}分別代表范圍(i，j)上在時(shí)刻t時(shí)的信息素?cái)?shù)量與從一個(gè)巡檢點(diǎn)至另一個(gè)巡檢點(diǎn)的距離；與分別表期望啟發(fā)因子與信息素啟發(fā)因子；在(i，j)上，ηij=1/dij表示啟發(fā)函數(shù)，該啟發(fā)函數(shù)也就是兩個(gè)巡檢點(diǎn)之間的期望度；AK與{C-tabUk}相等，其中tabUk等于{1，2，…，m}，同時(shí)tabUk也代表第k個(gè)螞蟻的禁忌表，該表用來(lái)統(tǒng)計(jì)第k個(gè)螞蟻經(jīng)過(guò)的巡檢點(diǎn)。

正常情況下螞蟻遺留的信息素存在揮發(fā)現(xiàn)象，外界環(huán)境也會(huì)對(duì)螞蟻行進(jìn)造成路線影響，對(duì)這些因素綜合考慮，信息素?fù)]發(fā)情況設(shè)定ρ表示，1-ρ為經(jīng)過(guò)揮發(fā)后信息素剩余量。螞蟻遍歷一次巡視后，重新更新巡視路徑上的信息素：

(2)

2.2.2 改進(jìn)蟻群算法

(1)構(gòu)建轉(zhuǎn)角啟發(fā)因子。把方向系數(shù)ε引入到基礎(chǔ)蟻群算法中，由此使得途徑選擇指向性得以提升，避免機(jī)器人轉(zhuǎn)彎角度太大導(dǎo)致路徑搜索時(shí)間浪費(fèi)。設(shè)定圖1表示t時(shí)刻路徑搜索時(shí)機(jī)器人狀態(tài)。

圖1 路徑搜索原理Fig.1 Principle of path search

機(jī)器人巡檢過(guò)程中依次經(jīng)過(guò)巡檢點(diǎn)1-4，如果機(jī)器人行進(jìn)從巡檢點(diǎn)1到巡檢點(diǎn)2，巡檢點(diǎn)3和下一個(gè)巡檢路徑的起點(diǎn)，巡檢點(diǎn)4是下一個(gè)巡檢路徑的終點(diǎn)，當(dāng)機(jī)器人巡檢到巡檢點(diǎn)2時(shí)，和x軸之間形成一個(gè)角度，稱為φ1，當(dāng)機(jī)器人巡檢到巡檢點(diǎn)3時(shí)，和x軸之間形成一個(gè)角度，稱為φ2。從圖1中能夠看出，機(jī)器人巡檢的方向越接近終點(diǎn)越大，由此獲得轉(zhuǎn)角啟發(fā)因子：

(3)

(2) 啟發(fā)函數(shù)改進(jìn)。前文中所闡述的蟻群算法并沒(méi)有對(duì)當(dāng)前巡檢點(diǎn)與目標(biāo)巡檢點(diǎn)之間的距離加以考慮，這一欠缺導(dǎo)致蟻群算法的搜索效率被降低。所以本文改進(jìn)方法中引進(jìn)A*算法中的估價(jià)函數(shù)，使得算法在計(jì)算過(guò)程中如果遇到自鎖情況可以自動(dòng)跳出[14]。使用A*算法能夠?qū)⒙窂街挟?dāng)前巡檢點(diǎn)與目標(biāo)巡檢點(diǎn)代價(jià)估計(jì)出來(lái)，開(kāi)展選擇，使得搜索范圍降低，由此確保搜索效率的提升[15]。式(4)為估計(jì)函數(shù)：

f(n)=g(n)+h(n)

(4)

式中，g(n)與h(n_)分別表示實(shí)際代價(jià)與估計(jì)代價(jià)，二者又分別是巡檢起點(diǎn)與當(dāng)前巡檢點(diǎn)距離以及下個(gè)巡檢點(diǎn)至目標(biāo)巡檢點(diǎn)之間的距離。

改進(jìn)啟發(fā)函數(shù)為：

(5)

式中，dij相當(dāng)于g(n)，也是巡檢起點(diǎn)與當(dāng)前巡檢點(diǎn)的距離，djE相當(dāng)于h(n)，也是當(dāng)前巡檢點(diǎn)與目標(biāo)巡檢點(diǎn)的距離。

(3)改進(jìn)信息素?fù)]發(fā)因子。上文所研究的基礎(chǔ)蟻群算法原理中，以固定值確定信息素，這種信息素內(nèi)容確定方式比較單一，不適合路徑巡檢過(guò)程中分配信息素，這種情況下，巡檢初期由于信息素較少，螞蟻搜索時(shí)盲目性過(guò)高，巡檢后期大量信息素積累，干擾選擇信息素，所以這種固定值確定信息素不能搜索得到最優(yōu)路徑。通過(guò)這些分析，本文對(duì)信息素?fù)]發(fā)因子加以改進(jìn)，確保信息素?fù)]發(fā)因子符合拉普拉斯概率密度函數(shù)變化：

(6)

式中，b與μ分別表示尺度與位置的參數(shù)，如果μ與ρ相等，選取最大值作為取值。

根據(jù)拉普拉斯概率分布研究分析獲悉，路線規(guī)劃之初選取比較小的信息素因子，積累下一定量的信息素，使得螞蟻搜索路徑時(shí)提升導(dǎo)向性；路線規(guī)劃中期增大揮發(fā)因子，使得蟻群算法的迭代速率得到提升；路線規(guī)劃末期，降低信息素?fù)]發(fā)因子，使得算法收斂速度加快。經(jīng)過(guò)改進(jìn)后的蟻群算法，在時(shí)刻下某個(gè)螞蟻從巡視點(diǎn)i至j的概率使用式(7)表示：

(7)

(4) 算法流程。改進(jìn)蟻群算法的改進(jìn)蟻群算法變電站巡檢機(jī)器人路徑規(guī)劃流程如圖2所示。

圖2 改進(jìn)蟻群算法計(jì)算流程Fig.2 Calculation process of improved ant colony algorithm

改進(jìn)蟻群算法變電站巡檢機(jī)器人路徑規(guī)劃步驟如下：①利用柵格法構(gòu)建環(huán)境地圖；②將算法參數(shù)設(shè)定下來(lái)，確定巡檢的起始位置與巡檢終點(diǎn)位置；③在巡檢起點(diǎn)位置放置一只螞蟻，開(kāi)始尋找巡檢路線；④通過(guò)概率公式確定螞蟻行進(jìn)的下一個(gè)巡檢點(diǎn)；⑤對(duì)全部螞蟻位置開(kāi)展判斷，判定每只螞蟻是否都到達(dá)巡檢終點(diǎn)，如果全部螞蟻已經(jīng)到達(dá)巡檢終點(diǎn)就僅需下一步計(jì)算，如果沒(méi)有到達(dá)巡檢終點(diǎn)就繼續(xù)返回上一步；⑥依據(jù)改進(jìn)后的信息素更新準(zhǔn)則，更新信息素；⑦將各個(gè)螞蟻的路徑長(zhǎng)度保存下來(lái)，對(duì)當(dāng)下螞蟻?zhàn)顑?yōu)路徑加以選擇并且對(duì)比曾經(jīng)獲取的最優(yōu)路徑，得到全局最優(yōu)解；⑧判定迭代是否達(dá)到次數(shù)，如果已經(jīng)多達(dá)迭代次數(shù)就將最優(yōu)解輸出，如果沒(méi)有到達(dá)迭代次數(shù)就重新返回到步驟③，重新尋找路線。

3 具體應(yīng)用實(shí)例分析

3.1 應(yīng)用對(duì)象

以某市大型變電站為例，使用本文方法規(guī)劃巡檢機(jī)器人的行進(jìn)路線，同時(shí)尋找出機(jī)器人巡檢的最優(yōu)路徑。使用平面坐標(biāo)系把該變電站布局與巡檢點(diǎn)標(biāo)記出來(lái)，平面效果如圖3所示。

圖3 變電站平面效果及巡檢點(diǎn)分布Fig.3 Layout of substation plan and inspection point

在該變電站中機(jī)器人巡檢的起點(diǎn)是充電室，對(duì)變電站中的20個(gè)巡檢點(diǎn)開(kāi)展巡檢，針對(duì)各個(gè)巡檢點(diǎn)，巡檢機(jī)器人每次只巡檢一次，待遍歷全部巡檢點(diǎn)后，巡檢機(jī)器人重新回到充電室之內(nèi)。

3.2 相關(guān)參數(shù)設(shè)置

實(shí)驗(yàn)過(guò)程中需要先確定改進(jìn)蟻群算法數(shù)，這些參數(shù)包含4組，分別分為：信息素重要程度、信息素蒸發(fā)系數(shù)、啟發(fā)因子重要程度、信息素增加強(qiáng)度系數(shù)，分析最小路徑長(zhǎng)度與迭代次數(shù)時(shí)，改變?nèi)我庵档谴_保有一個(gè)值不變，參數(shù)計(jì)算結(jié)果如圖4所示。在圖4中，只對(duì)改進(jìn)蟻群算法每組參數(shù)中最優(yōu)代表性的一組開(kāi)展實(shí)驗(yàn)分析，只改變單一變量，獲得最優(yōu)參數(shù)，經(jīng)過(guò)各組實(shí)驗(yàn)中曲線波動(dòng)收斂情況與最終獲得的最優(yōu)路徑計(jì)算結(jié)果，確定各參數(shù)分別為1.0、8.0、0.4、1.0時(shí)路徑尋優(yōu)效果較為理性，所以后續(xù)機(jī)器人巡檢路線規(guī)劃可以使用這4個(gè)參數(shù)。

圖4 參數(shù)選擇對(duì)迭代最短路徑影響Fig.4 Influence of parameter selection on shortest path of iteration

3.3 結(jié)果與分析

使用柵格法針對(duì)圖3中的變電站平面圖構(gòu)建變電站巡檢柵格圖，圖中的自由區(qū)域與設(shè)備分布導(dǎo)致的障礙區(qū)域利用二值表示，改進(jìn)蟻群算法規(guī)劃的機(jī)器人巡檢路線如圖5所示。

圖5 機(jī)器人巡檢路線規(guī)劃Fig.5 Robot inspection route planning

在圖5中，使用本文改進(jìn)的蟻群算法規(guī)劃路徑后機(jī)器人在巡檢過(guò)程中能夠避開(kāi)變電站環(huán)境中的障礙物，利用算法中螞蟻開(kāi)辟的全新道路，獲得更加直接平滑的巡檢路線，加快機(jī)器人巡檢速度，這也直接證明經(jīng)過(guò)改進(jìn)的蟻群算法具有較強(qiáng)的搜索能力。

4 結(jié)語(yǔ)

研究改進(jìn)蟻群算法的變電站巡檢機(jī)器人路徑規(guī)劃方法，在基礎(chǔ)蟻群算法的基礎(chǔ)上引入啟發(fā)因子，使得選擇路徑時(shí)具有較高的指向性，降低路徑搜索時(shí)間，避免出現(xiàn)機(jī)器人轉(zhuǎn)彎角過(guò)大的情況；在蟻群算法的基礎(chǔ)上結(jié)合A*算法，使得啟發(fā)函數(shù)得到改進(jìn)，對(duì)多個(gè)巡檢點(diǎn)之間的距離加以考慮，進(jìn)一步提升路徑規(guī)劃效率；使用拉普拉變化信息素?fù)]發(fā)策略，使得蟻群算法的迭代速率得到提升。以實(shí)際變電站為實(shí)驗(yàn)對(duì)象開(kāi)展試驗(yàn)，證明本文方法在規(guī)劃?rùn)C(jī)器人巡檢路線時(shí)具有較高的巡檢效率與較短的巡檢時(shí)間，適合推廣使用。