Stanford Encyclopedia of Philosophy
This is a file in the archives of the Stanford Encyclopedia of Philosophy.

The Frame Problem

First published Mon 23 Feb, 2004

To most AI researchers, the frame problem is the challenge of representing the effects of action in logic without having to represent explicitly a large number of intuitively obvious non-effects. To many philosophers, the AI researchers' frame problem is suggestive of a wider epistemological issue, namely whether it is possible, in principle, to limit the scope of the reasoning required to derive the consequences of an action.

1. Introduction

The frame problem originated as a narrowly defined technical problem in logic-based artificial intelligence (AI). But it was taken up, in an embelished and modified form, by philosophers of mind, and given a wider interpretation. The tension between its origin in the laboratories of AI researchers and its treatment at the hands of philosophers has engendered an interesting, and sometimes heated, debate. To gain an understanding of the issues, this article will begin with a look at the frame problem in its technical guise. Some of the ways in which philosophers have re-interpreted the problem will then be examined. Finally, since the philosophical issue has generated little new writing in recent years, and the technical problem has been largely solved, it will be possible to attempt a retrospective assessment of the relevance and importance of the frame problem today.

2. The Frame Problem in Logic

Put succinctly, the frame problem in its narrow, technical form is this (McCarthy & Hayes 1969). Using mathematical logic, how is it possible to write formulae that describe the effects of actions without having to write a large number of accompanying formulae that describe the mundane, obvious non-effects of those actions? Let's take a look at an example. The difficulty can be illustrated without the full apparatus of formal logic, but it should be borne in mind that the devil is in the mathematical details. Suppose we write two formulae, one describing the effects of painting an object and the other describing the effects of moving an object.

  1. Colour(x,c) holds after Paint(x,c)
  2. Position(x,p) holds after Move(x,p)

Now, suppose we have an initial situation in which Colour(A,Red) and Position(A,House) hold. According to the machinery of deductive logic, what then holds after the action Paint(A,Blue) followed by the action Move(A,Garden)? Intuitively, we would expect Colour(A,Blue) and Position(A,Garden) to hold. Unfortunately, this is not the case. If written out more formally in classical predicate logic, using a suitable formalism for representing time and action such as the situation calculus (McCarthy & Hayes 1969), the two formulae above only license the conclusion that Position(A,Garden) holds. This is because they don't rule out the possibility that the colour of A gets changed by the Move action.

The most obvious way to augment such a formalisation so that the right common sense conclusions fall out is to add a number of formulae that explicitly describe the non-effects of each action. These formulae are called frame axioms. For the example at hand, we need a pair of frame axioms.

  1. Colour(x,c) holds after Move(x,p) if Colour(x,c) held beforehand
  2. Position(x,p) holds after Paint(x,c) if Position(x,p) held beforehand

In other words, painting an object will not affect its position, and moving an object will not affect its colour. With the addition of these two formulae (written more formally in predicate logic), all the desired conclusions can be drawn. However, this is not at all a satisfactory solution. Since most actions do not affect most properties of a situation, in a domain comprising M actions and N properties we will, in general, have to write out almost MN frame axioms. Whether these formulae are destined to be stored explicitly in a computer's memory, or are merely part of the designer's specification, this is an unwelcome burden.

The challenge, then, is to find a way to capture the non-effects of actions more succinctly in formal logic. What we need, it seems, is some way of declaring the general rule-of-thumb that an action can be assumed not to change a given property of a situation unless there is evidence to the contrary. This default assumption is known as the common sense law of inertia. The (technical) frame problem can be viewed as the task of formalising this law.

The main obstacle to doing this is the monotonicity of classical logic. In classical logic, the set of conclusions that can be drawn from a set of formulae always increases with the addition of further formulae. This makes it impossible to express a rule that has an open-ended set of exceptions, and the common sense law of inertia is just such a rule. For example, in due course we might want to add a formula that captures the exception to Axiom 3 that arises when we move an object into a pot of paint. But our not having thought of this exception before should not prevent us from applying the common sense law of inertia and drawing a wide enough set of (defeasible) conclusions to get off the ground.

Accordingly, researchers in logic-based AI have put a lot of effort into developing a variety of non-monotonic reasoning formalisms, such as circumscription (McCarthy 1986), and investigating their application to the frame problem. None of this has turned out to be at all straightforward. One of the most troublesome barriers to progress was highlighted in the so-called Yale shooting problem (Hanks & McDermott 1987), a simple scenario that gives rise to counter-intuitive conclusions if naively represented with a non-monotonic formalism. To make matters worse, a full solution needs to work in the presence of concurrent actions, actions with non-deterministic effects, continuous change, and actions with indirect ramifications. In spite of these subtleties, a number of solutions to the technical frame problem now exist that are adequate for logic-based AI research. Although improvements and extensions continue to be found, it is fair to say that the dust has settled, and that the frame problem, in its technical guise, is more-or-less solved (Shanahan 1997).

