Experiments with automatically created memory-based heuristics

Abstract. A memory-based heuristic is a function, h(s), stored in the form of a lookup table: h(s) is computed by mapping s to an index and then retrieving the corresponding entry in the table. In this paper we present a notation for describing state spaces, PSVN, and a method for automatically creating memory-based heuristics for a state space by abstracting its PSVN description. Two investigations of these automatically generated heuristics are presented. First, thousands of automatically generated heuristics are used to experimentally investigate the conjecture by Korf [4] that m·t is a constant, where m is the size of a heuristic’s lookup table and t is the number of nodes expanded when the heuristic is used to guide search. Second, a similar large-scale experiment is used to verify that the Korf and Reid’s complexity analysis [5] can be used to rapidly and reliably choose the best among a given set of heuristics.