Multimapping Abstractions and Hierarchical Heuristic Search

Proceedings of the International Symposium on Combinatorial Search, 5

Volume

Vol. 5 No. 1 (2012): Fifth Annual Symposium on Combinatorial Search

Full Papers

In this paper we introduce a broadly applicable method, called multimapping abstraction, that allows multiple heuristic values for a state to be extracted from one abstract state space. The key idea is to define an abstraction to be a multimapping, i.e., a function that maps a state in the original state space to a set of states in the abstract space. We performed a large-scale experiment on several benchmark state spaces to compare the memory requirements and runtime of Hierarchical IDA* (HIDA*) using multimapping domain abstractions to HIDA* with individual domain abstractions and to HIDA* with multiple, independent domain abstractions. Our results show that multimapping domain abstractions are superior to both alternatives in terms of both memory usage and runtime.

10.1609/socs.v3i1.18234