3. The Epistemological Frame Problem

Let's move on now to the frame problem as it has been re-interpreted by various philosophers. The first significant mention of the frame problem in the philosophical literature was made by Dennett (1978, p.125). The puzzle, according to Dennett, is how “a cognitive creature … with many beliefs about the world” can update those beliefs when it performs an act so that they remain “roughly faithful to the world”? In The Modularity of Mind, Fodor steps into a roboticist's shoes and, with the frame problem in mind, asks much the same question: “How … does the machine's program determine which beliefs the robot ought to re-evaluate given that it has embarked upon some or other course of action?” (Fodor 1983, p.114).

At first sight, this question is only impressionistically related to the logical problem exercising the AI researchers. In contrast to the AI researcher's problem, the philosopher's question isn't expressed in the context of formal logic, and doesn't specifically concern the non-effects of actions. In a later essay, Dennett acknowledges the appropriation of the AI researchers' term (1987). Yet he goes on to reaffirm his conviction that, in the frame problem, AI has discovered “a new, deep epistemological problem — accessible in principle but unnoticed by generations of philosophers”.

The best way to gain an understanding of the issue is to imagine being the designer of a robot that has to carry out an everyday task, such as making a cup of tea. More particularly, for the frame problem to be neatly highlighted, we must confine our thought experiment to a certain class of robot designs, namely those based on explicitly stored, sentence-like representations of the world. Obviously, the AI researchers who tackled the original frame problem in its narrow, technical guise were working under this constraint. But philosophers sympathetic to a computational theory of mind — who suppose that mental states comprise sets of propositional attitudes and mental processes are forms of inference over the propositions in question — will also feel at home with such an assumption.

Now, suppose the robot has to take a tea-cup from the cupboard. The present location of the cup is represented as a sentence in its database of facts alongside those representing innumerable other features of the ongoing situation, such as the ambient temperature, the configuration of its arms, the current date, the colour of the tea-pot, and so on. Having grasped the cup and withdrawn it from the cupboard, the robot needs to update this database. The location of the cup has clearly changed, so that's one fact that demands revision. But which other sentences require modification? The ambient temperature is unaffected. The location of the tea-pot is unaffected. But if it so happens that a spoon was resting in the cup, then the spoon's new location, inherited from its container, must also be updated.

The epistemological difficulty discerned by the philosophers at this point is this. How does the robot limit the scope of the propositions it must reconsider in the light of its actions? In a sufficiently simple robot, this doesn't seem like much of a problem. Surely the robot can simply examine its entire database of propositions one-by-one and work out which require modification. But if we imagine that our robot has near human-level intelligence, and is therefore burdened with an enormous database of facts to examine every time it so much as spins a motor, such a strategy starts to look computationally intractable.

In AI, this has been dubbed the computational aspect of the frame problem (McDermott 1987). This is the question of how to compute the consequences of an action without the computation having to range over the action's non-effects. The solution to the computational aspect of the frame problem adopted in most symbolic AI programs is some variant of what McDermott calls the “sleeping dog” strategy (McDermott 1987). The idea here is that not every part of the data structure representing an ongoing situation needs to be examined when it is updated to reflect a change in the world. Rather, those parts that represent facets of the world that have change are modified, and the rest is simply left as it is (following the dictum “let sleeping dogs lie”).

However, computational complexity is not the root of the genuine philosophical puzzle. For the epistemological question is not so much how the computational challenge can be met, but rather how the robot could ever be sure it had sufficiently thought through the consequences of its actions to know that it hadn't missed anything important. Only then is it in a position to safely apply the “common sense law of inertia” andassume the rest of the world is untouched. This epistemological problem coincides with the computational problem in the restrictive context of a representational formalism that is computationally decidable, such as propositional logic. But if we need the representational power of first-order predicate logic to build our robot — a fairly conservative assumption — then the epistemological issue remains separate.

Fodor suggestively likens this to “Hamlet's problem: when to stop thinking” (Fodor 1987, p.140). The frame problem, he claims, is “Hamlet's problem viewed from an engineer's perspective”. But to warrant the award of depth, an epistemological problem must at least resist the most obvious attempts to resolve it. In the case of Hamlet's problem, the obvious appeal is to the notion of relevance. Only certain properties of a situation are relevant in the context of any given action, and consideration of the action's consequences can be conveniently confined to those.

