Date/Time: Tuesday Februar

y 19 2008 2:00 p.m.

Location: ACES 2.302

Host: Bruce Port

er

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

Ta

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
experimentally
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

es).

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
cost-sen

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

ling 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
automati

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

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

d
on the steering committee or program committee of numerous major
in