韓耀廷，趙志梅，郝曉宇，劉亦鑫

（內(nèi)蒙古電力集團(tuán)蒙電信息通信產(chǎn)業(yè)有限責(zé)任公司，呼和浩特 010020）

0 引言

變電站巡檢是保證變電站穩(wěn)定運(yùn)行的重要工作之一，傳統(tǒng)巡檢工作由人工完成，對工作人員的要求較高，而且變電站存在異常情況時，易造成人員傷亡和經(jīng)濟(jì)損失，給電網(wǎng)的安全穩(wěn)定運(yùn)行帶來不良影響。隨著人工智能產(chǎn)品的成熟，部分變電站的巡檢工作已逐步由巡檢機(jī)器人代替[1-2]。巡檢機(jī)器人可通過各種傳感器對變電站中設(shè)備的各項(xiàng)指標(biāo)進(jìn)行檢測，同時，后臺管理系統(tǒng)可對采集的數(shù)據(jù)進(jìn)行自動分析、實(shí)時預(yù)警[3-4]。巡檢機(jī)器人在巡檢工作中依賴的導(dǎo)航技術(shù)包括全局路徑規(guī)劃、機(jī)器人地圖定位、指示機(jī)器人局部行為等（其中全局路徑規(guī)劃是最核心技術(shù)）。目前采用A*算法進(jìn)行巡檢路徑規(guī)劃時，在啟發(fā)式前期將某些潛在的最優(yōu)節(jié)點(diǎn)無差別刪除，導(dǎo)致在某些情況下無法找到全局最優(yōu)路徑，只能尋得次優(yōu)路徑，使得巡檢效率較低[5-6]。本文從增加搜索鄰域節(jié)點(diǎn)和提升算法效率兩個角度優(yōu)化傳統(tǒng)A*算法，以提升路徑規(guī)劃的效果和效率。

1 A*算法路徑規(guī)劃存在的問題

針對機(jī)器人外界環(huán)境及人為因素，采用智能算法規(guī)劃巡檢路徑，定義一條最優(yōu)路徑或次優(yōu)路徑，以檢測變電站內(nèi)部關(guān)鍵位置，采集重要設(shè)備信息，這個過程要求巡檢機(jī)器人無碰撞到達(dá)[7-8]。在基于柵格法建立的變電站地圖中，路徑規(guī)劃通常采用基于啟發(fā)式的搜索算法和基于智能路徑的規(guī)劃算法[9-10]。

啟發(fā)式算法中常用的是A*算法，該方法在靜態(tài)環(huán)境中有較好的路徑規(guī)劃能力[11-12]。然而在以柵格為基礎(chǔ)的A*算法中，每個柵格的中心都存儲著節(jié)點(diǎn)的所有狀態(tài)信息（見圖1），節(jié)點(diǎn)臨近的8個區(qū)域都是這個節(jié)點(diǎn)的擴(kuò)展方向，即該節(jié)點(diǎn)在選擇下一個行進(jìn)點(diǎn)時，周圍最多存在8個（有可能存在障礙點(diǎn)）待選行進(jìn)點(diǎn)，因此運(yùn)動方向的角度被限定為π/4的整數(shù)倍[13-14]。由于受到行進(jìn)方向的限制，使用A*算法在柵格地圖上進(jìn)行巡檢機(jī)器人路徑規(guī)劃時，規(guī)劃出的路徑不平滑，增加了路徑長度，可能不是最優(yōu)路徑，巡檢效率不能達(dá)到最優(yōu)[15]。圖2為采用以柵格為基礎(chǔ)的A*路徑算法規(guī)劃X點(diǎn)到Y(jié)點(diǎn)的巡檢路徑（無障礙點(diǎn)）。從規(guī)劃效果看，規(guī)劃路徑并不是最優(yōu)路徑，存在轉(zhuǎn)折點(diǎn)復(fù)雜、轉(zhuǎn)折次數(shù)多、平滑性欠缺等問題。

