上篇讲了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在前期浪费大量迭代去探索。四、面试实战QInformed RRT和RRT的区别是什么A核心区别是采样策略。RRT在整个空间均匀采样Informed RRT在找到第一条路径后只在椭球内采样。椭球内的点才有可能改善当前路径椭球外的点被跳过。这让收敛速度快了5-10倍。Q椭球的几何意义是什么A椭球内任意点到起点和终点的距离之和小于当前最优路径代价。这意味着只有椭球内的采样点有可能产生更短的路径。QInformed RRT*在高维空间中有效吗A有效而且比低维更有效。维度越高均匀采样越浪费椭球约束的收益越大。在7D关节空间中Informed RRT比RRT快一个数量级。Q实际项目中用过Informed RRT*吗A用过。做移动机器人全局规划时对比了RRT和Informed RRT。同样的场景RRT需要约8000次迭代才能收敛到满意的路径Informed RRT只要1500次。计算时间从4秒降到了0.8秒。QInformed RRT*有什么局限A它依赖第一条路径的质量。如果第一条路径很差比如绕了很大的弯初始椭球很大前期加速效果不明显。所以工程上通常先用RRT快速找到第一条路径再用Informed RRT*优化。另外如果最优路径恰好经过狭窄通道椭球可能把通道排除在外——这时候需要回退到均匀采样。QInformed RRT*的椭球在高维空间是什么形状A在n维空间中是超椭球体。数学上是一个仿射变换的单位球。焦点仍然是起点和终点长轴等于c_best/2短轴由c_best和起点-终点距离决定。采样时先在n维单位球内采样然后做仿射变换映射到超椭球体。QInformed RRT*在MoveIt2中怎么用AMoveIt2通过OMPL库支持Informed RRT*。在planning pipeline配置中把planner设为RRTstar然后开启informed_transition。也可以直接用InformedRRTstar规划器。实际使用中MoveIt2的默认参数通常就能工作但迭代上限max_nearest_neighbors可能需要根据场景调整。QInformed 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——双向搜索的经典算法有任何问题欢迎评论区留言我会尽量回复。