一種基于動態(tài)最小成本路徑啟發(fā)式算法的水冷壁爬壁機器人路徑規(guī)劃方法

摘要：為了滿足水冷壁爬壁機器人在復雜多變的表面進行工作的需求，文章針對其持續(xù)爬移運動的特點，提出了一種基于動態(tài)最小成本路徑啟發(fā)式（D*）算法的水冷壁爬壁機器人路徑規(guī)劃方法。該方法通過柵格法對須爬壁的工作環(huán)境進行建模，利用D*算法的動態(tài)重規(guī)劃特性，實現(xiàn)機器人在復雜多變的水冷壁表面環(huán)境下的有效路徑規(guī)劃。實驗結(jié)果表明，該方法能夠使爬壁機器人高效地完成水冷壁表面的路徑規(guī)劃任務。

關鍵詞：水冷壁爬壁機器人；D*算法；路徑規(guī)劃

中圖分類號：TP242.2 "文獻標志碼：A

0 引言

隨著自動化技術的快速發(fā)展，越來越多的機器人被廣泛地應用于各種危險、高空作業(yè)和苛刻工作環(huán)境。針對各種實際情況，國內(nèi)外研究人員研制了一系列專門的機器人來代替工人。水冷壁爬壁機器人作為其中的一種，在大型立面設備的檢測和維護方面具有重要的應用價值，例如在核電站冷卻塔、大型化工管路和石油化工儲罐［1］等重要設備的維修中，水冷壁機器人被大量使用。由于其工作危險性大，又經(jīng)常面臨高溫、高壓和強腐蝕性介質(zhì)等惡劣工況，常規(guī)的人工維修方法很難實現(xiàn)并具有重大安全隱患。水冷壁機器人的使用極大地提高了檢測與維護工作的效率，同時也大幅減少了人為作業(yè)所造成的安全隱患。

在水冷壁機器人的實際應用中，如何進行路徑規(guī)劃，關系到其工作效率與質(zhì)量。高效的路徑規(guī)劃算法可以有效降低路徑的重復次數(shù)，進而實現(xiàn)最少的工作時間與能量消耗。

路徑規(guī)劃效率對于爬壁機器人至關重要，主要受所采用的路徑規(guī)劃算法的影響?，F(xiàn)有的路徑規(guī)劃算法主要分為傳統(tǒng)算法和智能算法。傳統(tǒng)算法主要包括基于人工勢場的方法、向量場直方圖策略以及柵格地圖化技術；智能算法領域則涵蓋了蟻群優(yōu)化算法、基于遺傳機制的算法和神經(jīng)網(wǎng)絡驅(qū)動的方法，為爬壁機器人的路徑規(guī)劃提供了多樣化的選擇。當前國內(nèi)外學者對爬壁機器人路徑規(guī)劃進行了大量的研究［2-3］。如Metropolis等［4］首次提出模擬退火算法。該算法是一種基于概率跳躍特性的隨機優(yōu)化方法，以最高的初始溫度為開始，隨著溫度的逐步降低，對空間進行隨機搜索，從而獲得目標函數(shù)的最優(yōu)解。這一算法的優(yōu)點是無論函數(shù)多么復雜，系統(tǒng)都能找到最優(yōu)解。但該算法須要耗費大量的時間用于計算，收斂速度慢［5］。Lamini等［6］提出了一種在靜態(tài)環(huán)境中使用改進交叉算子的遺傳算法解決路徑規(guī)劃問題，結(jié)果表明該方法有助于找到最優(yōu)解。遺傳算法的結(jié)構(gòu)簡單，性能穩(wěn)定，尋優(yōu)能力強，效率高，魯棒性好，但是編碼時間較長，容易過早收斂。

在現(xiàn)代工業(yè)領域中，對水冷壁的維護和清潔工作至關重要。為了提高此類作業(yè)的效率和安全性，爬壁機器人技術得到了廣泛的研究和應用。本文提出一種新的解決方案，結(jié)合D*算法為爬壁機器人規(guī)劃出一條全面而詳盡的路徑規(guī)劃方案。該算法能夠確保機器人在執(zhí)行任務時對工作區(qū)域進行動態(tài)、細致的覆蓋。這樣的路徑規(guī)劃不僅減少了機器人因路徑不清或障礙物導致的重復移動，還顯著降低了控制難度，使機器人可以更加精確地執(zhí)行預定任務，同時保持較高的靈活性和適應性。

