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
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.
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.