上篇讲了PRM——先建路线图再查询。今天讲RRTRapidly-exploring Random Tree思路完全不同不预计算直接从起点长出一棵树边长边找路。讲真RRT是运动规划领域用得最广的算法之一面试几乎必问。RRT的核心思想很简单从起点开始每次随机采一个点找到树上离它最近的节点往那个方向长一小步加到树里。重复这个过程直到树长到目标点附近。说白了就是用随机采样的方式快速探索空间。一、RRT算法流程RRT的每一步就做四件事随机采样一个点q_rand在树中找离q_rand最近的节点q_near从q_near往q_rand方向走一小步步长固定为delta得到新节点q_new检查q_new是否在障碍物中不在就加到树里步长delta是个关键参数——太大容易穿过障碍物太小长得太慢。工程上一般取空间对角线的1%-5%。class RRT: def __init__(self, start, goal, step_size0.5): self.tree [start] self.parent {tuple(start): None} self.step step_size self.goal goal def plan(self, max_iter5000): for _ in range(max_iter): q_rand random_sample() q_near nearest_node(q_rand) q_new steer(q_near, q_rand, self.step) if not collision(q_near, q_new): self.tree.append(q_new) self.parent[tuple(q_new)] q_near if distance(q_new, self.goal) self.step: return self.extract_path() return None二、RRT为什么快RRT快的原因就一个字——贪。它不像A*那样维护一个优先队列算f值也不像Dijkstra那样保证最短路径。它就做一件事往随机方向长。这种贪带来了两个好处。空间探索速度快——树均匀地往各个方向扩展不会只盯着一个方向死磕。高维空间也能用——RRT的复杂度主要和空间体积有关和维度没有直接关系。6D、7D的构型空间RRT照样能跑。但代价也很明显——路径质量差。RRT找到的路径通常弯弯曲曲离最优解差很远。而且每次运行结果不同路径不稳定。三、RRT的工程细节工程实现中有几个容易踩的坑。最近邻搜索每步都要找树上离采样点最近的节点。树大了以后这一步很慢——O(N)遍历所有节点。工程上一般用KD树加速把最近邻查询降到O(logN)。但KD树在高维空间10D效率下降明显这时候用FLANN或者简单的随机子集近似。碰撞检测每长一步都要检查新边是否和障碍物碰撞。这是RRT最耗时的部分之一。工程上常用的优化先用包围盒做粗检测过了再精细检测。在机械臂场景中用FCL库做GJK碰撞检测效率很高。数据结构树怎么存每个节点需要保存坐标、父节点指针、到起点的代价。用邻接表或者直接用字典存parent关系就行。回溯路径时从目标节点沿parent链走回起点。四、RRT的局限与改进方向RRT的主要问题有三个。路径质量差是最突出的。树是随机长的路径自然七扭八歪。工程上通常要做后处理——用shortcut方法随机取两个路径点尝试直线连接能连就截掉中间那段。反复做几十次路径长度能缩短20%-50%。狭窄通道也有问题。虽然比PRM好一些树会往各个方向长但如果通道特别窄随机采样也很难恰好穿过去。改进思路是加目标偏置或者用RRT-Connect双向搜索。目标到达问题——标准RRT不保证能找到精确到达目标的路径。工程上用目标偏置goal bias来解决每次迭代有一定概率直接把目标点当作q_rand。这样树会主动往目标方向长。目标偏置的概率一般设5%-10%太高了树就变成贪心搜索失去了随机探索的优势。# 目标偏置 路径短接 if random() 0.05: q_rand self.goal def shortcut(path, iterations50): for _ in range(iterations): i, j sorted(sample(range(len(path)), 2)) if not collision(path[i], path[j]): path path[:i1] path[j:] return path五、RRT家族一览RRT出来之后学术界搞出了一堆变体面试经常拿来对比RRT-Connect双向搜索从起点和终点各长一棵树两棵树相遇就找到路径。速度比单向RRT快很多。RRT*加了重连机制路径渐进趋向最优。代价是计算量增大。Informed RRT*用启发式函数引导搜索收敛更快。BIT*把RRT和图搜索结合起来兼顾效率和最优性。这些变体后面都会讲到。但万变不离其宗——核心思想都是随机采样树扩展。六、面试实战QRRT和PRM有什么区别APRM先建路线图再查询路线图和起止点无关适合多次查询。RRT每次查询长一棵树树和起止点有关适合单次查询。PRM预计算代价大RRT没有这个问题。QRRT是概率完备的吗A是的。如果解存在随着迭代次数趋向无穷RRT找到解的概率趋向1。但有限次迭代不保证找到解。QRRT的路径为什么质量差怎么改善A因为树是随机生长的路径节点不在最优位置上。改善方法路径短接shortcut、用RRT*代替RRT、或者跑完RRT后用优化器平滑。Q实际项目中用过RRT吗A用过。之前做机械臂避障规划7自由度机械臂在 cluttered 环境中抓取。用RRT在关节空间规划大概200ms能出路径。路径质量一般后面加了shortcut后处理路径长度缩短了约30%。QRRT的步长怎么选A步长太大容易穿过薄障碍物漏检太小长得慢。一般取空间范围的1%-3%。也可以用自适应步长——离障碍物近时步长小空旷区域步长大。QRRT能处理动态障碍物吗A标准RRT不行——它假设环境是静态的。动态环境要用动态RRT或者每帧重新规划。实际工程中动态环境一般用DWA或者TEB这类局部规划器RRT做全局规划两者配合使用。QRRT的时间复杂度是多少A单次迭代O(logN)KD树最近邻查询N是树上节点数。总复杂度O(NlogN)。但N和找到路径所需的迭代次数有关这个没有理论上界——取决于问题的难度。QRRT和A*在什么场景下分别使用A低维空间2D/3D用A*——路径最优、确定性强。高维空间机械臂6-7D用RRT——A*根本跑不动。工程上经常是RRT做全局规划DWA做局部避障两者分层配合。小结RRT的核心从起点随机长树每步往随机采样点方向走一小步。简单、通用、适合高维。优势不用预计算高维空间能用实现简单对狭窄通道比PRM友好。 劣势路径质量差结果不稳定需要后处理不适合动态环境。RRT是采样规划领域最基础也最核心的算法。理解RRT之后后面的RRT、Informed RRT、RRT-Connect都是在这个基础上的改进。面试中RRT是必考点——不光要会讲原理还要能聊工程细节KD树加速、碰撞检测优化、路径短接。把这些细节讲清楚面试官会觉得你确实做过。下一篇讲RRT*——在RRT基础上加了重连机制让路径渐进趋向最优解。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第213篇 PRM概率路线图——预计算方案的适用场景下一篇预告第215篇 RRT*渐进最优——从可行解到最优解有任何问题欢迎评论区留言我会尽量回复。