圖1 A*算法8鄰域示意圖

圖2 A*算法規(guī)劃路徑

2 算法改進(jìn)

為了使路徑規(guī)劃更加合理，對傳統(tǒng)A*算法進(jìn)行改進(jìn)。將傳統(tǒng)A*算法每個節(jié)點(diǎn)的擴(kuò)展個數(shù)從8個鄰域增加至16個鄰域，擴(kuò)展后的鄰域示意圖見圖3。同時，采用最小二叉堆對傳統(tǒng)A*算法的OPEN列表按照歐氏距離由小到大的順序在堆中有序存儲，每次取堆中第一個元素即為路徑中代價最小的節(jié)點(diǎn)，16鄰域A*算法路徑規(guī)劃流程見圖4。具體流程如下。

圖3 A*算法16鄰域示意圖

圖4 16鄰域A*算法路徑規(guī)劃流程

（1）模擬變電站的路徑信息，建立如圖5所示的基于柵格地圖的工作環(huán)境空間，藍(lán)色邊框?yàn)楫?dāng)前變電站的邊界，藍(lán)色不規(guī)則圖形代表變電站中的障礙物，白色代表可通行路徑，區(qū)域長度為300單元格，寬度為200單元格。

圖5 模擬變電站柵格圖

（2）在數(shù)據(jù)空間中建立OPEN和CLOSE表，以最小二叉堆的形式在OPEN表中納入堆頂點(diǎn)為s，CLOSE表內(nèi)用數(shù)值表示存儲障礙點(diǎn)，以表明其為禁止通過區(qū)域。

（3）根據(jù)16鄰域A*算法對每個輸入點(diǎn)為中心的兩層鄰接點(diǎn)進(jìn)行判斷。首先判斷其是否為障礙點(diǎn)或已經(jīng)存在于OPEN表中的點(diǎn)，若既不是障礙點(diǎn)也不是OPEN表中已有的點(diǎn)，則采用最小二叉堆的存儲方式加入到OPEN表中，以節(jié)點(diǎn)的F值作為排列父子節(jié)點(diǎn)順序的規(guī)則，每個父節(jié)點(diǎn)的F值都比其子節(jié)點(diǎn)的F值小，采用這種方式存儲時，每次在堆頂?shù)墓?jié)點(diǎn)有可能成為最優(yōu)路徑上的節(jié)點(diǎn)；若其為障礙點(diǎn)或已經(jīng)存在于CLOSE表中，則跳過該點(diǎn)；若其不是障礙點(diǎn)且在OPEN表中，則比較該節(jié)點(diǎn)與其父節(jié)點(diǎn)的G值，取G值小的點(diǎn)作為新的父節(jié)點(diǎn)，并重新計(jì)算G值和F值。

（4）取出OPEN表中F值最小的節(jié)點(diǎn)加入到CLOSE表中，即將根節(jié)點(diǎn)加入CLOSE表中。判斷當(dāng)前節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)，若為目標(biāo)節(jié)點(diǎn)，則最優(yōu)解找到，否則判斷OPEN表是否為空，若為空，則路徑不存在；若不為空，則擴(kuò)展當(dāng)前節(jié)點(diǎn)并生成后繼節(jié)點(diǎn)，返回步驟3繼續(xù)判斷。

3 試驗(yàn)與結(jié)果

3.1 環(huán)境配置

在PyCharm COMMUNITY 2019.2環(huán)境中，創(chuàng)建長度為300單元格，寬度為200單元格的柵格圖，內(nèi)部包含60 000個頂點(diǎn)，59 501個柵格。試驗(yàn)中主機(jī)配置為Intel Core i7-8565U CPU@1.8 GHz，內(nèi)存為8 GB，16鄰域A*算法通過Python編程實(shí)現(xiàn)。路徑規(guī)劃結(jié)果使用Python進(jìn)行繪圖展示。

3.2 對比試驗(yàn)

