機(jī)器人路徑基于采樣的規(guī)劃

路徑規(guī)劃算法主要可分成兩種，一種是基于搜索結(jié)果的規(guī)劃，另一類便是本文中將要提及的基于采樣的規(guī)劃。

一般而言，基于搜索的規(guī)劃（如Astar）通常是運(yùn)行在柵格地圖上的。當(dāng)柵格的分辨率越大時(shí)，算法搜索的路徑就會(huì)越優(yōu)。

還有一類算法是基于采樣的，主要就是RRT和它的變種算法。這類算法的核心在于隨機(jī)采樣，從父節(jié)點(diǎn)開(kāi)始，隨機(jī)在地圖上生成子節(jié)點(diǎn)，連接父子節(jié)點(diǎn)并進(jìn)行碰撞檢測(cè)，若無(wú)碰撞，就擴(kuò)展該子節(jié)點(diǎn)。

就這樣，不斷地隨機(jī)擴(kuò)展樣本點(diǎn)，直到生成一條連接起點(diǎn)和終點(diǎn)的路徑。如下圖所示，RRT算法的擴(kuò)展圖與盤根錯(cuò)節(jié)的樹(shù)枝十分相似。

這里我們簡(jiǎn)要討論兩種算法的區(qū)別，并配置Python+matplotlib環(huán)境來(lái)對(duì)路徑規(guī)劃算法進(jìn)行研究。

搜索路徑規(guī)劃算法

這一大類算法，在移動(dòng)機(jī)器人軟件上常常是在occupAncy grid的格紋版圖上進(jìn)行計(jì)劃（只能單純地理解成二值地圖的像素矩陣）以深入擇優(yōu)尋徑算法、廣度擇優(yōu)尋徑算法、Dijkstra（迪杰斯特拉）算法為始祖，以A Star算法（Dijkstra算法上以減小運(yùn)算量為目的加入了一種啟發(fā)式代價(jià)）則更為常見(jiàn)。

如較近期的theta Star算子是在A Star算子的基礎(chǔ)上加入了line-of-sight優(yōu)化所以計(jì)劃起來(lái)的路線不全然依賴于單獨(dú)的柵格圖形如圖所示。

完備的運(yùn)算的最大優(yōu)點(diǎn)就在于其對(duì)解的信息捕獲能力上是完全的，不過(guò)隨之形成的最大弊端便是運(yùn)算復(fù)雜性太大。

這些缺陷在二維的小尺寸柵格地圖上并不突出，但在大尺寸，特別是在多維度規(guī)模問(wèn)題上，如機(jī)器臂、蛇形機(jī)器人的規(guī)劃問(wèn)題將形成很大的計(jì)算代價(jià)，這也就徑直促進(jìn)了第二大類算法的誕生。

抽樣路徑規(guī)劃算法

這些計(jì)算通常都是并不直觀的在grid地圖實(shí)現(xiàn)最小柵格分辨率的計(jì)劃，但是它能夠通過(guò)在版圖上隨意撒下特定密度的粒子，來(lái)抽象定義為現(xiàn)實(shí)版圖上的輔助計(jì)劃。

因此，PRM算法及其變種就是從原始版圖上開(kāi)始撒點(diǎn)，并通過(guò)抽取roadmap在這樣的一種拓?fù)浒鎴D上展開(kāi)計(jì)劃；

而RRT和其更先進(jìn)的變體RRT-connect，則是在版圖上的每一區(qū)域內(nèi)都能夠開(kāi)始撒點(diǎn)，以迭代生長(zhǎng)樹(shù)的方法，以連結(jié)起止點(diǎn)為目的，終于在所連結(jié)的版圖上實(shí)現(xiàn)計(jì)劃，如圖所示。

雖然這種基于采樣的計(jì)算速率比較快，但是所產(chǎn)生的路徑損失（可認(rèn)知為時(shí)間）較完備的計(jì)算高，而且會(huì)出現(xiàn)“有解求不出”的情形（PRM的逢Narrowspace卒的情形）。

這樣的方式，通常會(huì)在更高維的城市規(guī)劃等實(shí)際問(wèn)題上廣泛使用。