# IBBT: Informed Batch Belief Trees for Motion Planning Under Uncertainty

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 39 references that are in the map.
- First posted on arXiv 21 Apr 2023.

## Builds on (most cited first, 12 of 12)

- [DESPOT: Online POMDP Planning with Regularization](https://mlsanity.com/paper/1609.03250/) (2016)
- [Fast Marching Tree: a Fast Marching Sampling-Based Method for Optimal Motion Planning in Many Dimensions](https://mlsanity.com/paper/1306.3532/) (2013)
- [Batch Informed Trees (BIT*): Informed Asymptotically Optimal Anytime Search](https://mlsanity.com/paper/1707.01888/) (2017)
- [Monte Carlo Motion Planning for Robot Trajectory Optimization Under Uncertainty](https://mlsanity.com/paper/1504.08053/) (2015)
- [Belief Space Planning: A Covariance Steering Approach](https://mlsanity.com/paper/2105.11092/) (2021)
- [Uncertainty-Constrained Differential Dynamic Programming in Belief Space for Vision Based Robots](https://mlsanity.com/paper/2012.00218/) (2020)
- [Belief Space Planning for Mobile Robots with Range Sensors using iLQG](https://mlsanity.com/paper/2102.05466/) (2021)
- [Risk-Averse RRT* Planning with Nonlinear Steering and Tracking Controllers for Nonlinear Robotic Systems Under Uncertainty](https://mlsanity.com/paper/2103.05572/) (2021)
- [Gaussian Belief Space Path Planning for Minimum Sensing Navigation](https://mlsanity.com/paper/2109.13976/) (2021)
- [Gaussian Belief Trees for Chance Constrained Asymptotically Optimal Motion Planning](https://mlsanity.com/paper/2202.12407/) (2022)
- [Real-Time Stochastic Kinodynamic Motion Planning via Multiobjective Search on GPUs](https://mlsanity.com/paper/1607.06886/) (2016)
- [Moment State Dynamical Systems for Nonlinear Chance-Constrained Motion Planning](https://mlsanity.com/paper/2003.10379/) (2020)

## Abstract (arXiv)

In this work, we propose the Informed Batch Belief Trees (IBBT) algorithm for motion planning under motion and sensing uncertainties. The original stochastic motion planning problem is divided into a deterministic motion planning problem and a graph search problem. We solve the deterministic planning problem using sampling-based methods such as PRM or RRG to construct a graph of nominal trajectories. Then, an informed cost-to-go heuristic for the original problem is computed based on the nominal trajectory graph. Finally, we grow a belief tree by searching over the graph using the proposed heuristic. IBBT interleaves between batch state sampling, nominal trajectory graph construction, heuristic computing, and search over the graph to find belief space motion plans. IBBT is an anytime, incremental algorithm. With an increasing number of batches of samples added to the graph, the algorithm finds motion plans that converge to the optimal one. IBBT is efficient by reusing results between sequential iterations. The belief tree searching is an ordered search guided by an informed heuristic. We test IBBT in different planning environments. Our numerical investigation confirms that IBBT finds non-trivial motion plans and is faster compared with previous similar methods.