面向大型工件的改進A*無碰路徑規劃

陳潔濤

廣東工業大學 廣東 廣州 510006

0 引言

當今,機器人在工業、科研探索以及服務業等領域都有廣泛的應用,其應用都離不開路徑規劃[1]。用于實體噴涂的機器人路徑規劃方法存在效率低、實用性差等問題,如何有效提高噴涂機器人無碰路徑的安全性和實用性已成趨勢[2-4]。

隨著自動化技術等高速發展,A*、RRT等智能算法在無碰路徑規劃得到了廣泛的研究和應用[5]。傳統的A*算法是基于柵格地圖的算法,而傳統A*算法在規劃過程中拓展的節點數多,存在冗余點多以及路徑長的問題[6-8]。為解決面向大型工件的無碰路徑規劃時建圖和尋路效率低的問題,本文對傳統的A*算法進行改進,提高運算效率。

(一)改進A*算法無碰路徑規劃

本文改進的A*算法,其代價函數的啟動置于從起點直線到終點的過程中碰到障礙物前啟動,并且在其子節點離開障礙物時,關閉代價函數的建立,然后判斷是否可直線到達終點,若不能直接到達,則到達下一個障礙物前,繼續建立代價函數直到找到終點為止。

如圖1所示,改進A*算法流程:

圖1 傳統A*和改進A*在工字鋼的仿真情況(綠色線-傳統A*路徑,紅色線-改進A*路徑)

1首先確保起點S和終點E在三維柵格地圖中是可到達的點,如果不是則退出尋路過程;

2首先判斷起點S到終點E之間是否可直線通過,若是則返回空路徑,若否則繼續;

3對起點S開始,把S作為待檢查方格,尋找起點S周圍可達方格,檢測是否有不可達的點,若是則將起點S和周圍可達的點都放入OPEN開啟列表,開啟尋路操作,跳轉至⑤;若不是則進行快速接近,跳轉至④;

4在三維柵格地圖中,以起點B到終點E的方向開始遍歷,直到接近障礙物為止,將臨近障礙物的P點作為新的起始點S,尋找周圍可達的點,并放入到OPEN開啟列表;

5計算每個周圍方格的F值,F=G+H,其中G值表示從起點S移動至指定方格的實際距離,H值表示從指定方格移動至終點E的估計距離。

6從OPEN列表中選擇F值最低的方格a,將其從OPEN列表中刪除,放入到CLOSE列表中;

7檢查方格a臨近方格,若周圍都是可達方格,則進行快速接近,否則繼續,并只檢測方格a臨近且可到達的點;

a)障礙物和CLOSE列表中的不考慮;

b)若不在OPEN列表中,則加入到OPEN列表中,并計算F值,將父方格設置為方格a;

c)若某相鄰方格c已在OPEN列表,計算新的路徑從S經方格a到達方格c,判斷新的G值是否更低,則修改父節點為方格a,重新計算F值,H值不變;而如果G值更高,值不做改變;

8繼續在OPEN列表中找出F值最小的,從OPEN列表刪除,添加至CLOSE列表,繼續尋找周圍可達的方格,如此循環;

a)直到OPEN列表中出現方塊E則路徑找到;

b)而若OPEN列表中無數據,則無合適路徑。

(二)仿真測試

在Matlab上進行仿真,設定柵格大小10mm*10mm*10mm,在仿真過程中取若干組起始點和目標點分別用傳統A*算法和改進的A*算法在H型鋼工件所構成的三維柵格形地圖進行驗證,分析兩者的路徑、長度和時間。

對比傳統A*與改進A*兩種算法,改進的A*算法能快速找到無碰路徑,并減少節點的拓展數,在長度方面與傳統A*算法近似,而在計算時間方面會優于傳統A*算法,能夠提高無碰路徑搜索的效率;且對于離障礙物較遠的起始點和目標點,改進A*的效率尤為顯著。

(三)結語

本文對于噴涂機器人全覆蓋路徑規劃過程中出現的路徑過渡問題以及對大型工件建圖所帶來的大量的數據,采用改進的A*算法,減少節點的拓展,減少搜索時間,提高噴涂機器人尋找無碰路徑的效率。