柵格遺傳算法的變電站巡檢機(jī)器人路徑規(guī)劃

姜英杰　呂學(xué)勤　段利偉

摘 要：根據(jù)變電站巡檢機(jī)器人的巡檢環(huán)境和巡檢任務(wù)，提出采用柵格法模擬劃分機(jī)器人的工作空間，將變電站工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元，并結(jié)合遺傳算法對(duì)變電站巡檢機(jī)器人進(jìn)行全局路徑規(guī)劃。提出了連續(xù)相鄰柵格定義和不等長(zhǎng)染色體編碼，并使用自適應(yīng)方法選取了交叉概率和變異概率進(jìn)行路徑尋優(yōu)。通過(guò)MATLAB仿真，證明了這種柵格地圖與遺傳算法結(jié)合的方法能快速、有效地在已知環(huán)境中得到機(jī)器人的避障最優(yōu)路徑。

關(guān)鍵詞：巡檢機(jī)器人；柵格法；改進(jìn)遺傳算法；路徑規(guī)劃

中圖分類號(hào)：TP242 文獻(xiàn)標(biāo)識(shí)碼：A DOI：10.15913/j.cnki.kjycx.2015.06.012

變電站傳統(tǒng)的人工巡檢方式中存在勞動(dòng)強(qiáng)度大、管理成本高和工作效率低等不足，且很多變電站受惡劣地理、氣候條件的限制，一般的人工巡檢很難實(shí)現(xiàn)有效的巡檢工作，即使一些變電站實(shí)現(xiàn)了少人或無(wú)人值班，但依舊在一定程度上存在因無(wú)人及時(shí)監(jiān)視、巡視而帶來(lái)的一系列問(wèn)題。因此，智能化巡檢已成為發(fā)展智能變電站的必然要求?；谝苿?dòng)機(jī)器人技術(shù)開(kāi)發(fā)的變電站巡檢機(jī)器人系統(tǒng)，利用機(jī)器人主體的自主運(yùn)動(dòng)，并根據(jù)巡檢任務(wù)在特定的工位?？?，通過(guò)攜帶的紅外熱像儀、可見(jiàn)光CCD等相關(guān)電站設(shè)備檢測(cè)裝置進(jìn)行設(shè)備檢測(cè)，能及時(shí)發(fā)現(xiàn)電力設(shè)備的內(nèi)部熱缺陷、外部機(jī)械和電氣問(wèn)題，從而提高工作效率和質(zhì)量，真正起到減員增效的作用，最終推進(jìn)變電站無(wú)人值守的發(fā)展。

巡檢機(jī)器人是輪式移動(dòng)機(jī)器人在工業(yè)上的又一典型應(yīng)用，其路徑規(guī)劃的主要任務(wù)是在已知障礙物的環(huán)境中的靜態(tài)全局規(guī)劃。目前，全局路徑規(guī)劃研究主要包括環(huán)境建模和路徑搜索兩個(gè)子問(wèn)題。其中，環(huán)境建模的主要方法有可視圖法（V—Graph）、自由空間法（Free Space Approach）和柵格法（Grids）等；路徑搜索策略主要方法有A×算法、D×算法等。

隨著人工智能的發(fā)展，啟發(fā)式優(yōu)化方法被逐漸應(yīng)用到路徑規(guī)劃的研究中。遺傳算法作為一種典型的啟發(fā)式算法，成為尋優(yōu)搜索方面的主要方法之一。本文采用柵格法進(jìn)行環(huán)境建模，結(jié)合自適應(yīng)算子的遺傳算法對(duì)機(jī)器人進(jìn)行全局路徑靜態(tài)規(guī)劃。柵格法表示的地圖簡(jiǎn)單、直觀，直接使用柵格標(biāo)號(hào)對(duì)路徑個(gè)體進(jìn)行編碼，易于操作且節(jié)省內(nèi)存空間。不等長(zhǎng)染色體編碼和連續(xù)相鄰柵格搜索方法保證了初始生成路徑的多樣性和可行性，可自適應(yīng)地調(diào)整交叉概率和變異概率，能夠避免早熟現(xiàn)象。

1 建立巡檢模型

1.1 建立柵格地圖

