# What is the frame problem in AI, and why did McCarthy and Hayes call it a problem?

Date: 2019-08-16 · Author: Robert Scales · https://guidetoartificialintelligence.com/en/learn/what-is-the-frame-problem-in-ai/

**Answer:** The frame problem, named by John McCarthy and Patrick Hayes in a 1969 paper, is the difficulty of telling a logic-based AI system what changes when an action happens without also having to tell it, one fact at a time, everything that does not change. With many actions and many facts, those "nothing else changed" statements multiply until they swamp the useful ones.

If you pick up your phone and look up a friend's number, you do not stop to confirm that you still own the phone, that your friend still lives at the same address, or that the kitchen is still the same color. You simply know that looking something up does not change those things. A computer reasoning with strict logic does not know that. Unless it is told, it has no grounds to assume anything survives an action. That gap is the frame problem.

## Where the name comes from

The term first appears in a long paper by John McCarthy and Patrick J. Hayes, "Some Philosophical Problems from the Standpoint of Artificial Intelligence." It was published in 1969 in *Machine Intelligence 4*, a volume edited by Bernard Meltzer and Donald Michie and printed by Edinburgh University Press. McCarthy, one of the founders of the field, worked at Stanford University.

The paper's starting point is that a program meant to act intelligently in the world must carry some general picture of that world, and that building such a picture forces AI researchers to face old philosophical questions about knowledge, cause and ability. The authors wanted a program that decides what to do by reasoning, in a formal language, that a given plan will reach its goal.

## The tools: situations and fluents

To make that possible, McCarthy and Hayes set out a framework now known as the situation calculus. Three ideas carry it:

- A **situation** is a snapshot of the world at one moment.
- A **fluent** is any fact whose value depends on the situation, such as "Pat has a telephone" or "it is raining."
- An **action** takes one situation to the next, and rules say which fluents hold afterward.

The paper works through a down-to-earth example: one person getting into conversation with another by looking the number up in a phone book and then dialing it. The authors wrote down rules for looking up a number and for making a call, and then tried to prove that the plan works.

It did not work. The rules said nothing about whether the caller still has the telephone, or whether the friend is still at home, once the lookup action is over. In logic, what is not stated cannot be assumed. To rescue the proof, the authors had to add a rule saying, in effect, that looking up a number leaves those facts alone. They admitted the extra assumptions were "quite ad hoc," meaning patched on for this one case.

## Why it grows out of control

In the section titled "The Frame Problem," they spelled out the cost. If there are a number of actions and a number of fluents, you may need a separate "this action does not change that fact" statement for almost every pair. Here is the arithmetic for a modest home robot:

| Actions it knows | Facts it tracks | "No change" rules needed (roughly actions × facts) |
|---|---|---|
| 3 (look up, dial, walk) | 4 (has phone, friend at home, door shut, light on) | about 12 |
| 20 | 50 | about 1,000 |
| 100 | 1,000 | about 100,000 |

The useful rules, the ones about what each action actually does, grow slowly. The "nothing else changed" rules, which logicians call frame axioms, grow as the product. Murray Shanahan, writing in the Stanford Encyclopedia of Philosophy, gives a simple illustration: rules for painting an object and for moving it do not, on their own, let a logical system conclude that moving the object leaves its color unchanged.

> **Try it:** Pick three actions you do in the morning, such as making coffee, opening the curtains and checking your phone. List five facts about your kitchen. For each action and fact, write "changes" or "doesn't change." Count how many "doesn't change" boxes you filled. That is your personal set of frame axioms.

## How people tried to solve it

McCarthy and Hayes sketched one way out themselves: group the fluents into a "frame," like the variables in a computer program, and describe each action only by which ones it changes, with all the rest presumed to stay as they were. Robot builders took a similar path. The planner for SRI's Shakey robot, called STRIPS, described each action by its preconditions, the facts it deletes and the facts it adds, and assumed everything else stayed put. The IEEE describes that design as a practical solution to the frame problem.

Logicians wanted something more principled. The underlying rule of thumb, that an action leaves a fact alone unless there is reason to think otherwise, goes by the name "common sense law of inertia." Classical logic struggles to express it, because adding new information can never cancel an earlier conclusion, a property called monotonicity. That led to new "non-monotonic" logics in which conclusions can be withdrawn, including McCarthy's own circumscription in the 1980s. Progress was slow, and puzzles such as the Yale shooting problem showed how easily the new logics gave odd answers. By 2016 Shanahan judged the narrow technical problem more or less solved.

Philosophers, meanwhile, took the name and widened it. Daniel Dennett and Jerry Fodor asked how any thinking creature, human or machine, decides which of its many beliefs to recheck after it acts. That broader question about relevance is far from settled.

## Do today's AI systems still face the frame problem?

In its original form, it belongs to systems that store knowledge as explicit logical statements, and those systems now have workable solutions. The neural networks that dominate AI headlines in 2019 do not write out frame axioms at all; they learn patterns from data, so the problem does not appear in the same shape.

The wider version has not gone away. A self-driving car, a warehouse robot or a planning program still has to decide which parts of the world an action might affect and which it can safely ignore. Getting that wrong in either direction is costly: check too little and the system misses a change that matters, check too much and it never acts. McCarthy and Hayes put a name to that dilemma in 1969, and it remains one of the clearest ways to explain why common sense is hard to build.

## Sources

- Some Philosophical Problems from the Standpoint of Artificial Intelligence: https://www-formal.stanford.edu/jmc/mcchay69.pdf
- The Frame Problem: https://plato.stanford.edu/archives/spr2019/entries/frame-problem/
- Milestones: SHAKEY: The World's First Mobile Intelligent Robot, 1972: https://ethw.org/Milestones:SHAKEY:_The_World%E2%80%99s_First_Mobile_Intelligent_Robot,_1972