Efficient memory-bounded search methods
Stuart Russell · 1992
. Memory-bounded algorithms such as Korf's IDA* and Chakrabarti et al's MA* are designed to overcome the impractical memory requirements of heuristic search algorithms such as A* . It is shown that IDA* is inefficient when the heuristic function can take on a large number of values; this is a consequence of using too little memory. Two new algorithms are developed. The first, SMA*, simplifies and improves upon MA*, making the best use of all available memory. The second, Iterative Expansion (IE), is a simple recursive algorithm that uses linear space and incurs little overhead. Experiments indicate that both algorithms perform well. 1 Introduction This paper adopts the standard framework of heuristic search, in which the object is to find a sequence of operators leading from a given initial state to any goal state. The search is guided by a heuristic function h(n), which estimates the lowest cost of any path from state n to a goal state. Although heuristic search is a well-establish...