Frame problem

In artificial intelligence, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic without explicitely specifying which conditions are not affected by an action. John McCarthy and Patrick J. Hayes defined this problem in their 1969 article, Some Philosophical Problems from the Standpoint of Artificial Intelligence. Later, the term acquired a broader meaning in philosophy, where it is formulated as the problem of limiting the beliefs of that have to be updated in response to actions.

The name “frame problem” derives from a common technique used by cartoon makers called framing where the currently moving parts of the cartoon are superimposed on the “frame”, which depicts the background of the scene, which does not change. In the logical context, actions are typically specified by what they change, with the implicit assumption that everything else (the frame) remain unchanged.

The frame problem in artificial intelligence

The frame problem occurs even in very simple domains. A scenario with a door, which can be open or closed, and a light, which can be on or off, is statically represented by two propositions open and on. If these conditions can change, they are better represented by two predicates open(t) and on(t) that depend on time. A domain in which the door is closed, the light is off, and the door is opened at time 0, can be directly represented in logic by the following formulae:

$\neg open(0)$

$\neg on(0)$

$true\rightarrow open(1)$

The first two formulae represent the initial situation; the third formula represents the effect of executing the action of opening the door at time 0. If such an action had preconditions, such as the door must not be locked, it would have been represented by $\neg locked(0)\rightarrow open(1)$; this is not needed for this exposition. This is a simplified formalization in which the effects of actions are specified directly in the time points in which the actions are executed, and actions are not named (the article on the situation calculus gives more details.)

While the three formulae above are a direct expression in logic of what is known, they do not suffice to correctly draw consequences. While the following conditions (representing the expected situation) are consistent with the three formulae above, they are not the only ones.

$\neg open(0)$	$open(1)$
$\neg on(0)$	$\neg on(1)$

Indeed, another set of conditions that is consistent with the three formulae above is:

$\neg open(0)$	$open(1)$
$\neg on(0)$	$on(1)$

The frame problem is that specifying only which conditions are changed by the actions do not allow, in logic, to conclude that all other conditions are not changed. This problem can be solved by adding the so-called “frame axioms”, which explicitely specify that all conditions not affected by an actions are not changed while executing that action. For example, since the action executed at time 0 is that of opening the door, a frame axiom would state that the status of the light do not change from time 0 to time 1:

$on(0)\equiv on(1)$

The frame problem is that these one such frame axiom is necessary for every pair of action and condition such that the action do not affect the condition. In other words, the problem is that of formalizing a dynamical domain without explicitely specifying the frame axioms.

The solution proposed by McCarthy to solve this problem involves assuming that a minimal amount of condition changes have occurred; this solution is formalized using the framework of circumscription. The Yale shooting problem, however, shows that this solution is not always correct. Alternative solutions were then proposed, involving predicate completion, fluent occlusion, successor state axioms, etc. By the end of the 1980s, the frame problem as defined by McCarthy and Hayes was solved. Even after that, however, the term “frame problem” was still used, in part to refer to the same problem but under different settings (e.g., concurrent actions), and in part to refer to the general problem of representing and reasoning with dynamical domains.

According to J. van Brakel, some other problems that are related to, or more specific versions of, the frame problem include the following:

• extended prediction problem
• holism problem
• inertia problem
• installation problem
• planning problem
• persistence problem
• qualification problem
• ramification problem
• relevance problem
• temporal projection problem

The frame problem in philosophy

In philosophy, the frame problem was used to refer to a problem similar to that originating in artificial intelligence, but referring to rationality in general, rather than being specific to formal logic. This is therefore the problem of how a rational agent bounds the set of beliefs to change when an action is performed.

See also

• Circumscription
• Common sense
• Default logic
• Defeasible reasoning
• Non-monotonic logic
• Situation calculus

References

• P. Doherty, J. Gustafsson, L. Karlsson, and J. Kvarnström. TAL: Temporal action logics language specification and tutorial. Electronic Transactions on Artificial Intelligence, 2:273-306, 1998.

• M. Gelfond and V. Lifschitz. Representing action and change by logic programs. Journal of Logic Programming, 17:301-322, 1993.

• M. Gelfond and V. Lifschitz. Action languages. Electronic Transactions on Artificial Intelligence, 2:193-210, 1998.

• S. Hanks and D. McDermott. Nonmonotonic logic and temporal projection. Artificial Intelligence, 33(3):379-412, 1987.

• H. Levesque, F. Pirri, and R. Reiter. Foundations for the situation calculus. Electronic Transactions on Artificial Intelligence, 2:159-178, 1998.

• J. McCarthy. Applications of circumscription to formalizing common-sense knowledge. Artificial Intelligence, 28:89-116, 1986.

• J. McCarthy and P. J. Hayes. Some philosophical problems from the standpoint of artificial intelligence. Machine Intelligence, 4:463-502, 1969.

• R. Reiter. The frame problem in the situation calculus: a simple solution (sometimes) and a completeness result for goal regression. In Vladimir Lifschitz, editor, Artificial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, pages 359-380. Academic Press, New York, 1991.

• E. Sandewall. Features and Fluents. Oxford University Press, 1994.

• E. Sandewall. Cognitive robotics logic and its metatheory: Features and fluents revisited. Electronic Transactions on Artificial Intelligence, 2:307-329, 1998.

• M. Thielscher. Introduction to the fluent calculus. Electronic Transactions on Artificial Intelligence, 2:179-192, 1998.

External links

• The Frame Problem at the Stanford Encyclopaedia of Philosophy.
• Some Philosophical Problems from the Standpoint of Artificial Intelligence; the original article of McCarthy and Hayes that proposed the problem.
• Robotics and the common sense informatic situation presents solution to the frame problem