Hierarchical A *: searching abstraction hierarchies efficiently

Abstract

Abstraction, in search, problem solving, and planning, works by replacing one state space by space are used to guide search in the original space. A natural application of this technique is to use the length of the abstract solution as a heuristic for A * in searching in the original space. However, there are two obstacles to making this work efficiently. The first is a theorem [Valtorta, 1984] stating that for a large class of abstractions, "embedding abstractions, " every state expanded by blind search must also be expanded by A * when its heuristic is computed in this way. The second obstacle arises because in solving a problem A * needs repeatedly to do a full search of the abstract space while computing its heuristic. This paper introduces a new abstraction-induced search technique, "Hierarchical A*, " that gets around both of these difficulties: first, by drawing from a different class of abstractions, "homomorphism abstractions, " and, secondly, byusing novel caching techniques to avoid repeatedly expanding the same states in successive searches in the abstract space. Hierarchical A * outperforms blind search on all the search spaces studied.