Seminar: Robert Holte, "Multimapping Abstractions and Hierarchical Heuristic Search," Monday, April 1, 10:30 am, ED 209 (Expired)

Dr. Robert C. Holte
Professor of Computing Science and Vice Dean of Science
University of Alberta

Multimapping Abstractions and Hierarchical Heuristic Search

Monday, April 1, 10:30 am

ED 209

Heuristic state-space search algorithms, such as A* and IDA*,
are guided by a heuristic function, h(s), which estimates the cost
to reach the goal state from state s.  Many of the most powerful
heuristics these days are created by abstracting the given state
space to create another state space (the "abstract state space")
in which the cost to reach the abstract goal from a given abstract
state can be quickly computed.  Given an abstraction function
ABS, h(s) is defined to be the exact cost to reach ABS(goal) from
ABS(s).  This presentation will begin by describing these ideas.

The presentation will then introduce a new kind of abstraction,
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.

Breaking News

Recent News

Do You Have News for the Department of Computer Science?

  • Please send a plain text version of your posting, which can include URL links, to
To Top of Page