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. (Korf97) conjectures that for A* search using memory-based heuristics m*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 memory-based heuristics and use this to test Korf’s conjecture in a large-scale experiment. The results strongly support Korf’s conjecture.
Registration: ISBN 978-0-262-51106-3
Copyright: July 18-22, 1999, Orlando, Florida. Published by The AAAI Press, Menlo Park, California.