為驗(yàn)證基于16鄰域A*算法對于路徑規(guī)劃的有效性，使用傳統(tǒng)A*算法與16鄰域A*算法進(jìn)行對照試驗(yàn)，在一張300單元格×200單元格柵格地圖上，通過設(shè)置4個不同的終點(diǎn)，進(jìn)行4組對比試驗(yàn)。為避免試驗(yàn)過程中產(chǎn)生隨機(jī)誤差，每組試驗(yàn)數(shù)據(jù)由5次重復(fù)試驗(yàn)的平均值得出。本次試驗(yàn)過程中，4組試驗(yàn)的起點(diǎn)位置均為（50，30），終點(diǎn)位置的橫坐標(biāo)按照從左至右、縱坐標(biāo)按照從下至上依次增加的方式進(jìn)行組合，最終得到相應(yīng)的終點(diǎn)位置，如表1所示。

表1 傳統(tǒng)A*算法與16鄰域A*算法路徑規(guī)劃效果對比

由第一組和第四組試驗(yàn)可以看出，路徑上障礙物越多，尋路時間越長，符合客觀規(guī)律。在尋路時間較長的路徑中，16鄰域A*算法在尋路效率方面更有優(yōu)勢。比如，在第一組和第二組試驗(yàn)中，由于路徑上障礙物較多，尋路時間均超過50 s，16鄰域A*算法的尋路時間較傳統(tǒng)A*算法節(jié)約4 s的時間；而尋路時間較短的路徑中，兩種算法的尋路效率相近，如第三組和第四組試驗(yàn)中，兩種算法的尋路時間和最終獲得的最優(yōu)路徑在數(shù)值上趨近，差距較小。16鄰域A*算法的遍歷點(diǎn)數(shù)較傳統(tǒng)A*算法多，因?yàn)?6鄰域A*算法在OPEN表中加入了更多的候選節(jié)點(diǎn)，使路徑可選方向得到進(jìn)一步擴(kuò)展。在最優(yōu)路徑的尋找過程中，16鄰域A*算法能夠在更短的時間內(nèi)找出更優(yōu)的路徑，尤其在尋路時間較長的路徑上更明顯。

圖6—圖9為傳統(tǒng)A*算法與16鄰域A*算法路徑規(guī)劃對比圖。圖中包含了4組試驗(yàn)中兩種算法各自選出的最優(yōu)路徑?？梢钥闯?，傳統(tǒng)A*算法在解決移動機(jī)器人路徑規(guī)劃時，由于受到了運(yùn)動方向的限制，導(dǎo)致規(guī)劃處的路徑轉(zhuǎn)折點(diǎn)比較復(fù)雜、轉(zhuǎn)折次數(shù)較多，最終得到的路徑不夠平滑，而且規(guī)劃出的路徑長度也不是最優(yōu)，而16鄰域A*算法在路徑的轉(zhuǎn)折點(diǎn)個數(shù)、路徑平滑性等指標(biāo)上都有所改進(jìn)。

圖6 第一組試驗(yàn)對比圖

圖9 第四組試驗(yàn)對比圖

圖7 第二組試驗(yàn)對比圖

圖8 第三組試驗(yàn)對比圖

4 結(jié)束語

本文針對傳統(tǒng)A*算法在路徑規(guī)劃時可能出現(xiàn)規(guī)劃路徑長度不是最優(yōu)、路徑不夠平滑等問題，提出采用16鄰域A*算法對每個輸入點(diǎn)為中心的兩層所有鄰接點(diǎn)進(jìn)行判斷，使得A*算法在進(jìn)行路徑規(guī)劃時，路徑方向的選擇不再受限于π/4的整數(shù)倍。同時，采用最小二叉堆對OPEN表中的候選節(jié)點(diǎn)進(jìn)行存儲，使算法整體復(fù)雜度變小。新算法在提高路徑規(guī)劃平滑性上有較好效果，同時保證了算法的效率，為解決變電站巡檢路徑規(guī)劃問題提供了新的思路。