On Transposition Tables for Single-Agent Search and Planning: Summary of Results

Proceedings of the International Symposium on Combinatorial Search, 3

Volume

Vol. 3 No. 1 (2010): Third Annual Symposium on Combinatorial Search

Oral Presentations

Transposition tables are a well-known method for pruning duplicates in heuristic search. This paper presents a detailed analysis of transposition tables for IDA*. We show that some straightforward implementations of IDA* with transposition tables (IDA*+TT) can result in suboptimal solutions being returned. Furthermore, straightforward implementations of IDA*+TT are not complete. We identify several variants of IDA*+TT which are guaranteed to return the optimal solution, as well as a complete variant. An empirical study shows that IDA*+TT can significantly improve upon the performance of A* in domain-independent planning.

10.1609/socs.v1i1.18164