上篇讲了Informed RRT*——用椭球约束采样加速收敛。今天讲另一个方向的改进RRT-Connect。思路很直接一棵树长得慢那就两棵树一起长——从起点长一棵从终点长一棵两棵树相遇就找到路径了。讲真RRT-Connect是工程上最常用的RRT变体之一很多实际项目用的都是它而不是原版RRT。RRT-Connect是Kuffner和LaValle在2000年提出的。核心思想就是双向RRT——两棵树交替生长每步让一棵树往另一棵树上的随机节点方向长一步。当两棵树能直接连起来时路径就找到了。一、双向搜索的原理单向RRT的问题树从起点开始长要长到目标附近才能找到路径。如果起点和目标相距很远树需要长很多步才能到达目标区域。双向RRT的思路从起点和终点各长一棵树。两棵树交替生长——每步先选一棵树随机采样一个点让这棵树往采样点方向长一步。然后尝试让另一棵树的最近节点往新节点方向连——如果能连上无碰撞路径就找到了。class RRTConnect: def __init__(self, start, goal): self.tree_a [start] # 从起点长 self.tree_b [goal] # 从终点长 self.parent_a {tuple(start): None} self.parent_b {tuple(goal): None} def plan(self, max_iter5000): for _ in range(max_iter): q_rand random_sample() # 树A往随机点长 q_new_a extend(self.tree_a, q_rand) if q_new_a is None: continue # 树B往树A的新节点长 q_connect connect(self.tree_b, q_new_a) if q_connect q_new_a: return self.extract_path(q_new_a) # 交换两棵树 self.tree_a, self.tree_b self.tree_b, self.tree_a return None关键操作有两个extend往随机点方向长一步和connect往目标方向一直长直到连上或者撞墙。connect不是只长一步——它会沿着方向一步步长直到新节点和目标节点距离足够近或者碰到障碍物。二、为什么比单向RRT快RRT-Connect快的原因很直观两棵树同时往中间长每棵只需要长一半的距离。在开阔空间中这个加速效果大约是2-4倍。更深层的原因是connect操作。单向RRT每步只长一个固定步长遇到空旷区域效率很低。RRT-Connect的connect操作在空旷区域会快速推进——沿着方向一直长直到碰到障碍物或者连上另一棵树。这在开阔区域特别有效。但RRT-Connect也有弱点。在狭窄通道场景中两棵树可能都在通道口附近打转很难恰好穿过通道连上。这时候双向搜索的优势就不明显了。工程上的一个常见策略如果RRT-Connect在限定时间内没找到路径就交换起点和终点重新跑一次。因为两棵树的生长策略不完全对称交换后可能更快找到路径。三、工程实现细节RRT-Connect的实现有几个容易忽略的细节。树的交换每次迭代后两棵树要交换角色。如果不交换一棵树可能长得很大另一棵树很小效率降低。工程上有些实现用谁小谁先长的策略——节点少的树优先扩展保持两棵树的平衡。connect操作的终止条件connect往目标方向长时什么时候停通常是两种情况新节点和目标节点距离小于阈值或者新节点碰到障碍物。有些实现还会限制connect的最大步数防止在空旷区域长太远。路径提取两棵树连上后路径要从连接点分别回溯到起点和终点然后拼接。注意第二棵树的回溯方向是反的——从连接点到终点。def connect(tree, target, step0.5, max_steps100): q nearest_node(tree, target) for _ in range(max_steps): q_new steer(q, target, step) if collision(q, q_new): break add_to_tree(tree, q_new) if distance(q_new, target) step: return target q q_new return q_new四、RRT-Connect的变体RRT-Connect之后学术界又搞出了几个改进版本RRT-Connect**在RRT-Connect基础上加了RRT的优化机制——选最优父节点和re-wire。路径质量比RRT-Connect好但计算量大。Informed RRT-Connect结合Informed RRT*的椭球采样——找到第一条路径后两棵树都在椭球内采样。收敛速度比RRT-Connect快很多。Lazy RRT-Connect延迟碰撞检测——先假设所有边都有效找到路径后再做碰撞检测。如果检测到碰撞移除无效边继续搜索。在碰撞检测代价很高的场景中比如复杂机械臂模型Lazy版本能省不少时间。工程上最常用的是原版RRT-Connect和Lazy RRT-Connect。MoveIt2中默认用的是RRT-Connect可以通过配置切换到Lazy版本。五、面试实战QRRT-Connect和RRT有什么区别ARRT-Connect是双向搜索——从起点和终点各长一棵树两棵树相遇就找到路径。RRT是单向的只从起点长。RRT-Connect通常比RRT快2-4倍因为它只需要长一半的距离。QRRT-Connect的connect操作是什么Aconnect不是只长一步而是沿着方向一直长直到连上目标或者碰到障碍物。这让它在空旷区域推进很快。QRRT-Connect有渐进最优性吗A没有。RRT-Connect找到路径就停了不做优化。如果需要最优路径得用RRT或者Informed RRT。工程上经常是RRT-Connect快速找到路径然后用shortcut后处理优化。Q实际项目中用过RRT-Connect吗A用过。做移动机器人全局规划时用RRT-Connect在2D栅格地图上规划。10m x 10m的房间起点和终点在对角RRT-Connect平均50ms找到路径单向RRT要200ms。后来加了shortcut后处理路径长度缩短了约25%。QRRT-Connect在高维空间中表现如何A可以用但效率会下降。高维空间中最近邻搜索变慢connect操作的效果也不如低维空间明显。7D关节空间中RRT-Connect通常比单向RRT快1.5-2倍不如2D空间中的2-4倍。MoveIt2中默认用的就是RRT-Connect。小结RRT-Connect的核心从起点和终点各长一棵树交替扩展两棵树相遇就找到路径。connect操作让它在空旷区域推进很快。优势比单向RRT快2-4倍实现简单工程上广泛使用。 劣势没有渐进最优性路径质量依赖后处理狭窄通道场景效率下降。RRT-Connect是工程上最实用的RRT变体没有之一。面试中如果问到RRT的改进方案RRT-Connect是最应该提到的——因为它确实被大量项目使用MoveIt2、导航框架里都有它的身影。能把RRT-Connect的原理和工程细节讲清楚面试官会认为你有实际项目经验。下一篇讲BIT*——把RRT和图搜索结合起来的算法。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第216篇 Informed RRT*——用启发式信息加速收敛下一篇预告第217篇 RRT-Connect——双向搜索的经典算法有任何问题欢迎评论区留言我会尽量回复。