Frame problem in AI: why robots struggle with what stays the same

The frame problem in AI is the puzzle of how a machine can know what does not change when it acts. If a robot opens a door, it is obvious to you that the light stays as it was. To a program that reasons in plain logic, nothing says so unless someone writes it down. This post sets out the problem as Wikipedia's article on it describes it, the example everyone uses, the fixes that were proposed and the wider question it grew into.

If you like to explore AI ideas as a story, Contain ASI is a story strategy game for 1 to 4 players that runs in your browser, where you try to keep four fictional AI labs from crossing into recursive self-improvement.

What is the frame problem?

Wikipedia describes the frame problem as an issue with using first-order logic to express facts about a robot in the world. Describing a robot's state in traditional first-order logic takes many axioms, rules that simply say things in the environment do not change arbitrarily. The article's example is a "block world" from Hayes with rules about stacking blocks. To make inferences about it, you need extra axioms, such as that a block cannot change position unless it is physically moved.

So the frame problem is the problem of finding adequate collections of axioms for a viable description of a robot environment. The word "frame" refers to everything an action leaves alone.

The article credits John McCarthy and Patrick J. Hayes with defining it in their 1969 article, Some Philosophical Problems from the Standpoint of Artificial Intelligence. That paper, and many after it, used the formal problem as a starting point for wider talk about how hard knowledge representation is for AI. Issues such as rational default assumptions, and what people count as common sense, came into it.

The door and the light

The problem shows up even in a tiny world. Take a door that can be open or closed and a light that can be on or off. Because these can change over time, the article writes them as conditions that depend on time, called fluents.

Say the door is closed and the light is off at time 0, and the door is opened at time 1. You can write all of that in logic: the starting state, and the effect of the action of opening the door.

The catch, in the article's words, is that these formulae do not suffice to correctly draw consequences. A world where the light switched on when the door opened is also consistent with them. Saying only which conditions an action changes does not entail that every other condition is unchanged.

Frame axioms and why they pile up

The obvious repair is to add what the article calls frame axioms. They state outright that every condition an action does not affect stays the same. Here, a frame axiom would say that opening the door leaves the light's status as it was.

The trouble is the count. One such axiom is needed for every pair of an action and a condition where the action does not affect the condition. A robot with many actions and many conditions would need a great number of these, almost all of them saying "nothing happened here". The real aim is to describe a changing world without writing out the frame axioms by hand.

The fixes people proposed

McCarthy's own answer was to assume that a minimal amount of change has occurred, which he formalized with a framework called circumscription. The article notes that the Yale shooting problem showed this is not always correct. Other solutions followed, and the article says that by the end of the 1980s the frame problem as McCarthy and Hayes defined it was solved. The term lived on, partly for the same problem in other settings, such as concurrent actions, and partly for related problems.

The article walks through several solutions. Here is each in one line:

• Fluent occlusion (Erik Sandewall): track whether the last action could affect a condition. An "occluded" condition has permission to change; every other one must obey inertia.
• Predicate completion: similar, but the extra predicates mark change, not permission to change, and a condition changes only if its change predicate is true.
• Successor state axioms (Ray Reiter): one axiom per condition, saying it is true after an action if the action makes it true, or it was true and the action does not make it false.
• Fluent calculus and event calculus: represent states or fluents as terms, with the event calculus using a single axiom for the law of inertia.
• Default logic and answer set programming: write the default that things stay as they are as a rule, which the article calls the commonsense law of inertia.
• Separation logic: a frame rule lets a specification about a piece of code ignore memory it never touches.
• Action description languages: they elude the problem, which only appears if a specification is translated into logic.

Not every fix was accepted

The article gives an example of the disagreement. The default that "everything is presumed to remain in the state in which it is" is credited to Leibniz in about 1679. Reiter wrote it in default logic. Steve Hanks and Drew McDermott argued from their Yale shooting example that this solution is unsatisfactory. Hudson Turner then showed that it works correctly with appropriate additional postulates.

So even a problem declared solved in a formal sense kept producing argument about which formalism is the right one. Our post on Moravec's paradox is another case where something trivial for a person turned out to be hard to build into a machine.

Where it shows up in real code

One place the idea has paid off is in checking programs. Separation logic is a way to reason about computer programs with before-and-after specifications. Its frame rule lets you add a description of memory outside what the code touches, so a specification can focus only on the code's footprint. The article's example is code that sorts one list and so does not unsort a separate list, without the specification mentioning that other list at all.

The article says that automating the frame rule led to significant gains in scalability for automated reasoning about code. It has been deployed industrially on codebases with tens of millions of lines. It also notes some similarity between this solution and the fluent calculus.

The wider philosophical version

In philosophy, the article says, the frame problem was construed more broadly. It became the problem of limiting the beliefs that have to be updated in response to actions. In the logical setting, an action is described by what it changes, with the unstated assumption that the rest, the frame, stays put.

That broader form connects to a question people ask about any reasoning agent: how does it decide what is relevant after something happens? A person does this without effort. A system with only written rules has to be given the answer, one rule at a time, or given a method that produces it.

Try it yourself: write the frame axioms for your room

This exercise takes ten minutes and shows why the problem is hard.

1. Pick a small space, such as your desk, with five things you can change: a lamp, a window, a door, a cup and a screen.
2. List four actions, such as "switch the lamp", "open the window", "lift the cup" and "close the door".
3. For each action, write what it changes. That is the easy part, and it gives you four short lines.
4. Now write a line for every action and thing it does not change, such as "lifting the cup does not change the window". Count the lines.
5. Add one more thing and one more action, and count again.

You will find that the "does not change" list grows far faster than the "changes" list. That is the frame problem in a small form, and it is why people looked for ways to state the law of inertia once instead of thousands of times.

Why it matters for thinking about AI

The article is about a logic problem, not about any current system, and it makes no claim about how today's AI behaves. What it gives you is a way to ask what a system takes for granted when it acts. Any agent that plans has to decide what stays the same, and a wrong default can cause errors even when each step looks reasonable.

If you are curious about the limits of rule-based systems, see our posts on the Chinese room argument and the symbol grounding problem. The Wikipedia article lists "Symbol grounding" among its see-also topics, next to common sense, commonsense reasoning and the qualification and ramification problems.

Frequently asked questions

What is the frame problem in simple terms?

It is the problem of telling a machine what stays the same when it acts. Saying what an action changes does not, by itself, say that everything else is unchanged.

Who defined the frame problem?

John McCarthy and Patrick J. Hayes, in their 1969 article Some Philosophical Problems from the Standpoint of Artificial Intelligence.

What is a frame axiom?

It is a rule that says a condition does not change when a given action is carried out, such as opening a door not changing a light. One is needed for each action and condition that do not affect each other.

Has the frame problem been solved?

The article says the problem as McCarthy and Hayes defined it was solved by the end of the 1980s, with several formal solutions. The name is still used for related problems, and some solutions drew objections.

Get started

If you would like to explore AI risk as fiction after the theory, play Contain ASI: a story strategy game for 1 to 4 players that runs in your browser and needs WebGL 2. Chapter 1, Before ASI, starts in January 2024 with four fictional AI labs in one race, and you try to keep every lab from crossing into recursive self-improvement before 2027. All its labs, people and events are fictional, and it is inspired by the AI 2027 scenario. It is a game, not a forecast, and it is not a course.

For the source, read Wikipedia's article on the frame problem.