Bilingual Paper Reading · 中英对照精读
优化信息RRT路径规划：让「快但次优」的 RRT 打赢「慢但最优」的 RRT*
准大一 · 机器人工程 × 路径规划 × 采样规划 —— 优化信息 RRT 路径规划精读材料
原文：arXiv:2108.08051
2021年8月18日发布
arXiv 预印本（cs.RO · eess.SY）
路径规划 × RRT/RRT* × 信息引导采样 × 路径优化
附英文摘要朗读音频
一、论文档案
英文标题Optimised Informed RRTs for Mobile Robot Path Planning
中文标题面向移动机器人路径规划的优化信息 RRT（中文短名：优化信息RRT路径规划）
作者邦加尼·B·马塞科, 科尔内·E·范·达伦, 约翰·特罗尼赫特（机构未在素材中标注）
发布时间2021年8月18日（v1）｜分类：cs.RO（机器人）、eess.SY（系统与控制）
一句话概括把「信息引导采样 + 路径优化」这对加速 RRT* 的招数用在基础 RRT 上，得到优化信息 RRT 算法族——结果在规划时间受限时，基于 RRT 的版本全面胜过基于 RRT* 的版本。
💡 为什么选这篇给你：① 路径规划是移动机器人最基础、最常考的问题，RRT / RRT* 是面试和竞赛的「必答词」；② 问题意识极好——「最优算法太慢，快算法不优，能不能让快的变好」，一句话就能讲清；③ 方法不依赖复杂数学：信息采样、剪枝、随机捷径，全部可以用直觉理解，非常适合入门。
二、核心术语表（先扫一遍再读正文）
| 英文术语 | 中文 | 大白话解释 |
|---|
| rapidly-exploring random tree (RRT) | 快速探索随机树 | 在构型空间里随机撒点、连成一棵树，快速找到一条可行路径的采样规划器。 |
| RRT* | 最优 RRT | RRT 的渐近最优扩展：迭代次数趋于无穷时，解收敛到最优解。 |
| almost-surely suboptimal | 几乎必然次优 | 基础 RRT 几乎肯定找不到最优解，只能保证「找到一条可行路径」。 |
| informed sampling | 信息引导采样 | 不在地图里乱撒点，而是把采样集中在「最优路径可能出现的椭圆区域」里，加快收敛。 |
| path optimisation | 路径优化 | 对已找到的路径做后处理（缩短、拉直、平滑），让路径更好更短。 |
| convergence rate | 收敛速率 | 路径质量随迭代/时间提升的速度；提升越快越好。 |
| asymptotically optimal | 渐近最优 | 随着计算量趋于无穷，解越来越接近最优解的性质。 |
| single-query | 单查询 | 只规划一次就完成任务；与之相对的是反复查询的 multi-query。 |
| configuration space | 构型空间 | 把机器人所有可能的位姿/状态构成的抽象空间，路径规划在其中进行。 |
| path pruning | 路径剪枝 | 删掉路径上多余的转折点，让路径更短。 |
| random shortcut | 随机捷径 | 随机挑两个路径点尝试用直线连接，成功就替换掉中间一大段。 |
| wrapping process | 包裹处理 | 不断把路径「包裹」到障碍物边缘，压出更短的路径。 |
| gradient-based path optimisation | 基于梯度的路径优化 | 把路径点当作优化变量，沿梯度方向迭代缩短路径。 |
三、摘要中英对照（精读核心）
🎧 音频在文末，可先听一遍原文再读；每个英文句都配了逐句翻译。
摘要 Abstract
EN · 原文
Path planners based on basic rapidly-exploring random trees (RRTs) are quick and efficient, and thus favourable for real-time robot path planning, but are almost-surely suboptimal.
CN · 翻译
基于
基础快速探索随机树（RRT）的路径规划器
快速高效，因此适合实时机器人路径规划，但
几乎必然次优。
EN · 原文
In contrast, the optimal RRT (RRT*) converges to the optimal solution, but may be expensive in practice.
CN · 翻译
相比之下，
最优 RRT（RRT*）收敛到最优解，但在实践中可能
代价高昂。
EN · 原文
Recent work has focused on accelerating the RRT*'s convergence rate.
CN · 翻译
近期工作聚焦于
加速 RRT* 的收敛速率。
EN · 原文
The most successful strategies are informed sampling, path optimisation, and a combination thereof.
CN · 翻译
最成功的策略是
信息引导采样、
路径优化以及
两者的组合。
EN · 原文
However, informed sampling and its combination with path optimisation have not been applied to the basic RRT.
CN · 翻译
然而，信息引导采样及其与路径优化的组合
还没有被应用到基础 RRT 上。
EN · 原文
Moreover, while a number of path optimisers can be used to accelerate the convergence rate, a comparison of their effectiveness is lacking.
CN · 翻译
此外，虽然多种路径优化器都可用于加速收敛，但
缺乏对其有效性的系统比较。
EN · 原文
This paper investigates the use of informed sampling and path optimisation to accelerate planners based on both the basic RRT and the RRT*, resulting in a family of algorithms known as optimised informed RRTs.
CN · 翻译
本文研究用信息引导采样与路径优化加速
基于基础 RRT 和 RRT*两类规划器，得到一族算法——
优化信息 RRT（optimised informed RRTs）。
EN · 原文
We apply different path optimisers and compare their effectiveness.
CN · 翻译
我们应用不同的路径优化器并
比较它们的有效性。
EN · 原文
The goal is to ascertain if applying informed sampling and path optimisation can help the quick, though almost-surely suboptimal, path planners based on the basic RRT attain comparable or better performance than RRT*-based planners.
CN · 翻译
目标是确认：信息引导采样与路径优化能否帮助「快速但几乎必然次优」的基础 RRT 规划器，取得
与 RRT* 规划器相当或更好的性能。
EN · 原文
Analyses show that RRT-based optimised informed RRTs do attain better performance than their RRT*-based counterparts, both when planning time is limited and when there is more planning time.
CN · 翻译
分析表明：基于 RRT 的优化信息 RRT
确实取得了优于基于 RRT* 对应版本的表现——无论是
规划时间受限还是
时间更充裕时。
关键词 Keywords：Path Planning 路径规划 ｜ RRT / RRT* ｜ Informed Sampling 信息引导采样 ｜ Path Optimisation 路径优化 ｜ Mobile Robots 移动机器人
四、引言精选（为什么这个问题重要）
① 自主运输系统对路径规划器的要求：又快又稳又优
EN · 原文
Key requirements for an autonomous transportation system include safety, reliability and responsiveness. The path planner, which is a critical component of such a system, therefore has to plan near-optimal paths that result in reaching destinations safely. Moreover, paths must be planned quickly, otherwise unacceptable delays (in real-time path planning) are incurred.
CN · 翻译
自主运输系统的关键要求包括
安全、可靠与快速响应。作为核心组件的路径规划器必须规划出
接近最优的路径以安全到达目的地；而且必须
规划得快，否则实时路径规划会产生不可接受的延迟。
② 经典两难：RRT 快但次优，RRT* 最优但太慢
EN · 原文
The basic rapidly-exploring random tree (RRT) (LaValle, 1998) is a quick and efficient single-query sampling-based path planner that has, unfortunately, been proven to be almost-surely suboptimal. The optimal RRT (RRT*) (Karaman and Frazzoli, 2011), an asymptotically-optimal extension of the RRT, finds a solution that tends to the optimal solution as the number of iterations tends to infinity; so, it may take very long to find a near-optimal path.
CN · 翻译
基础 RRT 是快速高效的单查询采样规划器，但已被证明
几乎必然次优；RRT* 作为 RRT 的
渐近最优扩展，当迭代次数趋于无穷时解趋于最优，因此找到近优路径
可能要花很长时间。
③ 被忽略的空白：加速招数只用在 RRT* 上，没用在 RRT 上
EN · 原文
Although some strategies, notably informed sampling (Gammell et al., 2014) and its combination with path optimisation (Kim and Song, 2015), have been shown to be effective in accelerating the RRT*'s convergence, this has not been compared to similar acceleration of the basic RRT. Basic RRT-based planners are usually much faster than RRT*-based planners, which would allow more time to improve the solution.
CN · 翻译
虽然信息引导采样及其与路径优化的组合已被证明能有效加速 RRT* 收敛，但这
从未与基础 RRT 的同类加速进行比较。基于基础 RRT 的规划器通常比 RRT* 快得多，这会给「继续改进解」
留出更多时间。
④ 本文做法：给两类规划器都加上「信息采样 + 四种路径优化」
EN · 原文
To this end, we apply a combination of informed sampling and path optimisation to both planners based on the basic RRT and the RRT*, and compare their convergence rates. We use different path optimisers, including path pruning, random shortcut, the wrapping process and gradient-based path optimisation (Geraerts and Overmars, 2007; Kim and Song, 2015; Campana et al., 2016).
CN · 翻译
为此，我们把「信息引导采样 + 路径优化」的组合
同时应用到基础 RRT 与 RRT*两类规划器上并比较收敛速率。使用的路径优化器包括：
路径剪枝、随机捷径、包裹处理、基于梯度的路径优化。
💡 这是全文最有味道的一句：“Basic RRT-based planners are usually much faster than RRT*-based planners, which would allow more time to improve the solution.”——别人只盯着「怎么让最优算法更快」，这篇论文反问：「快算法省下的时间，不正好用来把解改好吗？」换个视角，问题就翻过来了。
五、论文贡献（3 个要点）
EN · 原文
1. A new family of algorithms. This paper investigates the use of a combination of informed sampling and path optimisation to accelerate convergence of RRT* and RRT-based path planners. Four path optimisers, namely path pruning, random shortcut, the wrapping process and a gradient-based path optimiser, are used to accelerate convergence of the benchmark path planners, resulting in a family of algorithms known as optimised informed RRTs.
CN · 翻译
1. 新算法族。研究「信息引导采样 + 路径优化」组合对 RRT* 与 RRT 规划器收敛的加速；用
四种路径优化器（剪枝、随机捷径、包裹、梯度）加速基准规划器，得到
优化信息 RRT 算法族。
EN · 原文
2. Benchmarks with informed sampling. Two RRT-based path planners, namely informed basic RRT and informed k-nearest RRT, that make use of informed sampling, are used as benchmarks, along with informed RRT*.
CN · 翻译
2. 信息采样基准。采用
信息基础 RRT 与
信息 k 近邻 RRT 两个使用信息引导采样的 RRT 规划器作为基准，与
信息 RRT* 一起对比。
EN · 原文
3. Systematic comparison of optimisers. Analyses show that when planning time is limited, all optimised informed basic RRT (OIB-RRT) versions outperform all optimised informed RRT* (OI-RRT*) versions.
CN · 翻译
3. 优化器的系统比较。分析表明：当规划时间受限时，
所有优化信息基础 RRT（OIB-RRT）版本都胜过所有优化信息 RRT*（OI-RRT*）版本——这是全文最硬核的结论。
六、结论中英对照
EN · 原文
This paper investigates the use of a combination of informed sampling and path optimisation to accelerate convergence of RRT* and RRT-based path planners. The key goal is to ascertain if incorporating informed sampling and path optimisation can help a quick, but almost-surely suboptimal, RRT-based planner attain comparable or better performance than an asymptotically optimal RRT*-based counterpart.
CN · 翻译
本文研究「信息引导采样 + 路径优化」对 RRT* 与 RRT 规划器收敛的加速作用，核心目标是确认：这些技术能否帮助「快速但几乎必然次优」的 RRT 规划器，取得与
渐近最优的 RRT* 对应版本相当或更好的性能。
EN · 原文
Analyses show that when planning time is limited, all optimised informed basic RRT (OIB-RRT) versions outperform all optimised informed RRT* (OI-RRT*) versions. The best two OIB-RRT versions (RS-based and wrapping-based) also outperform all OI-RRT* versions when there is more planning time; the last two OIB-RRT versions (GB-based and path-pruning-based) have comparable performance to the best two OI-RRT* versions in this case. Thus incorporating informed sampling and path optimisation does help the quick, but almost-surely suboptimal, basic RRT attain better performance than its RRT*-based counterpart.
CN · 翻译
分析表明：时间受限时，
所有 OIB-RRT 版本都胜过所有 OI-RRT* 版本；时间更充裕时，最好的两个 OIB-RRT 版本（基于随机捷径 RS 与基于包裹处理）
依然胜过所有 OI-RRT* 版本，其余两个 OIB-RRT 版本（基于梯度 GB 与基于剪枝）也与最好的两个 OI-RRT* 版本性能相当。因此，引入信息引导采样与路径优化
确实帮助「快但次优」的基础 RRT 取得了优于 RRT* 对应版本的表现。
七、编者解读：这篇论文到底讲了什么（大白话版）
- 问题：路径规划有个经典两难——基础 RRT 快得飞起，但几乎必然次优；RRT* 保证收敛到最优，但可能慢到没法实时用。而移动机器人（自动驾驶、AGV）恰恰既要快又要好。
- 做法：过去大家只想着「怎么把 RRT* 加速」（信息引导采样：把随机撒点集中在最优解可能出现的椭圆区域；路径优化：剪枝、随机捷径、包裹、梯度优化）。这篇论文的妙处是——这些招数也用到基础 RRT 上：RRT 本来就快，省下的时间正好让路径优化器把解改好。
- 结果：时间受限时，所有基于 RRT 的优化信息 RRT 都打赢了所有基于 RRT* 的版本；时间充裕时，最好的两个 RRT 版本依然全胜，另外两个打平。结论：「快而次优」+「后处理优化」可以反超「慢而最优」。
- 最值钱的观点：实时系统里的「最优」不是数学最优，而是「在时限内能拿到的最好解」——把时间花在刀刃上，比追求理论最优更实际。这背后的思想（anytime / 渐进改进）在现代规划算法里到处可见。
- 工程意义：对做移动机器人/自动驾驶的同学，这篇论文是理解「采样规划 → 信息采样 → 路径优化」演进脉络的最佳入口；文中四种优化器的对比也很有参考价值。
🎯 对保研的启示：这篇论文示范了「问题重定义」的科研套路——大家都忙着给 RRT* 提速，作者把问题改成「快算法能不能通过后处理变好」，一下就打开了新空间。复试时能讲出「我重新定义了什么问题、为什么这么定义」，是很大的加分项。
八、给准大一的阅读路线图 & 延伸方向
📖 怎么读这篇论文（三遍法）
- 第一遍（10 分钟）：只读摘要和术语表，回答三个问题——问题是什么？（RRT 快但次优）方法是什么？（信息采样 + 路径优化）结果是什么？（RRT 版反超 RRT* 版）。
- 第二遍（20 分钟）：读引言 + 结论，重点体会「为什么没人把信息采样用到基础 RRT 上」以及四种优化器的分工（剪枝删点、捷径拉直、包裹贴边、梯度平滑）。
- 第三遍（30 分钟）：读方法文字部分，跳过所有公式和编号，只看文字描述；遇到不懂的术语回查术语表。
🚀 这个方向你能延伸做什么
- 现在就能做：装 Python 的 OMPL 库，在 2D 地图上分别跑 RRT、RRT*、Informed RRT*，肉眼对比路径质量和耗时——五分钟就能复现这篇论文的核心直觉。
- 大一→大二：学好概率论（随机采样是 RRT 的数学根基）与数据结构（树、图搜索）；算法竞赛和数学建模的「迷宫寻路」题可以直接用 RRT 练手。
- 大二→大三：方向可扩展为采样路径规划（RRT*/PRM）、运动规划中的约束处理、自动驾驶全局路径规划、多机器人协同规划、学习式采样（把深度学习用于引导采样）——都是机器人工程热门方向；可关注 ICRA、IROS、T-RO 与国内《机器人》。
九、英文摘要朗读（练听力用）
先盲听一遍→再看对照稿→再听一遍。目标是听出术语（informed sampling、path optimisation、RRT*、convergence rate）和结论句（RRT-based … better performance）。