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

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

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

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

這里我們簡要討論兩種算法的區別，并配置Python+matplotlib環境來對路徑規劃算法進行研究。

搜索路徑規劃算法

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

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

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

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

抽樣路徑規劃算法

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

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

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

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

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