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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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