柵格遺傳算法的變電站巡檢機器人路徑規劃

姜英杰　呂學勤　段利偉

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

關鍵詞：巡檢機器人；柵格法；改進遺傳算法；路徑規劃

中圖分類號：TP242 文獻標識碼：A DOI：10.15913/j.cnki.kjycx.2015.06.012

變電站傳統的人工巡檢方式中存在勞動強度大、管理成本高和工作效率低等不足，且很多變電站受惡劣地理、氣候條件的限制，一般的人工巡檢很難實現有效的巡檢工作，即使一些變電站實現了少人或無人值班，但依舊在一定程度上存在因無人及時監視、巡視而帶來的一系列問題。因此，智能化巡檢已成為發展智能變電站的必然要求。基于移動機器人技術開發的變電站巡檢機器人系統，利用機器人主體的自主運動，并根據巡檢任務在特定的工位停靠，通過攜帶的紅外熱像儀、可見光CCD等相關電站設備檢測裝置進行設備檢測，能及時發現電力設備的內部熱缺陷、外部機械和電氣問題，從而提高工作效率和質量，真正起到減員增效的作用，最終推進變電站無人值守的發展。

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

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

1 建立巡檢模型

1.1 建立柵格地圖

只考慮巡檢機器人工作的變電站環境的平面狀況，變電站環境用正方形表示，變電站內設備等效于機器人路徑中的障礙物，且尺寸和位置己知。在機器人的運動過程中，障礙物的位置不發生變化。如圖1所示，采用柵格法將機器人的工作空間劃分為成一系列大小相等的、具有二值信息的網格單元。柵格的二值信息包括直角坐標（x，y）和柵格序號N，每個柵格都能用其中一個量值唯一表示。利用序號法編碼表示路徑，易于操作且節省存儲空間。當需要評價一個路徑的優劣時，可以將柵格序號轉換為二維直角坐標，用以計算每條路徑的距離。每個柵格的序號和坐標的對應關系為：

N=x+10y. （1）

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

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

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

圖1 環境地圖的10×10柵格描述

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

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

當0

柵格越過地圖的下邊界，與N互為非連續相鄰柵格。

當9≤N/10≤10時，柵格為地圖中的上邊界柵格，N+10柵格越過地圖的上邊界，與N互為非連續相鄰柵格。

當mod（N，10）=1 mod時，柵格為地圖中的左邊界柵格，N-1柵格是地圖的右邊界，與N互為非連續相鄰柵格。

當mod（N，10）=0時，柵格為地圖中的右邊界柵格，N+1柵格是地圖的左邊界，與N互為非連續相鄰柵格。

1.2 巡檢任務介紹

變電站常規巡檢承擔著變電站日常巡檢的主體任務，但因其巡檢范圍大，所需的巡檢強度和巡檢成本較高，加之一些突發狀況的干擾，常規巡檢模式不能完全滿足變電站巡檢的可靠性要求。針對某些需要多次巡檢的重要設備和一些特殊情況，需要增加重點設備巡檢和設備分級巡檢對常規巡檢進行補充。

依據圖1所示的環境地圖，重點設備巡檢和設備分級巡檢的描述如下。

1.2.1 重點設備巡檢

設機器人充電室在柵格N1處，某個重點巡視設備對象停靠工位在柵格Nm處，機器人從充電室出發，根據規劃路徑運動到重點設備處工位，巡視完畢后原路返回充電室，最優規劃路徑要求路徑最短。

1.2.2 設備分級巡檢

設機器人充電室在柵格N1處，多個需要區分先后巡視順序的設備的停靠工位分別位于柵格N2，N3，…，Nm處，機器人從充電室出發，根據規劃路徑依次運動到各個重點設備工位處，巡視完畢后原路返回充電室。設備分級巡檢是變電站巡檢模式之一，從算法上可以將其分解成多個、單個重點設備巡檢的依次銜接。

2 改進遺傳算法的路徑規劃

2.1 染色體編碼

一般的遺傳算法對解空間的編碼采用二進制形式。對于柵格地圖中機器人的路徑規劃問題，采用路徑經過的柵格序號序列進行編碼，機器人從起點達到終點的完整路徑表示1條染色體，每個柵格序號是1條染色體的基因之一。存儲算法所產生的路徑，有利于實現編程和節省存儲空間，無須解碼。

2.2 種群初始化

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

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

第i條染色體表示為：

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

（3）

初始種群產生方法為：從起點柵格N1開始，根據“連續的相鄰柵格”原則，從與之相鄰的8個柵格中，選取任一個連續相鄰柵格作為此染色體的第二個基因；從圍繞第二個基因的相鄰柵格中，選取一個連續相鄰柵格作為此染色體的第三個基因，依此類推，直到目標柵格Nm為止。在搜索過程中，每個連續相鄰柵格被選取的概率相等，且當前所選基因與間隔的上一基因不重復。

2.3 適應度函數

取每條路徑的距離長度為機器人路徑的目標函數，記作f（D），則路徑規劃目標函數為：

