How to Use Limited Memory in Heuristic Search

Abstract

Traditional best-first search for optimal solutions quickly runs out of space even for problem instances of moderate size, and linearspace search has unnecessarily long running times since it cannot make use of available memory. For using available memory effectively, we developed a new generic approach to heuristie search. It integrates various strategies and includes ideas from bidirectional search. Due to insights into different utilizations of available memory, it allows the search to use limited memory effectively. Instantiations of this approach for two different benchmark domains showed excellent results that are statistically significant improvements over previously reported results: for finding optimal solutions in the 15-Puzzle we achieved the fastest searches of all those using the Manhattan distance heuristic as the only knowledge source, and for a scheduling domain our approach can solve much more difficult problems than the best competitor. The most important lessons we learned from the experiments are first, that also in domains with symmetric graph topology selecting the right search direction can be very important, and second, that memory can— under certain conditions—be used much more effectively than by traditional best-first search. 1