LAO*: A heuristic search algorithm that finds solutions with loops. Hansen, Zilberstein

  1. A* tries to simply find a path, another solution could be in the form of a tree.  AO* finds a solution in the form of an acyclic graph/tree (specifically discuss and/or trees).  This is a conditional structure
  2. LAO* can find solutions in the form of graphs with with loops
  3. Claims it “shares the advantage heuristic search has over dynamic programming… Given a start state, it can find an optimal solution w/o evaluating the entire state space”
  4. Loops are relevant for finding policies in stochastic MDPs where an action can take you back to a state visited previously.  They are concerned with stochastic shortest-path problems (has terminal states)
  5. Under certain conditions A* evaluates the minimum number of states, same for AO*
  6. Discusses Trial-based RTDP, since it only performs computation on encountered states, it can avoid doing computation of entire MDP.
  7. Check out convergence theorem from LRTA* (learning real-time A*)
  8. AO* can be made more efficient by adding “solve-labeling.”  A state is labeled solved if it is a goal state, or if all children are solved.  This is similar to what FS^3 does.
  9. Proofs of admissibility, correctness
  10. They call doing backwards bellman backups from the goal to the start pruning by dominance.  They also call using bounds to prune the search tree/graph forward “pruning by bounds” (branch and bound)
  11. AO* uses branch and bound in its forward expansion step and dynamic programing for cost-revision
  12. The trick in allowing AO* to work in cyclic domains (making it LAO*) is to note that since a value function is being computed, other methods such as VI can be used in place of pure backwards induction
    1. It must be the case that when they query for an s,a they get all of T(s,a) and not just s’ because they dont really discuss resampling – not sure.
  13. Pretty simple proofs of admissibility and correctness
  14. RTDP was proved to converge to optimal, but there is no convergence test  or error bound for the algorithm, they state the proofs for LAO* for these can be adapted to RTDP
  15. Discuss consistency h(i) <= ci(a)+h(j) for next state j, as desirable because it ensures state costs increas monotonically as the algorithm converges.  If a nonconsistent (but admissible) heuristic is used, a pathmax trick can make it behave in a consistent manner (works in A*, AO*, LAO*).
  16. Discuss weighting heuristic, which weights the cost observed versus the heuristic cost (in the original formulation, both costs are 1).  Its possible to bound by how much the found solution is different from optimal.
  17. In A* if two heuristic functions are used s.t. h1(i)<=h2(i)<=f*(i), the set of nodes examined when following h2 is a subset of those followed when exploring h1.  This isn’t true necessarily in AO*/LAO*, but holds in terms of worst-case sets of states
  18. LAO* can be used in MDPs without terminal states by adding discount factor
  19. Analyze LAO* performance on racetrack and a supply-chain management problem.
    1. In racetrack, performance of LAO* in zero-heuristic case is basically the same as VI, PI takes too long to finish.  Giving a good heuristic allows LAO* to finish in 1/3 the time, using weighting helps even more
    2. They use tricks to improve performance of LAO* because otherwise it is quite poor, one thing is analyzing all vertices from an edge at the same time instead of one at a time, most of the cost is from running VI
    3. Show convergence as faster than RTDP.
  20. It would be interesting to see performance of LAO* vs prioritized sweeping

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: