LAO*: A Heuristic Search Algorithm that Finds Solutions with Loops

Eric A. Hansen and Shlomo Zilberstein. LAO*: A Heuristic Search Algorithm that Finds Solutions with Loops. Artificial Intelligence, 129(1-2):35-62, 2001.

Abstract

Classic heuristic search algorithms can find solutions that take the form of a simple path (A*), a tree, or an acyclic graph (AO*). In this paper, we describe a novel generalization of heuristic search, called LAO*, that can find solutions with loops. We show that LAO* can be used to solve Markov decision problems and that it shares the advantage heuristic search has over dynamic programming for other classes of problems: given a start state, it can find an optimal solution without evaluating the entire state space.

Bibtex entry:

@article{HZaij01b,
  author	= {Eric A. Hansen and Shlomo Zilberstein},
  title		= {{LAO}*: A Heuristic Search Algorithm that Finds Solutions with Loops},
  journal	= {Artificial Intelligence},
  volume	= {129},
  number	= {1-2},
  year		= {2001},
  pages		= {35-62},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/HZaij01b.html}
}

shlomo@cs.umass.edu