1 問題描述

1.1 構(gòu)造環(huán)境模型

設已知水冷壁爬壁機器人的工作環(huán)境，根據(jù)其作業(yè)需求，本文首先將工作區(qū)域分割成若干子區(qū)域并通過柵格方法為這些子區(qū)域創(chuàng)建網(wǎng)格地圖。柵格大小是由爬壁機器人的結(jié)構(gòu)確定的，保證爬壁機器人在進入某個柵格后可以完全覆蓋該網(wǎng)格進行作業(yè)。

通過繪制水冷壁柵格地圖，利用（xi，yi）表示柵格的位置坐標，由于實際的水冷壁形狀與柵格形狀不一致，構(gòu)建柵格地圖時須要將這些障礙物做“膨脹”處理［7］，變成規(guī)則的柵格地圖，如圖1所示。圖1中，障礙物使用黑色填充，需要遍歷的路徑使用白色填充。

1.2 D*算法

1.2.1 算法描述

D*算法是在A*算法基礎上發(fā)展起來的一種新的路徑規(guī)劃方法［8］，適用于動態(tài)的環(huán)境和復雜的場景。與A*算法相比，D*算法的最大優(yōu)點是以目標點為起點，保持從目標點出發(fā)的優(yōu)先級（OpenList），直至機器人目前所在的位置節(jié)點不在隊列中。該方法可以有效地利用已知的最短路徑，降低搜索成本，提升路徑規(guī)劃效率。在此基礎上，本文引入了一種啟發(fā)式、增量式的搜索策略并將其在路徑搜索中進行更好地優(yōu)化。

D*算法的公式為：

f（s）=g（s）+h（s）（1）

其中，s為爬壁機器人當前狀態(tài)，f（s）是機器人從初始狀態(tài)經(jīng)由狀態(tài)s到目標狀態(tài)的代價評估；g（s）為初始狀態(tài)到狀態(tài)s的實際代價；h（s）為狀態(tài)s到目標狀態(tài)的代價估計，也被稱作啟發(fā)函數(shù)。

對于空間中的2個點（x1，y1）（x2，y2），主要使用歐氏距離、曼哈頓距離等。在D*算法中，研究者常用歐氏距離作為代價值，其表達式如式（2）所示。

dEuclid=（x2-x1）2+（y2-y1）2（2）

1.2.2 D*算法流程

D*算法可分為初始化階段和動態(tài)搜索階段。

在初始化階段中，首先將目標點放入優(yōu)先隊列OpenList。與A*算法相比，D*算法的主要不同之處在于選擇拓展點的方式。在D*算法中，從OpenList中選擇具有最小k值的節(jié)點進行拓展，而在A*算法中則是選擇具有最小f值（即g+h）的節(jié)點進行拓展。這種反向搜索的方式使得D*算法能夠更好地應對動態(tài)環(huán)境的變化。

在動態(tài)避障搜索過程中，算法應判定當前擴展點的k與該擴展點的h值是否相等，即該擴展點是否恢復到Lower態(tài)。若klt;h，則根據(jù)一定的準則進行節(jié)點的拓展。這些準則包括如下3個方面：

（1）若相鄰節(jié)點從未被拓展過，則將其父節(jié)點設為當前點并將相鄰節(jié)點的h值設為當前點的h值加上從當前點到相鄰節(jié)點的代價值，將其放入OpenList；

（2）若相鄰節(jié)點的父節(jié)點是當前點，但相鄰節(jié)點的h值不等于當前點的h值加上從當前點到相鄰節(jié)點的代價值，則更新相鄰節(jié)點的h值，將其重新放入OpenList；

（3）若相鄰節(jié)點的父節(jié)點不是當前點且相鄰節(jié)點的h值大于當前點的h值加上從當前點到相鄰節(jié)點的代價值，則將當前點放入OpenList。