只考慮巡檢機(jī)器人工作的變電站環(huán)境的平面狀況，變電站環(huán)境用正方形表示，變電站內(nèi)設(shè)備等效于機(jī)器人路徑中的障礙物，且尺寸和位置己知。在機(jī)器人的運(yùn)動(dòng)過(guò)程中，障礙物的位置不發(fā)生變化。如圖1所示，采用柵格法將機(jī)器人的工作空間劃分為成一系列大小相等的、具有二值信息的網(wǎng)格單元。柵格的二值信息包括直角坐標(biāo)（x，y）和柵格序號(hào)N，每個(gè)柵格都能用其中一個(gè)量值唯一表示。利用序號(hào)法編碼表示路徑，易于操作且節(jié)省存儲(chǔ)空間。當(dāng)需要評(píng)價(jià)一個(gè)路徑的優(yōu)劣時(shí)，可以將柵格序號(hào)轉(zhuǎn)換為二維直角坐標(biāo)，用以計(jì)算每條路徑的距離。每個(gè)柵格的序號(hào)和坐標(biāo)的對(duì)應(yīng)關(guān)系為：

N=x+10y. （1）

在圖1中，空白柵格表示巡檢機(jī)器人能夠自由通過(guò)的通道；陰影柵格表示障礙物，即變電站設(shè)備所占空間。一般在電氣設(shè)

———————————————————————————

備實(shí)際邊界的基礎(chǔ)上增加1個(gè)電氣絕緣的安全距離，并將其增補(bǔ)等效為正方形柵格。給每個(gè)柵格單元賦予一個(gè)二值屬性Property，記作P，空白柵格P值為0，陰影柵格P值為1.模擬機(jī)器人在自由通道行走時(shí)，需定義連續(xù)的相鄰柵格。如圖2所示，一般情況下，當(dāng)前柵格N有8個(gè)相鄰柵格，分別記作N-10-1，N-1，N+10-1，N+10，N+10+1，N+1，N-10+1和N-10.

圖1 環(huán)境地圖的10×10柵格描述

對(duì)于N-1，N+10，N+1和N-10柵格，與柵格N是連續(xù)相鄰柵格的條件為它們都為自由柵格；對(duì)于N-10-1，N+10-1，N+10+1和N+10+1柵格，都是柵格N的對(duì)角柵格，與柵格 是連續(xù)相鄰柵格的條件為各個(gè)對(duì)角柵格都為自由柵格，且每個(gè)對(duì)角柵格與柵格 公共的水平柵格和垂直柵格中至少有一個(gè)是自由柵格。搜索路徑時(shí)，當(dāng)前柵格的下一柵格可以是其任意一個(gè)連續(xù)相鄰的柵格。

對(duì)于柵格地圖中的邊界柵格 ，處理方式如下。

當(dāng)0

柵格越過(guò)地圖的下邊界，與N互為非連續(xù)相鄰柵格。

當(dāng)9≤N/10≤10時(shí)，柵格為地圖中的上邊界柵格，N+10柵格越過(guò)地圖的上邊界，與N互為非連續(xù)相鄰柵格。

當(dāng)mod（N，10）=1 mod時(shí)，柵格為地圖中的左邊界柵格，N-1柵格是地圖的右邊界，與N互為非連續(xù)相鄰柵格。

當(dāng)mod（N，10）=0時(shí)，柵格為地圖中的右邊界柵格，N+1柵格是地圖的左邊界，與N互為非連續(xù)相鄰柵格。

1.2 巡檢任務(wù)介紹

變電站常規(guī)巡檢承擔(dān)著變電站日常巡檢的主體任務(wù)，但因其巡檢范圍大，所需的巡檢強(qiáng)度和巡檢成本較高，加之一些突發(fā)狀況的干擾，常規(guī)巡檢模式不能完全滿足變電站巡檢的可靠性要求。針對(duì)某些需要多次巡檢的重要設(shè)備和一些特殊情況，需要增加重點(diǎn)設(shè)備巡檢和設(shè)備分級(jí)巡檢對(duì)常規(guī)巡檢進(jìn)行補(bǔ)充。

依據(jù)圖1所示的環(huán)境地圖，重點(diǎn)設(shè)備巡檢和設(shè)備分級(jí)巡檢的描述如下。

1.2.1 重點(diǎn)設(shè)備巡檢

設(shè)機(jī)器人充電室在柵格N1處，某個(gè)重點(diǎn)巡視設(shè)備對(duì)象?？抗の辉跂鸥馧m處，機(jī)器人從充電室出發(fā)，根據(jù)規(guī)劃路徑運(yùn)動(dòng)到重點(diǎn)設(shè)備處工位，巡視完畢后原路返回充電室，最優(yōu)規(guī)劃路徑要求路徑最短。

