ACM Computing Surveys 28A(4), December 1996, Copyright © 1996 by the Association for Computing Machinery, Inc. See the permissions statement below.

Structured Representations and Intractibility

Position Statement for SDCR Workshop

Daphne Koller

Computer Science Department, Stanford University
Gates Building 1A
Stanford, CA 943-5-9010, USA,

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.

1 Introduction

The first difficulty that one encounters when doing AI research is that the basic task --- building intelligent agents --- is so vague and ill-defined. (This is exemplified by the fact that there are so many very different and to a large extent incompatible formulations of the AI task.) This makes it very hard to evaluate ideas, to compare different approaches, and to estimate progress. A relatively recent trend in AI research tries to address this issue by extracting well-defined tasks, such as planning, supervised learning, or uncertain reasoning, that seem to play a major role in intelligent behavior. For these tasks, we can design criteria (e.g., benchmarks) for evaluating different approaches, thereby giving a concrete quantifiable metric for progress. It is not surprising that some of the greatest progress made in AI over the last decade is in these subareas, where the AI endeavor becomes a science.

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.

2 Utilizing domain structure

One factor that contributes heavily to this phenomenon is that, in order to formulate a useful task to work on, we must abstract away many of the details of the problem. Unfortunately, most tasks are hard if you look at them at a sufficiently abstract level. If a formulation is sufficiently general, it allows us to encode very complex problems; these form the basis for the theoretical results on worst-case intractability.

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.

3 Some successful examples

This methodology has already proved itself successful for a wide range of problems. In planning, for example, the initial approach was to use a general-purpose logical theorem prover to construct plans. When this proved intractable, the solution was the development of a more special-purpose representation --- the STRIPS representation of actions [Fikes & Nilsson, 1971]. The STRIPS representation was designed to take advantage of the temporal structure of actions, particularly the fact that an action can be viewed as changing only a few aspects of the current situation. This supported a special-purpose reasoning algorithm --- goal regression --- which was much more efficient than general purpose theorem proving. Note that, while the resulting representation and reasoning algorithm are far less general than full first-order logic and theorem proving, STRIPS-style planning systems (particularly with some of the subsequent enhancements both to the language and the inference algorithm) are useful in a very wide range of applications.

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.

4 Where next?

The success of this paradigm is very encouraging, and there appear to be many tasks in AI that could benefit from exploiting it. Nowhere, however, is the need for suitable structured representations more obvious than in reasoning tasks involving complex/dynamic/uncertain/multi-agent environments. In recent years, there is a growing understanding that AI must learn to deal with such tasks, and a growing consensus that, in order to do so, we must utilize the mathematical and semantic foundations developed over many years in economics, decision theory, game theory, and operations research.

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.

5 Conclusion

Structured representations present us with a mechanism to provide guidance to our inference algorithms in their reasoning process. However, in order to do so, structured representations must walk a fine line between the abstract and the domain-specific. How can we judge whether a representation is structured enough to provide significant computational benefits, yet abstract enough to be applicable to a broad class of problems?

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,
[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

Last modified: Fri Nov 15 12:33:51 EDT 1996
Daphne Koller <>