Heuristic search in cyclic AND/OR graphs
Eric A. Hansen, Shlomo Zilberstein · 1998
Heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree or acyclic graph (AO*). We present a novel generaliza-tion of heuristic search (called LAO*) that can find solutions with loops, that is, solutions that take the form of a cyclic graph. We show that it can be used to solve Markov decision problems without evaluat-ing the entire state space, giving it an advantage over dynamic-programming al orithms such as policy iter-ation and value iteration as an approach to stochastic planning.