LAO A heuristic search algorithm that finds solutions with loops》.pdfVIP

Artificial Intelligence 129 (2001) 35–62 LAO*: A heuristic search algorithm that finds solutions with loops Eric A. Hansen a,∗, Shlomo Zilberstein b a Computer Science Department, Mississippi State University, Mississippi State, MS 39762, USA b Computer Science Department, University of Massachusetts, Amherst, MA 01002, USA Received 15 February 2000; received in revised form 8 March 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.  2001 Elsevier Science B.V. All rights reserved. Keywords: Heuristic search; Dynamic programming; Markov decision problems 1. Introduction One of the most widely-used frameworks for problem-solving in artificial intelligence is state-space search. A state-space search problem is defined by a set of states, a set of actions (or operators) that map states to successor states, a start state, and a set of goal states. The objective is to find a sequence of actions that transforms the start state into a goal state, and also optimizes some measure of the quality of the solution. Two well-known heuristic search algorithms for state-space search problems are A* and AO* [18]. A* finds a solution that takes the form of a sequence of actions leading in a path from the start state to a goal state. AO* finds a solution that has a conditional structure and takes the form of a tree, or more generally, an acycli