以上準則的目的在于使爬壁機器人在動態(tài)環(huán)境中保持路徑的最優(yōu)性并在需要時及時更新節(jié)點的狀態(tài)信息。其偽代碼如下：

Function： PROCESS-STATE（）

L1X=MIN-STATE（～）

L2if X=NULL then return -1

L3koId=GET-KMIN（）;DELETE（X）

L4if koldlt;h（X） then

L5 for each neighbor Y of X ：

L6 "if h（Y）≤kold and h（X）gt;h（Y）+c（Y，X） then

L7 ""b（X）=Y;h（X）=h（Y）+c（Y，X）

L8if kold=h（X） then

L9 for each neighbor Y of X ：

L10 "if t（Y）=NEW or

L11 """（b（Y）=X and h（Y）≠h（X）+c（X，Y） or

L12b（Y）≠X and h（Y）gt;h（X）+c（X，Y）） then

L13b（Y）=X;INSERT（Y，h（X）+c（X，Y） ）

L14else

L15for each neighbor Y of X ：

L16if t（Y）=NEW or

L17 """（b（Y）=X and h（Y）≠h（X）+c（X，Y） then

L18b（Y）=X;INSERT（Y，h（X）+c（X，Y））

L19else

L20" if b（Y）≠X and h（Y）gt;h（X）+c（X，Y） then

L21 "INSERT （X，h（X））

L22 else

L23 "if b（Y）≠X and h（X）gt;h（Y）+c（Y，X） and

