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.