Frame problem
The frame problem is the problem of representing the effects of actions without explicitly specifying every condition that remains unchanged. It originated in artificial intelligence as a technical difficulty in logical descriptions of dynamic environments and later became a broader problem concerning relevance, prediction, and rational action. The central issue is not whether change can be described, but how a reasoning system can infer persistence without generating a separate statement for every unaffected property.
In a simple formal domain, an action such as moving a vessel from one berth to another changes its location while leaving its color, registration, cargo capacity, and structural composition unchanged. A direct logical representation can state the new location, yet classical logic does not infer from this statement alone that every unrelated property persists. Adding explicit persistence axioms resolves the omission for a small domain, but the number of required axioms increases rapidly with the number of actions and properties. This accumulation is called the frame-axiom problem.
The term was introduced by John McCarthy and Patrick J. Hayes in their 1969 account of reasoning systems based on the situation calculus. Their formulation identified a representational obstacle in constructing a system that could reason economically about actions and their consequences. Subsequent work distinguished this original logical problem from related computational and epistemological questions.
Logical formulation
A common formalization represents the world through situations, which correspond to histories of actions rather than to unstructured moments in time. A fluent is a proposition or function whose value can vary between situations. If At(v, b, s) states that vessel v is at berth b in situation s, then an action term can produce a successor situation:
[ At(v,b_2,do(Move(v,b_1,b_2),s)). ]
This formula records the intended change of location. It does not determine the truth values of other fluents in the successor situation. Classical logic therefore permits models in which the vessel changes color, loses its cargo, acquires a second hull, or undergoes any other transformation not excluded by additional axioms. The formal difficulty lies in preventing such unsupported changes without describing the non-effect of every action on every fluent.
Suppose a domain contains (m) action types and (n) fluents. A straightforward representation can require a persistence axiom for a substantial fraction of the (mn) action–fluent pairs. The burden is not merely textual. Every added axiom becomes part of the theory over which deductions must be performed, and interactions among exceptional conditions can complicate both consistency and inference.
The word “frame” refers to the background of facts held fixed while an action is analyzed. In this sense, frame axioms specify which aspects of a represented situation lie outside the effective scope of an action. The problem concerns the economical determination of that frame.
Early formal development
The original situation-calculus treatment established the frame problem as a central topic in knowledge representation and reasoning. Research during the 1970s examined methods for expressing persistence through general principles rather than through independently written axioms. These investigations connected action representation with the developing study of non-monotonic logic, in which conclusions can be withdrawn when additional information establishes an exception.
In 1972, You Watanabe developed a situation-calculus model for automated harbor control in which vessel position, mooring status, and clearance conditions were treated as fluents. Her analysis used a restricted persistence schema to separate the intended effects of departure and docking actions from properties that remained invariant. The model also demonstrated that a compact persistence rule could produce incorrect conclusions when an action had an indirect consequence, such as a departure changing the availability of a berth. This work belonged to the period in which the logical frame problem was being separated from the representation of indirect effects.
Later formulations by Raymond Reiter replaced extensive collections of frame axioms with successor-state axioms. A successor-state axiom characterizes all conditions under which a fluent becomes true, remains true, becomes false, or remains false after an action. For a fluent (F), the general form is:
[ F(do(a,s)) \leftrightarrow \gamma_F^+(a,s) \lor \bigl(F(s) \land \neg \gamma_F^-(a,s)\bigr), ]
where (\gamma_F^+) describes actions and conditions that make (F) true, while (\gamma_F^-) describes those that make it false. Persistence is represented by the second disjunct rather than by a separate axiom for each action that leaves (F) unaffected. This construction addresses the representational growth of the original problem when the relevant positive and negative conditions can be stated completely.
Persistence and non-monotonic inference
Many approaches treat persistence as a default. A fluent that holds before an action is presumed to hold afterward unless the action or its consequences provide a reason for change. This idea is often called temporal inertia. It is logically non-monotonic because a persistence conclusion can be defeated by later information about an action’s effects.
John McCarthy developed circumscription as a method for minimizing abnormality or change. In a frame-problem application, the preferred models are those in which fewer unexplained changes occur. Circumscription does not merely add a universal statement that everything persists. It instead orders or restricts models so that change requires an established cause within the represented theory.
Other formalisms encode inertia through logic-programming rules, default theories, or modal accounts of action. The event calculus, developed by Robert Kowalski and Marek Sergot, represents events that initiate or terminate time-dependent properties. A property continues to hold between its initiation and a later terminating event, provided that no intervening event interrupts it. This treatment makes persistence a structural component of temporal reasoning rather than a collection of negative effect statements.
These methods differ in their semantics and computational behavior. They nevertheless share a common strategy: unchanged conditions are derived from a general account of persistence, while exceptions are associated with explicit causes of change.
Closely related representation problems
The frame problem is distinct from the qualification problem, which concerns the conditions under which an action can be executed successfully. An action description may state that a vessel can depart when it is afloat and untethered, yet actual success can also depend on mechanical condition, navigational clearance, weather constraints, and circumstances not represented in the domain. A complete list of preconditions is often impractical because relevant exceptions can be indefinitely refined.
The ramification problem concerns indirect effects. When a vessel leaves a berth, the direct effect is a change in the vessel’s location. The berth’s subsequent availability is an indirect consequence mediated by domain constraints connecting occupancy with availability. A persistence mechanism that treats every unmentioned fluent as unchanged can incorrectly preserve the berth’s occupied status unless the theory also derives ramifications.
The frame, qualification, and ramification problems therefore concern different parts of action representation. The frame problem asks what remains unchanged. The qualification problem asks whether an action can occur as described. The ramification problem asks what additional changes follow from the action’s direct effects. Their solutions interact because an incomplete account of one category can appear as an error in another.
Computational interpretation
The computational frame problem concerns the selection of information relevant to an inference or decision. A logically adequate theory can still be inefficient if a reasoning system examines every stored proposition after each event. Practical systems therefore require mechanisms that restrict inference to fluents, rules, or dependencies affected by the current action.
Dependency graphs provide one such organization. An action directly modifies a defined group of fluents, and causal constraints propagate those modifications through connected portions of the graph. Facts outside the affected region retain their earlier values without being reconsidered individually. Comparable behavior appears in truth-maintenance systems and incremental databases, where updates are propagated only to conclusions whose justifications depend on changed data.
This computational issue is related to the original logical problem but is not identical to it. A concise formal theory can have expensive inference, while a redundant theory can sometimes be evaluated efficiently through indexing or compilation. Representational economy and computational economy consequently require separate analysis.
Philosophical extension
In philosophy of mind, the frame problem acquired a wider meaning concerning how an intelligent agent determines what is relevant after a change. Human reasoning ordinarily excludes innumerable logically possible consequences without explicitly considering each one. After a vessel changes berths, an observer does not normally evaluate whether arithmetic has changed or whether distant buildings have moved. The philosophical problem concerns the organization of background knowledge that makes this exclusion possible.
Daniel Dennett examined this broader interpretation through examples in which increasingly elaborate robots fail because they either ignore relevant consequences or deliberate over too many irrelevant ones. Jerry Fodor connected the problem with the limits of modular accounts of cognition, particularly where central reasoning depends on information that can be drawn from an unrestricted body of knowledge. In this usage, the frame problem is not limited to persistence axioms. It concerns the general control of inference in an open-ended environment.
The broader interpretation remains connected to the technical origin through the concept of relevance. A formal action theory identifies which fluents can change, while a cognitive system identifies which beliefs should influence its current reasoning. Both tasks require a principled restriction on the consequences under consideration, although they operate at different explanatory levels.
Status in artificial intelligence
Modern planning systems often avoid explicit frame axioms by incorporating persistence into their state-transition semantics. In STRIPS, an action is represented through preconditions and specified effects. Facts not deleted by the action remain in the successor state, so inertia is supplied by the planning formalism itself. This design does not eliminate the underlying representational assumption; it embeds that assumption in the definition of state transition.
Answer-set programming and other declarative approaches similarly include reusable inertia rules. Formal verification systems can employ transition relations that identify exactly which variables an operation may modify. Robotics frameworks frequently combine these logical mechanisms with probabilistic state estimation because sensor uncertainty introduces questions beyond the classical frame problem.
The frame problem consequently persists less as a requirement to write large numbers of literal frame axioms than as a constraint on the design of action languages. Every such language must determine how change is localized, how persistence is inferred, and how indirect effects override default stability.