Informed RRT*

Source Code

Informed RRT* 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

Informed RRT* is an improvement to the RRT* algorithm that increases the rate at which the found solution converges to the optimum. Developed specifically for problems seeking to minimize path-length, this work uses a method to directly sample the subset of a planning problem that contains all possible improvements to a given solution. In doing so, it continues to consider all relevant paths without requiring any additional parameters.

This direct informed sampling is actually required to generally solve the planning problem, as the probability of improving a given solution goes to zero as the size of the problem domain, or the number of dimensions, increases. For a 6DOF arm, even an intelligent sample-rejection technique will limit the probability of improvement at each iteration to ~8%, while direct sampling imposes no such limit.

Publications

  1. J. D. Gammell, T. D. Barfoot, S. S. Srinivasa. “Informed sampling for asymptotically optimal path planning.” IEEE Transactions on Robotics (T-RO), 34(4): 966–984, Aug. 2018.
  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. “Informed RRT*: Optimal sampling-based path planning focused via direct sampling of an admissible ellipsoidal heuristic.” in Proceedings of the IEEE/RSJ international conference on intelligent robots and systems (IROS), pp. 2997–3004, Chicago, IL, USA, 14–18 Sep. 2014.