Broad Area Colloquium For AI-Geometry-Graphics-Robotics-Vision
Recent Progress in the Design and Analysis of Heuristic Evaluation Functions
Richard E. Korf
Computer Science Department
University of California, Los Angeles
Monday, Oct 2, 2000, 4:15PM
TCseq200, Lecture Hall A
http://robotics.stanford.edu/ba-colloquium/
Abstract
In this two-part talk, we first consider new methods for the automatic design
of admissible heuristic evaluation functions, based on pattern databases.
These heuristic functions have made possible the computation of the first
optimal solutions to Rubik's Cube and the 5x5 Twenty-Four Puzzle, a larger
relative of the well-known Fifteen Puzzle. In the second part, we consider a
new approach to the analysis of the time complexity of admissible heuristic
search algorithms. This analysis has led to the first accurate predictions of
the performance of heuristic search on real problems. Contrary to
conventional
wisdom, our analysis shows that the asymptotic heuristic branching factor is
the same as the brute-force branching factor, and that the effect of a
heuristic function is to reduce the effective depth of search, rather than the
effective branching factor.
About the Speaker
Richard Korf is a Professor of computer science at the University of
California,
Los Angeles. He received his B.S. from M.I.T. in 1977, and his M.S. and
Ph.D. from Carnegie-Mellon University in 1980 and 1983, respectively, all in
computer science. From 1983 to 1985, he served as Herbert M. Singer Assistant
Professor of Computer Science at Columbia University. His research is in the
areas of problem solving, planning, and heuristic search in artificial
intelligence. He is the author of "Learning to Solve Problems by Searching for
Macro-Operators" (Pitman, 1985). He serves on the editorial board of the
Journal of Applied Intelligence and Artificial Intelligence. Dr. Korf
is
the recipient of a 1985 IBM Faculty Development Award, a 1986 NSF Presidential
Young Investigator Award, the first UCLA Computer Science Department
Distinguished Teaching Award in 1989, and the UCLA Engineering School First
Annual Student's Choice Award for Excellence in Teaching in 1996. He was
elected a Fellow of the American Association for Artificial Intelligence in
1994.
bac-coordinators@cs.stanford.edu
Back to the Colloquium Page
Last modified: Wed Sep 27 14:54:12 PST 2000