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


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.
Back to the Colloquium Page
Last modified: Wed Sep 27 14:54:12 PST 2000