The Frame Problem

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. But to many philosophers, the AI researchers' frame problem is suggestive of wider epistemological issues. Is it possible, in principle, to limit the scope of the reasoning required to derive the consequences of an action? And, more generally, how do we account for our apparent ability to make decisions on the basis only of what is relevant to an ongoing situation without having explicitly to consider all that is not relevant?

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 embellished 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 engendered an interesting and sometimes heated debate in the 1980s and 1990s. But since the narrow, technical problem is largely solved, recent discussion has tended to focus less on matters of interpretation and more on the implications of the wider frame problem for cognitive science. 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. The article will conclude with an assessment of the significance 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.

Colour(x, c) holds after Paint(x, c)

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.

Colour(x, c) holds after Move(x, p) if Colour(x, c) held beforehand

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; Lifschitz 2015).

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, 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, 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. Moreover, for the frame problem to be neatly highlighted, we must confine our thought experiment to a certain class of robot designs, namely those using explicitly stored, sentence-like representations of the world, reflecting the methodological tenets of classical AI.

The AI researchers who tackled the original frame problem in its narrow, technical guise were working under this constraint, since logic-based AI is a variety of classical AI. Philosophers sympathetic to the 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—also tend to feel at home with this prescription.

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 now discerned by philosophers is this. How could 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.

Thus, a related issue in AI 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.