快速扩展随机树（RRT/RRT*）

快速扩展随机树，几乎总是被叫做 RRT，是一种通过从机器人的起始姿态向外生长出一棵分叉的树、直到某根枝条触及目标来寻找路径的方法。它靠不断重复的小步骤运作：在机器人所有可能姿态构成的空间里随机选一个目标点，找到树上离这个目标最近的那个点，再从那个点朝目标方向迈出一小步——只有当这一步的动作不发生碰撞时，才长出一根新的小枝。由于随机目标会落在空间各处，这棵树会被牵引着，最快地朝它尚未探索过的开阔区域生长，迅速地铺展开来填满自由空间——这正是它名字的由来。

RRT 是为“在一个可能未知或杂乱的空间里做一次性查询”而设计的：你只从一个起点生长出一棵树，直到它碰到目标，然后沿枝条回溯，就读出了路径。这让它天然适合那些必须当场规划出一段新动作的移动机器人和机械臂。最朴素的版本速度快、擅长找到“某一条”可行路径，但它并不保证这条路径是短的——它返回的路线往往曲折迂回，是“一条能走通的路”，而不是“一条好路”。

RRT*（读作“RRT 星”）就是修正这一点的升级版。每当它新增一个点，它还会查看树里附近已有的那些点，只要经由这个新点去到它们会更省代价，就重新连接它们的连线。在许多次迭代里，这种悄悄进行的重连会不断把树上的路径拉直、缩短，因此 RRT* 是“渐近最优”的：它运行得越久，找到的路径就越逼近真正的最短路径。你用额外的计算换来稳步变好的路径——只需要快速拿到“任何一条”安全路径时就用朴素的 RRT，当你有余裕让它打磨路线时就用 RRT*。