为什么网格不管用了
在前面的台阶里，我们把世界切成网格，再在格子上跑 Dijkstra 算法 或 A* 来规划。对于在平地上滚动的机器人，这很好用——它的位形空间（机器人能摆出的所有姿态的集合）只有两三个维度。但想象一只有七个关节的机械臂：它的位形是七个角度的列表，所以它的位形空间是七维的。
假设我们把每个关节角度只切成 100 份。二维网格有 100 x 100 = 10000 个格子——轻松。七维网格则有 100 的七次方：一百万亿个格子。没有计算机能构建、存储或搜索它。维度增加时格子数量的这种爆炸，常被称为“维度灾难”。
共同的诀窍：采样、检查、连接
基于采样的规划干脆绕开网格。它不去遍历每个格子，而是“撒飞镖”：随机挑一些位形，留下好的，再把它们缝在一起。本指南里的两种规划器都靠同一个三步引擎驱动。
- 采样。随机抽取一个位形——比如给七个关节角度各定一个随机值。这就是一支飞镖落在位形空间的某处。
- 检查。做一次碰撞检查：机器人摆成那个姿态时，会不会撞到障碍物、墙，或自己？只保留落在自由空间里的采样点，丢掉落进障碍空间的那些。
- 连接。试着用一小段直线运动把每个存活的采样点和附近的点连起来。如果机器人能在两点之间滑过而不碰撞，这条连线就成了一条可以走的边。
注意，我们从不遍历整个空间——只就飞镖恰好命中的那少数姿态去问碰撞检查器。采样把力气集中在要紧的地方，而且规划器运行得越久效果越好。
PRM：一张可复用的道路网
概率路图（PRM）把这三步分成两个阶段。先是构建阶段：在整个自由空间里撒下大量采样点，把每个点和邻居相连，长成一张安全道路网——这就是“路图”。这个阶段不管机器人从哪出发、要去哪。
接着是查询阶段：要规划某次具体运动，就把起点姿态和目标姿态接入已有的道路网，再在路图上跑普通的 A* 找出一条路线。好处在于复用——只要为固定场景建好这张网，就能廉价地回答成千上万次“从起点到目标”的查询。
RRT：一棵向外伸展的树
有时你并不想预先建好整张地图——你只需要现在就拿到一条路，而且这个场景可能再也不会遇到。这正是快速扩展随机树（RRT）的活儿。它不长网，而是从起点姿态生根，长出一棵树，朝着自由空间里尚未探索的角落不断伸展。
- 在位形空间的某处随机取一个采样点。
- 找到树上离这个采样点最近的节点，从它出发朝采样点的方向伸出一小段树枝。
- 如果碰撞检查放行了这小段树枝，就把它加进树里。重复，直到某根树枝够到目标。
由于随机采样点往往落在树还没够到的大片空旷区域，RRT 会自然地把自己拉向开阔处，探索得很快——名字便由此而来。普通 RRT 一碰到目标就停，所以得到的路径常常是一条又快又毛糙的单一路线。
它流行的变体 RRT*（读作“RRT 星”）更进一步。每加入一个节点，它就重连附近的树枝去采用更省的连接，所以采样越多，路径就越短、越直——只要时间足够，它会向最优路线收敛，而不是凑合用最先找到的那条。
诚实的取舍
采样在高维里换来了速度，却放弃了网格给过我们的两点安心。其一，原始输出是毛糙的：一串带突兀拐角的直线段，没有哪个真实电机愿意去跟踪。规划器通常会先把这条路径交给平滑或轨迹优化环节，机器人才真正动起来。
其二，这些方法只是“概率完备”的：若存在一条路，找到它的概率会随采样增多而趋近于必然——但在任何有限的时刻，没找到并不能证明它不存在。相比之下，网格搜索可以确定无疑地宣布“无路可走”。
实践中，选择取决于查询次数。PRM 把一次缓慢的构建摊销到固定场景里的多次往返上；当你在全新或不断变化的环境里需要快速得到一条路时，RRT 与 RRT* 是首选。两者通常都充当全局规划器，由一个局部控制器去处理每时每刻的临场躲避。