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

Seems similar to FS3 because it uses an upper and lower heuristic to prune extensively

An epsilon-optimal planning algorithm for probabilistic domains where objective is to reach a goal state with minimum cost

Based on LAO*, comparison to RTDP

Is an on-line method, which maintains provably good bounds over time

They mention other algs that use upper and lower bounds, mainly RTDP and variants. I forgot RTDP used bounds in that manner.

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.

the AO in LAO* comes from And/Or graphs

LAO* fixes AO* so that it functions in acyclic graphs

Does so by transforming graph into a tree, it seems

LAO* functions in cyclic domains by performing value iteration instead of regular backups from leaf to root

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

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.

Discussion includes addition of weighted heuristics, this makes heuristics inadmissible, but helps to find a solution in most real-world cases

Looks like it is possible to adjust the weights while maintaining epsilon-optimality? Thats interesting.

Use two comparison domains because one has low, one high branching factor

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here:
Cookie Policy