Experiments with Automatically Created Memory-Based Heuristics
- Robert Holte, Department of Computing Science, University of Alberta
- Istvan Hernadvolgyi, School of Information Technology and Engineering, University of Ottawa
A memorybased heuristic is a function, h(s), stored in the
form of a lookup table: h(s) is computed by mapping s to an index and
then retrieving the corresponding entry in the table. In this paper we
present a notation for describing state spaces, PSVN, and a method for
automatically creating memorybased heuristics for a state space by ab
stracting its PSVN description. Two investigations of these automatically
generated heuristics are presented. First, thousands of automatically gen
erated heuristics are used to experimentally investigate the conjecture by
Korf [4] that m Delta t is a constant, where m is the size of a heuristic's lookup
table and t is the number of nodes expanded when the heuristic is used
to guide search. Second, a similar largescale experiment is used to verify
that the Korf and Reid's complexity analysis [5] can be used to rapidly
and reliably choose the best among a given set of heuristics.
Citation
R. Holte,
I. Hernadvolgyi.
"Experiments with Automatically Created Memory-Based Heuristics".
Symposium on Abstraction, Reformulation and Approximation, Horseshoe Bay Resort and Conference Club; HorseshoeBay (Lake LBJ), Texas, January 2000.
| Keywords: |
automatically, experiments, machine learning |
| Category: |
In Conference |
BibTeX
@incollection{Holte+Hernadvolgyi:SARA00,
author = {Robert Holte and Istvan Hernadvolgyi},
title = {Experiments with Automatically Created Memory-Based Heuristics},
booktitle = {Symposium on Abstraction, Reformulation and Approximation},
year = 2000,
}Last Updated: April 25, 2007
Submitted by Christian Smith 
