Frame Problem

The frame problem is a foundational challenge in AI concerning how to represent the effects of actions in a changing world without explicitly enumerating everything that stays the same. When an agent performs an action — a robot moving an object, for instance — a logical world model must update to reflect the change while implicitly preserving thousands of unaffected facts. In classical logic-based systems, this requires stating each unchanged fact explicitly, a requirement that becomes computationally intractable as the complexity of the environment grows. The problem exposes a fundamental tension between the expressiveness of formal reasoning systems and the practical demands of real-world AI.

First articulated by John McCarthy and Patrick J. Hayes in 1969, the frame problem emerged from attempts to formalize commonsense reasoning using situation calculus. Their work revealed that naive logical approaches to action representation suffer from an explosion of "frame axioms" — statements asserting that properties persist across actions that don't affect them. This isn't merely a technical inconvenience; it reflects a deeper difficulty in capturing the default assumption humans make effortlessly: that the world mostly stays the same unless something specific changes it.

Several approaches have been developed to address the frame problem. Non-monotonic reasoning frameworks, such as default logic and circumscription, allow systems to assume persistence by default and retract assumptions only when contradicted. Action description languages like STRIPS, ADL, and the situation calculus with successor state axioms offer more tractable formalisms by encoding what changes rather than what doesn't. These approaches shift the burden from exhaustive enumeration to compact, exception-based representations.

The frame problem remains relevant beyond classical planning systems. In modern machine learning, it surfaces in reinforcement learning environments where agents must generalize about state transitions, and in neural-symbolic systems attempting to integrate logical reasoning with learned representations. Large language models implicitly grapple with a version of the frame problem when tracking entity states across a narrative or conversation. Understanding the frame problem helps clarify why building AI systems that reason robustly about dynamic, open-ended worlds remains genuinely difficult.