Based on intro from NSF Faculty Early Career Development
Award (1998-2002) proposal.
In the 70's and 80's the success of knowledge-intensive approaches to problem solving eclipsed earlier work on compute-intensive 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 1997 ACM Challenge match. Deep Blue's performance led Kasparov to exclaim, "I could feel --- I could smell --- a new kind of intelligence across the table.'' Deep Blue derives its strength mainly from highly optimized search; it considers an astonishing 200 million chess positions per second. Another dramatic development in the compute-intensive approach was the recent computer proof resolving the Robbins problem. The Robbins problem is a well-known problem in algebra, and was open for over sixty years. The computer proof was found by applying powerful search techniques guided by general search tactics. Unlike some 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 Robbin's theorem are good examples of a qualitative change in performance of compute- intensive approaches compared to just a few years ago.
In my own work, on stochastic reasoning and search methods, our most recent procedures can handle problem encodings with tens of thousands of variables and several million constraints. Being able to tackle problem encodings of this size has led to a qualitative difference in the kinds of tasks that one might consider for general search and reasoning methods. Automatic planning is one of our application areas. We can now synthesize (optimal) plans consisting of several hundred actions, which opens up new opportunities in the area of planning and scheduling, but also in program synthesis and protocol verification.
I predict that this is just the beginning of a shift to
compute-intensive methods. Given the tremendous difficulty of supplying
a program with certain kinds of domain-specific knowledge, we may in fact
be better off attacking the inherent combinatorics head on. I don't mean
to suggest that simply faster machines and implementations will be sufficient.
Further research on search and reasoning procedures and on problem encodings
will certainly be needed. Also, there are still many examples where general
methods quickly become ineffective. Nevertheless, we now have concrete
evidence that the battle against combinatorics can be won, at least in
certain interesting cases. The challenge is to continue pushing the
compute-intensive approach into areas that have previously been considered
off limits.
In my research on compute-intensive methods, I focus on the following areas:
Robustness, uncertainty, and the brittleness of knowledge representation schemes. Subtle differences in problem representations can lead to large differences in our ability to solve the underlying problem. Moreover, many problem encodings used in, for example, planning and reasoning, lead to solutions that are quite brittle when it comes to small changes in the original problem. A principled approach for designing "good'' problem encodings is needed.
The nature of hard computational problems and its connections to statistical physics. During the past five years, we have obtained a much better understanding of the nature of computationally hard problems, mainly by studying distributions of random problem instances. A better understanding of more structured instances, as they occur in actual applications, is needed. This is a rapidly emerging area of research incorporating concepts and methods from statistical physics (Kirkpatrick and Selman, Science, vol. 264, 1994, 1297--1301). See Cipra.
Reasoning from first principles: Compilation, approximation, and abstraction. Compute-intensive methods operate from "first principles.'' That is, little or no domain- specific search control knowledge is used. This kind of reasoning or search generally requires substantial computational resources. In building real-time systems, it is often desirable to shift the computational cost to an off-line, pre-processing (compilation or abstraction) phase. There are interesting tradeoffs to be explored between the cost of preprocessing and on-line savings.
Challenge applications in planning, operations research, learning, and computational biology. Planning is a notoriously hard combinatorial search problem. The previous generation of domain indendent AI planners (circa 1995) could synthesize plans of only 10 to 20 steps. Recent planners, based on reformulating planning in terms of large constraint satisfaction problems, can find plans with several hundred operations. The next step is to develop planners that synthesize sequences of thousands of steps. This would lead to new applications in areas as diverse as protocol verification, supply-chain management, and program synthesis. Other promising areas of application of compute-intensive methods are in machine learning, operations research, and computational biology.