1 Introduction

The frame problem is a fundamental challenge in artificial intelligence (AI) and philosophy of mind concerning how an intelligent system can efficiently represent and reason about the effects of actions in a changing environment. It arises when an agent must determine not only what changes as a result of an action, but also what remains unchanged—the "frame" of the situation—without requiring an exhaustive enumeration of all non-effects. The problem highlights a tension between logical completeness and computational tractability, and it has shaped research in planning, common‑sense reasoning, and cognitive architecture since its identification in the late 1960s.

1.1 Historical Context

The frame problem was first explicitly articulated by John McCarthy and Patrick J. Hayes in their 1969 paper "Some Philosophical Problems from the Standpoint of Artificial Intelligence." Working within the tradition of logical AI, they noted that when using first‑order logic to describe a dynamic world, an agent must include axioms that state which properties are not altered by an action. Without such axioms, the agent cannot infer that a block remains at a location after another block is moved, unless a separate axiom is added for every possible combination of action and unaffected fact. This led to the "frame problem" as a core obstacle to scaling logical reasoning to realistic domains. The issue quickly attracted attention from philosophers, cognitive scientists, and AI researchers, becoming a classic topic in the philosophy of mind.

1.2 Core Definition

In its most general form, the frame problem is the difficulty of representing and reasoning about the invariant aspects of a changing world. Given a set of actions and a description of the current state, an agent must efficiently determine which facts persist and which are modified. In classical logic‑based AI, this requires "frame axioms" that explicitly declare what does not change. The problem is that an action may leave most facts untouched, but writing individual axioms for each unaffected fact leads to an explosion of axioms (the "proliferation problem"). The challenge is to find a representational and inferential mechanism that captures persistence implicitly, without enumerating all non‑changes.

2 Formalization in Classical AI

The frame problem was first formalized within the situation calculus, a logical language for describing states (situations) and actions.

2.1 Situation Calculus

The situation calculus, introduced by John McCarthy in 1963, models the world as a series of situations. A situation is a snapshot of the state of the world at a given time. Actions are functions that map one situation to another. The outcome of an action is described by effect axioms, but these axioms alone do not specify which facts remain the same. For example, an effect axiom might state that moving block A onto block B results in the block being on top of B (On(A,B,s)), but it does not say that the color of block A remains unchanged. To deduce that the color stays the same, an explicit frame axiom is needed.

2.2 Frame Axioms

Frame axioms are logical statements that specify that a given property is unaffected by a given action. They are the classical solution to the frame problem, but they introduce new difficulties.

2.2.1 Explicit Frame Axioms

An explicit frame axiom takes a form such as: ∀s [holds(Color(A, Red), s) → holds(Color(A, Red), do(move(A,B), s))] More generally, for each action and each property that might persist, an axiom is written. If there are *m* actions and *n* properties, the number of frame axioms grows as *m × n*, which is manageable for toy problems but becomes unwieldy for realistic domains.

2.2.2 The Proliferation Problem

The proliferation problem is the practical consequence of requiring explicit frame axioms for every combination of action and unaffected fact. As the number of actions and properties increases, the axiom set becomes extremely large. Worse, if new actions or properties are added later, the system must be updated with new frame axioms. This makes the approach brittle and non‑scalable, motivating the search for more compact logical representations and non‑monotonic reasoning.

3 Logical Solutions

To overcome the inefficiency of explicit frame axioms, researchers developed logical frameworks that capture persistence implicitly.

3.1 Circumscription

Circumscription is a non‑monotonic logic proposed by McCarthy that minimizes the extent of certain predicates. It provides a way to infer that the only changes are those forced by explicit effect axioms.

3.1.1 McCarthy's Circumscription

McCarthy's circumscription allows an agent to assume that the set of objects satisfying a predicate is as small as possible. Applied to the frame problem, one circumscribes the "abnormal" predicate that would indicate a change. If an effect axiom forces a fact to change in a particular situation, circumscription assumes that otherwise the fact remains true. This eliminates the need for explicit frame axioms by making non‑change the default.

3.1.2 Minimal Models

Circumscription is often defined in terms of minimal models: a formula is true if it holds in all models that are minimal with respect to a given ordering (e.g., minimal in the extension of a predicate). For the frame problem, the minimal models are those where actions alter only what they are required to alter. This captures the intuition that "things stay the same unless stated otherwise." However, circumscription can be computationally expensive and may not handle all forms of indirect effects.

