Learning Depth-First Search: A Unified Approach to Heuristic Search in Deterministic and Non-Deterministic Settings, and its application to MDPs. Bonet, Geffner. ICAPS 2006

  1. Introduces a framework, Learning Depth-First Search.
    1. Naturally reduces to some existing algorithms, like IDA*, and MTD
    2. Yields some new algorithms
  2. “The LDFS framework is built around two simple notions: depth-first search and learning in the sense of…[Barto, Bradtke & Singh], where state values are updated to make them consistent with the values of their successors.”
  3. The LDFS framework shows that one of the main ideas behind most search algorithms is “the use of iterated depth-first searches with memory” for improving the accuracy of the value estimates for states until one is found that is optimal
  4. By coming up with a framework that easily allows algorithms to be recognized as a variant of some other algorithm, it becomes easier to infer what strengths and weaknesses an algorithm may have
  5. The framework relates IDA* to use in game tree search which relates it closely to MTD
  6. And/Or graphs?
  7. Framework functions in deterministic/stochastic, cyclic/acyclic, trees/game trees/andor trees
  8. As expected, values are not discounted, doing cost minimization
  9. Some algorithms require that the goal state be reachable from all other states with probability nonzero
  10. The assume that a heuristic value function exists that is a monotone lower bound (in our speak, upper bound for reward maximization), which means the heuristic is admissible
  11. Frame algorithms in terms of “find and revise,” where a node is selected for expansion by some method, and then value estimates are updated based on that expansion
    1. An algorithm is called Find-and-Revise[epsilon] if after each iteration of the algorithm, it either returns a state reachable from the start state with residual less than epsilon, or proves that no state with that property exists (that hasnt already been expanded?) and terminates
  12. They dont care about cycles as long as the cycles are not part of the solution

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 )

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: