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 pathlength, 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 samplerejection technique will limit the probability of improvement at each iteration to ~8%, while direct sampling imposes no such limit.
Publications


J. D. Gammell, S. S. Srinivasa, T. D. Barfoot. “Informed RRT*: Optimal samplingbased 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.