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

陳潔濤

廣東工業(yè)大學 廣東 廣州 510006

0 引言

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

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

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

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

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

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

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

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

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臨近方格,若周圍都是可達方格,則進行快速接近,否則繼續(xù),并只檢測方格a臨近且可到達的點;

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

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

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

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

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

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

(二)仿真測試

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

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

(三)結語

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