演示 / 机器人经典

RRT* 对比 RRT：找到路之后，继续把路变短

同一批随机样本，两种树连接方式。观察最低代价选父和邻域重连如何逐渐改善可行路径。

小屏可左右滑动图表查看完整内容；聚焦图表后也可用方向键横向滚动。

不是多撒一些点，而是持续改善树的连接

  1. 采样与延伸：黄色目标由同一随机序列产生，两棵树向它走相同步长；碰墙或擦边都拒绝。
  2. 选父：RRT 直接接最近节点；RRT* 在可见邻居中最小化「父节点累计代价 + 新边长度」。
  3. 重连：若经新节点更便宜，邻居换父节点；所有后代的累计代价一并更新。
  4. 发现路径之后继续运行。观察下方紫色曲线是否下降，以及黄色重连边出现在哪里。

绿线是各自当前最优已知路径，蓝色 / 紫色是两棵树。调整参数会暂停并使用固定种子重来。两棵树的节点坐标相同，只比较父节点与代价；每步的计算开销并不相同。

实验建议

先保持默认运行 600 次采样，再把邻域上限从 24 调到 10，比较重连次数与路径长度。较大邻域可提供更多改道机会，也需要更多碰撞检查。采样预算增大不保证有限时间内每一次都明显改进。

模型与论文边界

二维点机器人，矩形障碍，直线局部规划器。代价为欧氏路径长度；邻域半径 r(n) = min(r_max, 90√(log n / n))，目标在 12 单位内且连线无碰撞时接入。采用 8% 目标偏置。这里展示 RRT* 的选父 / 重连核心，不实现动力学约束、机器人尺寸或 Informed 采样。有限样本最优已知路径不等于全局最优；渐近性质不代表本动画已经收敛。

对照精读：RRT* · RRT 精读 · Karaman & Frazzoli：Sampling-based Algorithms for Optimal Motion Planning