Home / 机器人经典基础 / BIT*：让随机采样按照值得尝试的顺序进行搜索

081｜BIT*：让随机采样按照值得尝试的顺序进行搜索

论文：Jonathan D. Gammell、Siddhartha S. Srinivasa、Timothy D. Barfoot，Batch Informed Trees (BIT): Sampling-Based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs*，2014 年首次预印本，2015 年会议版本。精读版本 v7 · OMPL 官方接口。

先接住前作的问题

从Informed RRT*继承可改善区域的限制，仍留下“区域内先验证哪条边”的问题；BIT* 把A*式下界排序与逐批随机图组合起来。它与TrajOpt是平行路线：前者探索可行路径拓扑并渐近改善，后者在给定初始化附近优化轨迹，不应把后者写成本篇的后代。

五个前置概念

五个前置概念：

可采纳启发式：不超过真实最优代价的估计。
随机几何图：以随机状态为顶点、按空间邻近建立潜在边。
重连：更换树节点父边以降低已知到达代价。
任意时间算法：允许在有解后继续计算并改善结果。
渐近最优：资源无限增长时趋近最优，不是有限预算保证。

一、问题设定：批量采样图中怎样优先检查最可能改善的连接

RRT* 能不断增加随机状态，并逐步改善路径，但候选连接的处理顺序不够有针对性。另一方面，A* 很善于优先搜索可能更短的路线，却通常需要面对一个事先确定的离散图。

背景与问题定义

状态可以是机械臂关节角向量，动作在规划层表现为两个状态之间的局部连接。给定起点、目标集合、碰撞空间与路径代价，目标是寻找可行且代价尽可能低的路径。

这不是强化学习。没有奖励训练、策略梯度或环境回合；“采样”指在构型空间抽取候选状态，“代价”指路径长度等规划目标。

离散图太稀，会错过狭窄通道；太密，又会产生大量昂贵的碰撞检查。BIT* 不预先构建和验证所有边，而是保留隐式连接规则：哪些样本互为近邻、哪些连接可能值得检查，按需要展开。

与 Informed RRT* 相比，它不仅限制采样范围，还对同一批候选连接进行有序处理。与固定批次的 FMT* 相比，它能够继续加样本，并复用前一批的信息。

二、区分三类代价，用双队列延迟昂贵验证

三个代价必须区分

设 $g^*(x)$ 是真实最优的起点到 $x$ 代价， $g_T(x)$ 是当前树里已找到的代价， $\hat g(x)$ 是低估真实代价的启发式。通常有：

$\hat g(x)\le g^*(x)\le g_T(x).$

再令 $\hat h(x)$ 是到目标的代价下界，当前最好完整路径的代价为 $c_{best}$ 。能够包含更好解的候选区域满足：

$\hat g(x)+\hat h(x)<c_{best}.$

对于欧氏路径长度，起点与目标的直线距离之和给出椭球形区域。它不直接指出哪条路没有障碍，只保证区域外的状态无法构成更短解。

最容易犯的错是用 $g_T$ 替代 $\hat g$ 做永久剪枝。某状态当前绕远到达，不代表将来不能找到更短的到达方式；树内代价是已知路径的上界，不是所有可能路径的下界。

双队列：先便宜判断，再昂贵验证

顶点队列按 $g_T(v)+\hat h(v)$ 排序，决定哪些顶点需要生成候选边。边队列按

$g_T(v)+\hat c(v,x)+\hat h(x)$

排序，其中 $\hat c$ 是连接代价下界。只有值得进一步考虑时，才执行真正的局部连接与碰撞检查，得到 $c(v,x)$ ；碰撞边可视为代价无穷。

这种延迟不是不检查安全性。最终进入路径的边仍要通过所用碰撞检查器，只是不为明显无望的边提前付费。

在树中发现更低代价父节点时进行重连；新批次加入时继续使用已有树。剪枝还要谨慎处理被断开的后代：若其状态仍可能有用，可以退回未连接样本集合，而不是一并永久删除。

一条候选边究竟过几道门

把第 III-B 节的检查展开，才能看出“下界”与“当前树”怎样分工。对候选边 $(v,x)$ ，先检查 $g_T(v)+\hat c(v,x)+\hat h(x)<c_{best}$ ；最小队列键都失败，说明当前这一批搜索可以结束，却不意味着所有未来批次都无解。计算真实边代价 $c(v,x)$ 后，还检查 $\hat g(v)+c(v,x)+\hat h(x)<c_{best}$ ，最后要求 $g_T(v)+c(v,x)<g_T(x)$ 才接入树。第二道门使用到达下界，第三道门比较实际树内改善，两者不能合并。

