A Space-Time Tradeoff for Memory-Based Heuristics

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Scheduling

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.