連興文，朱旭東，陳云海，王少楠

（中國南方電網(wǎng)有限責(zé)任公司超高壓輸電公司昆明局，云南昆明 650000）

近年來，隨著智能電網(wǎng)[1]的不斷推廣與普及，我國的電力規(guī)劃取得了長足發(fā)展。而變電站智能化作為電網(wǎng)智能化的重要組成部分，也逐漸在智能巡檢[2]領(lǐng)域嶄露頭角。傳統(tǒng)的人工巡檢方式存在效率較低、耗費(fèi)人力成本及容易引發(fā)安全問題等缺點(diǎn)，因此采用巡檢機(jī)器人進(jìn)行智能巡檢的方式已成為變電站智能化的主流發(fā)展方向。

若要變電站智能巡檢機(jī)器人實(shí)現(xiàn)高質(zhì)量巡檢，則需一種高效率和高精確度的路徑優(yōu)化算法[3]。針對現(xiàn)實(shí)場景下存在的路況環(huán)境復(fù)雜多變及周圍工作人員干擾等情況，可采用智能算法[4]規(guī)劃出一條優(yōu)異路徑，以此達(dá)到高效率巡檢的目的。目前常用的啟發(fā)式智能[5]路徑優(yōu)化算法為傳統(tǒng)A*算法[6]，該算法在周圍環(huán)境簡單的情況下通常具有較好的路徑規(guī)劃能力。但在實(shí)際復(fù)雜多變的變電站環(huán)境下，其規(guī)劃出的路徑可能較長且不平滑，甚至可能存在碰撞。為解決上述問題，該文從規(guī)劃搜索空間及優(yōu)化啟發(fā)函數(shù)兩個(gè)角度對傳統(tǒng)A*算法進(jìn)行了優(yōu)化提升。一方面將機(jī)器人在柵格中的運(yùn)動方向擴(kuò)展為24 鄰域，另一方面在啟發(fā)函數(shù)中引入了碰撞威脅代價(jià)這一影響因素，進(jìn)而實(shí)現(xiàn)了最終規(guī)劃的路徑完整、平滑，且距離較短，并有效解決了巡檢過程中的碰撞問題。

1 基于改進(jìn)A*算法的路徑優(yōu)化

1.1 機(jī)器人巡檢環(huán)境建模

在進(jìn)行變電站智能巡檢機(jī)器人路徑優(yōu)化的研究中，首先需要將巡檢場景加以抽象。即通過傳感器獲取周圍環(huán)境信息，并對此進(jìn)行建模，以形成巡檢環(huán)境地圖。柵格地圖法[7-8]憑借其建模魯棒性強(qiáng)、表達(dá)直觀清晰等優(yōu)勢，目前已被廣泛應(yīng)用于機(jī)器人路徑規(guī)劃算法的研究之中。

該文在對機(jī)器人巡檢環(huán)境進(jìn)行建模時(shí)，采用單位長度的柵格地圖來表示巡檢機(jī)器人周邊的環(huán)境狀況信息，具體如圖1 所示。該方法將智能機(jī)器人的巡檢環(huán)境表示為多個(gè)具有相同尺度的方形網(wǎng)格，同時(shí)根據(jù)環(huán)境的阻塞情況將網(wǎng)格區(qū)分為兩種不同的狀態(tài)，分別是通暢與阻塞狀態(tài)。圖中空白區(qū)域網(wǎng)格表示該區(qū)域平坦，巡檢機(jī)器人可順利通過，即通暢狀態(tài)；黑色區(qū)域網(wǎng)格則表示該區(qū)域擁堵，巡檢機(jī)器人將會遇到障礙物，即阻塞狀態(tài)。

圖1 柵格地圖

為方便后續(xù)路徑優(yōu)化算法的研究，該文對機(jī)器人的具體運(yùn)動巡檢信息做出如下規(guī)定：1）智能機(jī)器人巡檢的整個(gè)過程中，變電站周圍的環(huán)境信息保持不變，即柵格地圖固定；2）如圖2 所示，當(dāng)巡檢機(jī)器人周圍不存在障礙物時(shí)，其可按照上、下、左、右、左上、左下、右上和右下共8 個(gè)方向移動。且智能機(jī)器人在巡檢的過程中，可忽略其自身高度信息的影響。

圖2 機(jī)器人運(yùn)動方向

1.2 A*路徑優(yōu)化算法

在路徑優(yōu)化領(lǐng)域的研究中，A*算法由于具有較強(qiáng)的靈活性及對周邊多變環(huán)境的高度適應(yīng)性而備受關(guān)注[9-12]。從本質(zhì)上來看，該算法歸屬于人工智能領(lǐng)域，其實(shí)現(xiàn)了傳統(tǒng)BFS 算法(Breadth-First-Search)[13]和Dijkstra 算法[14]的巧妙結(jié)合，從而表現(xiàn)出了更為優(yōu)異的路徑規(guī)劃性能。A*算法對應(yīng)的啟發(fā)函數(shù)可描述為：

