基于RRT 算法的逆正向?qū)?yōu)路徑規(guī)劃

朱道揚(yáng)

(武漢交通職業(yè)學(xué)院, 湖北 武漢 430065)

0 引言

根據(jù)對(duì)環(huán)境信息的把握程度可將路徑規(guī)劃劃分為全局路徑規(guī)劃和局部路徑規(guī)劃。 全局路徑規(guī)劃需要采集地圖信息來(lái)進(jìn)行路徑規(guī)劃,傳統(tǒng)算法有A*算法[1]、Dijkstra 算法[2]、快速擴(kuò)展隨機(jī)樹(shù)(RRT)算法[3-5]等,這類(lèi)算法對(duì)復(fù)雜空間和障礙物進(jìn)行建模的精度直接影響搜索效率。 基于智能算法有遺傳算法[6]、粒子群算法[7]、蟻群算法[8]等,此類(lèi)算法雖然學(xué)習(xí)能力非常強(qiáng),但實(shí)時(shí)性差、計(jì)算量大,需要占用大量的存儲(chǔ)空間。 其中,RRT算法具有結(jié)構(gòu)簡(jiǎn)單、概率完備性、強(qiáng)大的搜索擴(kuò)展能力以及避免對(duì)復(fù)雜空間精確建模等優(yōu)點(diǎn)被廣泛運(yùn)用于機(jī)器人的路徑規(guī)劃,然而現(xiàn)有的RRT 算法有著搜索效率低、易陷入局部極小值、路徑不光滑等缺點(diǎn)。 北京工業(yè)大學(xué)的阮曉鋼等[9]提出了一種基于信息增益與RRT 相結(jié)合的機(jī)器人環(huán)境探索策略,增強(qiáng)機(jī)器人對(duì)未知環(huán)境的探索,降低傳統(tǒng)RRT 算法固有的盲目性,但是需要精確的空間建模且計(jì)算量較大。 廣東工業(yè)大學(xué)的何兆楚等[10]利用人工勢(shì)場(chǎng)法與RRT 算法結(jié)合避免陷入局部極小值,但是全局路徑不是最優(yōu)。 譚波等[11]對(duì)搜索路徑的節(jié)點(diǎn)進(jìn)行修剪,利用B 樣條曲線得到光順路徑,但是修剪節(jié)點(diǎn)常常不能取得滿意的結(jié)果,導(dǎo)致全局路徑不最優(yōu)。

針對(duì)原始RRT 算法存在全局規(guī)劃路徑不最優(yōu)、路徑平滑性差的問(wèn)題,本文提出一種改進(jìn)RRT 算法,該算法首先對(duì)原始RRT 算法的規(guī)劃路徑進(jìn)行逆向?qū)?yōu),減少路徑規(guī)劃的長(zhǎng)度和節(jié)點(diǎn)數(shù),然后再對(duì)該路徑進(jìn)行正向?qū)?yōu),避免規(guī)劃路徑陷入局部最優(yōu),實(shí)現(xiàn)規(guī)劃路徑的全局優(yōu)化,最后通過(guò)在4 種地圖環(huán)境下對(duì)3 種算法進(jìn)行100 次路徑規(guī)劃仿真實(shí)驗(yàn)驗(yàn)證本算法的可靠性和有效性。……