Anytime Motion Planning using the RRT*. Karaman, Walter, Perez, Frazzoli, Teller. ICRA 2011

  1. Paper presents a variant of RRT that interleaves execution of plans and replanning, as opposed to RRT which monolithically plans and then executes
  2. Execution starts with a short planning period, of which at least one path should reach the goal.
  3. The algorithm then chooses some initial segment of this plan to execute, and executes this segment in its entirety.
  4. While executing this segment, it begins replanning with the end of the segment as the next start point
  5. Planning leverages a branch and bound method; esssentially A* down to the fact that it requires admissible heuristics
  6. 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
  7. 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
    1. 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
    2. 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
  8. The algorithm has asymptotic convergence to optimal behavior

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: