*ACM Computing Surveys*
**28A**(4), December 1996,
http://www.acm.org/surveys/1996/Structured/. Copyright ©
1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Position Statement for SDCR Workshop

Computer Science Department, Stanford University

Gates Building 1A

Stanford, CA 943-5-9010, USA

koller@cs.stanford.edu, http://robotics.stanford.edu/~koller

Abstract:Over the years, artificial intelligence has made significant progress in isolating certain crucial components of the AI problem and formulating them as concrete technical problems. Unfortunately, we have again and again been faced with the fact that most of these technical problems are highly intractable. It seems that when we formulate an intelligent behavior pattern as a technical problem, we lose that indefinable property that makes the problem solvable by a human being. In this paper, I argue that our representations of problems have often been too general, preventing us from taking advantage of the underlying structure of the domain. By way of contrast, some of AI's most impressive success stories (e.g., Bayesian belief networks), utilize representations geared specifically to capturing domain structure. I argue that the most promising path for scaling up AI systems is via the development of representations that capture the underlying structure of our domains.Categories and Subject Descriptors: I.2.4

[Artificial Intelligence]: Knowledge Representation Formalisms and Methods -Representation languages; F.2[Analysis of Algorithms and Problem Complexity]General Terms: Artificial Intelligence, Knowledge Representation, Complexity, Uncertainty.

Additional Key Words and Phrases: Structured representation, economics, decision theory, probability.

In order to be completely successful, this paradigm of extracting specific tasks and solving them must overcome two obstacles. The first, of course, is that a solution to a number of important but separate subproblems does not immediately (or even easily) result in a coherent solution to the task as a whole. We have yet to understand how the different pieces can be put together into a working intelligent agent. As argued by Nils Nilsson [Nilsson, 1995], it is important, while trying to solve individual problems, to also `keep an eye on the prize.

The second obstacle that must be overcome is more immediate, and encountered even when attempting to address the (perhaps shorter term goal of AI) of building useful systems that exhibit some intelligent behavior. It seems an inescapable fact that a precise formulation of any interesting task is inherently intractable. Not only is the worst-case complexity of the problem typically overwhelming, but it is also hard to design algorithms that do well on the typical instances. This often prevents us from applying our ideas to realistic and interesting problems, making it difficult both to evaluate their usefulness, and to demonstrate concrete contributions to real-world problems.

One might say that the solution is to ignore worst-case behavior. After all, the bizarre instances that we use in our intractability proofs do not actually arise in real life. Unfortunately, a very general, abstract formulation of a task can be deficient in another, more important way: by its very generality, it cannot support representations that are targeted for reasoning patterns that are suitable to the specific task at hand. Thus, the inference engine must often proceed with little or no guidance.

It might appear that the above statement calls for a return to building very
domain-specific systems. That is *not* the intent. Rather, it calls
for the specification of general representation languages that capture some
underlying structure that is present in many real-world domains, and for
inference algorithms that are designed to utilize this structure to guide
the reasoning process.

Another source of structure that has proved enormously useful in solving the
planning problem is based on the fact that people plan their actions at
several levels of granularity, with a high-level action being composed of a
number of lower-level actions. This idea was first utilized in the original
STRIPS planner and in the ABSTRIPS planner [Sacerdoti, 1974]. The resulting representation, and
the *hierarchical decomposition planning* algorithm based on it (which
uses the choice of higher-level actions to guide the lower-level planning
--- see [Erol *et al.* 1994] for a survey), is now a
fundamental component of all real-world planning systems.

*Bayesian networks* [Pearl, 1988] are a similar
success story for a very different task. For many years, probabilistic
inference was rejected as an approach for reasoning under uncertainty. The
primary reason was the apparent infeasibility of exact probabilistic
inference, which seemed to call for the elicitation and manipulation of an
exponential number of probabilities. Bayesian networks utilize the
*locality structure* of a domain --- the fact that only very few
aspects of the situation directly affect each other --- to allow for a
natural and compact representation of a probability distribution. Just as
in the case of planning, this more specialized representation (suitable for
a certain class of domains) also supports a more effective inference
algorithm. Bayesian networks have proved themselves to be highly effective
for a wide range of tasks; they are largely responsible for the revival
of probabilistic reasoning for AI applications that has occurred over the
past decade.

Other success stories include description logics as a structured sublanguage of full first-order logic, tree-structured constraints in constraint satisfaction algorithms, my own work on structured strategies in imperfect information game trees, and many more.

Many of the models in these fields were developed with the primary goal of getting a better mathematical model for the problem. Unfortunately, this goal is best accomplished with representations that are very abstract, e.g., a set of `possible states of the world', or a set of `all possible agent strategies (conditional plans in AI terminology)'. These representations, which are completely unstructured, are generally incapable of supporting effective inference.

Judging by the enormous success of belief networks, the benefits of
cross-fertilization between AI and economics/operations research can be
tremendous (partially because many of the existing representations are
*so* unsuitable for inference). Even beyond the computational benefits
resulting from such a synergy, one might hope that the resulting
representations will allow for integration of uncertain reasoning formalisms
with more traditional AI work, leading to a unification between these two
competing paradigms in AI.

The only answer is to test our candidate representation languages against the real world. It is not useful to design a representation language for a certain type of structure if the structure is not present in a sufficiently rich class of real world applications. Thus, our design process must rely on continuous interaction with real-world problems, in order to test whether our representation and the associated inference algorithms rely on structure that is really there. These problems, of course, must be challenging enough so that the representation really makes a difference. After all, it is easy to impose structure onto problems that are so simple that they can be perceived in almost any way that we want.

The process of designing and evaluating structured representations is thus a difficult one. But, as we have seen in the past, when successful, structured representations can be an enormously valuable weapon in our fight against intractibility.

**[Erol***et al.*1994]- Erol, K., Hendler, J., and Nau D. S. HTN planning: complexity and
expressivity,
*Proceedings of the Twelth National Conference on Artificial Intelligence (AAAI-94)*, 1994, 1123-1128. **[Fikes and Nilsson 1971]**- Fikes, R. E., and Nilsson, N. J. STRIPS: a new approach to the
application of theorem proving to problem solving,
*Artificial Intelligence*,**2**, 3-4, 1971, 189-208. **[Nilsson 1995]**- Nilsson, N. Eye on the
Prize (artificial intelligence),
*AI Magazine*,**16**, 2, 1995, 9-17, http://robotics.stanford.edu/people/nilsson/prize.ps **[Pearl 1988]**- Pearl, J.
*Probabilistic Reasoning in Intellligent Systems: Networks of Plausible Inference,*Morgan Kaufmann, San Francisco, California, 1988. **[Sacerdoti 1977]**- Sacerdoti, E. D.
*A Structure for Plans and Behavior,*Elsevier/North-Holland, New York, 1977.

Permission to make digital
or hard copies of part or all of this work for personal or classroom
use is granted without fee provided that copies are not made or
distributed for profit or commercial advantage and that copies bear
this notice and the full citation on the first page. Copyrights for
components of this work owned by others than ACM must be honored.
Abstracting with credit is permitted. To copy otherwise, to
republish, to post on servers, or to redistribute to lists, requires
prior specific permission and/or a fee. Request permissions from
Publications Dept, ACM Inc., fax +1 (212) 869-0481, or
`permissions@acm.org`.

Last modified: Fri Nov 15 12:33:51 EDT 1996 Daphne Koller <koller@cs.stanford.edu>