式中，函數(shù)G(n)表示為物體從路徑起點(diǎn)到當(dāng)前位置節(jié)點(diǎn)的實(shí)際運(yùn)動距離，即從路徑起點(diǎn)至節(jié)點(diǎn)n所需的實(shí)際代價(jià)值，在單位距離標(biāo)度準(zhǔn)則下，物體此刻位置距離起點(diǎn)越遠(yuǎn)，G(n)的值便越大；相應(yīng)的，函數(shù)H(n)則表示物體從路徑起點(diǎn)至當(dāng)前位置節(jié)點(diǎn)的運(yùn)動距離估計(jì)值。由此可見，啟發(fā)函數(shù)F(n)包含了實(shí)際運(yùn)動距離與估計(jì)運(yùn)動距離兩部分信息。

基于上述介紹可知，函數(shù)H(n)代表了物體運(yùn)動距離的估計(jì)值，因此A*算法需選擇一個(gè)有效的距離評估公式來確定H(n)的大小。常用的距離評估函數(shù)包括歐氏距離[15]與曼哈頓距離[16]。

歐氏距離確定了n維空間中兩個(gè)孤立點(diǎn)p和q間的真實(shí)距離，其又被稱為歐幾里得距離，具體的數(shù)學(xué)符號可描述為：

在常見的二維平面中，對于點(diǎn)(x1，y1)和點(diǎn)(x2，y2)，二者間的歐氏距離可由式（2）改寫為：

由式（3）可知，二維平面中兩點(diǎn)間的歐氏距離即二者間的平面幾何距離。

曼哈頓距離從坐標(biāo)軸的角度對點(diǎn)之間的距離做了定義，在n維空間下，其可描述為兩個(gè)孤立點(diǎn)在n維坐標(biāo)軸上距離差的總和，具體數(shù)學(xué)實(shí)現(xiàn)如下：

對于點(diǎn)(x1,y1)和點(diǎn)(x2,y2)，二者間的曼哈頓距離則可由式（4）改寫為：

由式（5）可知，二維平面內(nèi)的曼哈頓距離為直角坐標(biāo)系中兩個(gè)點(diǎn)在坐標(biāo)軸上投影的距離之和。

確定了距離評估算法后，便可依據(jù)啟發(fā)函數(shù)進(jìn)行迭代搜索過程。在具體的算法實(shí)現(xiàn)過程中，主要依靠對OPEN 表與CLOSE 表的維護(hù)。其中，OPEN 表主要用于存放被運(yùn)動物體發(fā)現(xiàn)但還未對其進(jìn)行搜索的節(jié)點(diǎn)信息，而CLOSE 表則主要存放運(yùn)動物體已經(jīng)到達(dá)且搜索過的節(jié)點(diǎn)信息?；谶@兩個(gè)表并依據(jù)啟發(fā)函數(shù)，A*算法便會不斷朝著趨近目標(biāo)路徑的方向進(jìn)行迭代更新，從而實(shí)現(xiàn)最優(yōu)的路徑規(guī)劃。其具體的路徑規(guī)劃過程，如圖3 所示。

圖3 A*算法路徑規(guī)劃過程

1.3 變電站機(jī)器人智能巡檢

在傳統(tǒng)靜態(tài)環(huán)境中，A*算法能有效求得兩點(diǎn)間的最優(yōu)路徑規(guī)劃距離。然而在變電站具體巡檢環(huán)境的應(yīng)用背景下，由于場景的復(fù)雜性約束，傳統(tǒng)A*算法并不能表現(xiàn)出最優(yōu)異的性能，因此需要對其進(jìn)行改進(jìn)。該文從規(guī)劃搜索空間及優(yōu)化啟發(fā)函數(shù)兩個(gè)角度對該算法進(jìn)行優(yōu)化提升。

當(dāng)機(jī)器人在柵格中按照圖2 所示方向運(yùn)動時(shí)，其周圍最多存在8 個(gè)鄰域搜索點(diǎn)，且這些點(diǎn)可能為通暢或阻塞狀態(tài)。基于此，機(jī)器人運(yùn)動的方向角度被限制在了π/4 的整數(shù)倍內(nèi)，因此搜索迭代的行進(jìn)方向也被限制在了較小的鄰域范圍內(nèi)。為解決此問題，并擴(kuò)展機(jī)器人運(yùn)動搜索區(qū)域，該文在每個(gè)節(jié)點(diǎn)僅有8 個(gè)鄰域的基礎(chǔ)上，擴(kuò)展節(jié)點(diǎn)至周圍的24 個(gè)鄰域，從而增加了搜索范圍。

變電站智能巡檢機(jī)器人在巡檢過程中，不僅要求符合軌跡特性的最短路徑，同時(shí)也要求巡檢過程中不會與周圍障礙物發(fā)生碰撞，且可保持一定的安全距離。因此，為了防止機(jī)器人在最短路徑下與障礙物發(fā)生碰撞，需對A*算法原始啟發(fā)函數(shù)進(jìn)行相應(yīng)的優(yōu)化。即在原始啟發(fā)函數(shù)的基礎(chǔ)上引入碰撞威脅代價(jià)，并賦予一定的加權(quán)系數(shù)后，能獲得改進(jìn)的啟發(fā)函數(shù)為：