3.2 Default Logic and Non-Monotonicity

Default logic, introduced by Ray Reiter, offers another non‑monotonic approach. A default rule can state: "If a property holds before an action, and it is not known that the action changes it, then it continues to hold." For example: holds(P, s) : not ab(action, P, s) / holds(P, do(action, s)) This rule captures persistence without writing frame axioms for each property. Default logic allows reasoning with incomplete information, but the problem of deciding which defaults apply remains.

3.3 Successor State Axioms

A more compact solution within the situation calculus is the use of successor state axioms (SSAs), proposed by Reiter in the 1990s. An SSA for a fluent (a property that changes over time) states all the conditions under which it becomes true or false after an action. For each fluent F, the SSA is of the form: holds(F, do(a, s)) ↔ (some action makes F true) ∨ (holds(F, s) ∧ ¬(some action makes F false)) This combines effect and frame axioms into a single axiom per fluent, reducing the number of axioms from *m×n* to *n* (one per fluent). SSAs are the standard solution in modern situation‑calculus‑based reasoning and are directly implementable in logic programming systems.

4 Philosophical Dimensions

The frame problem is not merely a technical issue in AI; it has profound implications for understanding human cognition and the nature of common sense.

4.1 The Relevance to Common Sense

Common‑sense reasoning involves extensive knowledge about what does and does not change when actions occur. For example, when a person walks into a room, they know that the furniture remains in place, the color of the walls does not change, and the laws of physics continue to hold. Representing this implicit knowledge in a formal system is analogous to the frame problem. Philosophers like Daniel Dennett have argued that the frame problem reveals a deep challenge for any computational theory of mind: how can a finite system efficiently store and use all the seemingly trivial facts that are relevant to everyday actions?

4.2 The Frame Problem in Philosophy of Mind

In philosophy of mind, the frame problem is often linked to issues of mental representation and the architecture of cognition.

4.2.1 Dennett's Perspective

Daniel Dennett (1984) characterized the frame problem as a problem of "representational generativity" that any intelligent agent must solve. He argued that the human mind is able to ignore most irrelevant details and focus only on what matters, but a classical AI system would need to consider an enormous number of logical implications. Dennett saw the frame problem as evidence that human cognition does not operate through a massive logical deduction process but instead relies on heuristic, parallel, and content‑addressed mechanisms.

4.2.2 Connection to the Binding Problem

The binding problem in neuroscience concerns how the brain integrates different features (e.g., color, shape, motion) into a unified percept. Some philosophers have drawn parallels between binding and the frame problem: both involve coordinating information that changes across time and across distinct processing modules. While the frame problem is about persistence after actions, the binding problem is about coherence across features at a single moment. The two are not identical, but they both challenge simple symbolic accounts of representation.

5 Computational and Cognitive Approaches

Practical AI systems have developed alternative methods to avoid the overhead of logic‑based frame axioms.

5.1 STRIPS and the Add/Delete-List Approach

The STRIPS planning system (Fikes and Nilsson, 1971) sidesteps the frame problem through a procedural representation. A STRIPS operator consists of a precondition, an add‑list (facts made true), and a delete‑list (facts made false). The planner assumes that all facts not in the add‑list or delete‑list remain unchanged—a "closed‑world assumption" applied to the effects of each action. This is a computationally efficient solution, but it assumes that the planner can fully enumerate all immediate effects, which may not hold for domains with ramifications (indirect effects). Nevertheless, the add/delete‑list approach became the standard in classical planning for decades.

5.2 Planning Domain Definition Language

The Planning Domain Definition Language (PDDL), introduced in 1998 for the International Planning Competition, inherits the STRIPS‑style representation. Actions are defined with preconditions and effects (add/delete lists). The frame problem is "solved" by convention: any fact not listed as an effect is assumed to persist. This pragmatic approach works well for many planning domains, though it inherits the limitations of the add/delete‑list model, such as difficulty handling continuous change or complex ramifications.

5.3 Human Cognition and the Frame Problem

Cognitive scientists have investigated how humans effortlessly solve the frame problem in everyday life.

5.3.1 Fodor's Challenge

Jerry Fodor argued that the frame problem is a major obstacle to classical cognitivism. In his 1987 book *Psychosemantics*, Fodor claimed that if human reasoning were based on a central, all‑purpose logical inference engine (as in classical AI), then the frame problem would be intractable. He took this as evidence for modularity and domain‑specific reasoning, though he remained pessimistic about a complete computational account of common sense.

