The Frame Problem

Unit 6: Knowledge-Based Agents and Inference — Section 6.6

Suppose a robot picks up a red book from a table. After the action, the book is in the robot’s gripper, the table is no longer supporting the book, and the robot’s hand is no longer empty. What about the book’s color? Its weight? The color of the table? The temperature of the room? The robot’s battery level?

Everything else in the world stays the same — but how does the agent know this? In formal logic, you can only use facts that have been explicitly stated or derived. If the logic doesn’t say "the book is still red after pickup," how can the robot be sure? This deceptively simple question is the frame problem, and it has no trivial solution.

What Is the Frame Problem?

The frame problem was first identified by John McCarthy and Patrick Hayes in 1969 as a fundamental challenge in AI planning and knowledge representation. The name comes from the analogy of movie frames: between two consecutive frames of a film, most things stay the same while only a few things change. An AI system needs to know which things persist (the "frame") and which things change.

Frame Problem: The challenge of efficiently representing which properties of the world remain unchanged when an action occurs. In formal logic, an agent can only use what it has been explicitly told or can derive; this forces it to account for every persistent property of every object after every action.

The problem is not that it is hard to say what changes — that is usually straightforward. The difficulty is saying what does not change without writing an infinite list of axioms.

The Naive Approach: Explicit Frame Axioms

The obvious solution is to write an explicit frame axiom for every property that stays the same after every action. Let’s see why this fails catastrophically.

The Combinatorial Explosion

Consider a robot world with 100 objects and 10 possible actions. Every action must explicitly state what it does not change.

pickup(book) ∧ color(book, red) → color(book, red)
pickup(book) ∧ color(table, brown) → color(table, brown)
pickup(book) ∧ location(robot, room1) → location(robot, room1)
pickup(book) ∧ temperature(room, 72) → temperature(room, 72)
...and thousands more axioms for this one action alone.

Calculation: If there are n objects and m actions, we need roughly O(n² × m) frame axioms. With 100 objects and 10 actions: approximately 100,000 axioms just to represent what doesn’t change. Adding a new action requires hundreds of new axioms. This approach is completely impractical for real-world planning.

Fluent: A property of the world that can change over time as a result of actions. Examples: location(robot, X), holding(robot, book), light_on. Contrast with eternal properties that never change: color(book, red), weight(book, 2lb).

Solution 1: The STRIPS Assumption

The most practical solution to the frame problem is the STRIPS assumption (Stanford Research Institute Problem Solver), proposed by Fikes and Nilsson in 1971.

STRIPS Assumption: The convention that everything stays the same after an action unless explicitly listed in the action’s effects. Rather than stating what doesn’t change (the impossible task), STRIPS actions specify only what does change.

Under the STRIPS assumption, each action is described by three lists:

Preconditions: What must be true before the action can be executed.
Add list: What becomes true after the action.
Delete list: What becomes false after the action.

Everything not on the add list or delete list is implicitly preserved.

Pickup Action in STRIPS Format

Action: pickup(robot, book)

Preconditions:
  - at(robot, location)
  - at(book, location)
  - handempty(robot)

Add list (becomes TRUE):
  - holding(robot, book)

Delete list (becomes FALSE):
  - at(book, location)
  - handempty(robot)

Implicit: Everything else stays the same — the book’s color, weight, title, the table’s position, the room temperature, all of it is unchanged. The STRIPS assumption buys us this for free.

Contrast with the naive approach, which would require hundreds of explicit "X stays the same" axioms per action.

Applying a STRIPS Action

To compute the next state after an action:

Start with the current state (the set of true facts).
Check that all preconditions are satisfied. If not, the action cannot be executed.
Remove all facts in the delete list from the current state.
Add all facts in the add list to the current state.
Everything else in the current state is carried over unchanged (STRIPS assumption).

Robot Turning Off a Light Switch

Initial state:

at(robot, A) = TRUE
light_switch_at(B) = TRUE
light_on = TRUE
door_closed = TRUE

Actions:

Action: move(A, B)
  Precond: at(robot, A)
  Add:     at(robot, B)
  Delete:  at(robot, A)

Action: flip_switch
  Precond: at(robot, B) ∧ light_on
  Add:     light_off
  Delete:  light_on

Plan execution:

Step 1: move(A, B)
  Before: {at(robot,A), light_on, door_closed, ...}
  After:  {at(robot,B), light_on, door_closed, ...}  ← door_closed persists!