1.2.2 設(shè)備分級(jí)巡檢

設(shè)機(jī)器人充電室在柵格N1處，多個(gè)需要區(qū)分先后巡視順序的設(shè)備的?？抗の环謩e位于柵格N2，N3，…，Nm處，機(jī)器人從充電室出發(fā)，根據(jù)規(guī)劃路徑依次運(yùn)動(dòng)到各個(gè)重點(diǎn)設(shè)備工位處，巡視完畢后原路返回充電室。設(shè)備分級(jí)巡檢是變電站巡檢模式之一，從算法上可以將其分解成多個(gè)、單個(gè)重點(diǎn)設(shè)備巡檢的依次銜接。

2 改進(jìn)遺傳算法的路徑規(guī)劃

2.1 染色體編碼

一般的遺傳算法對(duì)解空間的編碼采用二進(jìn)制形式。對(duì)于柵格地圖中機(jī)器人的路徑規(guī)劃問(wèn)題，采用路徑經(jīng)過(guò)的柵格序號(hào)序列進(jìn)行編碼，機(jī)器人從起點(diǎn)達(dá)到終點(diǎn)的完整路徑表示1條染色體，每個(gè)柵格序號(hào)是1條染色體的基因之一。存儲(chǔ)算法所產(chǎn)生的路徑，有利于實(shí)現(xiàn)編程和節(jié)省存儲(chǔ)空間，無(wú)須解碼。

2.2 種群初始化

假定初始化種群染色體的個(gè)體數(shù)目為M=50，種群用1個(gè)染色體集合表示為：

Xt={X1，X2，…，Xm}. （2）

第i條染色體表示為：

Xi={N1，i ，N2，i，N3，i，…，Nj，i，…，Nm，i，}i∈{1，2，…，M}.

（3）

初始種群產(chǎn)生方法為：從起點(diǎn)柵格N1開(kāi)始，根據(jù)“連續(xù)的相鄰柵格”原則，從與之相鄰的8個(gè)柵格中，選取任一個(gè)連續(xù)相鄰柵格作為此染色體的第二個(gè)基因；從圍繞第二個(gè)基因的相鄰柵格中，選取一個(gè)連續(xù)相鄰柵格作為此染色體的第三個(gè)基因，依此類推，直到目標(biāo)柵格Nm為止。在搜索過(guò)程中，每個(gè)連續(xù)相鄰柵格被選取的概率相等，且當(dāng)前所選基因與間隔的上一基因不重復(fù)。

2.3 適應(yīng)度函數(shù)

取每條路徑的距離長(zhǎng)度為機(jī)器人路徑的目標(biāo)函數(shù)，記作f（D），則路徑規(guī)劃目標(biāo)函數(shù)為：

. （4）

式（4）中：d（Nj，iNj+i，i）為第i組染色體中的柵格Nj，i到柵格Nj+i，i的中心距離。

第i組染色體中的柵格Nj，i到柵格Nj+i，i的中心距離可表示為：

. （5）

適應(yīng)度函數(shù)取目標(biāo)函數(shù)的倒數(shù)，距離越短，適應(yīng)度值越大：

Fitness（Ni）=1/f（D）. （6）

2.4 遺傳操作

2.4.1 選擇算子

采用競(jìng)爭(zhēng)策略，令每一代染色體按適應(yīng)度優(yōu)劣競(jìng)爭(zhēng)，從中選出優(yōu)勝個(gè)體進(jìn)入下一代種群，直到充滿種群為止。輪盤(pán)賭是一種正比選擇策略，能根據(jù)與適值成正比的概率選出新種群，具體步驟如下。

第一步，分別計(jì)算每一個(gè)染色體的累積概率：

. （7）

式（7）中：Fitness（Xk）為第k個(gè)染色體的適應(yīng)值；

為一代所有個(gè)體適應(yīng)值的和。

第二步，在[0，1]區(qū)間隨機(jī)產(chǎn)生M個(gè)均勻分布的偽隨機(jī)數(shù)r.

第三步，對(duì)于每一個(gè)rk，如果pk-1

第四步，重復(fù)第三步，直到充滿種群得到大小為M的新種群。

2.4.2 交叉算子

