UTCS/AI: Robert Holte/University of Alberta Methods for Predicting IDA*'s Performance ACES 2.302 Tuesday February 19 2008 2:00 p.m.

Contact Name: 
Jenna Whitney
Feb 19, 2008 2:00pm - 3:00pm

There is a sign up schedule for this event:

Type of Talk: UTCS Colloquium/AI

Date/Time: Tuesday Februar

y 19 2008 2:00 p.m.

Location: ACES 2.302

Host: Bruce Port


Talk Title: Methods for Predicting IDA*''s Performance


lk Abstract:
The goal of the research presented in this talk is to accur

ately predict
the number of nodes that the heuristic search algorithm ID

A* will expand
for a given depth bound heuristic and start state or se

t of start states.
The talk begins by describing the landmark paper by M

ike Reid and
Rich Korf in AAAI 1998. This paper presented a simple but

very effective
analysis framework and developed a formula that was shown
to make almost perfect predictions. This prediction met

hod has two
shortcomings (1) it is only applicable when the given heuris

tic is consistent;
(2) its predictions are accurate only for average pe

rformance over a large
random sample of start states. The talk then desc

ribes recent work that
overcomes these two obstacles. The method present

ed makes accurate
predictions for consistent and inconsistent heuristics
and for arbitrary sets of
start states (including individual start stat


Speaker Bio:
Professor Robert Holte is a well-known member o

f the international machine
learning research community former editor-i

n-chief of the leading international
journal in this field (Machine Lear

ning) and current director of the Alberta
Ingenuity Centre for Machine

Learning. His main scientific contributions are his
seminal works on the
problem of small disjuncts and the performance of very
simple classific

ation rules. His current machine learning research investigates

sitive learning and learning in game-playing (for example: opponent

ling in poker and the use of learning for gameplay analysis of commercial

computer games). In addition to machine learning he undertakes

in single-agent search (pathfinding): in particular the use of

c abstraction techniques to speed up search. He has over 55 scientific

apers to his credit covering both pure and applied research and has serve

on the steering committee or program committee of numerous major

ternational AI conferences.