Frame ProblemJohn McCarthy and Pat Hayes first mentioned the frame problem in their seminal essay “Some Philosophical Problems from the Standpoint of Artificial Intelligence” in 1969. In its original formulation the frame problem described a stubborn difficulty arising in a first-order logic formulation, the situation calculus, in specifying which things remain unchanged when reasoning about changes in a domain. Since then, the frame problem has achieved a famous—or rather notorious—reputation in the Artificial Intelligence community as an example of a seemingly simple, specific problem in AI uncovering deeper and even philosophical difficulties for the task of creating artificial intelligence.
McCarthy and Hayes’ formulation of the frame problem begins in a narrow context, but the problem they discovered remains central to the spirit of the problem. Taking the situation calculus, the frame problem arose because apparently simple descriptions of toy domains:
Holds(Situation_O, Black(Block A))
Holds (Situation_O, Clear(Block A))
Holds (Situation_O, Clear(Block B))
led to questions about how to reason about non-change in the domain. For instance, given the description above, is Holds(Result (Put_On(Block A, Block B), Situation_0), Black(Block A)) true? In other words, if Block A is black and we put it on Block B, does it remain black? This inference, so simple for humans to resolve, isn’t allowable in terms of the situation calculus theory.
In an effort to obviate this weakness, McCarthy and Hayes formulated “frame axioms” to specify which things stay the same when reasoning about change:
Holds(Situation_O, Black(Block A)) à Result (Put_On(Block A, Block B), Situation_0), Black(Block A))
This fixes the problem, but raises another: there are many, many things that do not change when reasoning about something that does—how does one avoid writing overwhelming numbers of frame axioms (if such a task is possible at all)? [1] The problem of how to reason about change without needing to specify frame axioms for everything that does not change became known as the frame problem.
Since its original statement as a representational problem in the situation calculus, many researchers in AI have come to see the frame problem as a frustratingly general problem for machine reasoning. For instance, the frame problem has been identified with a persistence problem of predicting what will stay the same when reasoning about change. Others see it as pointing to the problem of determining both what changes and what doesn’t (the temporal projection problem), and still others have recognized the frame problem as a general problem of temporal reasoning, including reasoning about what happened in the past (explanation). The frame problem now covers all of these cases and more (some philosophers have even identified the frame problem as an instance of the problem of induction!).
Whatever level of generality one prefers, the frame problem has stubbornly resisted a solution. It has surfaced in all AI approaches to date, from traditional monotonic logics to non-monotonic logics, procedural planning, statistical and probabilistic methods, and non-traditional connectionist approaches. It has allowed only fleeting solutions that, one by one, have quickly been shown to be brittle and specific to a particular domain. (Drew McDermott, the famous apostate of the logicist camp of AI, captured the mood well by asking, after hearing of a “solution” to the frame problem, what everyone should do “next time.”) Indeed, whatever one’s philosophical leanings toward the possibility of true machine intelligence, the last thirty five years of the history of AI—a discipline only about fifty years old—have been marked by the frame problem. The seemingly solvable puzzle pointed out by McCarthy and Hayes over three decades ago has essentially sidelined the once grandiose aims of the field of AI.
[1] If there are m actions and n things that stay the same for each action, there are m*n required frame axioms.
Web Resources On Frame Problem
The Frame Problem in AI
Cognitive Wheels: The Frame Problem of AI
Book Resources On Frame ProblemThe Robots Dilemma: The Frame Problem in AI by Zenon W. Pylyshyn
The Robots Dilemma Revisited by Kenneth M. Ford, Zenon W. Pylyshyn
Solving the Frame Problem by Murray Shanahan
Editor(s): Erik Larson
|
|
|