交叉操作是結(jié)合來(lái)自父代交配種群中的信息產(chǎn)生新個(gè)體的過(guò)程，通常有單點(diǎn)交叉、多點(diǎn)交叉和均勻交叉等方法，本文選擇單點(diǎn)不等長(zhǎng)交叉的方法。只要2條路徑除首、尾柵格外通過(guò)相同的柵格，就可以以相同柵格為交叉點(diǎn)交叉。如果相同的柵格不止一個(gè)，則在這些相同的柵格中任選一個(gè)交叉；如果沒(méi)有相同的柵格，則不交叉。用交叉后的子代個(gè)體代替原種群中的父代個(gè)體，以產(chǎn)生新的種群。比如，2條染色體分別為：{64，75，86，77，78，79，89，99}和{64，65，66，76，86，96，97，98，99}，2條染色體有共同柵格86，以86柵格為交叉點(diǎn)交叉，交叉后得到新的2條子染色體為{64，75，86，96，97，98，99}和{64，65，66，76，86，77，78，79，89，99}。

2.4.3 變異算子

由于所產(chǎn)生的初始路徑個(gè)體均為機(jī)器人的連續(xù)路徑，一般的變異操作必然會(huì)產(chǎn)生不連通的路徑個(gè)體，對(duì)個(gè)體的優(yōu)越性產(chǎn)生破壞，進(jìn)而造成種群退化。為了克服這一不足，本文在保證路徑連續(xù)性的前提下進(jìn)行變異操作，具體過(guò)程如下。

第一步，隨機(jī)從種群中挑選出M×Pm個(gè)待變異的個(gè)體，Pm為變異概率。

第二步，選取每個(gè)個(gè)體靠近中間位置的2個(gè)柵格，并將其中部分刪除，將原染色體分成前、后兩段。

第三步，以前段路徑的最后柵格作為路徑起點(diǎn)，后部分路徑的起始柵格作為終點(diǎn)，采用節(jié)種群初始化方法搜索一段新的子路徑，將前、后兩段分開(kāi)的路徑連接起來(lái)構(gòu)成一條連續(xù)的路徑，作為新一代種群中的個(gè)體。

2.5 交叉和變異概率

選取常值交叉概率Pc和變異概率Pm，想要達(dá)到滿意的遺傳算法行為和性能，就需要反復(fù)試驗(yàn)，其過(guò)程煩瑣且不易得到適應(yīng)于每個(gè)問(wèn)題的最優(yōu)解。采用自適應(yīng)遺傳算法計(jì)算群體的平均適應(yīng)度時(shí)，對(duì)于適應(yīng)度高于種群平均適應(yīng)度的個(gè)體需保護(hù)優(yōu)質(zhì)解，對(duì)其采用較低的Pc和Pm；對(duì)于適應(yīng)度低于種群平均適應(yīng)度的個(gè)體，需淘汰劣質(zhì)解，對(duì)其采用較高的Pc和Pm.

Pc和Pm的自適應(yīng)調(diào)整公式如下：

. （8）

. （9）

式（8）（9）中：Fmax為種群中最大的適應(yīng)度；Fav為每代種群的平均適應(yīng)度；F'為交叉的兩個(gè)個(gè)體中較大的適應(yīng)度；F為要變異個(gè)體的適應(yīng)度。

3 仿真結(jié)果分析

在Matlab仿真環(huán)境中，對(duì)上述算法進(jìn)行了仿真測(cè)試。變電站環(huán)境設(shè)備區(qū)柵格分布情況如圖3所示，分別對(duì)機(jī)器人的兩種不同巡檢模式進(jìn)行了仿真，結(jié)果如下。

3.1 重點(diǎn)設(shè)備巡檢

從圖3中可以看出，機(jī)器人充電室在柵格“1”處，重點(diǎn)巡視的設(shè)備?？抗の辉跂鸥瘛?00”處，圖3中的實(shí)線為機(jī)器人最優(yōu)規(guī)劃路徑，單程路徑用柵格序號(hào)依次表示為：1→12→22→33→34→45→56→66→77→78→79→90→100. 單程路徑的最小距離長(zhǎng)度值為144.852.

圖3 重點(diǎn)設(shè)備巡檢規(guī)劃路徑

3.2 設(shè)備分級(jí)巡檢