At this point, we have pushed the frame problem into familiar territory for Fodor. For the difficulty now is one of determining what is and isn't relevant. Fodor's claim is that when it comes to circumscribing the consequences of an action, just as in the business of theory confirmation in science, anything could be relevant (Fodor 1983, p.105). There are no a priori limits to the properties of the ongoing situation that might come into play. Accordingly, in his modularity thesis, Fodor uses the frame problem to bolster the view that the mind's central processes — those that are involved in fixing belief — are “informationally unencapsulated”, meaning that they can draw on information from any source (Fodor 1983; Fodor 2000).

There is a tempting but fallacious argument lurking here to the effect that a process must be informationally encapsulated to be computationally tractable. But you only have to consider the effectiveness of Internet search engines to see that, thanks to clever indexing techniques, this is not the case. Submit any pair of seemingly unrelated keywords (such as “banana” and “mandolin”) to a Web search engine, and in a fraction of a second it will identify every web page, in a database of several billion, that mentions those two keywords (now including this page, no doubt). But this is not the issue at hand. The real issue, to reiterate the point, is one of relevance. A process might indeed be able to index into everything the system knows about, say, bananas and mandolins, but the purported mystery is how it could ever work out that bananas and mandolins were relevant to its reasoning task in the first place.

4. The Metaphysics of Common Sense Inertia

An additional dimension to the frame problem is uncovered in (Fodor 1987), where the metaphysical justification for the common sense law of inertia is challenged. Although Fodor himself doesn't clearly distinguish this issue from other aspects of the wider frame problem, it appears on examination to be a separate philosophical conundrum. Here is the argument. As stated above, solutions to the logical frame problem developed by AI researchers typically appeal to some version of the common sense law of inertia, according to which properties of a situation are assumed by default not to change as the result of an action. This assumption is supposedly justified by the very observation that gave rise to the logical frame problem in the first place, namely that most things don't change when an action is performed or an event occurs.

According to Fodor, this metaphysical justification is unwarranted. To begin with, some actions change many, many things. Those who affirm that painting an object has little or no effect on most properties of most of the objects in the room are likely to concede that detonating a bomb actually does affect most of those properties. But a deeper difficulty presents itself when we ask what is meant by “most properties”. What predicates should be included in our ontology for any of these claims about “most properties” to fall out? To sharpen the point, Fodor introduces the concept of a “fridgeon”. Any particle is defined as a fridgeon at a given time if and only if Fodor's fridge is switched on at that time. Now, it seems, the simple act of turning Fodor's fridge on or off brings about an astronomical number of incidental changes. In a universe that can include fridgeons, can it really be the case that most actions leave most things unchanged?

The point here is not a logical one. The effect on fridgeons of switching Fodor's fridge on and off can concisely be represented without any difficulty (Shanahan 1997, p.25). Rather, the point is metaphysical. The common sense law of inertia is only justified in the context of the right ontology, the right choice of objects and predicates. But what is the right ontology to make the common sense law of inertia work? Clearly, fridgeons and the like are to be excluded. But what metaphysical principle underpins such a decision?

These questions and the argument leading to them are very reminiscent of Goodman's treatment of induction (Goodman 1954). Goodman's “new riddle of induction”, commonly called the grue paradox, invites us to consider the predicate grue, which is true before time t only of objects that are green and after time t only of objects that are blue. The puzzle is that every instance of a green emerald examined before time t is also an instance of a grue emerald. So, the inductive inference that all emeralds are grue seems to be no less legitimate than the inductive inference that all emeralds are green. The problem, of course, is the choice of predicates. Goodman showed that inductive inference only works in the context of the right set of predicates, and Fodor demonstrates much the same point for the common sense law of inertia.

An intimate relationship of a different kind between the frame problem and the problem of induction is proposed by Fetzer (1991), who writes that “The problem of induction [is] one of justifying some inferences about the future as opposed to others. The frame problem, likewise, is one of justifying some inferences about the future as opposed to others. The second problem is an instance of the first.” This view of the frame problem is highly controversial, however (Hayes 1991).

5. The Frame Problem Today

The frame problem generated a great deal of work in logic-based artificial intelligence in the late 1980s and early 1990s, and its philosophical implications were under closest scrutiny at around the same time. Although the subject still inspires occasional publications at the start of the 21st Century, it hasn't been visible at the top of the academic agenda for several years. The importance each thinker accords to the frame problem today will depend on their stance on wider matters.

