Multimapping Abstractions and Hierarchical Heuristic Search

Abstract

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.