上篇讲了RRT*——路径渐进最优，但收敛慢。问题出在哪？RRT在整个空间里均匀采样，大部分采样点对优化当前路径没有帮助。说白了，它在浪费时间在无关区域。Informed RRT的核心思想就是：找到第一条路径后，用一个椭球把搜索范围缩小到"有可能改善当前路径"的区域。
这个算法是Gammell等人在2014年提出的。核心改进就一个：采样时不再覆盖整个空间，而是只在一个椭球内采样。椭球的焦点是起点和终点，长轴长度等于当前最优路径的代价。
一、椭球采样原理
Informed RRT*的关键是一个椭球（在高维空间中是超椭球）。椭球的定义很直观：
- 两个焦点：起点和终点
- 长轴长度：当前最优路径的代价c_best
- 短轴长度：由c_best和起点-终点距离计算得出
几何意义：椭球内的任意一点，到起点和终点的距离之和小于c_best。换句话说，只有椭球内的点才有可能产生比当前路径更短的新路径。椭球外的点？不管怎么连，都不可能改善路径。
def informed_sample(start, goal, c_best, c_min): # c_best: 当前最优路径代价 # c_min: 起点到终点的直线距离（下界） # 计算椭球参数 a = c_best / 2 # 长半轴 c = distance(start, goal) / 2 # 焦距 b = sqrt(a**2 - c**2) # 短半轴 # 在椭球内均匀采样 return sample_in_ellipsoid(center, a, b, rotation)找到第一条路径之前，Informed RRT和普通RRT一样——在整个空间采样。一旦找到第一条路径，立刻切换到椭球采样。之后每次找到更好的路径，椭球就缩小一些——搜索范围越来越精确。
二、为什么加速这么明显
Informed RRT的加速效果非常显著。论文中的实验数据显示，在2D空间中，Informed RRT的收敛速度比RRT*快5-10倍。在高维空间中，加速效果更明显——因为高维空间的体积大，均匀采样浪费更多，椭球约束的收益更大。
道理很简单：假设当前路径长度是10m，起点-终点直线距离是6m。椭球的长轴是5m，短轴约4m。整个搜索被限制在这个椭球内——空间外的几万个潜在采样点全部跳过。
工程上有个细节：椭球采样不是简单地拒绝椭球外的点（那样效率太低），而是直接在椭球内生成样本。方法是先在单位球内采样，然后通过仿射变换映射到椭球。具体步骤：先在单位超球面上均匀采样一个方向向量，再在径向按椭球的轴长缩放，最后平移到椭球中心。
收敛过程的直觉理解：Informed RRT的收敛过程像"剥洋葱"。第一层（找到第一条路径后），椭球很大，几乎覆盖整个空间。之后每次找到更优路径，椭球缩小一层。到了最后几层，椭球变得很窄，采样集中在起点-终点连线附近，路径已经接近最优。这个过程比RRT的"大海捞针"高效得多。
有个数据可以感受一下：在一个有几十个障碍物的2D场景中，RRT需要约15000次迭代才能把路径优化到最优解的1.05倍以内。Informed RRT只需要约2000次迭代就做到了。差距一目了然。
三、工程实现要点
Informed RRT的实现基于RRT，主要改动两处：采样策略和路径更新。
采样策略：找到第一条路径前用均匀采样，找到后用椭球采样。每次找到更优路径，更新椭球参数。
路径更新：每次发现更优路径时，更新c_best，重新计算椭球。如果c_best接近c_min（直线距离），椭球变得很窄，采样几乎集中在起点-终点连线附近。
class InformedRRTStar: def __init__(self, start, goal): self.start = start self.goal = goal self.c_best = float('inf') self.c_min = distance(start, goal) def sample(self): if self.c_best < float('inf'): return ellipsoid_sample(self.start, self.goal, self.c_best) return random_sample() def update_path(self, new_cost): if new_cost < self.c_best: self.c_best = new_cost工程上还有一个实用技巧：初始时用RRT快速找到第一条路径（不需要最优），然后切换到Informed RRT模式优化。这样避免了RRT在前期浪费大量迭代去"探索"。
四、面试实战
Q：Informed RRT和RRT的区别是什么？A：核心区别是采样策略。RRT在整个空间均匀采样，Informed RRT在找到第一条路径后只在椭球内采样。椭球内的点才有可能改善当前路径，椭球外的点被跳过。这让收敛速度快了5-10倍。
Q：椭球的几何意义是什么？A：椭球内任意点到起点和终点的距离之和小于当前最优路径代价。这意味着只有椭球内的采样点有可能产生更短的路径。
Q：Informed RRT*在高维空间中有效吗？A：有效，而且比低维更有效。维度越高，均匀采样越浪费，椭球约束的收益越大。在7D关节空间中，Informed RRT比RRT快一个数量级。
Q：实际项目中用过Informed RRT*吗？A：用过。做移动机器人全局规划时，对比了RRT和Informed RRT。同样的场景，RRT需要约8000次迭代才能收敛到满意的路径，Informed RRT只要1500次。计算时间从4秒降到了0.8秒。
Q：Informed RRT*有什么局限？A：它依赖第一条路径的质量。如果第一条路径很差（比如绕了很大的弯），初始椭球很大，前期加速效果不明显。所以工程上通常先用RRT快速找到第一条路径，再用Informed RRT*优化。另外，如果最优路径恰好经过狭窄通道，椭球可能把通道排除在外——这时候需要回退到均匀采样。
Q：Informed RRT*的椭球在高维空间是什么形状？A：在n维空间中是超椭球体。数学上是一个仿射变换的单位球。焦点仍然是起点和终点，长轴等于c_best/2，短轴由c_best和起点-终点距离决定。采样时先在n维单位球内采样，然后做仿射变换映射到超椭球体。
Q：Informed RRT*在MoveIt2中怎么用？A：MoveIt2通过OMPL库支持Informed RRT*。在planning pipeline配置中把planner设为"RRTstar"，然后开启informed_transition。也可以直接用"InformedRRTstar"规划器。实际使用中，MoveIt2的默认参数通常就能工作，但迭代上限（max_nearest_neighbors）可能需要根据场景调整。
Q：Informed RRT*能处理多目标规划吗？A：标准Informed RRT是单目标的。多目标场景可以用Multi-Informed RRT——维护多个椭球，每个对应一个目标或者一条已发现的路径。不过工程上更常见的做法是把多目标问题分解成多个单目标问题分别规划。
小结
Informed RRT*的核心：找到第一条路径后，用椭球约束采样范围，只在"有可能改善路径"的区域采样。
优势：收敛速度比RRT*快5-10倍，高维空间效果更明显。 劣势：依赖第一条路径质量，初始阶段没有加速效果。
Informed RRT是目前工程上最常用的采样规划算法之一。MoveIt2中的OMPL库就内置了Informed RRT实现，很多自动驾驶和机械臂项目都在用。面试中聊到RRT的时候，如果能顺便讲一下Informed RRT的改进思路，面试官会觉得你对这个领域理解得比较深。下一篇讲RRT-Connect——双向搜索的经典算法。
如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。
「机器人软件开发面试·从入门到精通」连载系列
上一篇：第215篇 RRT*渐进最优——从可行解到最优解
下一篇预告：第217篇 RRT-Connect——双向搜索的经典算法
有任何问题欢迎评论区留言，我会尽量回复。
