基于改進A*算法的變電站智能巡檢機器人路徑優(yōu)化方法研究

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

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

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

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

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

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

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

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

圖1 柵格地圖

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

圖2 機器人運動方向

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

在路徑優(yōu)化領(lǐng)域的研究中，A*算法由于具有較強的靈活性及對周邊多變環(huán)境的高度適應(yīng)性而備受關(guān)注[9-12]。從本質(zhì)上來看，該算法歸屬于人工智能領(lǐng)域，其實現(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)表示為物體從路徑起點到當(dāng)前位置節(jié)點的實際運動距離，即從路徑起點至節(jié)點n所需的實際代價值，在單位距離標度準則下，物體此刻位置距離起點越遠，G(n)的值便越大；相應(yīng)的，函數(shù)H(n)則表示物體從路徑起點至當(dāng)前位置節(jié)點的運動距離估計值。由此可見，啟發(fā)函數(shù)F(n)包含了實際運動距離與估計運動距離兩部分信息。

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

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

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

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

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

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

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

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

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

1.3 變電站機器人智能巡檢

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

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

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

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

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

其中，巡檢機器人每運動一步的路徑代價d的大小為其在柵格中的搜索步長。

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

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

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

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

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

2 驗證與分析

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

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

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

圖5 第1組實驗路徑仿真

圖6 第2組實驗路徑仿真

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

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

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

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

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

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

3 結(jié)束語

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