. （4）

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

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

. （5）

適應度函數取目標函數的倒數，距離越短，適應度值越大：

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

2.4 遺傳操作

2.4.1 選擇算子

采用競爭策略，令每一代染色體按適應度優劣競爭，從中選出優勝個體進入下一代種群，直到充滿種群為止。輪盤賭是一種正比選擇策略，能根據與適值成正比的概率選出新種群，具體步驟如下。

第一步，分別計算每一個染色體的累積概率：

. （7）

式（7）中：Fitness（Xk）為第k個染色體的適應值；

為一代所有個體適應值的和。

第二步，在[0，1]區間隨機產生M個均勻分布的偽隨機數r.

第三步，對于每一個rk，如果pk-1

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

2.4.2 交叉算子

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

2.4.3 變異算子

由于所產生的初始路徑個體均為機器人的連續路徑，一般的變異操作必然會產生不連通的路徑個體，對個體的優越性產生破壞，進而造成種群退化。為了克服這一不足，本文在保證路徑連續性的前提下進行變異操作，具體過程如下。

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

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

第三步，以前段路徑的最后柵格作為路徑起點，后部分路徑的起始柵格作為終點，采用節種群初始化方法搜索一段新的子路徑，將前、后兩段分開的路徑連接起來構成一條連續的路徑，作為新一代種群中的個體。

2.5 交叉和變異概率

選取常值交叉概率Pc和變異概率Pm，想要達到滿意的遺傳算法行為和性能，就需要反復試驗，其過程煩瑣且不易得到適應于每個問題的最優解。采用自適應遺傳算法計算群體的平均適應度時，對于適應度高于種群平均適應度的個體需保護優質解，對其采用較低的Pc和Pm；對于適應度低于種群平均適應度的個體，需淘汰劣質解，對其采用較高的Pc和Pm.

Pc和Pm的自適應調整公式如下：

. （8）

. （9）

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

3 仿真結果分析

在Matlab仿真環境中，對上述算法進行了仿真測試。變電站環境設備區柵格分布情況如圖3所示，分別對機器人的兩種不同巡檢模式進行了仿真，結果如下。

3.1 重點設備巡檢

從圖3中可以看出，機器人充電室在柵格“1”處，重點巡視的設備停靠工位在柵格“100”處，圖3中的實線為機器人最優規劃路徑，單程路徑用柵格序號依次表示為：1→12→22→33→34→45→56→66→77→78→79→90→100. 單程路徑的最小距離長度值為144.852.

圖3 重點設備巡檢規劃路徑

3.2 設備分級巡檢

仿真結果如圖4所示，機器人充電室在柵格“1”處，多個先后巡視的設備停靠工位分別位于柵格“52”“46”“17”“100”處。從算法上看，將中間停靠點“52”“46”“17”依次當作前、后尋優路徑的終點和起點。圖4中的實線為機器人最優規劃路徑，“o”表示各個不同的停靠工位。單程路徑用柵格序號依次表示為：1→12→22→32→42→52→63→64→55→46→36→26→17→18→19→39→49→60→70→80→90→100.單程路徑最小距離長度值為238.9949.

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

4 結束語

本文對變電站的工作環境進行了分解建模，結合巡檢機器人的2種巡檢模式，并采用一種改進的遺傳算法對巡檢機器人進行了全局靜態規劃。

基于不等長染色體編碼和連續相鄰柵格的隨機搜索算法初始化種群，能夠保證初始化種群的多樣性和可行性。同時，適當改進了遺傳算子，自適應地調整了交叉概率和變異概率，能夠避免早熟現象。

2種巡檢模式的仿真結果顯示，本文采用的遺傳算法簡單、有效，對變電站巡檢機器人實際應用中的全局路徑規劃具有一定的借鑒意義。

圖4 分級設備巡檢規劃路徑

參考文獻

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

[2]劉滿祿.路徑規劃在巡邏機器人中的應用[D].綿陽：西南科技大學，2009.

[3]魯守銀，錢慶林，張斌，等.變電站設備巡檢機器人的研制[J].電力系統自動化，2006，30（13）：94-98.

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

[5]朱大奇，顏明重.移動機器人路徑規劃技術綜述[J].控制與決策，2010，25（7）：961-967.

[6]于振中，閆繼宏，趙杰，等.改進人工勢場法的移動機器人路徑規劃[J].哈爾濱工業大學學報，2011，43（01）：50-55.

[7]李擎，王麗君，陳博，等.一種基于遺傳算法參數優化的改進人工勢場法[J].北京科技大學學報，2012，34（2）：202-206.

[8]黃席樾，蔣卓強.基于遺傳模擬退火算法的靜態路徑規劃研究[J].重慶工學院學報（自然科學版），2007，21（6）：53-57.

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

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

[11]師黎，邵國.改進遺傳算法用于移動機器人路徑規劃[J].計算工程與設計，2008，29（24）：6330-6333.

〔編輯：張思楠〕