Heuristic Search in Cyclic AND/OR Graphs

Eric A. Hansen and Shlomo Zilberstein. Heuristic Search in Cyclic AND/OR Graphs. Proceedings of the Fifteenth National Conference on Artificial Intelligence (AAAI), 412-418, Madison, Wisconsin, 1998.

Abstract

Heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree or an acyclic graph (AO*). We present a novel generalization 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 evaluating the entire state space, giving it an advantage over dynamic-programming algorithms such as policy iteration and value iteration as an approach to stochastic planning.

Bibtex entry:

@inproceedings{HZaaai98,
  author	= {Eric A. Hansen and Shlomo Zilberstein},
  title		= {Heuristic Search in Cyclic {AND/OR} Graphs},
  booktitle     = {Proceedings of the Fifteenth National Conference on Artificial
                   Intelligence},
  year		= {1998},
  pages		= {412-418},
  address       = {Madison, Wisconsin},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/HZaaai98.html}
}

shlomo@cs.umass.edu