其中，gp(n)為巡檢機(jī)器人已走過路程的路徑代價(jià)，gc(n)為在巡檢途中與障礙物發(fā)生碰撞的代價(jià)，而Wp和Wc則為引入的加權(quán)系數(shù)，分別表示路徑與碰撞代價(jià)在實(shí)際代價(jià)中所占的比例。

路徑代價(jià)gp(n)可由機(jī)器人運(yùn)動路徑節(jié)點(diǎn)中距離的累加值表示：

其中，巡檢機(jī)器人每運(yùn)動一步的路徑代價(jià)d的大小為其在柵格中的搜索步長。

該文通過關(guān)鍵約束點(diǎn)與障礙物的距離來定義碰撞代價(jià)gc(n)，定義Cn為當(dāng)前節(jié)點(diǎn)下的碰撞威脅，dmin為關(guān)鍵約束點(diǎn)到障礙物的距離最小值，dsafe為設(shè)定的安全距離，則每個(gè)節(jié)點(diǎn)下的碰撞威脅Cn可表示為：

根據(jù)式（8），可得到碰撞代價(jià)gc(n)為巡檢機(jī)器人運(yùn)動途中發(fā)生的所有碰撞威脅總和，即：

綜上所述，優(yōu)化改進(jìn)后啟發(fā)函數(shù)的實(shí)際代價(jià)便由路徑及碰撞代價(jià)共同決定，且通過設(shè)定路徑代價(jià)和碰撞代價(jià)占比大小的不同，便可達(dá)到更優(yōu)的路徑規(guī)劃效果。

依據(jù)上文改進(jìn)A*算法的設(shè)計(jì)，該文所提算法具有復(fù)雜環(huán)境條件下的適應(yīng)性與穩(wěn)定性。綜合這兩個(gè)角度的優(yōu)化點(diǎn)，能夠確定出該算法的整體實(shí)現(xiàn)流程如圖4 所示。

圖4 該文算法實(shí)現(xiàn)流程

2 驗(yàn)證與分析

仿真測試在PC 端的Matlab 平臺上進(jìn)行，軟硬件環(huán)境參數(shù)如表1 所示。

表1 實(shí)驗(yàn)軟硬件環(huán)境配置

該文分別對傳統(tǒng)A*算法與所提算法進(jìn)行路徑規(guī)劃對比，具體的仿真環(huán)境限定為50×50 大小的柵格地圖。在此環(huán)境下，分別進(jìn)行兩次不同運(yùn)動距離的路徑規(guī)劃仿真，仿真結(jié)果如圖5-6 所示。

圖5 第1組實(shí)驗(yàn)路徑仿真

圖6 第2組實(shí)驗(yàn)路徑仿真

由圖可知，該文所提算法在實(shí)驗(yàn)仿真中規(guī)劃出的路徑具有轉(zhuǎn)折次數(shù)少、線路平滑及距離較短等多種優(yōu)勢，同時(shí)其規(guī)劃路徑有效規(guī)避了障礙物的影響。

為了從數(shù)據(jù)層面進(jìn)一步測試該算法的性能，通過設(shè)定不同尺寸的柵格地圖，來直接測定路徑尋優(yōu)的搜索時(shí)間與規(guī)劃路徑的長度，具體實(shí)驗(yàn)結(jié)果如表2-3 所示。

表2 路徑規(guī)劃搜索時(shí)間比較

由表2 可知，相比于傳統(tǒng)A*算法，該文算法的尋優(yōu)時(shí)間較少，且這種時(shí)間差異隨著柵格地圖尺寸的增大而變得更加明顯。當(dāng)柵格地圖的單邊尺寸增加到100 時(shí)，該文算法的搜索時(shí)間得到了顯著優(yōu)化。

由表3 可知，該文算法規(guī)劃出的最優(yōu)路徑距離低于傳統(tǒng)A*算法，這表明改進(jìn)后的算法具有更優(yōu)異的規(guī)劃性能。

表3 規(guī)劃路徑長度比較

3 結(jié)束語

該文從擴(kuò)展尋優(yōu)搜索鄰域及改進(jìn)啟發(fā)函數(shù)兩個(gè)角度對傳統(tǒng)的A*算法進(jìn)行了改進(jìn)，通過24 鄰域進(jìn)行啟發(fā)式搜索，提高了路徑規(guī)劃路線的平滑性、縮短了距離。同時(shí)，針對無法有效避障等問題，引入碰撞威脅代價(jià)對原有啟發(fā)函數(shù)進(jìn)行了改進(jìn)。實(shí)驗(yàn)仿真結(jié)果充分證明了該文所述的改進(jìn)算法具有更為優(yōu)越的綜合性能。