原创手算跟踪。 已有完整解代价 12，某候选满足 $g_T(v)=4,\hat g(v)=2,\hat c(v,x)=2,\hat h(x)=3,g_T(x)=8$ 。队列键为 9，值得检查。若真实连接代价为 5，第二道门得到 $2+5+3=10<12$ ，但第三道门是 $4+5=9>8$ ，所以不能重连；若真实代价为 3，两道门分别得到 8 和 7，才把 $x$ 的树内代价从 8 改为 7。候选“可能改善完整解”不等于“这次接边确实改善树”。

这里的数字是假设的非负边代价，不是图 4 的实验。图 4 比较的是达到同一指定代价所需时间；上述跟踪解释它为何可能省掉工作，却不能从检查次数直接推出实际加速，因为近邻、队列和碰撞检查各有不同成本。检查顺序依据原论文 III-B2–3。

原论文图4：四种采样规划器在同一二维障碍场景中的树与返回路径 — Jonathan D. Gammell、Siddhartha S. Srinivasa、Timothy D. Barfoot（2014），图 4，PDF 第 5 页；原文与图注。原版权保留。

读图：四个面板达到相同指定路径代价时才停止；图下时间与各自搜索结构应一起比较。

为何可能有效，理论保证又是什么

收益主要来自两个方向：降低搜索无望区域的比例；把碰撞检查等昂贵工作放到更有希望的连接上。批量处理提供排序空间，持续批次提供逐渐加密的分辨率。

第 IV 节定理 1通过与满足条件的随机几何图及 RRT* 联系，讨论几乎必然渐近最优性。它依赖采样分布、连接规则和启发式下界等条件。将连接半径任意减得很小、使用高估启发式错误剪枝，不能继续无条件引用该结论。

概率完备性与渐近最优性都是样本数增长后的性质，不给每次 100 ms 运行一个确定的误差上界。狭窄通道在有限预算内仍可能没有被采到。

候选边先按便宜下界排队，真正的碰撞验证可以延后。下面检查双队列怎样避免过早支付代价，再分别看首解与持续改善。

三、扩充样本批次并复用搜索，检查下界剪枝

初始化树 T={起点}，未连接样本含目标，最好代价为无穷
预算未耗尽时：
    若本批次没有可继续处理的候选：
        用可采纳下界剪去不可能改进的状态
        在仍可能改进的区域采样一批状态
        更新近邻连接规则，初始化顶点队列
    展开可能产生更优候选边的顶点，加入边队列
    取估计完整路径代价最低的候选边
    若本批候选已无法改善当前解：开始下一批
    否则执行必要的真实连接代价与碰撞检查
    若连接有效且改善目标顶点代价：接入或重连树
    若到达目标并改善代价：保存新解
返回截至当前预算已找到的最好可行路径

这是概念伪代码。可运行版本还需要处理空队列、旧/新顶点重连规则、代价变化后的队列维护与具体连接半径。

自构例子与前置概念

自构例子，未运行：起点和终点相距 10，已有绕障路径长度 14。某样本到两端的直线距离和为 16，它不可能产生更短解，可不再考虑；另一样本下界为 12，却可能被墙挡住，仍要碰撞检查。

若后一状态在当前树中的到达代价很高，也不能据此永久删除，因为下一批样本可能提供更短的到达方式。下界用于判断“有没有可能”，当前树代价用于描述“现在已经找到什么”。

四、同时读首解时间、最终代价与成功率

Fig. 5：上排看预算内成功比例，下排看已求解样本的中位代价 — 原论文结果图／表摘引：Jonathan D. Gammell、Siddhartha S. Srinivasa、Timothy D. Barfoot（2014），Fig. 5，PDF 第 6 页；核对原文。原版权保留。

读图：上排看预算内成功比例，下排看已求解样本的中位代价。较低代价必须与多少运行成功一起解释；成功样本集合随时间改变，中位数也不必逐时刻下降。

这里采用 v7 会议稿中的图与算法；当前 OMPL 接口的后续变化不能反推为原论文实验设置。

实验	规模与设置	比较方法	指标与验证意图
随机二维、八维世界	每维度 10 个世界，每世界 50 个伪随机种子	RRT、RRT-Connect、RRT、Informed RRT、FMT*	给定时间内成功率、路径代价
批次设置	BIT* 每批 100 样本，欧氏启发式；第 V 节	FMT* 尝试不同固定样本数	观察逐批细化和固定批次的取舍
HERB 单臂与双臂	真实平台对应的高维构型与碰撞规划问题	相同规划家族	昂贵碰撞检查下能否更快改善
调参	随机实验参数在独立训练世界上选择	不是训练策略网络	减少直接针对测试世界调参的影响
统计	中位数与非参数 95% 置信区间，见图 5说明	未成功试验的纳入方式会变化	同时查看成功率，避免幸存者偏差

BIT星二维和八维随机环境的四面板结果及完整六方法图例 — Gammell、Srinivasa、Barfoot（2015），图5完整四面板，PDF第6页；原文与图注。原版权保留。

读图：补齐原有裁切缺失的完整图例，四面板分别区分成功比例与解成本；各条曲线的颜色必须与下方算法名称一起读取。

