Iterative Bounding LAO*. Hakan Warnquist, Jonas Kvarnstrom, Patrick Doherty. ECAI 2010

  1. Seems similar to FS3 because it uses an upper and lower heuristic to prune extensively
  2. An epsilon-optimal planning algorithm for probabilistic domains where objective is to reach a goal state with minimum cost
  3.  Based on LAO*, comparison to RTDP
  4. Is an on-line method, which maintains provably good bounds over time
  5. They mention other algs that use upper and lower bounds, mainly RTDP and variants.  I forgot RTDP used bounds in that manner.
  6. One issue with RTDP is that it will continue to attempt value function updates for states that have converged values, which is wasteful. Its later variants use upper and lower bounds to prevent this from happening.
  7. the AO in LAO* comes from And/Or graphs
  8. LAO* fixes AO* so that it functions in acyclic graphs
    1. Does so by transforming graph into a tree, it seems
  9. LAO* functions in cyclic domains by performing value iteration instead of regular backups from leaf to root
  10. IB-LAO* doesn’t perform full VI, but instead does one backup of all ancestors of states that are newly expanded, so its like one iteration of VI
  11. LAO* is not rollout-based (like RTDP) and therefore keeps track of a fringe that must be expanded.  Since the fringe can get very large, it is best to expand only a subset of the fringe, prioritized based on which nodes can maximally influence the root.  The computation is done with other fringe operations and doesn’t increase the computational cost.
  12. Discussion includes addition of weighted heuristics, this makes heuristics inadmissible, but helps to find a solution in most real-world cases
    1. Looks like it is possible to adjust the weights while maintaining epsilon-optimality?  Thats interesting.
  13. Use two comparison domains because one has low, one high branching factor

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: