基于RRT 改進(jìn)算法的AGV 路徑規(guī)劃*

程 滿(mǎn) 楊光永 徐天奇 黃卓群 劉 葉

（云南民族大學(xué)電氣信息工程學(xué)院 昆明 650500）

1 引言

自動(dòng)導(dǎo)引車(chē)（AGV）在自動(dòng)化、靈活性方面具有獨(dú)特的優(yōu)勢(shì)，使AGV 成為智慧倉(cāng)儲(chǔ)，智能物流自動(dòng)化上的最優(yōu)選擇。路徑規(guī)劃是AGV 的核心，所以設(shè)計(jì)合理高效的路徑規(guī)劃算法十分重要［1］。AGV的路徑規(guī)劃目標(biāo)在于通過(guò)采用某個(gè)算法，在包含有各種障礙物的空間中，避開(kāi)障礙物于自由空間中安全行駛，最終生成一條從起點(diǎn)到終點(diǎn)的無(wú)碰撞的安全路徑。路徑規(guī)劃的核心是算法，算法的高效、安全、路徑最優(yōu)等指標(biāo)經(jīng)常作為算法優(yōu)劣的衡量項(xiàng)。目前對(duì)于一些常見(jiàn)算法的分類(lèi)主要有全局路徑規(guī)劃和局部路徑規(guī)劃；圖搜索算法和幾何結(jié)構(gòu)搜索算法；傳統(tǒng)算法和人工智能算法。因?yàn)樗惴ū旧砟承┓矫娴木窒扌裕栽诿鎸?duì)不同問(wèn)題或者不同環(huán)境的時(shí)候不同的算法及其改進(jìn)算法被用來(lái)解決某些類(lèi)型的問(wèn)題，采取算法某些方面的優(yōu)點(diǎn)，去粗取精的混合算法也越來(lái)越受到研究者的喜愛(ài)［2～3］。

RRT 算法于1998 年由Lavall 所提出的［4］，基于環(huán)境空間的隨機(jī)采樣點(diǎn)規(guī)劃的一種算法，節(jié)點(diǎn)的擴(kuò)展不需要預(yù)處理，建模簡(jiǎn)單，速度快并且是一種概率完備算法，同時(shí)在高維空間中表現(xiàn)優(yōu)秀，受到很多研究人員的關(guān)注，各種改進(jìn)算法也相繼提出［5～11］。Lavalle 等隨后又提出了雙向隨機(jī)樹(shù)（bi-RRT）［12］，在起始點(diǎn)和目標(biāo)節(jié)點(diǎn)同時(shí)生長(zhǎng)兩棵樹(shù)，兩個(gè)方向進(jìn)行擴(kuò)展，加快算法的速度；RRT-connect 算法又是在bi-RRT 算法的基礎(chǔ)上引入了貪婪的思想；Frazzoli 等提出了RRT*算法［13］，在生成新節(jié)點(diǎn)的時(shí)候，通過(guò)比較代價(jià)替換父節(jié)點(diǎn)，隨著迭代次數(shù)的增加生成的路徑向最優(yōu)路徑逼近；……