BIT*: Batch informed trees for optimal sampling-based planning via dynamic programming on implicit random geometric graphs

Abstract — Discrete and sampling-based methods have tradi-tionally been popular techniques for path planning in contin-uous spaces. Discrete techniques use the principles of dynamic programming to solve a discretized approximation of the problem, while sampling-based techniques use random samples to perform a stochastic search on the continuous state space. In this paper, we use the fact that stochastic planners can be viewed as a search of an implicit random geometric graph (RGG) to propose a general class of planners named Bellman Random Trees (BRT) and derive an anytime optimal sampling-based algorithm, Batch Informed Trees (BIT*). BIT * searches for a solution to the continuous planning problem by efficiently building and searching a series of implicit RGGs in a principled manner. In doing so, it strikes a balance between the advantages of discrete methods and sampling-based planners. By using the implicit RGG representation, defined as set of random samples and successor function, BIT * is able to scale more effectively to high dimensions than other optimal sampling-based planners. By using heuristics and intelligently reusing existing connections, like discrete lifelong planning algorithms, BIT * is able to focus its search in a principled and efficient manner. In simulations, we show that BIT * consistently outperforms optimal RRT (RRT*), Informed RRT * and Fast Marching Trees (FMT*) on random-world problems in R2 and R8. We also present preliminary theoretical analysis demonstrating that BIT * is probabilistically complete and asymptotically optimal and conjecture that it may be optimally efficient under some probabilistic conditions. I