Anytime Heuristic Search: First Results

Eric A. Hansen, Shlomo Zilberstein, and Victor A. Danilchenko. Anytime Heuristic Search: First Results. Technical Report 97-50, Computer Science Department, University of Massachusetts Amherst, 1997.

Abstract

We describe a simple technique for converting heuristic search algorithms into anytime algorithms that offer a tradeoff between search time and solution quality. The technique is related to work on use of non-admissible evaluation functions that make it possible to find good, but possibly sub-optimal, solutions more quickly than it takes to find an optimal solution. Instead of stopping the search after the first solution is found, however, we continue the search in order to find a sequence of improved solutions that eventually converges to an optimal solution. The performance of anytime heuristic search depends on the non-admissible evaluation function that guides the search. We discuss how to design a search heuristic that "optimizes" the rate at which the currently available solution improves.

Bibtex entry:

@techreport{HZDtr9750,
  author	= {Eric A. Hansen and Shlomo Zilberstein and Victor A. Danilchenko},
  title         = {Anytime Heuristic Search: First Results},
  year          = {1997},
  number        = {97-50},
  institution   = {Computer Science Department, University of Massachussetts Amherst},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/HZDtr9750.html}
}

shlomo@cs.umass.edu