Iterative-Expansion A*

In this paper we describe an improvement to the popular IDA* search algorithm that emphasizes a different space-for-time trade-off than previously suggested. In particular, our algorithm, called Iterative-Expansion A* (IEA*), focuses on reducing redundant node expansions within individual depth-first search DFS iterations of IDA* by employing a relatively small amount of available memory--bounded by the error in the heuristic--to store selected nodes. The additional memory required is exponential not in the solution depth, but only in the difference between the solution depth and the estimated solution depth. A constant-time hash set lookup can then be used to prune entire subtrees as DFS proceeds. Overall, we show 2- to 26-fold time speedups vs. an optimized version of IDA* across several domains, and compare IEA* with several other competing approaches. We also sketch proofs of optimality and completeness for IEA*, and note that IEA* is particularly efficient for solving implicitly-defined general graph search problems.