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 heuristic search. It integrates various strategies and includes ideas from bidirectional search . Due to insights into differe nt utilizations of available memory, it allows the search to use limited me mory effectively. Instantiations of this approach for two different benchmark domains showed exce ll e nt results that are statistically significant improve ments over previously re ported results: for finding optima l 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 b es t 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 canunder certain conditions- be used much more e ffect iv e ly than by traditional best-first search.