Although it has been convincingly argued that it arises even in a connectionist setting (Haselager & Van Rappard 1998), the frame problem inherits much of its philosophical significance from the so-called computational theory of mind, the presuppositions of which have been under vigorous attack for some time (Clark 1997). Despite this, many philosophers of mind, alongside the likes of Fodor and Pylyshyn, still subscribe to the view that human mental processes consist chiefly of inferences over a set of propositions, and that those inferences are carried out by some form of computation. To any such philosopher, the epistemological frame problem is a genuine threat.

However, even adherents to the computational theory of mind have to idealise the inference involved for the frame problem to carry its full weight. After all, humans might be more clever than today's robots, but they still make mistakes (McDermott 1987). People often fail to foresee every consequence of their actions even though they lack none of the information required to derive those consequences, as any novice chess player can testify. Fodor asserts that “the frame problem goes very deep; it goes as deep as the analysis of rationality” (Fodor 1987). But the analysis of rationality can accommodate the boundedness of the computational resources available to derive relevant conclusions (Simon 1957; Russell & Wefald 1991; Sperber & Wilson 1996). Because it sometimes jumps to premature conclusions, bounded rationality is logically flawed, but no more so than human thinking. So, with the account of rationality on which it depends suitably modified to allow resource-boundedness, the computational theory of mind can be relieved of the frame problem, even though the epistemological problem remains for idealised rationality.

In (Fodor 2000, Ch. 2), we find a response to an argument which is superficially similar to the one above, and needs to be distinguished from it. Fodor points out that appealing to human limitations to justify the imposition of a heuristic boundary to the kind of information available to an inferential process is not a viable approach to the frame problem. This is because it neglects the issue of how the heuristic boundary is to be drawn, which is to say it fails to address the heart of the problem, namely how to determine what is and isn't relevant to the inferential process. But the heuristic imposition of a boundary is not to be confused with the recommended compromise solution of adopting bounded rationality. An inferential process that is computationally bounded is not necessarily informationally encapsulated.

In artificial intelligence, a variety of workable solutions to the logical frame problem have been developed, and it is no longer considered a serious obstacle even for those working in a strictly logic-based paradigm (Shanahan, 2002). It's worth noting that logically-minded AI researchers can consistently retain their methodology and yet reject the computational theory of mind, to the extent that they view their products purely as engineering. But irrespective of their opinion of the computational theory of mind, such AI researchers, like their philosopher counterparts, have to resort to bounded rationality to escape the epistemological frame problem.  On the other hand, for an AI researcher working outside the paradigm of symbolic representation altogether, the logical frame problem simply doesn't feature in day-to-day investigations.

Perhaps the lasting philosophical legacy of the frame problem is that it has helped draw attention to a cluster of issues relating to informational encapsulation, or what Fodor calls “isotropy”. A process is isotropic if there is no a priori boundary to what information is relevant to it. Indeed, in recent writing, Fodor himself uses the term “frame problem” in the context of all isotropic processes, not just those to do with inferring the consequences of change (Fodor 2000 Ch.2). Now, it's clear that idealised rationality is isotropic, in this sense. The epistemological frame problem is one consequence of this, but may be amenable to a compromise solution, as we have seen. It has also been suggested that isotropy is damaging to the so-called theory theory of folk psychology (Heal 1996). For Heal, this lends support to the rival simulation theory, but Wilkerson (2001) argues that isotropy is a problem for both accounts of folk psychology. Either way, some version of the compromise solution may be applicable here too.

By contrast, as Fodor says, analogical reasoning is “isotropy in the purest form: a process which depends precisely upon the transfer of information among cognitive domains previously assumed to be irrelevant” (Fodor 1983, p.105). No obvious compromise solution will work here. Arguably, a capacity for analogical and metaphorical thinking — a talent for creatively transcending the boundaries between different domains of understanding — is the source of human cognitive prowess (Lakoff & Johnson 1980; Mithen 1996). So the isotropy of analogical reasoning is potentially very troublesome, and especially so in the context of a highly modular theory of mind (Carruthers 2003).

Yet it may turn out that the brain incorporates a solution to the problem of isotropy in the form of an attention mechanism that limits access to a global workspace, which in turn broadcasts information to numerous otherwise independent brain processes (Baars 1988). Indeed, it's hard to assess the true force of arguments from isotropy. As shown by work on the logical frame problem — once thought by many to be an incurable symptom of isotropy — armchair speculation about cognition doesn't always reflect the real issues facing an engineer trying to build it into a machine or a neuroscientist investigating its basis in the biological brain.

Bibliography

Other Internet Resources

Related Entries

artificial intelligence: logic and | mental representation | mind: computational theory of