LaValle Planning Algorithms Chs 2,3


Various notes I took while reading LaValle’s excellent planning book; what I understood and misunderstood.

  • Sometimes good heuristics for A* are impossible to find
  • BFS doesn’t always give optimal results
  • Iterative deepening is a sort of systematic DFS in that it iteratively deepens search depth It throws out old work, but this is ok as the cost spent on previous generations is small compared to cost of planning in current generation (depth).  Has very low memory requirements
  • Can combine A* and iterative deepening to get an algorithm called IDA*
  • If inverse kinematics are available, can do backwards search.  If both are available can do bidirectional search
  • Dijkstra’s can be recovered from application of VI to deterministic domains
    • Dijkstra’s only “VIs” one state at a time; focuses on where the cost-to-go can change
    • VI is more flexible as it deals with stochasticity
Advertisements
Tagged ,

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s

%d bloggers like this: