# Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Jul 2017.

## Built on by (most cited first, 23 of 23)

- [Motion Planning Diffusion: Learning and Adapting Robot Motion Planning with Diffusion Models](https://mlsanity.com/paper/2412.19948/) (2024)
- [Motion Planning by Learning the Solution Manifold in Trajectory Optimization](https://mlsanity.com/paper/2107.05842/) (2021)
- [PLAYER*: Enhancing LLM-based Multi-Agent Communication and Interaction in Murder Mystery Games](https://mlsanity.com/paper/2404.17662/) (2024)
- [Fast Kinodynamic Planning on the Constraint Manifold with Deep Neural Networks](https://mlsanity.com/paper/2301.04330/) (2023)
- [Reaching Through Latent Space: From Joint Statistics to Path Planning in Manipulation](https://mlsanity.com/paper/2210.11779/) (2022)
- [A Survey on the Integration of Machine Learning with Sampling-based Motion Planning](https://mlsanity.com/paper/2211.08368/) (2022)
- [GSON: A Group-based Social Navigation Framework with Large Multimodal Model](https://mlsanity.com/paper/2409.18084/) (2024)
- [Leveraging Scene Embeddings for Gradient-Based Motion Planning in Latent Space](https://mlsanity.com/paper/2303.03364/) (2023)
- [Neural Potential Field for Obstacle-Aware Local Motion Planning](https://mlsanity.com/paper/2310.16362/) (2023)
- [Real-time goal recognition using approximations in Euclidean space](https://mlsanity.com/paper/2307.07876/) (2023)
- [Speeding up deep neural network-based planning of local car maneuvers via efficient B-spline path construction](https://mlsanity.com/paper/2203.06963/) (2022)
- [Robot Motion Planning as Video Prediction: A Spatio-Temporal Neural Network-based Motion Planner](https://mlsanity.com/paper/2208.11287/) (2022)
- [Global Tensor Motion Planning](https://mlsanity.com/paper/2411.19393/) (2024)
- [Toward Generalist Neural Motion Planners for Robotic Manipulators: Challenges and Opportunities](https://mlsanity.com/paper/2603.24318/) (2026)
- [Flow Motion Policy: Manipulator Motion Planning with Flow Matching Models](https://mlsanity.com/paper/2604.07084/) (2026)
- [IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty](https://mlsanity.com/paper/2304.10984/) (2023)
- [LEA*: An A* Variant Algorithm with Improved Edge Efficiency for Robot Motion Planning](https://mlsanity.com/paper/2309.10722/) (2023)
- [Fast End-to-End Generation of Belief Space Paths for Minimum Sensing Navigation](https://mlsanity.com/paper/2409.12902/) (2024)
- [Real-Time Adaptive Motion Planning via Point Cloud-Guided, Energy-Based Diffusion and Potential Fields](https://mlsanity.com/paper/2507.09383/) (2025)
- [Referring-Aware Visuomotor Policy Learning for Closed-Loop Manipulation](https://mlsanity.com/paper/2604.05544/) (2026)
- [Optimal any-angle path planning in static and dynamic environments](https://mlsanity.com/paper/2607.00065/) (2026)
- [ELMP: Efficient Learning for Motion Planning via Analytical Policy Gradients](https://mlsanity.com/paper/2607.00215/) (2026)
- [Conflict-Based Lazy Search for Fast Multi-Manipulator Planning](https://mlsanity.com/paper/2607.04124/) (2026)

## Abstract (arXiv)

Path planning in robotics often requires finding high-quality solutions to continuously valued and/or high-dimensional problems. These problems are challenging and most planning algorithms instead solve simplified approximations. Popular approximations include graphs and random samples, as respectively used by informed graph-based searches and anytime sampling-based planners. Informed graph-based searches, such as A*, traditionally use heuristics to search a priori graphs in order of potential solution quality. This makes their search efficient but leaves their performance dependent on the chosen approximation. If its resolution is too low then they may not find a (suitable) solution but if it is too high then they may take a prohibitively long time to do so. Anytime sampling-based planners, such as RRT*, traditionally use random sampling to approximate the problem domain incrementally. This allows them to increase resolution until a suitable solution is found but makes their search dependent on the order of approximation. Arbitrary sequences of random samples approximate the problem domain in every direction simultaneously and but may be prohibitively inefficient at containing a solution. This paper unifies and extends these two approaches to develop Batch Informed Trees (BIT*), an informed, anytime sampling-based planner. BIT* solves continuous path planning problems efficiently by using sampling and heuristics to alternately approximate and search the problem domain. Its search is ordered by potential solution quality, as in A*, and its approximation improves indefinitely with additional computational time, as in RRT*. It is shown analytically to be almost-surely asymptotically optimal and experimentally to outperform existing sampling-based planners, especially on high-dimensional planning problems.