區(qū)域限制及人工勢場引導(dǎo)的改進(jìn)RRT路徑規(guī)劃算法

徐勁力，曹 其

(武漢理工大學(xué) 機(jī)電工程學(xué)院，湖北 武漢 430070)

路徑規(guī)劃是指從起始位置到目標(biāo)位置生成一條無碰撞路徑，在無人駕駛、手術(shù)醫(yī)療、航空航天[1-3]等多個(gè)領(lǐng)域都有廣泛應(yīng)用。到目前為止，根據(jù)采用的類型方法，常用的路徑規(guī)劃算法有圖搜索法[4-5]、隨機(jī)采樣法[6]、人工勢場法[7]和智能算法[8]等。其中人工勢場法算法簡單且容易實(shí)現(xiàn)，同時(shí)所規(guī)劃的路徑平滑，但容易陷入局部極小值。快速探索隨機(jī)樹(rapidly-exploring random trees, RRT)算法避免了空間建模，能夠高效解決高維空間和復(fù)雜約束的路徑規(guī)劃問題，但由于該方法在生成擴(kuò)展樹時(shí)在整個(gè)采樣空間內(nèi)隨機(jī)采樣，因此擴(kuò)展會(huì)過于平均，整個(gè)算法的效率較低。蟻群算法、神經(jīng)網(wǎng)絡(luò)法等智能算法應(yīng)用于復(fù)雜環(huán)境時(shí)需要大量迭代去尋找并優(yōu)化路徑，因此求解困難、收斂時(shí)間長。

為了提高搜索速度，Karaman等[9]提出了漸進(jìn)最優(yōu)RRT算法(RRT*)。針對RRT算法的采樣生成點(diǎn)盲目性強(qiáng)的缺點(diǎn)，Bruce等[10]將啟發(fā)思想融入RRT算法形成了Informed RRT*算法，該算法建立一個(gè)長軸上的焦點(diǎn)位于起始點(diǎn)和目標(biāo)點(diǎn)的橢圓區(qū)域，在該區(qū)域進(jìn)行隨機(jī)點(diǎn)采樣，并在路徑搜索過程中不斷調(diào)整橢圓區(qū)域，以提高隨機(jī)采樣點(diǎn)可用概率。為了利用環(huán)境信息引導(dǎo)隨機(jī)樹生長，很多學(xué)者研究了RRT算法與人工勢場法的結(jié)合。文獻(xiàn)[11-12]在人工勢場法陷入局部最小值時(shí)，利用RRT算法的隨機(jī)性選擇臨時(shí)目標(biāo)點(diǎn)，以此跳出局部極小值點(diǎn)；文獻(xiàn)[13]先采用RRT進(jìn)行全局路徑規(guī)劃，再使用人工勢場法進(jìn)行局部避障；文獻(xiàn)[14]采用人工勢場法優(yōu)化RRT*的采樣過程，減少了算法的計(jì)算量。……