BIT*

分批撒采样点、再按启发式顺序搜索最优路径的运动规划算法。

BIT*（批量知情树）是 Gammell、Srinivasa、Barfoot 提出的基于采样的运动规划算法，2015 年发表于 ICRA，完整版 2020 年刊于 IJRR。RRT* 一类算法每次加一个随机点逐步长树；BIT* 则一次撒一批点，把它们看成一张隐式随机几何图（边不预先连好，用到才做碰撞检查），再像 A* 那样按「经过这条边的路径最短可能多长」的启发式顺序搜索。找到第一条解后，只在能改进当前解的椭球区域里撒下一批点（沿用 Informed RRT* 的做法），逐轮细化。它随时能给出当前最好解、越跑越优，并且概率完备、渐近最优；论文实验中，尤其在高维问题上，它比 RRT*、Informed RRT*、FMT* 更快找到更好的解。OMPL 已内置 BIT*，后续还有 ABIT*、AIT*、EIT* 等变体。

例子给 7 自由度机械臂规划绕过货架隔板的路径时，可在 OMPL 里把规划器从 RRTConnect 换成 BITstar：前者只求尽快找到一条能用的路径，后者在给定时间内持续把路径缩短。

也叫

批量知情树、BITstar

相关

Informed RRT*、快速扩展随机树、A* 算法、基于采样的规划、概率完备性、OMPL

来源

Gammell, Srinivasa, Barfoot. Batch Informed Trees (BIT*) (arXiv:1405.5848, ICRA 2015)
OMPL: ompl::geometric::BITstar Class Reference