This volume is a useful guides to recent advances in AI and cognitive science towards a satisfactory solution to the frame problem. Being an original collection, many of the contributions further the advance of research in this area. In addition, many of the articles point the way for the reader interested in exploring broader foundational issues.
1.1 The Frame Problem concerns the representation of knowledge in a changing world. In so-called declarative computational representations of knowledge, the world is depicted as a set of assertions. Knowledge about the effects of actions, in particular, is often depicted in assertions of the form: If P is true, then Q is true as the result of performing action A. There are two related problems with this representation: the first is in listing all the conditions (P) which must be true for A to produce its "intended" effect. The other problem is to specify (in Q) all the truths which follow from A being performed, including not only a specification of things that change, but also things that do not. The former problem is called the qualification problem; the latter, the frame problem. Finally, there is a related ramification problem, which is the problem of formalizing all the things that do change as the result of an action. In the following, unless more specificity is required, I shall use the term frame problem in a generic sense, which includes all three problems just identified.
1.2 The Ford & Hayes (1991, henceforth F&H) volume contains expanded and revised versions of papers presented at the First International Workshop on Human and Machine Cognition in 1989. The objective of the workshop was to bring together researchers in AI, cognitive science, psychology, and philosophy for the purpose of presenting different perspectives on a common problem or theme, to achieve "a focused exchange of ideas" (p. ix). Despite the interdisciplinary intent, the majority of papers present a more or less conventional AI perspective. That is, they attempt to solve what is sometimes called the technical frame problem, in contradistinction to the broader formulation sometimes preferred by philosophers. The papers from this workshop that had a broader philosophical approach appear in a separate volume (Ford and Pylyshyn, 1992). A review of the workshop itself appears in (Dietrich, 1991).
1.3 The book is useful to researchers in cognitive science, AI and philosophy who wish to possess a single resource for technical discussions on the frame question. It differs from other edited volumes in having original contributions and also in stressing an interdisciplinary approach. Those likely to benefit the most from this collection will have some background in logic and formal semantics, familiar with what the frame problem is, appreciative its significance, but perhaps not yet familiar with the current approaches to solving it. Alternatively, for those who need to obtain the relevant background knowledge in semantics and logic, some of the more self-contained papers provide a useful introduction; otherwise, the accompanying bibliographies are useful. In addition, the interdisciplinary nature of the collection gives the reader a valuable reference source for authors in logic and cognitive science who are not as well known in AI. This I found especially useful.
2.1 In dealing with the frame problem, most of the contributors to the book take as the starting point of their analysis the current state of AI research. To understand this current state, it is useful to summarize some recent history.
2.2 The original technical solution to the frame problem was proposed within the framework of nonmonotonic reasoning (McCarthy, 1986). There are a number of formalizations of nonmonotonic reasoning, including circumscription, default logic, and the closed world assumption. In general, nonmonotonic reasoning systems attempt to model reasonable but deductively unsound inferencing. These models allow for the expression of default knowledge, such as "birds typically fly," in terms of rules to the effect that unless refutable from what is known, the system can infer from knowledge that X is a bird, that X flies (i.e. is typical). This system is "nonmonotonic" because further information to the effect that X is not typical (e.g., it is a penguin) will force the removal of the default conclusion. Circumscription sanctions this inference through a formal process of "minimizing" the set of abnormal things. Minimizing formalizes the intuition that the only things the system should identify as abnormal are the things it can prove to be such. The relevance of the nonmonotonic perspective for the frame problem is the observation that any general assertion of the effects or preconditions of actions (or other events) will also be defeasible, given additional knowledge.
2.3 The use of nonmonotonic techniques can lead, unfortunately, to the so-called "Yale Shooting Problem" (YSP) (Hanks, McDermott, 1987). The YSP involves a loaded gun, a victim, and a waiting period prior to the firing of the gun. Minimizing abnormality in this case does not yield the singular intended solution that the victim dies; equally minimal is the world in which the gun becomes unloaded. This result is unintuitive because, barring new knowledge, common sense would maintain that loaded guns remain loaded.
2.4 The YSP led immediately to attempts to revise the formalizations of default reasoning which "work but don't seem natural" (McCarthy, 1993). The current state of research on the frame problem in AI can be characterized roughly as attempts to formulate criteria for justifying formal proposals for solving YSP and similar problems. This supplies the necessary background for understanding the focus of the workshop.
2.5 Articles in the collection can be divided roughly into two categories: first, "expanding old directions," in which authors use the framework of nonmonotonic reasoning to devise new (and, one hopes, less ad hoc) frameworks for solving the frame problem. The other category can be called "proposing new directions," in which an alternative representation and reasoning framework is identified. This partitioning is rough, and some authors are hard to classify; but I will use this distinction in the remainder of my summary.
3.1 Scott Goodwin and Andre Trudel (F&H, p. 87) see the key to solving the frame problem in an adequate characterization of persistence. Their approach to formalization differs from the traditional one in opting for the framework of so-called continuous temporal logics (i.e., logics which represent time explicitly), rather than that of the situation calculus. Their system operates within a first-order hypothetical reasoning framework, with knowledge consisting of facts and hypotheses, as well as meta-knowledge sufficient to make assertions about justifications of knowledge (including notions like plausibility and unacceptability, p. 93). Default assumptions are represented differently from the usual form of "true until proven false"; rather, an empirically verifiable statistical approach is presented (p. 94). Temporal persistence underlies a kind of default knowledge: it states that "for most intervals, the truth value of a relation is the same at every point in the interval" (p.100). The minimal models of the YSP are, on this approach, treated "skeptically," i.e., neither is acceptable without further information. To achieve the desired solution, the assumption of "temporal independence" (the past is independent of the future) is required (p.101).
3.2 Leora Morgenstern (F&H, p. 133) presents new variations on the frame problem, ones in which there are multiple agents and "vicarious plans" (pp. 140-41). The examples point to a solution in which agents are able to reason without full knowledge of events that have occurred. This motivates an approach which adds a logic of belief to a temporal nonmonotonic framework; the result, she calls Epistemic Motivated Action Theory (EMAT). The central notion of motivation is similar to that of justification, in that it supplies the warrant for the reasoning agent either to maintain or "clip" models. The belief representation allows for a relativization of theories to agents and times, thus supporting the means for expressing concepts like ignorance and belief revision.
3.3 The chapter by Jay Weber (F&H, p. 259) raises a fundamental criticism of persistence-based solutions to the YSP and related problems and suggests a different explanation of, and approach to, the frame problem. His suggestion is that temporal minimization is "too insensitive to contextual information" (p. 260), and that the frame problem should be viewed as one of supplying enough domain-dependent information to infer the occurrence of particular events. He offers three solutions to the frame problem, each of which illustrates how adding domain-dependent knowledge avoids frame "problems," including the so-called knowledge omniscience assumptions.
3.4 Brian Haugh (F&H, p. 105) also cites YSP as illustrative of how solutions involving nonmonotonic formalisms violate common sense by "incorporating implicit assumptions about (a theory's) knowledge of its domain" (p. 108). His solution also introduces an explicit representation of belief. The key is the need to minimize changes ("disturbances") in factual knowledge without any justification. Justified changes are "roughly, those changes that are somehow justified by the facts, events, and laws of an explicitly stated theory"(p. 121). His chapter goes on to sketch a foundation for a representation of explicit knowledge, justification of knowledge, and causation.
3.5 Frank Brown (F&H, p. 1) returns to a situation calculus framework formulated in second-order modal quantification logic, with an intensional semantics and a proof technique involving reflective reasoning. The logic includes a formulation of frame laws for actions as quantifications over propositions in which modal operators are relativized to initial situations and those resulting from the action. Reflective reasoning involves solving an equation of the form K = A, where K may appear in A, presumably within a default law. To solve this equation, A is reduced to a disjunction of formulas in which K no longer occurs but which is logically equivalent to the original equation. This formulation allows for a solution to the frame problem by propagating properties across successive situations in which an action is performed through default laws (p. 13f). The intensional semantics is utilized for soundness and completeness results as well as to prove equivalence with other nonmonotonic systems.
4.1 Lynn Andrea Stein (p.219) objects to approaches that pose the frame problem as a problem in reasoning about time and suggests that the problem of determining what changes as the result of an action is a problem of relevance. Support for this idea comes by contrasting the frame problem with the so-called counterfactual validity problem. This is the problem of interpreting counterfactual statements like "if kangaroos didn't have tails, they would fall over." This is a particularly difficult problem, and one whose formal semantics seems to require something like possible worlds. However, such a semantics seems to lead to something analogous to the YSP for counterfactuals, since there may be multiple worlds which are consistent with the change implied by making the antecedent of the counterfactual true, but which differ in their common sense appeal. The chapter concludes with a recommendation for incorporating a record of changes made in the world to serve as justifications for inferences made during frame-like situations.
4.2 David Etherington, Sarit Kraus, and Donald Perlis (F&H, p. 43) summarize accounts that expose anomalous behavior in nonmonotonic reasoning systems. An example involving the persistence of a healthy state of an automobile relates these anomalies to the frame problem. Their solution involves recognizing a "scope of interest or concern." The idea, which is illustrated nicely with an example about an engineer (p. 47), is that "scoped minimization" is not constrained by the presence of assertions that there are counterexamples to default generalizations; this allows for the drawing of the intuitive default conclusions. On this reading, "scope" becomes a predicate true of domain objects; if it ranges "widely" over elements of the domain, few default conclusions are drawn. To solve the problem of vehicle servicing, one merely puts the time containing the trip home within the scope of the predicate "scope." This sanctions the desired inference.
4.3 Similarly, J. Terry Nutter (F&H, p. 171) focuses on the problem of context of reasoning, but in a broader setting. Her argument draws upon a rich set of examples which show how pervasive the frame problem is, and adopts the notion of salience as a paradigm for representing context and focus of attention. She suggests that for solving potentially complex reasoning problems such as those posed by the frame problem what is needed is not something that prunes a complex search space but rather something that limits what is accessible (salient) to the reasoner. This intriguing paradigm of context limitation involves nondestructive operations on the knowledge itself, producing simplified transformations of assertions, which thereby controls the complexity. Since these operations are nondestructive, they can be modified to handle changes in context as the result of adding new knowledge.
4.4 Donald Perlis (F&H, p. 189) and Daniel S. Weld (F&H, p. 275) offer contributions in a similar vein but using different frameworks. Perlis suggests that the key for a solution to the frame problem may reside in an explicit representation of the intensionality (the aboutness) of concepts. This leads from the uncertainty of the world from the standpoint of an axiomatic account of its behavior, to default reasoning with vague concepts, to the problem of "getting the right defeasible conclusion" (p.191) in the light of problems such as YSP. The latter may require a mechanism which recognizes something as conceptual, and hence can distinguish between reality and "mere appearance." This leads into a brief history of western philosophy and a suggestion that a systems be developed with the appearance/reality distinction. Weld, by contrast, uses the framework of system dynamics to argue that solutions to the qualification problem will result from developing computational systems which recognize that multiple models exist, each offering merely an approximation of the reality being modeled.
4.5 Erik Sandewall's chapter (F&H, p. 201) contains an interesting historical analysis which ties together the frame problem of McCarthy and Hayes with Minsky's (1974) notion of frames. Briefly, the term "frame" was used by Minsky to describe a particular knowledge structure representing things like objects with properties. McCarthy/Hayes, on the other hand use it to describe "histories", i.e., bundles of spacetime. Sandewall introduces a structure called "dynamic frames" as a generalization or synthesis of the two notions. The frame problem, on this approach, is unified with the problem of reasoning about the dynamics of dynamic frames. He distinguishes between two kinds of change, smooth (intraframe) and structural (interframe). The logic of smooth change involves chronological minimization and concepts like persistence. The logic of structural change, by contrast, is to be found by applying principles found in qualitative reasoning systems.
4.6 Josh Tennenberg offers a useful classification of frame problem solutions in terms of the conservative/permissive dichotomy. Permissive views, which include all of the proposals summarized in the previous section, assume the completeness of knowledge, thereby sanctioning inferences about change. Tennenberg echoes some of the remarks of Nutter in rejecting such accounts as overly simple and inadequate on many counts. The conservative approach, by contrast, sanctions inferences about change through the use of explanation-closure axioms of the form: "P changes between t and t+1 only when actions A1 ... An occur at t"(p.240). This approach avoids the limitations of the permissive approach, but at a price which makes it equally inadequate. The problem, of course, is coming up with the requisite axioms regarding change; as Tennenberg notes, this is the same as or close to the qualification problem itself. His solution uses probabilistic reasoning based on statistical assertions. Associating probabilities allows for the abandonment of completeness assumptions and yet allows for the propagation of knowledge. Unlike in traditional approaches, knowledge is also allowed to become obsolete, thus admitting revision of predictions about the future.
4.7 Finally, the collection includes a debate between James Fetzer (F&H, pp. 55, 77), and Patrick Hayes (F&H, p. 71). Fetzer offers an analysis of the frame problem which leads to a solution in terms of the proper formulation of natural laws. He reformulates the frame problem as the classical problem of induction as formulated by Hume. Like the problem of induction, the frame problem, in Fetzer's view, is one of justifying inferences about the future, both about what changes and what stays the same. It is therefore a problem of the justification of claims to knowledge. According to Fetzer, appeals to principles like persistence will work only if they follow from carefully formulated theories of natural law. Furthermore, so-called "common sense" fails to provide the source for such a theory, since common sense is too haphazard to offer a proper foundation for knowledge representation.
4.8 Instead, Fetzer offers a set of schemata for the formulation of natural laws. The schemata provide the warrant for predictive inferences about the future. Laws that instantiate the schema must be "maximally specific" in the characterization of their antecedent conditions; hence, "the system thereby described is a "closed system (p.60); in other words, the inferences they sanction are deductively valid. Such schemata are utilized by Fetzer in the formulation of laws sanctioning inferences about what changes as the result of an action, what stays the same, and about inferential situations in which the knowledge of the requisite law is lacking. Although the laws sanction deductively valid inferences, knowledge of these laws is itself empirically based, and hence fallible. He adopts a Popperian methodology for the validation of these laws. Finally, there is a suggestion that the schemata provide a foundation for a implementable knowledge representation language for AI.
4.9 In his response, Hayes proceeds to attack Fetzer on every count. The frame problem is not reducible to the problem of induction (it is a representation problem, not a problem in justification of knowledge), common sense does provide the key to its solution (humans can perform the proper inferences without knowledge of maximally specific causal laws), and Fetzer's schemata offer no help in finding a solution (in being maximally specific, they exemplify rather than solve the qualification problem, and they are useless as a representation language for AI).
4.10 Hayes's frontal attack leaves little hope of reaching any graceful resolution to the debate, and Fetzer's "final word" offers little more than a restatement of his original thesis. This debate seems indicative of a tension between some philosophers and AI researchers. This tension has led McCarthy (1993) to complain that "Some of the most confused people about formalized nonmonotonic reasoning and the problems for which AI people use it have been philosophers" (p. 25). This point is evidenced, I believe, by the remarks of a recent contributor to this journal, whose comments I will now briefly address.
5.1 I wish to address specific remarks made by van Brakel (1992). I ignore the broader question of whether van Brakel has even formulated the frame problem correctly, which is also questionable.
5.2 Van Brakel's discussion begins with identifying what he terms three AI "responses" to the frame problem (3.2), viz:
R1 the ostrich approach; R2 the panacea approach and R3 the approach that recognizes that there is a problem, but "assumes it does not exist for specific domains".
R1, the "ostrich" approach, van Brakel ambiguously defines as
(M1)"denying the problem exists", and (M2)"relegating the problem to the future work category (3.2).
In no clear sense are these two definitions equivalent. By adopting M2 I clearly identify it as a problem (otherwise, there would be nothing to relegate). The effect here seems to be to muddy the waters.
5.3 Van Brakel attributes the ostrich approach to Morgenstern, Etherington, Kraus, Perlis, and Haugh. But to attribute M1 to them is absurd (why would they attend a workshop on the problem unless they believe it exists)? The passages van Brakel cites from their chapters suggest that he is accusing them of M2. But what, exactly, is the criticism here? As my review has suggested, some of these authors are suggesting that a new direction be taken in solving the frame problem. It seems to be legitimate for contributors to a workshop to argue for a new direction without offering a complete technical solution, based on this new direction -- especially given the complexity of the problem itself.
5.4 R2 is attributed to Nutter, Perlis, Weber. This is the approach in which the solution to a problem is "delayed" by appealing to a question begging concept, i.e., a concept whose representation is at least as difficult a problem as the original one to be solved. Examples from the book of question-begging properties which are supposed to supply a key to solving the framing dilemma are "salient," "appropriate" and "relevant." There are two issues being conflated here: viz.,
1. How does a knowledge engineer partition a set of predicates into the appropriate categories for developing knowledge bases that are not subject to the frame problem, and
2. How does one automate this process?
The second problem is clearly more difficult than the first, and the solution to the second presupposes that the first has been solved. Problem 2 may be unsolvable in general, due to the complexity of the frame problem (but see the results in Brown's chapter ). Nutter seems to be addressing point (2), but the other authors seem to be addressing point (1). And although to a limited extent one might agree with van Brakel's point (some authors seemed to be pushing the problem back a bit), I do not find the point to carry a lot of force. The reason is that, as a design aid for nonmonotonic reasoning system builders, it is useful to have a theory which explains what makes certain relations abnormal (or projectable, etc). This is a kinder and more accurate characterization of what the authors van Brakel criticizes are doing. It is simply too casual to dismiss what they are doing in the manner van Brakel adopts. As I indicated in my review, the AI research community is currently driven by the need to find solutions to the problem that are "grounded" in common sense, not just ones that "work." This explains the appeal to "grounding" concepts like relevance, context, and the like. Unlike van Brakel, I found these attempts, on the whole, to contribute to advancing the research.
5.5 Finally, commenting on R3 (3.6), van Brakel does not have any specific authors from the book in mind, but proceeds to criticize AI solutions in general as tending towards being the ad hoc and question-begging. He speaks of the "practical AI researchers" (whoever they are) who don't find anything wrong with the frame problem. I find these blind side attacks on AI completely lacking in substance. The very workshop that van Brakel is reviewing belies the claim that the AI community is insensitive to the depth of the problem. Even a cursory glance at the history of the problem (as I have tried to provide here; a more comprehensive reference is Ginsberg, 1987) shows that AI researchers have been engaged in a healthy, self-critical debate about the value of proposed technical solutions. One is forced to conclude that the so-called "practical AI researcher" is clearly a straw man for confused and/or threatened philosophers.
6.1 This book, along with its companion (Ford and Pylyshun, 1992) are useful reference guides to recent advances in AI and cognitive science towards a satisfactory solution to the frame problem. Being an original collection, many of the contributions further the advance of research in this area. In addition, many of the articles point the way for the reader interested in exploring broader foundational issues.
Dietrich, E. (1991) The First International Workshop on Human and Machine Cognition, Pensacola, Florida. Topic: The Frame Problem. AI Magazine, 11(5) 60-64.
Ford, K.M. and P.J. Hayes (1991) Reasoning Agents in a Dynamic World: The Frame Problem, Greenwich: JAI Press.
Ford, K. and Pylyshyn, Z., eds. (1992) The Robot's Dilemma Revisited: The Frame Problem in Artificial Intelligence, in press.
Ginsberg, M. (ed.) (1987) Readings in Non-Monotonic Reasoning. Morgan Kaufmann Publishers, Inc.
McCarthy, J. (1993) History of Circumscription. Artificial Intelligence 59, 23-26.
Minsky, M. (1974) A framework for Representing knowledge. MIT Lab Memo # 306.
Van Brakel, J. (1992) The complete description of the frame problem. PSYCOLOQUY 3(60) frame-problem.2.