# Batch Informed Trees (BIT*): Sampling-based Optimal Planning via the Heuristically Guided Search of Implicit Random Geometric Graphs

arXiv: https://arxiv.org/abs/1405.5848 · HTML: https://mlsanity.com/paper/1405.5848/

## Key facts

- Cited by 39 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 May 2014.

## Built on by (most cited first, 30 of 39)

- [Habitat 2.0: Training Home Assistants to Rearrange their Habitat](https://mlsanity.com/paper/2106.14405/) (2021)
- [RoboGen: Towards Unleashing Infinite Data for Automated Robot Learning via Generative Simulation](https://mlsanity.com/paper/2311.01455/) (2023)
- [Toward General-Purpose Robots via Foundation Models: A Survey and Meta-Analysis](https://mlsanity.com/paper/2312.08782/) (2023)
- [Motion Policy Networks](https://mlsanity.com/paper/2210.12209/) (2022)
- [Potential Based Diffusion Motion Planning](https://mlsanity.com/paper/2407.06169/) (2024)
- [Goal-conditioned dual-action imitation learning for dexterous dual-arm robot manipulation](https://mlsanity.com/paper/2203.09749/) (2022)
- [NTFields: Neural Time Fields for Physics-Informed Robot Motion Planning](https://mlsanity.com/paper/2210.00120/) (2022)
- [Neural MP: A Generalist Neural Motion Planner](https://mlsanity.com/paper/2409.05864/) (2024)
- [Hazards in Daily Life? Enabling Robots to Proactively Detect and Resolve Anomalies](https://mlsanity.com/paper/2411.00781/) (2024)
- [CabiNet: Scaling Neural Collision Detection for Object Rearrangement with Procedural Scene Generation](https://mlsanity.com/paper/2304.09302/) (2023)
- [High-Speed Accurate Robot Control using Learned Forward Kinodynamics and Non-linear Least Squares Optimization](https://mlsanity.com/paper/2206.08487/) (2022)
- [ArticuBot: Learning Universal Articulated Object Manipulation Policy via Large Scale Simulation](https://mlsanity.com/paper/2503.03045/) (2025)
- [Motion Planning Transformers: A Motion Planning Framework for Mobile Robots](https://mlsanity.com/paper/2106.02791/) (2021)
- [Fast Kinodynamic Planning on the Constraint Manifold with Deep Neural Networks](https://mlsanity.com/paper/2301.04330/) (2023)
- [Deep Reactive Policy: Learning Reactive Manipulator Motion Planning for Dynamic Environments](https://mlsanity.com/paper/2509.06953/) (2025)
- [Learning Sampling Dictionaries for Efficient and Generalizable Robot Motion Planning with Transformers](https://mlsanity.com/paper/2306.00851/) (2023)
- [USA-Net: Unified Semantic and Affordance Representations for Robot Memory](https://mlsanity.com/paper/2304.12164/) (2023)
- [CVaR-based Flight Energy Risk Assessment for Multirotor UAVs using a Deep Energy Model](https://mlsanity.com/paper/2105.15189/) (2021)
- [Learning Forward Dynamics Model and Informed Trajectory Sampler for Safe Quadruped Navigation](https://mlsanity.com/paper/2204.08647/) (2022)
- [Recent Advancements in Deep Learning Applications and Methods for Autonomous Navigation: A Comprehensive Review](https://mlsanity.com/paper/2302.11089/) (2023)
- [Physics-informed Temporal Difference Metric Learning for Robot Motion Planning](https://mlsanity.com/paper/2505.05691/) (2025)
- [HDPlanner: Advancing Autonomous Deployments in Unknown Environments through Hierarchical Decision Networks](https://mlsanity.com/paper/2408.03768/) (2024)
- [Waypoint Planning Networks](https://mlsanity.com/paper/2105.00312/) (2021)
- [Cascaded Diffusion Models for Neural Motion Planning](https://mlsanity.com/paper/2505.15157/) (2025)
- [Warm-Starting Optimization-Based Motion Planning for Robotic Manipulators via Point Cloud-Conditioned Flow Matching](https://mlsanity.com/paper/2510.03460/) (2025)
- [Real-Time Verification of Embodied Reasoning for Generative Skill Acquisition](https://mlsanity.com/paper/2505.11175/) (2025)
- [CoverLib: Classifiers-equipped Experience Library by Iterative Problem Distribution Coverage Maximization for Domain-tuned Motion Planning](https://mlsanity.com/paper/2405.02968/) (2024)
- [aUToPath: Unified Planning and Control for Autonomous Vehicles in Urban Environments Using Hybrid Lattice and Free-Space Search](https://mlsanity.com/paper/2505.09475/) (2025)
- [Contrastive Diffusion Guidance for Spatial Inverse Problems](https://mlsanity.com/paper/2509.26489/) (2025)
- [Informed Steiner Trees: Sampling and Pruning for Multi-Goal Path Finding in High Dimensions](https://mlsanity.com/paper/2205.04548/) (2022)

## Abstract (arXiv)

In this paper, we present Batch Informed Trees (BIT*), a planning algorithm based on unifying graph- and sampling-based planning techniques. By recognizing that a set of samples describes an implicit random geometric graph (RGG), we are able to combine the efficient ordered nature of graph-based techniques, such as A*, with the anytime scalability of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT). BIT* uses a heuristic to efficiently search a series of increasingly dense implicit RGGs while reusing previous information. It can be viewed as an extension of incremental graph-search techniques, such as Lifelong Planning A* (LPA*), to continuous problem domains as well as a generalization of existing sampling-based optimal planners. It is shown that it is probabilistically complete and asymptotically optimal. We demonstrate the utility of BIT* on simulated random worlds in ℝ2 and ℝ8 and manipulation problems on CMU's HERB, a 14-DOF two-armed robot. On these problems, BIT* finds better solutions faster than RRT, RRT*, Informed RRT*, and Fast Marching Trees (FMT*) with faster anytime convergence towards the optimum, especially in high dimensions.