L24 """t（Y）=CLOSED and h（Y）gt;kold then

L25INSERT（Y，h（Y））

L26return GET-KMIN （ ）

D*算法最大的優(yōu)點是可以根據(jù)不同的情況，對不同的環(huán)境進行相應調(diào)整。在此基礎上，本文通過反向搜索方法，可以有效地利用已有的最短路徑信息以降低路徑規(guī)劃的時空復雜性。

2 實驗與分析

2.1 實驗步驟

所提算法的實驗步驟如下。

步驟1：建立水冷壁環(huán)境的柵格地圖。本文設計并實現(xiàn)一個水冷壁環(huán)境的柵格地圖，以模擬實際的水冷壁空間。

步驟2：定義路徑搜索的起點和終點。在柵格地圖中，所提算法設定路徑搜索的起始點和終點并規(guī)劃搜索路徑的走向。

步驟3：將D*算法應用于靜態(tài)障礙物的柵格地圖。研究者將D*算法應用于包含靜態(tài)障礙物的柵格地圖中，進行路徑規(guī)劃實驗并記錄實驗中每次路徑規(guī)劃所需的時間。

步驟4：分析仿真數(shù)據(jù)并形成結(jié)論。研究者對仿真實驗的數(shù)據(jù)進行詳細分析，基于分析結(jié)果得出實驗的結(jié)論。

2.2 仿真實驗

本文采用PYCHARM軟件進行實驗仿真，工作環(huán)境主要運用50×30和60×40這2種水冷壁仿真柵格模型并隨機生成障礙物。

本文在50×30的仿真柵格地圖上使用D*算法使爬壁機器人在仿真地圖上進行路徑規(guī)劃，結(jié)果如圖2所示。在60×40的仿真地圖上，重復上述的實驗步驟，其路徑規(guī)劃如圖3所示，其中白色區(qū)域為無障礙物區(qū)域，黑色區(qū)域為模擬水冷壁機器人在爬行過程中遇到的障礙物區(qū)域，曲線是爬壁機器人經(jīng)過D*算法計算出的路徑。

2.3 仿真實驗分析

本文利用D*算法在50×30和60×40的水冷壁仿真柵格地圖上進行多次仿真路徑規(guī)劃，并將D*算法在不同大小、不同環(huán)境的仿真地圖上完成路徑規(guī)劃所需要的時間并記錄在表1和表2中。

由圖2和圖3可以看出，在各種規(guī)模和環(huán)境復雜度的情況下，基于D*算法的水冷壁爬壁機器人展現(xiàn)出了卓越的規(guī)劃性能。這種算法不僅能夠迅速地識別并繞開潛在障礙，還能規(guī)劃出一條高效、安全的路徑，確保機器人能夠順利執(zhí)行各種探測任務，使其在復雜環(huán)境中安全穿行避免遭受意外碰撞或接觸障礙物的風險。當仿真地圖的規(guī)模不斷增大或者障礙物數(shù)量顯著增多時，機器人需要更多時間來解決這些復雜的路徑選擇問題。這意味著隨著地圖細節(jié)的增加和障礙物密度的提高，所需規(guī)劃時間將顯著增加。

3 結(jié)語

爬壁機器人在水冷壁等大型立面上的爬行能力在很大程度上依賴于其路徑規(guī)劃算法的高效性。本文通過研究水冷壁爬壁機器人的運動路徑規(guī)劃算法，利用柵格化建模技術，將復雜的壁面曲面轉(zhuǎn)換成易于求解的一維結(jié)構(gòu)面并在此基礎上增加了壁面上的障礙物位置及特征。爬壁機器人利用D*算法對柵格地圖進行快速搜索與規(guī)劃，以保證機器人的避障能力，同時縮短了機器人的運動軌跡。本文通過模擬試驗，驗證了該方法的正確性并以實測數(shù)據(jù)驗證了該方法的有效性與可靠性。本項目的研究成果將為水冷壁爬壁機器人的運動軌跡規(guī)劃提供重要的技術支撐。為了驗證算法的實際應用效果，本文采用PYCHARM開發(fā)環(huán)境對所提路徑規(guī)劃算法進行了仿真測試。仿真結(jié)果證明了D*算法在水冷壁柵格地圖中進行路徑規(guī)劃的可行性和有效性。

參考文獻

［1］王思佳，吳珊紅，李雷.爬壁機器人技術研究現(xiàn)狀及展望［J］.科技風，2019（2）：2.

［2］曹翔，俞阿龍.移動機器人全覆蓋信度函數(shù)路徑規(guī)劃算法［J］.智能系統(tǒng)學報，2018（2）：314-321.

［3］張赤斌，王興松.基于蟻群算法的完全遍歷路徑規(guī)劃研究［J］.中國機械工程，2008（16）：1945-1949.

［4］趙炳巍，賈峰，曹巖，等.基于模擬退火算法的人工勢場法路徑規(guī)劃研究［J］.計算機工程與科學，2022（4）：746-752.

［5］BEHNCK P L，DOERING D，PEREIRA E C，et al. A modified simulated annealing algorithm for SUAVs path planning［J］. IFAC PapersOnLine， 2015（10）：63-68.

［6］LAMINI C，BENHLIMA S，ELBEKRI A. Genetic algorithm based approach for autonomous mobile robot path planning［J］. Procedia Computer Science，2018，127：180-189.

［7］謝坤霖，李宗根，代宇航，等.基于啟發(fā)式搜索算法的掃地機器人路徑規(guī)劃［J］.西華大學學報（自然科學版），2019（4）：69-76.

［8］秦旭，黃曉華，馬東明，等.基于改進D*算法的巡檢機器人路徑規(guī)劃［J］.組合機床與自動化加工技術，2022（6）：10-13.

（編輯 王雪芬編輯）

Path planning method of water-cooled wall-climbing robot based on dynamic minimum

cost path heuristic algorithm

LIN" Jianhua1， FEI" Xuejun1， WU" Jie1， HUANG "Xianming2*

（1.Jiangsu Changshu Power Generation Co.， Ltd.， Suzhou 215500， China; 2.Changshu Institute of

Technology， Suzhou 215500， China）

Abstract： In order to meet the requirement for the robot working on the complex and variable surface of the water-cooled wall， as well as against its continuous crawling characteristics， a path planning method for a water-cooled wall-climbing robot based on the dynamic minimum cost path heuristic（D*） algorithm is proposed. By the grid method， this method models the working environment requiring climbing walls， and utilizes the dynamic reprogramming feature of the D* algorithm to achieve effective path planning for robots in complex and variable water-cooled wall surface environments. The experimental results demonstrate that the proposed method can make the wall-climbing robot effectively accomplish the path planning tasks for water-cooled wall surface.

Key words： water-cooled wall-climbing robot; D* algorithm; path planni