Not Logged In

Hierarchical A*: Searching Abstraction Hierarchies Efficiently

Abstraction, in search, problem solving, and planning, works by replacing one state space by another (the ?abstract' space) that is easier to search. The results of the search in the abstract 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 newabstraction­induced search technique, 'Hierarchical A*,' that gets around both of these difficulties: first, by drawing from adifferent class of abstractions, 'homomorphism abstractions,' and, secondly,by using novelcaching 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.

Citation

R. Holte, F. Peng, R. Zimmer, A. MacDonald. "Hierarchical A*: Searching Abstraction Hierarchies Efficiently". National Conference on Artificial Intelligence (AAAI), Portland, Oregon, January 1996.

Keywords: abstraction, machine learning
Category: In Conference

BibTeX

@incollection{Holte+al:AAAI96,
  author = {Robert Holte and Fuchun Peng and Robert Zimmer and Alan J.
    MacDonald},
  title = {Hierarchical A*: Searching Abstraction Hierarchies Efficiently},
  booktitle = {National Conference on Artificial Intelligence (AAAI)},
  year = 1996,
}

Last Updated: August 13, 2007
Submitted by Russ Greiner

University of Alberta Logo AICML Logo