采样规划系列讲了RRT、RRT、Informed RRT、RRT-Connect。今天讲一个思路完全不同的算法——BITBatch Informed Trees。说白了BIT把RRT的采样思想和A的图搜索思想结合到了一起。它用优先队列来管理采样点先扩展最有希望的点而不是随机选点。BIT也是Gammell团队提出的2015年。它要解决的核心问题是RRT的采样是盲目的均匀随机A*在离散网格上搜索又太慢。能不能两者结合——用采样来避免离散化用优先队列来避免盲目一、BIT*的核心思想BIT*的工作方式分批次batch。每一批中从当前采样点集合中用优先队列选出最有潜力的边来扩展优先队列的排序依据是从起点经过这条边到终点的预估代价类似A*的f值扩展完当前批次的所有有效边后增加新的采样点开始下一批关键区别RRT每步随机选一个采样点扩展BIT每步选最有潜力的边扩展。这让BIT*的搜索更有方向性收敛更快。class BITStar: def __init__(self, start, goal): self.start start self.goal goal self.vertices [start] self.edges set() self.queue PriorityQueue() # 按f值排序 self.best_cost float(inf) def plan(self): while True: self.sample_batch() # 采样一批新点 self.update_queue() # 更新优先队列 while not self.queue.empty(): c_parent, parent, child self.queue.pop() if c_parent dist(child, self.goal) self.best_cost: break # 剪枝 if not collision(parent, child): self.add_edge(parent, child) if child self.goal: self.best_cost cost(child) # 批次结束更新下界二、BIT*为什么高效BIT*高效的原因有两个。优先队列引导搜索和RRT的随机采样不同BIT用优先队列选择扩展顺序。优先队列按f值起点到当前节点代价当前节点到终点的启发式估计排序。f值小的边先扩展——搜索方向自然偏向目标。这和A的思想一脉相承。但和A不同的是BIT*的节点是连续空间中的采样点不是离散网格上的格子。这避免了维度灾难。动态剪枝每次找到更好的路径后BIT会更新代价上界c_best。优先队列中所有f值大于c_best的边都被剪掉——不用浪费时间扩展它们。这和Informed RRT的椭球约束异曲同工但实现方式不同。Informed RRT通过约束采样区域来剪枝BIT通过优先队列的f值来剪枝。效果类似但BIT*的剪枝更精确——因为它考虑了每条边的具体代价而不是一个粗略的椭球边界。批次采样BIT不是一次采一个点而是一次采一批。批次大小可以自适应——如果当前批次改善不大下一批多采一些。这让BIT能根据问题难度动态调整采样密度。具体来说如果一批中有大量边被剪枝说明当前采样点不够好下一批就多采一些来增加找到好路径的概率。和RRT*的本质区别RRT是先采样再优化——随机采一堆点然后通过re-wire慢慢优化。BIT是边采样边优化——用优先队列保证每次扩展的都是当前最有价值的边同时通过批次采样不断增加新的候选点。这种有方向的探索让BIT*的收敛速度快得多。三、BIT和RRT的对比面试中经常被问到BIT和RRT的区别。核心差异有三点搜索策略RRT是随机采样树扩展BIT是优先队列图搜索。RRT的搜索方向由随机性决定BIT的搜索方向由启发式函数引导。数据结构RRT维护一棵树BIT维护一个图因为一个节点可能有多个父节点候选。BIT*的图结构更灵活但内存消耗也更大。收敛特性两者都是渐进最优的。但BIT的收敛速度通常比RRT快——因为优先队列让搜索更有方向性。在论文实验中BIT在复杂场景中的收敛速度比RRT快1-2个数量级。# BIT* vs RRT* 对比经验数据 # 场景2D, 100个障碍物 # RRT*: 约15000次迭代收敛到最优的1.05倍 # BIT*: 约2000次迭代收敛到最优的1.05倍 # 加速比约7倍四、工程应用与面试实战BIT在工程上的应用不如RRT-Connect和Informed RRT广泛。主要原因是实现复杂度高——优先队列的管理、批次采样的策略、图的维护都比RRT复杂不少。OMPL库中有BIT的实现MoveIt2可以通过OMPL调用。QBIT和A有什么本质区别AA在离散化的网格上搜索BIT在连续空间中采样搜索。A的节点是网格中心BIT的节点是随机采样点。BIT*避免了网格离散化带来的精度损失和维度灾难。QBIT*在实际项目中用过吗A用过但只在离线规划场景中。BIT*的计算时间波动比较大——取决于批次大小和问题难度。在线规划比如实时避障中不太敢用因为最坏情况下的计算时间不好保证。离线规划比如机械臂预计算路径中效果不错。QBIT*适合什么场景A高维空间中需要最优路径的场景。比如7D机械臂规划——RRT收敛太慢A维度太高跑不动BIT*在这两者之间找到了一个平衡点。QBIT*的批次大小怎么选A初始论文建议固定批次大小比如100-500个采样点。后续改进ABIT*支持自适应批次大小——如果当前批次改善不大下一批多采一些。工程上自适应策略效果更好。一般初始批次大小设为200然后根据收敛情况动态调整。QBIT*能处理动态环境吗A原版BIT不能——它假设环境是静态的。但后续有扩展版本如DBIT支持动态环境。工程上动态环境一般用BIT*做全局规划DWA做局部避障和RRT系列的使用方式类似。QBIT*的优先队列怎么管理A优先队列中存的是边parent, child, f_value。每次pop出f值最小的边来扩展。如果扩展成功无碰撞把新边加入队列。如果扩展失败碰撞丢弃这条边。找到更优路径后更新队列中所有相关边的f值并剪掉f值超过上界的边。Q你在项目中对比过BIT*和其他算法吗A对比过。在一个7D机械臂场景中同样的起止点RRT跑了20000次迭代还没收敛到满意的路径BIT跑了3000次迭代就收敛了。但BIT的单步计算时间比RRT长优先队列操作有开销所以总时间差距没有迭代次数差距那么大——大约快了3倍。QBIT*有什么已知的缺点A实现复杂度高是最大问题。优先队列管理、批次采样策略、图结构维护——每个部分都比RRT复杂。调试起来也更困难。另外BIT的计算时间方差大——简单问题很快复杂问题可能突然变慢。在对实时性要求高的场景中这个特性让人不太放心。小结BIT*的核心用优先队列管理采样边的扩展顺序批次采样兼顾了采样规划的灵活性和图搜索的方向性。优势收敛速度比RRT*快1-2个数量级渐进最优避免网格离散化。 劣势实现复杂计算时间波动大工程应用不如RRT变体广泛。BIT*是采样规划领域的一个重要创新——它证明了采样和图搜索不是对立的可以结合起来。下一篇进入局部规划系列讲DWA动态窗口法。如果这篇文章对你有帮助欢迎点赞、在看、转发三连。 你的支持是我持续更新的最大动力。「机器人软件开发面试·从入门到精通」连载系列上一篇第217篇 RRT-Connect——双向搜索的经典算法下一篇预告第219篇 DWA动态窗口法——移动机器人的局部避障有任何问题欢迎评论区留言我会尽量回复。