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

(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 scala-bility of sampling-based algorithms, such as Rapidly-exploring Random Trees (RRT). BIT * uses a heuristic to efficiently search a series of in-creasingly dense implicit RGGs while reusing previous infor-mation. 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 R2 and R8 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 conver-gence towards the optimum, especially in high dimensions. I