Batch Informed Trees

A planning algorithm that samples points in batches and searches them in a heuristic order to converge on an optimal path.

BIT* (Batch Informed Trees) is a sampling-based motion planning algorithm by Gammell, Srinivasa, and Barfoot, published at ICRA 2015 with a complete version in IJRR in 2020. Where RRT*-family algorithms grow a tree one random point at a time, BIT* samples a whole batch at once, treats them as an implicit random geometric graph (edges aren't pre-connected — collision-checked only when needed), and searches it in an A*-like order based on the heuristic ‘how short could a path through this edge possibly be.’ After finding a first solution, it samples the next batch only inside the ellipsoidal region that could still improve the current solution (following Informed RRT*), refining round by round. It can report its best-so-far solution at any time, keeps improving, and is both probabilistically complete and asymptotically optimal; the paper's experiments show it finding better solutions faster than RRT*, Informed RRT*, and FMT*, especially in high dimensions. OMPL already includes BIT*, and later variants include ABIT*, AIT*, and EIT*.

ExamplePlanning a path for a 7-DOF arm around a shelf's dividers, one can swap the OMPL planner from RRTConnect to BITstar: the former just wants a usable path as fast as possible, while the latter keeps shortening the path within the given time budget.

Also called

BIT*, BITstar

Related

Informed RRT* (Informed Sampling) · Rapidly-exploring Random Tree · A* Search · Sampling-Based Planning · Probabilistic Completeness · Open Motion Planning Library (OMPL)

Sources

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