A Space-Time Tradeoff for Memory-Based Heuristics

Abstract

A memory-based heuristic is a function, h(s), stored in the form of a lookup table (pattern database): h(s) is computed by mapping s to an index and then retrieving the appropriate entry in the table. (Korf 1997) conjectures for search using memory-based heuristics that m \\Delta t is a constant, where m is the size of the heuristic's lookup table and t is search time. In this paper we present a method for automatically generating memorybased heuristics and use this to test Korf's conjecture in a large-scale experiment. Our results confirm that there is a direct relationship between m and t. Introduction A heuristic is a function, h(s), that computes an estimate of the distance from state s to a goal state. In a memory-based heuristic this computation consists of mapping s to an index which is then used to look up h(s) in a table. Even heuristics that have a normal functional definition are often precomputed and stored in a lookup table in order to speed up search ((Priedi...