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.

本文提出一种名为 IBBT 算法的运动规划算法，该算法利用启发式算法，将随机运动规划问题划分为确定性运动规划问题和图搜索问题，并交替进行批量状态采样、路径规划和启发式搜索，以找到满足信念空间运动规划的最优解。实验表明，IBBT 算法在不同规划环境中具有更快的运行速度和更好的性能。