Anytime Motion Planning using the RRT*. Karaman, Walter, Perez, Frazzoli, Teller. ICRA 2011
Paper presents a variant of RRT that interleaves execution of plans and replanning, as opposed to RRT which monolithically plans and then executes
Execution starts with a short planning period, of which at least one path should reach the goal.
The algorithm then chooses some initial segment of this plan to execute, and executes this segment in its entirety.
While executing this segment, it begins replanning with the end of the segment as the next start point
Planning leverages a branch and bound method; esssentially A* down to the fact that it requires admissible heuristics
A major criticism of the paper is the planning domains they use are very simple and could be solved optimally with dead reckoning and very basic obstacle avoidance
They say that regular RRT often will end up finding a suboptimal path and then only performing local optimizations of that bad path instead of finding a whole different, better path
I think the reason RRT* ends up finding less suboptimal paths is because while RRT is doing mostly hillclimbing with few restarts, RRT* has a complete restart at the end of each path segment, so it gets itself out of local optima. They do not present this interpretation but I’m pretty sure it is what is going on
You can see (and they point this out as well) when it starts to do something suboptimal but then catches itself and performs the correction
The algorithm has asymptotic convergence to optimal behavior