上篇讲了RRT——随机长树，找到路径就停。问题是RRT的路径质量差，弯弯曲曲的。今天讲RRT，它在RRT基础上加了两个关键操作：选父节点时不只看最近的，还看代价最小的；加完之后还要re-wire（重连）附近的节点。说白了，RRT用更多的计算换来更好的路径。
RRT*是Karaman和Frazzoli在2011年提出的。核心贡献是证明了"渐进最优性"——随着迭代次数趋向无穷，路径代价趋向全局最优解。这个性质RRT没有。
一、RRT*和RRT的区别
RRT*和RRT的差异集中在两个地方。
选父节点：RRT直接把q_near当作新节点的父节点。RRT*不这样——它在q_new附近找一个半径为r的球，检查球里所有节点，选"起点到该节点代价+该节点到q_new代价"最小的那个当父节点。
重连（Rewire）：选完父节点后，RRT*还要检查附近节点的代价——如果通过q_new到达某个邻居比直接到达更便宜，就把那个邻居的父节点改成q_new。
def rrt_star_step(q_rand): q_near = nearest(q_rand) q_new = steer(q_near, q_rand, step) # 区别1：选最优父节点 neighbors = near_nodes(q_new, radius) best_parent = min(neighbors, key=lambda n: cost(n) + dist(n, q_new)) # 区别2：重连邻居 for n in neighbors: if cost(q_new) + dist(q_new, n) < cost(n): rewire(n, q_new) add_to_tree(q_new, best_parent)这两步额外操作让RRT*的计算量比RRT大不少——每步要多做邻居搜索和re-wire。但换来的是路径质量随迭代次数持续提升，最终趋向最优。
二、渐进最优性怎么理解
"渐进最优"这个词听着玄乎，其实意思很直白：迭代次数越多，路径越好，最终逼近理论最优。
打个比方：RRT像随机撒网，捞到什么算什么。RRT*像撒网之后还会整理——把绕远的线段替换成更短的走法。迭代次数越多，整理得越彻底，路径越接近最优。
数学上，RRT*证明了路径代价的上界随N（迭代次数）增大而收敛到最优代价。收敛速度和空间的维度、体积有关。维度越高，收敛越慢——但至少在理论上保证能收敛。
工程上，RRT*不需要跑到无穷次。一般跑个几千次迭代，路径质量就比RRT好很多了。如果时间允许，跑一两万次，路径已经相当接近最优。
三、RRT*的工程挑战
讲真，RRT*在实际项目中的落地没有RRT那么顺利。
计算量大：每步要做近邻搜索（不只是最近邻，是半径r内的所有邻居），还要做re-wire。如果树有1万个节点，每步的邻居搜索和re-wire代价不小。工程上必须用高效的数据结构——KD树或者R树。在2D、3D空间中KD树效果不错，但到了7D关节空间，KD树效率急剧下降，这时候得用FLANN的随机KD树或者简单的暴力搜索加剪枝。
参数调优：半径r的选择很关键。r太大，每次邻居太多，计算量大；r太小，邻居太少，优化效果差。理论上有最优r的公式（和空间体积、维度、采样数有关），但工程上通常靠经验调。一个实用的策略是动态调整r——初始时r大一些（让树快速优化），后期r小一些（减少计算量）。
收敛慢：渐进最优是理论保证，但实际收敛速度可能很慢。在复杂环境中，跑了几千次迭代，路径可能还是比最优差不少。特别是在狭窄通道附近，树很难长过去，更别提优化了。这时候需要结合Informed RRT*（后面会讲）来加速收敛。
内存消耗：RRT*的树通常比RRT大——因为re-wire操作会让树的结构更复杂。每个节点需要存储父节点指针和代价值。10万个节点的树，内存占用大约在几十MB量级，一般不是问题。但如果采样数上百万，内存就成了瓶颈。
# 半径r的经验公式（Karaman & Frazzoli） # r = gamma * (log(N) / N) ^ (1/d) # gamma: 调优参数，d: 空间维度，N: 当前迭代数 # 动态调整r的策略 def adaptive_radius(N, d, vol_space): gamma = 2 * (1 + 1/d) ** (1/d) * (vol_space / unit_ball(d)) ** (1/d) return gamma * (log(N) / N) ** (1/d)三.5、RRT*的收敛过程
RRT的收敛过程很有意思。刚开始几百次迭代，路径质量和RRT差不多——都是弯弯曲曲的。到了1000-2000次迭代，RRT开始明显优于RRT——路径中那些绕远的弯开始被"拉直"。到5000次迭代，路径已经相当平滑了。继续迭代下去，改善越来越小，逐渐收敛。
有人做过对比实验：在2D空间中，RRT*跑1万次迭代，路径长度大约是最优解的1.1-1.3倍。在7D关节空间中，同样的迭代次数，路径可能是最优解的1.5-2倍。维度越高，收敛越慢——这和理论上界一致。
工程上，如果计算时间有限，可以设一个迭代上限（比如3000次），取当前最优路径。如果时间充裕，可以跑到路径长度不再变化为止。
四、面试实战
Q：RRT*和RRT的核心区别是什么？A：两个区别。选父节点时，RRT选最近的，RRT在半径r内选代价最小的。加完新节点后，RRT还要re-wire附近节点。这两步让RRT*的路径质量随迭代持续提升。
Q：RRT*的渐进最优性是什么意思？A：随着迭代次数趋向无穷，RRT*找到的路径代价趋向全局最优解。RRT没有这个保证——RRT的路径质量不随迭代改善。
Q：RRT*在实际项目中用过吗？A：用过。做机械臂规划时对比过RRT和RRT。同样的场景，RRT路径长度约12m，RRT跑5000次迭代后路径长度约8.5m，最优解大概7.8m。RRT*的计算时间大概是RRT的3-5倍。
Q：RRT*的半径r怎么选？A：理论上有公式，r和log(N)/N的1/d次方成正比。工程上一般取经验值，然后调参。r太大会导致每步邻居太多，计算量暴增；r太小优化效果不明显。
Q：什么时候用RRT*而不是RRT？A：对路径质量有要求、计算时间允许的场景。比如机械臂规划——路径短意味着运动时间短、能耗低。如果是实时性要求很高的场景（比如无人机避障），RRT*可能太慢，用RRT加后处理更实际。
Q：RRT*能保证找到最优解吗？A：不能保证。RRT保证的是"渐进最优"——迭代次数趋向无穷时路径趋向最优。有限次迭代只能给出一个次优解。这和A不同——A*在离散网格上能保证最优（如果启发函数可容许）。
Q：RRT和PRM有什么区别？A：两者都是渐进最优的采样规划算法。PRM是PRM的改进版，在建路线图时动态调整连接半径。RRT是基于树的。PRM适合多次查询（预计算路线图），RRT适合单次查询。工程上RRT*用得多一些，因为实现更简单，不需要预计算。
Q：你在项目中怎么权衡RRT和RRT*？A：看场景。如果规划频率要求高（>10Hz），用RRT加shortcut后处理，总时间能控制在50ms以内。如果规划频率不高（1-2Hz就行），用RRT跑几千次迭代，路径质量明显更好。之前做机械臂抓取时用的RRT，因为抓取动作本身就要几秒，规划多花几百毫秒不是问题。
小结
RRT*的核心：在RRT基础上加了最优父节点选择和re-wire操作，让路径渐进趋向最优。
优势：路径质量远好于RRT，有理论最优性保证。 劣势：计算量比RRT大3-5倍，收敛速度可能慢，参数调优有门槛。
RRT是采样规划从"能用"到"好用"的关键一步。理解RRT之后，下一篇讲Informed RRT*——用启发式信息加速收敛。
如果这篇文章对你有帮助，欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。
「机器人软件开发面试·从入门到精通」连载系列
上一篇：第214篇 RRT快速随机搜索树——高维空间规划的救星
下一篇预告：第216篇 Informed RRT*——用启发式信息加速收敛
有任何问题欢迎评论区留言，我会尽量回复。
