LAO∗: A heuristic search algorithm that finds solutions with loops

AbstractClassic 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