This is primarily a critical discussion of Ford & Hayes (1991; for PSYCOLOQUY Summary, see Hayes 1992), taking into account other recent literature on the frame problem. [References to chapters and pages in the Ford & Hayes volume are given in square brackets.]
1.1 If an event (for example, one brought about by an action, in order to achieve a goal) occurs in the real world, we may ask (either with respect to knowledge or belief):
[A] Which things (facts, etc.) change and which don't? (Most don't.)
[A1] What are the necessary and sufficient conditions for an event to occur (an action to be performed successfully, a plan to be carried out)? and
[A2] What (potential) changes are brought about by the event? (What are its consequences?)
[B] How can [A] be represented?
[C] How can/do we reason about [A]?
1.2 These questions, I suggest, constitute the family of frame problems (including the persistence problem, temporal projection problem, inertia problem, qualification problem, ramification problem, extended prediction problem, installation problem, planning problem, holism problem, relevance problem, and so on), covering all definitions in Ford & Hayes (1991) [Ford and Hayes: x; Brown: 1; Fetzer: 55; Hayes: 72; Goodwin and Trudel: 87; Haugh: 106f, 122; Morgenstern: 134, 168; Nutter: 173f; Perlis: 190; Sandewall: 206; Stein: 220; Tenenberg: 232, 252; Weber: 259; Weld: 275f] and most of the many definitions in Brown (1987) and Pylyshyn (1987). Part of the confusion about the frame problem is its family resemblance character. The best approximation to my own characterisation that I have found is Brown's (1987, v): "The frame problem... is the problem of describing in a computationally reasonable manner what properties persist and what properties change as actions are performed." This leaves out [A1], which could be added to Brown's terminology as the qualification problem.
1.3 Why is the frame problem a difficult one? Because "things are just normally quiet and uninteresting" [Hayes: 72]; because "a certain trick we have just observed is flat impossible" (Dennett 1987). "There is too much information about change to consider at any given time" [Nutter: 176]. "There is no end to the ways things might happen unexpectedly" [Hayes: 73]. This is the case, even apart from "technical" problems such as "explicit representation of concurrent events and multiagency" [Tenenberg 241].
1.4 The family of frame problems is more or less closely related to "the general problem of stating `laws of motion' which adequately describe the world" [Ford and Hayes: x]; the prediction problem [Tenenberg: 232]; the induction problem [Fetzer: 55]; "the general problem of default reasoning" [Perlis: 190]; "the larger, and uglier, counterfactual validity problem" [Stein: 225]; the "Frame* Problem" for natural language understanding, learning, and analogical reasoning [Nutter: 177]; and other problems.
1.5 I won't go into the details of trying to separate the frame problem from these other problems except to make a brief remark about the problem of induction. I tend to side with Hayes [71-76], in his exchange with Fetzer [55-70, 77-86]. The frame problem is not the problem of induction in disguise: "even if we had the laws of science given to us by an angel on tablets of bronze, the frame problem would still be there" [Hayes: 75]. The same point is made by Dennett (1987): Having access to absolutely justified true probabilistic knowledge is of little use to a robot who has to make a plan to save its spare battery if it does not know how to apply this knowledge to the task at hand. Nevertheless, the conflict about the relation between the frame problem and the induction problem is more indicative of the nature of the frame problem than a substantial substantive symptom in its own right: Philosophers tend to concentrate on [A], which is definitely related to the induction problem; Hayes concentrates on [B]; and knowledge engineers who have to deliver tomorrow concentrate on [C].
2.1 There seems to be general consensus that "a definition of the `frame problem' is harder to come by than the Holy Grail" [Stein: 219]. Still, I believe that questions [A] - [C] formulated above are quite straightforward. Nevertheless, Dennett (1987) and Hayes (1987) are right to stress that the frame problem is a deep one, not "the sort of glitch the hackers will sort out by themselves" (Hayes 1987), "of interest mainly to a fringe group" (McDermott 1987). Perhaps the problem is even deeper than they think.
2.2 The very difficulty of formulating it illustrates the frame problem: The frame problem is a special case of the PROBLEM OF COMPLETE DESCRIPTION (PCD). It is, in general, not possible to specify the necessary and sufficient conditions for something: not for the style of a work of an artist, not for the application of a concept or a rule, not for the occurrence of a particular event. Of course, it is possible to propose conventional definitions specifying necessary and sufficient conditions for, say, the use of a word, but we cannot step outside these definitions and give definitions for all the words that are used in the definitions (or the metalanguage). There are of course physical laws which are said to relate events in a necessary way. But laws (or other universal statements) cannot be applied to concrete events without the addition of unspecified ceteris paribus conditions.
2.3 The problem is not only that we don't know HOW to give a complete description (of, say, what is relevant for a particular action in a particular situation in view of a particular goal). We really don't even know what we mean by "giving a complete description."
2.4 The problem of giving a complete description has lurked behind the frame problem from its very inception in 1969 when the complete state of the universe at an instant of time was invoked by McCarthy and Hayes to solve it [Fetzer: 78]; and implicit or "intuitive" awareness of it can be found in many places in Ford & Hayes (1991): "Haugh, Morgenstern, Tenenberg, and Weld [all four are contributors to the volume] each point out that there is an implicit assumption that the agent doing the reasoning has complete knowledge of all the relevant facts" [Ford and Hayes: xii]. "Typical proposals assume omniscience about such things as successful action attempts, causal laws, `intervening' events, fact changes, 'motivated' event occurrences, and `potential causes' [Haugh: 105]. "The everyday world... is too complex for any creature to fully axiomatize its behavior" [Perlis: 191]; "humans do not solve the general problems of relevance and change, because they are unsolvable" [Nutter: 176]. "Approaches that depend on the ability to enumerate the infinite number of qualifications are doomed to failure" [Weld: 277]. "[I]t is notoriously impossible to list all the possible but unusual conditions that might obtain while being consistent with a simple description of a situation" [Hayes: 73]. (Cf also [Fetzer: 57, 62; Perlis: 191; Tenenberg: 235f; Weber: 263].) It is rare to find an explicit denial of the PCD. An example is Lenat and Feigenbaum (1991: 246) who exclaim: "one need never IN PRINCIPLE throw up one's hands and say `you just had to be there, I can't describe it!'"
3.1 A theoretical solution to the frame problem in the sense of providing and manipulating a complete description is impossible. But what about a practical solution? Ordinary human beings don't seem to suffer very much, if at all, from the frame problem: "people in their everyday thinking DO solve the frame problem" [Hayes: 72; cf Fetzer: 80; Nutter: 172].
3.2 Broadly speaking, there are three ways of dealing with the PCD in a pragmatic way. The first approach is to deny it (the ostrich policy). This view cannot be refuted because all problems encountered in solving it are simply relegated "to the proverbial FUTURE WORK category" [Etherington, Kraus, and Perlis: 52]. The second approach is to recognise it, after a fashion, but think that one can break out of it by using heuristics or a panacea like relevance or salience. The third approach is to recognise the PCD but assume that it does not exist for specific domains.
3.3 The ostrich approach is best illustrated with some straight quotations (in each case the first quotation is from the introduction or summary of the contribution, the second from the discussion or conclusion).
3.31 Morgenstern: "we show how an existing nonmonotonic temporal logic, Motivated Action Theory, can be extended to handle both problems"  but "we cannot express problems in which agents plan to combine their partial knowledge in order to perform some action" .
3.32 Etherington, Kraus, and Perlis: "a proper foundation for the frame problem must rest on a theory of nonmonotonic reasoning" , but "[w]e are not proposing to present an adequate treatment of the general [frame] problem but merely illustrate that our approach can avoid difficulties associated with indeterminate clippings" .
3.33 Haugh: "A particular situation-calculus-type theory... is presented... that solves the frame problem without omniscience assumptions"  but "[t]he particular formulation presented... will require some extensions before it will fully constitute such a solution. In particular, it will need extensions to handle ramifications, event-event causation, continuous change, and the qualification problem" .
3.4 Various "heuristics" have been proposed to permit a big leap forward, for example, "to simply minimize unjustified changes" [Haugh: 115; cf Morgenstern: 152], but this presupposes the solution of the PCD [cf Fetzer: 60; Haugh: 106, 122; Tenenberg: 237; Weber: 260-264]. It has been further suggested that the frame problem can be reduced "to the problem of choosing the appropriate reference class" [Tenenberg: 245; cf Fetzer: 62; Goodwin and Trudel: 95; Tenenberg: 231], but this merely pushes the problem ahead: How do we determine "the APPROPRIATE reference class for the probability assertions of interest" [Tenenberg: 253, emphasis added]? More seriously, such approaches appeal to our intuitions about what is appropriate, justified, etc. This is question begging, because one way of formulating the frame problem is as the problem of how to model our intuitions. Invoking something's having to be "appropriate" [Perlis: 189; Tenenberg: 231, 245, 253; Weld: 275, 283], "relevant" [Ford and Hayes: xii; Fetzer: 62, 80; Nutter: 182; Stein: 220ff; Weber: 269], "salient" [Nutter: 183], or "intuitive" for that matter, is useless as a contribution to solving the frame problem. The problem is just pushed ahead.
3.5 Consider Nutter, who writes: "The key issues in dealing with the Frame Problem and with frame problems in general are neither qualification nor ramification nor persistence, neither uncertainty nor belief revision nor causal relevance, neither time nor logic nor including enough information... The key issues are relevance, salience, and a rich enough sense of context, and the key mechanism is focus of attention" [175f]. But at the end of his chapter he says: "The primary untouched issue here is how our system decides what initial nodes and arc types to put into the context. This is a general problem for AI which surfaces over and over... It would be difficult to overestimate its complexity" . Although it has been said that "Fodor misuses the term `frame problem' in at least three different ways" (Hayes 1987), Fodor (1987) is perhaps at least partly right when he writes that "the frame problem is [that of] saying what a `real property' is." What is at issue here is that the choice of "the right primitives" is not a trivial matter but the core of the issue. As Dunn (1989) correctly points out: "relevance logic can no more tell us which are the relevant atomic properties, than can classical logic tell us which are the true atomic propositions... it is up to the database creator to decide which predicates are relevant." But how is the database creator to do this [cf Goodwin and Trudel: 90; Sandewall: 212; Weld: 276]?
3.6 The third way of dealing with the PCD is to dispute "The Myth of Domain-Independent Persistence" [Weber: 259]. This is the approach of Weber, who says that the "omniscience assumption is only valid in very restricted domains" [263; cf Fetzer: 60-63]. The appeal to "context limitation through salience" [Nutter: 186] might also be taken as a form of domain restriction. In practice, domain restriction and heuristics are usually combined. For example, Holland, Holyoak, Nisbett and Thagard (1986), responding to Fodor's worries, write: "a processing mechanism of the sort we favor circumvents the problem of the potential relevance of everything in the knowledge store by PRAGMATICALLY SELECTING limited areas of information to explore... By tending to fire the strongest and most GOAL-APPROPRIATE rules, a constrained search through the space of RELEVANT information can be carried out." It's the phrases that I've emphasised that worry me (and would, I presume, worry Fodor as well). But most practical AI researchers would not find much wrong here and would conclude with Lormand (1990), after discussing views of philosophers like Dennett and Fodor on the frame problem: "why should we suppose that it is a PROBLEM?" In fact, in not seeing a problem, Lormand is making two important assumptions: [i] the choice of primitive terms is straightforward; [ii] descriptions can be carried out independently for each domain. It is because these assumptions seem so "plausible" or "intuitively" correct that there doesn't seem to be a PCD. But these assumptions are incorrect (van Brakel 1991).
4.1 I have been rather cynical about the approaches referred to in the previous section because I think they all show insufficient awareness of the general problem of the impossibility of giving a complete description. It remains true, however, that humans do manage. How do they do so? Perhaps we have to reconsider some basic assumptions underlying all approaches to the frame problem. The assumptions are, of course, those of logicism (Kirsh 1991a):
(1) Modelling propositional knowledge and conceptualisation is essential for intelligence.
(2) Cognition can be studied separately from perception and motor output.
(3) The kinematics of knowledge is linguistic.
(4) The statics and dynamics of knowledge can be studied separately from learning, psychological development and evolution.
(5) There is one architecture.
I take it that all contributions in Ford & Hayes meet these five criteria (or at least four of them).
4.2 From such a perspective the PCD is not considered relevant. It is assumed that the frame problem can be solved in a piecemeal way. Logicists can acknowledge that, say, (2) and (4) might be disputable in principle, yet because of the primacy of the linguistic character of knowledge theirs is the best approach to the problem. But perhaps the ways humans (or evolution for that matter) have solved the frame problem in a practical sense do not live up to this kind of modular and piecemeal approach. Perhaps the piecemeal approach works, at least for a while, in some areas, but not for "solving" human behaviour. Perhaps "[t]he frame problem is an artifact of viewing perception as input to cognition, suggesting that input is predigested and exists apart from the process of behaving, and that memory is a special storage for descriptions of the world which are matched against rules that describe behaviors" (Clancey 1989: n18).
4.3 What about other approaches? First consider physicalism. Even if we allow externalism (what philosophers of mind call "wide content"), there MUST be a physical explanation of how humans do it. There MUST exist at least one practical solution to the frame problem, because humans use it. But "`common sense' (or `ordinary') knowledge is not enough to provide [it]... What is required is the kind of knowledge we only possess when we have discovered those causal laws whose operation governs the processes and outcomes concerning us" [Fetzer: 58]. This is also the argument of Ross (1990), whose reasoning is as follows: Induction works in practice, but we can't formalise it. Everything that is not completely deductive may accordingly fail to be formalizable. Even when something is deductive, in the general case, not everything that is true can be proved. Hence, as it were, theoretical solutions are excluded a priori.
4.4 But, to repeat, induction works in practice. So, by analogy, there must be a practical solution to the frame problem. During human evolution, "nature" has hit on a practical solution to the frame problem. We have to find the PHYSICAL description of how humans do it: "What we must do as AI researchers, then, is reproduce our structural architecture" (Ross 1990). Of course, this "solution" is of no direct practical use for AI (perhaps it even denies the relevance of AI). And there is a further problem: the distinction between a complete physical description and a complete commonsense description. It is not self-evident that there is a type-type correlation between physical and commonsense descriptions of what is going on.
4.5 What about connectionism? At first blush it seems better suited to solving the frame problem: it might provide a more natural connection to perceptual input and to getting knowledge by learning. Also the "old problem of how to retrieve relevant information is transformed by the realization that it does not have to be `retrieved'" (Churchland 1989: 195). However, it seems to me that current work on connectionist models makes the same assumptions as logicism about separate domains characterised by "natural" primitive terms. (Think of nets, taught or self-taught, that learn to separate cats and dogs.)
5.1 A proper assessment of the holism issue is crucial to evaluating the possibility of practical solutions to the frame problem. Here I can only set a few pointers. First, the subworlds of separate domains are not the same as isolated physical systems that can later be put together using a few rules to make the whole. Subworlds are local "representations" of a whole they presuppose (Dreyfus and Dreyfus 1990).
5.2 Second, it is often said that daily knowledge is extensive, but not deep. This is a mistake, because the cognitive and subcognitive levels cannot be separated. There is no a priori way to formalise judgements of association strengths, neologisms, jokes, epitaphs, etc. It is only good enough if it is identical to a complete human being (French 1989). (Think of a robot with eyes on its knees.)
5.3 Third, there is a fundamental difference between knowing a part of something and partly knowing something. As an example, consider Maloney (1991: 57): "FULLY understanding any given concept is holistic and requires knowing how that concept fits in with other concepts we may have. But that should not blind us to the fact that understanding a concept is a matter of degree." This is wrong, however. Maloney considers the complete description of a concept as something that is given, passing over variations across time, conversations, or persons. He compares the "limited knowledge" of scripts with the limited knowledge of small children (about chairs, for example) but he ignores the fact that children's knowledge of chairs is built up starting from "intimate" relations with chairs. This relational knowledge has little to do with the descriptive knowledge in a "chair"-script. He also passes over the fact that knowledge of chairs, as acquired by children, is part of a moral form of life (in which chairs play some role).
5.4 The only piecemeal approach to holism seems to be that of Brooks (1991). He argues that it is better to use the world as its own model. Human intelligence is too "complicated" for it to be possible to cut it up in the right pieces to study and model. His "mobots" consist of several layers which operate in parallel; each layer has its own "goal" and its own visual input, but there is no "total" observation of the environment. There is representation in the sense of covariation, but not symbolic, conceptual representation. The lingering questions are, of course: Will this bring us anything more than the intelligence of a spider? What about learning? How will the evolutionary jump to conceptual knowledge be made (cf Kirsh 1991b)? But these mobots really exist in their world.
6.1 All variants of the frame problem are special cases of the problem of complete description (PCD): It is impossible to give the necessary and sufficient conditions for something (e.g. for the occurrence of an event, the definition of a concept).
6.2 It is a mistake to talk about the frame problem as primarily concerning acting, reasoning, or justifying; it's a problem of description in the first place. (The notorious robots who didn't manage to save their spare batteries were not suffering from the frame problem. Perhaps their designers were.)
6.3 There is no theoretical solution to the frame problem. The quest for a theoretical solution presupposes the possibility of a complete description. The latter idea is incoherent, but this is of little relevance for AI: Humans also manage without a theoretical solution.
6.4 It is a mistake to suggest that folk knowledge is broad but not deep. It is deep in the sense of its holistic relation to the subcognitive level. This undermines the theoretical intelligibility of a piecemeal approach. Domain-restricted theoretical solutions to the frame problem are not possible because each part presupposes the whole.
6.5. The extent to which a practical solution might be feasible (in certain contexts) increases, in principle, in the direction: logicism, logicism + learning, connectionism, mobotics. Practical "total" solutions cannot be excluded: new forms of (artificial) life are possible. Practical instruments are of course always possible. Whether they are useful depends on the form of life in which they are put to use.
Boden, M.A. (ed.) (1990) The Philosophy of Artificial Intelligence. Oxford: Oxford University Press.
Brooks, R.A. (1991) Intelligence without representation. Artificial Intelligence 47: 139-159.
Brown, F.M. (ed.) (1987) The Frame Problem in Artificial Intelligence. Los Altos CA: Kaufmann.
Churchland, P.M. (1989) A Neurocomputational Perspective. Cambridge MA: The MIT Press.
Clancey, W.J. (1991) The frame of reference problem in the design of intelligent machines. In Architectures for Intelligence: The Twenty-Second Carnegie Symposium on Cognition (K. vanLehn, ed.). Hillsdale NJ: Lawrence Erlbaum, pp. 357-424.
Dennett, D. (1987) Cognitive wheels: The frame problem of AI. In: Pylyshyn (1987) 41-64; also in Boden (1990) 147-170.
Dreyfus, H.L. and S.E. Dreyfus (1990) Making a mind versus modelling the brain: Artificial intelligence back at a branch-point. in Boden (1990) 309-333.
Dunn, J.M. (1989) The frame problem and relevant predication. In: Knowledge Representation and Defeasable Reasoning (H. Kyburg et al., eds.). Dordrecht: Kluwer.
Fodor, J.A. (1987) Modules, frames, fridgeons, sleeping dogs, and the music of spheres. In: Pylyshyn (1987) 139-149.
Ford, K.M. and P.J. Hayes (1991) Reasoning Agents in a Dynamic World: The Frame Problem, Greenwich: JAI Press.
French, R.M. (1990) Subcognition and the limits of the Turing test. Mind 99: 53-65.
Hayes, P.J. (1987) What the frame problem is and isn't. In: Pylyshyn (1987) 123-138.
Hayes, P.J. (1992) Summary of "Reasoning Agents in a Dynamic World: The Frame Problem" (Ford & Hayes 1991, Eds.) PSYCOLOQUY 3(59) frame-problem.1
Holland, J.H., K.J. Holyoak, R.E. Nisbett and P.T. Thagard, Induction: Processes of Inference, Learning, and Discovery. Cambridge MA: The MIT Press.
Kirsh, D. (1991a) Foundations of AI: the big issues. Artificial Intelligence 47: 3-30.
Kirsh, D. (1991b) Today the earwig, tomorrow man?, Artificial Intelligence 47: 161-184.
Lenat, D.B. and E.A. Feigenbaum (1991) On the thresholds of knowledge. Artificial Intelligence 47: 185-250.
Lormand, E. (1990) Framing the frame problem. Synthese 82: 353-374.
Maloney, J.C. (1990) The Mundane Matter of Mental Language. Cambridge: Cambridge University Press.
McDermott, D. (1987) We've been framed: Or, why AI is innocent of the frame problem. In: Pylyshyn (1987) 113-122.
Pylyshyn, Z.W. (ed.) (1987) The Robot's Dilemma. Norwood NJ: Ablex Publishing Co.
Ross, D. (1990) Against positing central systems in the mind. Philosophy of Science 57: 297-312.
Van Brakel, J. (1991) Meaning, prototypes and the future of cognitive science. Minds and Machines 1: 233-257.