5.3.2 Heuristics and Relevance

Human cognition appears to rely on fast‑and‑frugal heuristics, massive parallelism, and associative memory to determine relevance. For example, when planning a trip, a person does not consider the effect of boarding a bus on the color of their shoes. Theories of cognition such as connectionism and embodied cognition suggest that the frame problem is mitigated by the fact that representations are not logically complete but are instead grounded in perception and action. The problem of relevance—deciding what information is pertinent—remains an active area of cognitive modeling.

The frame problem is part of a family of challenges in representing dynamic worlds.

6.1 The Qualification Problem

The qualification problem concerns the difficulty of listing all preconditions that must hold for an action to have its intended effect. For example, to turn on a light, the switch must be in working order, the bulb must not be burned out, the power must be on, and so on. An exhaustive list is practically impossible. Like the frame problem, the qualification problem requires non‑monotonic or default reasoning to handle exceptions implicitly.

6.2 The Ramification Problem

The ramification problem is the challenge of dealing with indirect (or side) effects of actions. For instance, moving a block may cause a stack of blocks to topple, which in turn changes the location of many blocks. Representing all these consequences without an explosion of axioms is difficult. Solutions often combine the frame problem's persistence assumptions with causal rules that propagate effects.

6.3 The Predictive Frame Problem

A more recent variant, the predictive frame problem, arises in the context of machine learning and reinforcement learning. An agent that learns a model of the world must know which features of the state are relevant for predicting future states. The classical frame problem was about logical deduction; the predictive version asks how to avoid learning all possible combinations of features and actions. This is particularly relevant for deep learning systems that must generalize from limited data.

7 Contemporary Research Directions

Modern AI research continues to grapple with the frame problem in various forms.

7.1 Deep Learning and Implicit Frame Reasoning

Deep neural networks, especially those used in reinforcement learning, often learn implicit representations of state and action effects. These models automatically capture which features tend to stay constant—for example, the background of an image remains unchanged when an agent moves. However, deep learning systems lack explicit reasoning about persistence and can struggle with out‑of‑distribution scenarios. Current research explores how to incorporate inductive biases that encourage the network to focus on relevant features, thereby mitigating the predictive frame problem.

7.2 Hybrid Symbolic-Connectionist Systems

A promising direction is to combine symbolic reasoning (with clear semantics for change and persistence) with connectionist learning for pattern recognition and perception. Hybrid systems use symbolic planners that rely on logic or probabilistic formalisms (such as Markov logic networks) to handle the frame problem formally, while neural networks process sensory data. This approach aims to achieve both the precision of logical reasoning and the flexibility of learned representations.

7.3 Cognitive Robotics and Real-Time Adaptation

In cognitive robotics, robots must operate in dynamic, partially known environments. The frame problem re‑emerges when the robot must plan actions while updating its world model from sensor data. Researchers have developed architectures that use belief‑state representations (e.g., partially observable Markov decision processes) to handle uncertainty about which facts persist. Real‑time adaptation techniques, such as model‑predictive control, avoid exhaustive frame reasoning by continually re‑planning based on the most recent state estimate.

8 References

[This section would list the seminal works referenced in the article. For the purpose of this encyclopedia expansion, representative references are provided below.]

  • McCarthy, J., & Hayes, P. J. (1969). Some philosophical problems from the standpoint of artificial intelligence. *Machine Intelligence*, 4, 463–502.
  • Reiter, R. (1991). The frame problem in the situation calculus: A simple solution (sometimes) and a completeness result for goal regression. In *Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy* (pp. 359–380).
  • Dennett, D. C. (1984). Cognitive wheels: The frame problem of AI. In C. Hookway (Ed.), *Minds, Machines and Evolution* (pp. 129–152). Cambridge University Press.
  • Fodor, J. A. (1987). *Psychosemantics: The Problem of Meaning in the Philosophy of Mind*. MIT Press.
  • Fikes, R. E., & Nilsson, N. J. (1971). STRIPS: A new approach to the application of theorem proving to problem solving. *Artificial Intelligence*, 2(3–4), 189–208.
  • Hanks, S., & McDermott, D. (1987). Nonmonotonic logic and temporal projection. *Artificial Intelligence*, 33(3), 379–412.
  • Shanahan, M. (1997). *Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia*. MIT Press.