Batch Informed Trees (BIT*)

Source Code

BIT* is now part of the Open Motion Planning Library (OMPL). You can find details on how to download and install OMPL on their website.

Description

Batch Informed Trees (BIT*) is an anytime optimal sampling-based planner that uses the principles of dynamic programming to search the implicit random geometric graph (RGG) given by batches of samples drawn from the problem domain. To do this efficiently, it uses a heuristic much like A* to prioritize both expansion towards the goal and high-quality paths. Experimental results show that it outperforms existing optimal sampling-based planning algorithms (e.g., RRT*, FMT*) in terms of computational cost to find equivalent results while still providing an anytime solution.

Publications

  1. J. D. Gammell, T. D. Barfoot, S. S. Srinivasa. “Batch Informed Trees (BIT*): Informed asymptotically optimal anytime search.” The International Journal of Robotics Research (IJRR), 39(5): 543–567, Apr. 2020.
  2. J. D. Gammell. “Informed anytime search for continuous planning problems.” Ph.D. thesis, University of Toronto, Feb. 2017. 2017 CIPPRS Doctoral Dissertation Award.
  3. J. D. Gammell, S. S. Srinivasa, T. D. Barfoot. “Batch Informed Trees (BIT*): Sampling-based optimal planning via the heuristically guided search of implicit random geometric graphs.” in Proceedings of the IEEE international conference on robotics and automation (ICRA), pp. 3067–3074, Seattle, WA, USA, 26–30 May 2015.