不同机器用于随机世界和 HERB 实验，因此不应直接跨两类实验比较毫秒数。本文不补造所有参数搜索消耗的完整预算；原文没有统一量化该项。

图 5展示的是代表性世界，不能将一张代表图称作所有 20 个世界的汇总结果。作者解释不同世界真实最优值未知且尺度不同，因而选择分问题呈现。

结果：首解、代价与成功率需要一起看

图 1。 困难双臂任务的路径与统计；有限预算中提高可行解获取能力；不能据此推出：每次都能在示例的 4 秒内解决。

尚未内嵌：图 1、图 6。剩余是 HERB 双臂/单臂运动叠加照片；当前评论主要评价成功率、计算时间和搜索性质，已展示相应图表及算法过程。照片不能独立证明这些定量结论，暂保留两个平台演示入口。

图 3。 加批次、剪枝与搜索推进；解释信息复用机制；不能据此推出：直观图本身就是速度证明。

原论文图3：BIT*加入批次、启发式搜索与剪枝的四阶段示意 — Jonathan D. Gammell、Siddhartha S. Srinivasa、Timothy D. Barfoot（2014），图 3，PDF 第 3 页；原文与图注。原版权保留。

读图：绿点和红点给出起终点；每次加入样本后只改变搜索支持集，不应把蓝色连线数量当成实测运行时间。

图 4。 同一二维问题达到相近代价；展示排序可减少无效工作；不能据此推出：单个例子代表平均加速比。

图 5。 成功率与中位代价随时间变化；观察有限时间性能；不能据此推出：中位数上升意味着每条路径变差。

图 6。 操作规划结果；将方法带到较贵的碰撞空间；不能据此推出：已比较任意动力学控制任务。

困难双臂问题在 25 次、每次 2.5 分钟预算中，BIT* 成功率为 68%，Informed RRT* 为 8%，FMT* 为 36%；图 1同时列出的中位代价分别为 17.4、25.3、17.2。FMT* 的已解路径代价略低，却更少找到解，不能只挑代价一列宣布谁全面获胜。

BIT* 相比 FMT* 的成功率是提高 32 个百分点，若计算相对提升则为 $(68-36)/36\approx88.9\%$ 。两者口径不同，本文优先使用百分点。

RRT-Connect 找到初始解更快的事实应保留，它对应“先快速拿到一条可行路”的不同取舍。渐近最优方法的价值在后续持续改善，不是必须赢每一个首解时间。

五、保留队列成本、有限预算和理论条件

贡献、代价与局限

新意是将启发式图搜索、随机几何图、批次加密和增量复用组织在一起，而不是单独发明 A*、采样或椭球区域。这样把搜索顺序与空间分辨率两件事协调起来。

队列维护、近邻检索与剪枝都有成本；碰撞检查很便宜、启发式很弱或只需极快首解时，优势可能缩小。批次太小，排序空间不足；太大，则可能在早期花太多时间处理一个过密图。这是算法设计的取舍，不是论文已经给出普适最佳批次。

作者讨论了未来约束规划扩展。本文分析认为：若机器人需要非完整运动或复杂动力学连接，真正边代价和可采纳启发式可能更难计算，不能只把几何版本伪代码换个状态向量就当作完成扩展。

六、追问：减少碰撞检查次数，为什么未必等量减少总运行时间？

减少碰撞检查次数，为什么未必等量减少总运行时间？

参考答案：双队列、近邻与批次管理也有成本，减少一类查询不等于其余开销不变。应固定碰撞检查器与预算，分别统计检查、搜索维护和最终解质量。首解时间与后续改善是不同指标，不能用一个总排名替代。

七、回看启发采样，再比较局部轨迹优化

直接继承：Informed RRT*：已有一条路之后，还值得搜索哪里。回看可改善区域的下界如何支撑批量搜索。
平行路线：TrajOpt：用局部凸问题修复整条碰撞轨迹。在给定初值附近局部优化轨迹，探索与优化职责不同。

八、自测与参考答案

问题一：为什么延迟碰撞检查不等于降低路径安全要求？

答案：延迟只是改变验证顺序，明显不可能改善结果的边不必花钱检查；真正接入树并返回的路径边仍必须通过所用碰撞检测。检测器本身的分辨率和准确性是另一层假设。

问题二：为什么不能用当前树代价加剩余启发式永久剪掉一个状态？

答案：当前树代价只是已经找到的路径上界，后续可能通过重连降低。永久剪枝需要对所有可能到达路径都成立的代价下界；否则可能删除未来最佳路线必须经过的状态。

问题三：成功率提高时，中位路径代价为什么可能上升？

答案：先前失败的困难试验后来得到较长路径，被加入统计，改变了样本组成。原文图注明确提醒这一点。应同时看成功率、统计纳入规则和单次最优代价，不能把汇总中位数上升误认为算法撤销了更好的路径。