Compute-Intensive Methods in Artificial Intelligence

Tutorial Presented at AAAI-97, Providence, RI

In the 1970s and 1980s the success of knowledge-intensive approaches to problem solving eclipsed earlier work on compute-intensive weak methods. However, in recent years compute-intensive methods have made a surprising comeback. One of the most prominent examples is the success of IBM's Deep Blue in defeating Gary Kasparov in the first game of the 1996 ACM Challenge match. The game led Kasparov to exclaim, "I could feel -- I could smell -- a new kind of intelligence across the table." Yet Deep Blue derives its strength mainly from highly optimized search.

Another dramatic development in the compute-intensive approach was the recent computer proof resolving the Robbins problem (McCune, Oct. 1996). The Robbins problem is a well-known problem in Boolean algebra, and was open for over sixty years. The computer proof was found by applying powerful search techniques guided by general search tactics. Unlike previous results in the area of automated theorem proving, this time several aspects of the computer proof could be called "creative" by mathematicians' standards.

Deep Blue's performance and the resolution of the Robbins problem are good examples of the dramatic improvement in performance of compute-intensive approaches compared to just a few years ago. Other examples of the recent success of such methods are in planning, qualitative reasoning about physical systems, and learning.

This tutorial will explore how and why quantitative changes in compute-intensive methods can lead to dramatic qualitative changes in overall performance. These technique promise to alleviate the knowledge acquisition bottleneck in AI by allowing expert-level performance to be achieved with only a a minimal amount of domain knowledge. We will discuss how these lessons can be broadly applied to problems in artificial intelligence, and we will speculate on where the next breakthroughs might occur.

Henry Kautz is head of the Artificial Intelligence Principles Research Department of AT&T Labs. His research interests include knowledge representation, intelligent software agents, and efficient reasoning systems. He received his Ph.D. from the University of Rochester in 1987, and joined AT&T Bell Labs that year. In 1989 he received the Computers and Thought Award from the International Joint Conference on Artificial Intelligence. His work on stochastic search for planning won the best paper award at the 1996 conference of the American Association for Artificial Intelligence.

Bart Selman is a member of the Artificial Intelligence Principles Research Department at AT&T Laboratories. He holds a Ph.D. and M.Sc. in computer science from the University of Toronto, and a M.Sc. in physics from Delft University of Technology. His research has covered many areas in artificial intelligence, including tractable inference, knowledge representation, search, planning, default reasoning, constraint satisfaction, and natural language understanding. He has received best paper awards at both the American and Canadian national artificial intelligence conferences, and at the International Conference on Knowledge Representation. His current research projects are on efficient reasoning, stochastic search methods, planning, knowledge compilation, and software agents.

Contents

Introduction
The Robbins Problem
Quasigroups
Deep Blue
Planning and Diagnosis
Reasoning and Search
Conclusions

Back to Henry Kautz's Home Page.