UTCS Colloquia/AI - Robert Holte/University of Alberta, "Knuth-Chen Meets Heuristic Search", PAI 3.14

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

There is a sign-up schedule for this event that can be found at


Type o

f Talk: UTCS Colloquia/AI

Speaker/Affiliation: Robert Holte/University
of Alberta

Talk Audience: UTCS Faculty, Graduate Students, Undergra

duate Students and Outside Interested Parties

Date/Time: Thursday, Fe

bruary 23, 2012, 11:00 a.m.

Location: PAI 3.14

Host: Bruce Port


Talk Title: Knuth-Chen Meets Heuristic Search

Talk Abstract:

nIn 1975 Knuth showed that a simple random-walk procedure gave an unbiased

estimate of the size of a depth-first backtrack search tree. His student P-

C Chen later improved Knuth''s method by partitioning the nodes in the sear

ch tree into types and broadening the random walk so that at each level of

search, for every type reached at that level one node of that type would b

e expanded. In this talk I describe our efforts to extend Chen''s method to
work in the context of heuristic search. First, we consider the problem o

f predicting the number of nodes expanded by IDA* for a given cost bound. C

hen''s method is almost immediately applicable to this problem, but it is

outperformed by CDP, the current state-of-the-art system for this predicti

on problem. However, when Chen''s method is used in conjunction with CDP''

s type system, new state-of-the-art results are produced. Second, we cons

ider the problem of predicting the optimal solution cost of a search proble

m without actually finding a solution. For this we devised a bidirectional

variation of Chen''s method which we call BiSS. We show that BiSS makes mor

e accurate predictions than SCP, the current state-of-the-art, and scales
to larger state spaces than SCP can handle. If time permits I will also di

scuss the application of BiSS to the problem of learning search heuristics

, and show that it reduces learning time for large state spaces from days t

o minutes.

Dr. Robert Holte is a professor in the Computing Sci

ence Department and Vice Dean of the Faculty of Science at the University o

f Alberta. He is a well-known member of the international machine learning

research community, former editor-in-chief of a leading international jour

nal in this field ("Machine Learning"), and past director of the Alberta I

ngenuity Centre for Machine Learning (AICML). His main scientific contribut

ions are his seminal works on the performance of very simple classification
rules and a technique ("cost curves") for cost-sensitive evaluation of cla

ssifiers. In addition to machine learning he undertakes research in single-

agent search (pathfinding), in particular, the use of automatic abstracti

on techniques to speed up search.