AAAI Publications, Third Annual Symposium on Combinatorial Search

Font Size: 
On Transposition Tables for Single-Agent Search and Planning: Summary of Results
Yuima Akagi, Akihiro Kishimoto, Alex Fukunaga

Last modified: 2010-08-25


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.


IDA*; transposition table; admissibility; completeness

Full Text: PDF