陳潔濤

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

0 引言

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

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

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

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

如圖1所示,改進(jìn)A*算法流程:

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

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

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

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

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

5計(jì)算每個(gè)周圍方格的F值,F=G+H,其中G值表示從起點(diǎn)S移動(dòng)至指定方格的實(shí)際距離,H值表示從指定方格移動(dòng)至終點(diǎn)E的估計(jì)距離。

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

7檢查方格a臨近方格,若周圍都是可達(dá)方格,則進(jìn)行快速接近,否則繼續(xù),并只檢測方格a臨近且可到達(dá)的點(diǎn);

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

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

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

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

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

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

(二)仿真測試

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

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

(三)結(jié)語

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