Home › UTCS Calendar

AI Forum: Dr. Robert Holte University of Alberta Additive Pattern Database Heuristics

Contact Name: 
Jenna Whitney
Date: 
Feb 23, 2007 11:00am - 12:00pm

There is a sign-up schedule for this event:

http://www.cs.utexas.edu/department/webevent/utcs/events/cgi/show_schedule

.cgi?person=Dr.RobertHolte

Speaker Name/Affiliation: Dr. Robert Holt

e University of Alberta

Date/Time: Friday February 23 2007 11:00

a.m.-Noon

Location: ACES 2.302

Host: Dr. Bruce Porter

Talk Abstract:
This research studies heuristic functions defined by
a

bstractions where the distance from a state S to the goal
state is esti

mated with the true distance from the abstract
state corresponding to S

to the abstract goal state. When
precomputed and stored as lookup tables
such heuristics are
called pattern databases (PDBs) and are the most

powerful
heuristics known for many problems.

The question address

ed in this presentation is: under what
conditions is the sum of several

PDB heuristic functions
admissible (guaranteed never to overestimate a d

istance)?

This question has previously been addressed by Felner Kor

f
and Hanan in a 2004 JAIR paper. Our work generalizes their
answer
greatly enlarging the types of search spaces for which
admissible addit

ive heuristics can be defined. Experimental
results on the Pancake puzzl

e show that well-chosen additive
PDBs reduce solution time by three orde

rs of magnitude over the
best published results for this puzzle. We also
show that
additive PDBs are not always superior to taking the maximumover heuristics based on the same abstractions.

The presentation a

ssumes basic knowledge of heuristic search
but does not require any kno

wledge of pattern databases.

Speaker Bio:
Professor Robert Holte

is a well-known member of the
international machine learning research co

mmunity former
editor-in-chief of the leading international journal in

this
field (Machine Learning) and current director of the Alberta
In

genuity Centre for Machine Learning. His main scientific
contributions a

re his seminal works on the problem of small
disjuncts and the performan

ce of very simple classification
rules. His current machine learning res

earch investigates
cost-sensitive learning and learning in game-playing

(for
example: opponent modeling in poker and the use of learning
for
gameplay analysis of commercial computer games). In
addition to machine
learning he undertakes research in
single-agent search (pathfinding):

in particular the use of
automatic abstraction techniques to speed up s

earch. He has
over 55 scientific papers to his credit covering both pur

e and
applied research and has served on the steering committee or
p

rogram committee of numerous major international AI
conferences.