上篇讲了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, keylambda 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次取当前最优路径。如果时间充裕可以跑到路径长度不再变化为止。四、面试实战QRRT*和RRT的核心区别是什么A两个区别。选父节点时RRT选最近的RRT在半径r内选代价最小的。加完新节点后RRT还要re-wire附近节点。这两步让RRT*的路径质量随迭代持续提升。QRRT*的渐进最优性是什么意思A随着迭代次数趋向无穷RRT*找到的路径代价趋向全局最优解。RRT没有这个保证——RRT的路径质量不随迭代改善。QRRT*在实际项目中用过吗A用过。做机械臂规划时对比过RRT和RRT。同样的场景RRT路径长度约12mRRT跑5000次迭代后路径长度约8.5m最优解大概7.8m。RRT*的计算时间大概是RRT的3-5倍。QRRT*的半径r怎么选A理论上有公式r和log(N)/N的1/d次方成正比。工程上一般取经验值然后调参。r太大会导致每步邻居太多计算量暴增r太小优化效果不明显。Q什么时候用RRT*而不是RRTA对路径质量有要求、计算时间允许的场景。比如机械臂规划——路径短意味着运动时间短、能耗低。如果是实时性要求很高的场景比如无人机避障RRT*可能太慢用RRT加后处理更实际。QRRT*能保证找到最优解吗A不能保证。RRT保证的是渐进最优——迭代次数趋向无穷时路径趋向最优。有限次迭代只能给出一个次优解。这和A不同——A*在离散网格上能保证最优如果启发函数可容许。QRRT和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*——用启发式信息加速收敛有任何问题欢迎评论区留言我会尽量回复。