Step 2: flip_switch
  Before: {at(robot,B), light_on, door_closed}
  After:  {at(robot,B), light_off, door_closed}

The door stays closed throughout (STRIPS assumption). No frame axiom needed.

Solution 2: Successor-State Axioms

A more rigorous (but more verbose) solution is to write successor-state axioms — logical sentences that fully characterize when each fluent is true in the state after an action.

Successor-State Axiom: A logical sentence of the form: "Fluent F is true in state S' if and only if action A caused F to become true, OR F was already true and A did not cause F to become false." This captures both the positive effect and the persistence assumption in a single sentence.

A successor-state axiom for holding(robot, book) might look like:

holding(robot, book, S') ↔
  [action(S) = pickup(book) ∧ at(robot, L, S) ∧ at(book, L, S)]
  ∨
  [holding(robot, book, S) ∧ action(S) ≠ putdown(book)]

Reading: "The robot holds the book in state S' if and only if: either the robot just picked it up (first clause), or the robot was already holding it and did not put it down (second clause)."

Successor-state axioms are more precise than the STRIPS assumption — they give exact conditions for when each fluent is true. They are used in situation calculus, a formal logical framework for reasoning about actions and change.

Solution 3: Situation Calculus

Situation calculus (McCarthy and Hayes, 1969) provides a full first-order logic framework for reasoning about dynamic worlds.

Situation Calculus: A formalism for representing actions and change in which: Situations (S₀, S₁, …) are snapshots of the world at particular times, Fluents are functions from situations to truth values, and Actions are functions that map one situation to the next.

In situation calculus:

at(book, table, S₀) = TRUE means the book is on the table in the initial situation.
S₁ = Result(pickup(book), S₀) defines the situation after the pickup action.
at(book, table, S₁) = FALSE because the pickup action moved the book.

A complete situation calculus representation includes:

An initial situation S₀ with all known initial facts.
Action schemas (preconditions and effects).
A set of successor-state axioms for every fluent.
A unique names assumption (different action terms denote different actions).

Situation Calculus for Book Pickup

% Initial situation
at(book, table, S₀) = TRUE
at(robot, table, S₀) = TRUE
holding(robot, book, S₀) = FALSE

% Action sequence
S₁ = Result(pickup(book, robot), S₀)
S₂ = Result(move(robot, shelf), S₁)
S₃ = Result(putdown(book, robot), S₂)

% Querying the representation
ASK: holding(robot, book, S₁)?   → TRUE
ASK: at(book, table, S₁)?        → FALSE
ASK: at(book, table, S₀)?        → TRUE (initial state unchanged)

Situation calculus allows querying any past state, reasoning about hypothetical action sequences, and planning.

Why the Frame Problem Matters Beyond Expert Systems

The frame problem is not just a technical curiosity. It touches on deep questions about how intelligent systems represent change and common sense.

Practical implications:

Robotics: A robot navigating a dynamic environment must constantly update its world model — knowing what changed (it moved) and what didn’t change (other objects stayed put).
Planning: Classical AI planners (used in game AI, logistics, and NASA missions) all use STRIPS-style action representations.
Game AI: A chess or Go engine must update its board state after each move without recomputing everything from scratch.
Common sense reasoning: Humans automatically assume the world stays mostly the same between observations (this is called default persistence). Building this assumption into AI systems is essential for natural behavior.

Philosophical significance:

The frame problem shows that even apparently simple reasoning tasks require careful representation. The fact that "most things stay the same" is so obvious to humans that we never think about it. Making it explicit in formal logic reveals how much implicit knowledge underlies everyday intelligence.

Consider a home robot assistant. You tell it: "Put the vase of flowers on the dining table." The robot picks up the vase and moves it.

After this action, which of the following should the robot update in its world model? Which should it assume are unchanged?

The vase’s location
The water in the vase
The flowers in the vase
The table’s location
The flowers' appearance
The robot’s position
The kitchen’s temperature
The time of day

Now consider: What if the robot dropped some water while carrying the vase? How would you modify the STRIPS action description to capture this side effect? What does this tell you about the difficulty of complete action modeling?

Apply the STRIPS assumption and identify what changes when an action occurs.

Next: 6.7 Building an Expert System →

Based on the UC Berkeley CS 188 Online Textbook by Nikhil Sharma, Josh Hug, Jacky Liang, and Henry Zhu, licensed under CC BY-SA 4.0.

This work is licensed under CC BY-SA 4.0.