Steps Towards the Automatic Creation of Search Heuristics
- Istvan Hernadvolgyi, School of Information Technology and Engineering, University of Ottawa
- Robert Holte, Department of Computing Science, University of Alberta
The long-term goal of our research is to develop robust methods that use ab-
straction to create heuristics automatically from a description of a search space.
Our research has progressed signi cantly towards this goal. This paper reviews the
current state of the art, and the major open problems remaining to be solved.
Pattern databases are the foundation of the approach. The paper describes do-
main abstraction, which extends the notion of pattern' in a way that permits
available memory to be more fully exploited to reduce search time.
The paper demonstrates that a certain easily computed approximation to a for-
mula developed by Korf and Reid [20] is monotonically related to the actual number
of nodes expanded using the pattern database. This involves a large-scale experi-
ment involving all possible domain abstractions for the 8-Puzzle in which the blank
tile remains unique.
The principal remaining obstacle to automatic heuristic creation is shown to
be the diĘculty of predicting or controlling the size of a pattern database. This
diĘculty arises for two reasons, the main one being non-surjectivity': domain
abstractions can create abstract spaces in which some states do not have a pre-
image. The paper identi es two speci c causes of non-surjectivity, related to the
space's orbits and blocks, and illustrates others.
Citation
I. Hernadvolgyi,
R. Holte.
"Steps Towards the Automatic Creation of Search Heuristics". Technical Report, January 2004.
| Keywords: |
automatic, creation, heuristics |
| Category: |
Technical Report |
BibTeX
@manual{Hernadvolgyi+Holte:04,
author = {Istvan Hernadvolgyi and Robert Holte},
title = {Steps Towards the Automatic Creation of Search Heuristics},
year = 2004,
}Last Updated: March 22, 2007
Submitted by Nelson Loyola 