仿真結(jié)果如圖4所示，機(jī)器人充電室在柵格“1”處，多個(gè)先后巡視的設(shè)備?？抗の环謩e位于柵格“52”“46”“17”“100”處。從算法上看，將中間?？奎c(diǎn)“52”“46”“17”依次當(dāng)作前、后尋優(yōu)路徑的終點(diǎn)和起點(diǎn)。圖4中的實(shí)線為機(jī)器人最優(yōu)規(guī)劃路徑，“o”表示各個(gè)不同的停靠工位。單程路徑用柵格序號(hào)依次表示為：1→12→22→32→42→52→63→64→55→46→36→26→17→18→19→39→49→60→70→80→90→100.單程路徑最小距離長(zhǎng)度值為238.9949.

圖3和圖4中的2種巡檢模式的仿真結(jié)果表明，本文采用的柵格法建模和遺傳算法避障規(guī)劃路徑的方法簡(jiǎn)單、有效，能快速、有效地得到最優(yōu)規(guī)劃路徑。

4 結(jié)束語(yǔ)

本文對(duì)變電站的工作環(huán)境進(jìn)行了分解建模，結(jié)合巡檢機(jī)器人的2種巡檢模式，并采用一種改進(jìn)的遺傳算法對(duì)巡檢機(jī)器人進(jìn)行了全局靜態(tài)規(guī)劃。

基于不等長(zhǎng)染色體編碼和連續(xù)相鄰柵格的隨機(jī)搜索算法初始化種群，能夠保證初始化種群的多樣性和可行性。同時(shí)，適當(dāng)改進(jìn)了遺傳算子，自適應(yīng)地調(diào)整了交叉概率和變異概率，能夠避免早熟現(xiàn)象。

2種巡檢模式的仿真結(jié)果顯示，本文采用的遺傳算法簡(jiǎn)單、有效，對(duì)變電站巡檢機(jī)器人實(shí)際應(yīng)用中的全局路徑規(guī)劃具有一定的借鑒意義。

圖4 分級(jí)設(shè)備巡檢規(guī)劃路徑

參考文獻(xiàn)

[1]毛琛琳，張功望，劉毅.智能機(jī)器人巡檢系統(tǒng)在變電站中的應(yīng)用[J].電網(wǎng)與清潔能源，2009，25（09）：30-33.

[2]劉滿祿.路徑規(guī)劃在巡邏機(jī)器人中的應(yīng)用[D].綿陽(yáng)：西南科技大學(xué)，2009.

[3]魯守銀，錢(qián)慶林，張斌，等.變電站設(shè)備巡檢機(jī)器人的研制[J].電力系統(tǒng)自動(dòng)化，2006，30（13）：94-98.

[4]高青，馮李軍，張鵬.智能巡檢機(jī)器人的研究[J].電氣時(shí)代，2012（4）：74-76.

[5]朱大奇，顏明重.移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)綜述[J].控制與決策，2010，25（7）：961-967.

[6]于振中，閆繼宏，趙杰，等.改進(jìn)人工勢(shì)場(chǎng)法的移動(dòng)機(jī)器人路徑規(guī)劃[J].哈爾濱工業(yè)大學(xué)學(xué)報(bào)，2011，43（01）：50-55.

[7]李擎，王麗君，陳博，等.一種基于遺傳算法參數(shù)優(yōu)化的改進(jìn)人工勢(shì)場(chǎng)法[J].北京科技大學(xué)學(xué)報(bào)，2012，34（2）：202-206.

[8]黃席樾，蔣卓強(qiáng).基于遺傳模擬退火算法的靜態(tài)路徑規(guī)劃研究[J].重慶工學(xué)院學(xué)報(bào)（自然科學(xué)版），2007，21（6）：53-57.

[9]朱磊，樊繼壯，趙杰.基于柵格法的礦難搜索機(jī)器人全局路徑規(guī)劃與局部避障[J].中南大學(xué)學(xué)報(bào)（自然科學(xué)版），2011， 42（11）：3421-3427.

[10]張碧叢，李琳，鄒炎飚.基于方位編碼的遺傳算法在路徑規(guī)劃中的應(yīng)用[J].煤礦機(jī)械，2011，32（03）：79-82.

[11]師黎，邵國(guó).改進(jìn)遺傳算法用于移動(dòng)機(jī)器人路徑規(guī)劃[J].計(jì)算工程與設(shè)計(jì)，2008，29（24）：6330-6333.

〔編輯：張思楠〕