為什麼網格不管用了
在前面的台階裡，我們把世界切成網格，再在格子上跑 Dijkstra 演算法 或 A* 來規劃。對於在平地上滾動的機器人，這很好用——它的位形空間（機器人能擺出的所有姿態的集合）只有兩三個維度。但想像一隻有七個關節的機械臂：它的位形是七個角度的列表，所以它的位形空間是七維的。
假設我們把每個關節角度只切成 100 份。二維網格有 100 x 100 = 10000 個格子——輕鬆。七維網格則有 100 的七次方：一百萬億個格子。沒有電腦能建構、儲存或搜尋它。維度增加時格子數量的這種爆炸，常被稱為「維度災難」。
共同的訣竅：取樣、檢查、連接
基於取樣的規劃乾脆繞開網格。它不去遍歷每個格子，而是「撒飛鏢」：隨機挑一些位形，留下好的，再把它們縫在一起。本指南裡的兩種規劃器都靠同一個三步引擎驅動。
- 取樣。隨機抽取一個位形——比如給七個關節角度各定一個隨機值。這就是一支飛鏢落在位形空間的某處。
- 檢查。做一次碰撞檢查：機器人擺成那個姿態時，會不會撞到障礙物、牆，或自己？只保留落在自由空間裡的取樣點，丟掉落進障礙空間的那些。
- 連接。試著用一小段直線運動把每個存活的取樣點和附近的點連起來。如果機器人能在兩點之間滑過而不碰撞，這條連線就成了一條可以走的邊。
注意，我們從不遍歷整個空間——只就飛鏢恰好命中的那少數姿態去問碰撞檢查器。取樣把力氣集中在要緊的地方，而且規劃器執行得越久效果越好。
PRM：一張可重複使用的道路網
機率路圖（PRM）把這三步分成兩個階段。先是建構階段：在整個自由空間裡撒下大量取樣點，把每個點和鄰居相連，長成一張安全道路網——這就是「路圖」。這個階段不管機器人從哪出發、要去哪。
接著是查詢階段：要規劃某次具體運動，就把起點姿態和目標姿態接入已有的道路網，再在路圖上跑普通的 A* 找出一條路線。好處在於重複使用——只要為固定場景建好這張網，就能廉價地回答成千上萬次「從起點到目標」的查詢。
RRT：一棵向外伸展的樹
有時你並不想預先建好整張地圖——你只需要現在就拿到一條路，而且這個場景可能再也不會遇到。這正是快速擴展隨機樹（RRT）的活兒。它不長網，而是從起點姿態生根，長出一棵樹，朝著自由空間裡尚未探索的角落不斷伸展。
- 在位形空間的某處隨機取一個取樣點。
- 找到樹上離這個取樣點最近的節點，從它出發朝取樣點的方向伸出一小段樹枝。
- 如果碰撞檢查放行了這小段樹枝，就把它加進樹裡。重複，直到某根樹枝搆到目標。
由於隨機取樣點往往落在樹還沒搆到的大片空曠區域，RRT 會自然地把自己拉向開闊處，探索得很快——名字便由此而來。普通 RRT 一碰到目標就停，所以得到的路徑常常是一條又快又毛糙的單一路線。
它流行的變體 RRT*（讀作「RRT 星」）更進一步。每加入一個節點，它就重連附近的樹枝去採用更省的連接，所以取樣越多，路徑就越短、越直——只要時間足夠，它會向最優路線收斂，而不是湊合用最先找到的那條。
誠實的取捨
取樣在高維裡換來了速度，卻放棄了網格給過我們的兩點安心。其一，原始輸出是毛糙的：一串帶突兀拐角的直線段，沒有哪個真實馬達願意去追蹤。規劃器通常會先把這條路徑交給平滑或軌跡最佳化環節，機器人才真正動起來。
其二，這些方法只是「機率完備」的：若存在一條路，找到它的機率會隨取樣增多而趨近於必然——但在任何有限的時刻，沒找到並不能證明它不存在。相比之下，網格搜尋可以確定無疑地宣布「無路可走」。
實踐中，選擇取決於查詢次數。PRM 把一次緩慢的建構攤銷到固定場景裡的多次往返上；當你在全新或不斷變化的環境裡需要快速得到一條路時，RRT 與 RRT* 是首選。兩者通常都充當全域規劃器，由一個區域控制器去處理每時每刻的臨場躲避。