基於取樣的規劃

基於取樣的規劃，是一類用來在「大到無法逐點檢查」的空間裡尋找路徑的方法。這裡說的空間，是機器人所有可能姿態的集合——它能擺出的每一種關節角度或位置的組合；對於一隻有好幾個關節的機械臂來說，這是一個巨大的、維度極多的區域，根本不可能一格一格地畫出來。基於取樣的規劃器不去把整個區域切成細密的柵格，而是像往靶盤上擲飛鏢那樣隨機撒下一些姿態，留下那些機器人不會撞到任何東西的姿態，再把這些零散的安全姿態逐步縫合成一張它可以沿著行走的網路。

這種做法之所以如此有效，是因為它繞開了「維數災難」——當你試圖給一個維度很多的空間鋪柵格時，規模會爆炸式增長。一旦有了六個甚至更多關節，足夠細以至於有用的柵格就需要天文數字般多的方格；而少數幾個放置得當的隨機取樣，卻能在根本不去逐一列舉的情況下，抓住自由空間的形狀。每一個新的取樣都會做碰撞檢查，若安全，就用一些短連線連接到附近的取樣上，而這些連線本身也會被檢查為不發生碰撞，於是整張網路裡始終只包含機器人真正做得出來的動作。

代價是：隨機性放棄了一些保證。基於取樣的規劃器通常是「機率完備」的，意思是只要存在一條路徑，給足夠多的取樣後它終究會找到——但「終究」不等於「立刻」，在任何一次單獨運行中，即便路徑確實存在，它也可能返回「無路徑」，或者返回一條有效卻並非最短的路徑。這一家族裡最有名的兩位成員，是會為整個空間建一張可複用地圖的機率路圖，以及從起點向目標向外生長出單棵樹的快速擴展隨機樹。