Frame problem
Encyclopedia
In artificial intelligence
, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic
without explicitly 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 that have to be updated in response to actions.
The name "frame problem" derives from a common technique used by animated 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) remains unchanged.
s open and on. If these conditions can change, they are better represented by two predicates open(t) and on(t) that depend on time; such predicates are called fluent
s. A domain in which the door is closed, the light is off, and the door is opened at time 1 can be directly represented in logic by the following formulae:
The first two formulae represent the initial situation; the third formula represents the effect of executing the action of opening the door at time 1. If such an action had preconditions, such as the door must not be locked, it would have been represented by
. In practice, one would have a predicate 
for specifying when an action is executed and a rule 
for specifying the effects of actions. 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.
Indeed, another set of conditions that is consistent with the three formulae above is:
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 explicitly specify that all conditions not affected by 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 does not change from time 0 to time 1:
The frame problem is that one such frame axiom is necessary for every pair of action and condition such that the action does not affect the condition. In other words, the problem is that of formalizing a dynamical domain without explicitly 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.
, who also defined a formal language
for the specification of dynamical domains; therefore, such a domain can be first expressed in this language and then automatically translated into logic. In this article, only the expression in logic is shown, and only in the simplified language with no action names.
The rationale of this solution is to represent not only the value of conditions over time, but also whether they can be affected by the last executed action. The latter is represented by another condition, called occlusion. A condition is said to be occluded in a given time point if an action has been just executed that makes the condition true or false as an effect. Occlusion can be viewed as “permission to change”: if a condition is occluded, it is relieved from obeying the constraint of inertia.
In the simplified example of the door and the light, occlusion can be formalized by two predicates
and 
. The rationale is that a condition can change value only if the corresponding occlusion predicate is true at the next time point. In turn, the occlusion predicate is true only when an action affecting the condition is executed.
In general, every action making a condition true or false also makes the corresponding occlusion predicate true. In this case,
is true, making the antecedent of the fourth formula above false for 
; therefore, the constraint that 
does not hold for 
. Therefore, 
can change value, which is also what is enforced by the third formula.
In order for this condition to work, occlusion predicates have to be true only when they are made true as an effect of an action. This can be achieved either by circumscription or by predicate completion. It is worth noticing that occlusion does not necessarily imply a change: for example, executing the action of opening the door when it was already open (in the formalization above) makes the predicate
true and makes 
true; however, 
has not changed value, as it was true already.
represents the fact that the predicate 
will change from time 
to 
. As a result, a predicate changes if and only if the corresponding change predicate is true. An action results in a change if and only if it makes true a condition that was previously false or vice versa.
The third formula is a different way of saying that opening the door causes the door to be opened. Precisely, it states that opening the door changes the state of the door if it had been previously closed. The last two conditions state that a condition changes value at time
if and only if the corresponding change predicate is true at time 
. To complete the solution, the time points in which the change predicates are true have to be as few as possible, and this can be done by applying predicate completion to the rules specifying the effects of actions.
the fact that the condition is true if and only if:
A successor state axiom is a formalization in logic of these two facts. For
example, if
and 
are two
conditions used to denote that the action executed at time
was
to open or close the door, respectively, the running example is encoded as
follows.
This solution is centered around the value of conditions, rather than the
effects of actions. In other words, there is an axiom for every condition,
rather than a formula for every action. Preconditions to actions (which are not
present in this example) are formalized by other formulae. The successor state
axioms are used in the variant to the situation calculus
proposed by
Ray Reiter.
is a variant of the situation calculus. It solves the frame problem by using first-order logic
terms, rather than predicates, to represent the states. Converting
predicates into terms in first order logic is called reification
; the
fluent calculus can be seen as a logic in which predicates representing the
state of conditions are reified.
The difference between a predicate and a term in first order logic is that a term is a representation of an object (possibly a complex object composed of other objects), while a predicate represents a condition that can be true or false when evaluated over a given set of terms.
In the fluent calculus, each possible state is represented by a term obtained by composition of other terms, each one representing the conditions that are true in state. For example, the state in which the door is open and the light is on is represented by the term
. It is important to notice that a term is not true or false by itself, as it is an object and not a condition. In other words, the term 
represent a possible state, and does not by itself mean that this is the current state. A separate condition can be stated to specify that this is actually the state at a given time, e.g., 
means that this is the state at time 
.
The solution to the frame problem given in the fluent calculus is to specify the effects of actions by stating how a term representing the state changes when the action is executed. For example, the action of opening the door at time 0 is represented by the formula:
The action of closing the door, which makes a condition false instead of true, is represented in a slightly different way:
This formula works provided that suitable axioms are given about
and 
, e.g., a term containing two times the same condition is not a valid state (for example, 
is always false for every 
and 
).
uses terms for representing fluents, like the fluent calculus, but also has axioms constraining the value of fluents, like the successor state axioms. In the event calculus, inertia is enforced by formulae stating that a fluent is true if it has been true at a given previous time point and no action changing it to false has been performed in the meantime. Predicate completion is still needed in the event calculus for obtaining that a fluent is made true only if an action making it true has been performed, but also for obtaining that an action had been performed only if that is explicitly stated.
in default logic
:
(if
is true in situation 
, and it can be assumed that 
remains true after executing action 
, then we can conclude that 
remains true).
Steve Hanks and Drew McDermott
argued, on the basis of their Yale shooting
example, that this solution to the frame problem is unsatisfactory. Hudson Turner showed, however, that it works correctly in the presence of appropriate additional postulates.
is a rule with strong negation:
(if
is true at time 
, and it can be assumed that 
remains true at time 
, then we can conclude that 
remains true).
s elude the frame problem rather than solving it. An action description language is a formal language with a syntax that is specific for describing situations and actions. For example, that the action
makes the door open if not locked is expressed by:
The semantics of an action description language depends on what the language can express (concurrent actions, delayed effects, etc.) and is usually based on transition systems.
Since domains are expressed in these languages rather than directly in logic, the frame problem only arises when a specification given in an action description logic is to be translated into logic. Typically, however, a translation is given from these languages to answer set programming
rather than first-order logic.
formal logic in particular. The frame problem in philosophy is therefore the
problem of how a rational agent bounds the set of beliefs to change when an
action is performed.
Artificial intelligence
Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
, the frame problem was initially formulated as the problem of expressing a dynamical domain in logic
Logic
In philosophy, Logic is the formal systematic study of the principles of valid inference and correct reasoning. Logic is used in most intellectual activities, but is studied primarily in the disciplines of philosophy, mathematics, semantics, and computer science...
without explicitly specifying which conditions are not affected by an action. John McCarthy
John McCarthy (computer scientist)
John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...
and Patrick J. Hayes
Patrick J. Hayes
Patrick John Hayes or Pat Hayes is a British computer scientist who lives and works in the United States. , he is a Senior Research Scientist at the Institute for Human and Machine Cognition in Pensacola, Florida. He received a B.A. in Mathematics from University of Cambridge and a Ph.D...
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
Philosophy
Philosophy is the study of general and fundamental problems, such as those connected with existence, knowledge, values, reason, mind, and language. Philosophy is distinguished from other ways of addressing such problems by its critical, generally systematic approach and its reliance on rational...
, where it is formulated as the problem of limiting the beliefs that have to be updated in response to actions.
The name "frame problem" derives from a common technique used by animated cartoon
Animated cartoon
An animated cartoon is a short, hand-drawn film for the cinema, television or computer screen, featuring some kind of story or plot...
makers called framing
Traditional animation
Traditional animation, is an animation technique where each frame is drawn by hand...
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) remains 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 propositionProposition
In logic and philosophy, the term proposition refers to either the "content" or "meaning" of a meaningful declarative sentence or the pattern of symbols, marks, or sounds that make up a meaningful declarative sentence...
s open and on. If these conditions can change, they are better represented by two predicates open(t) and on(t) that depend on time; such predicates are called fluent
Fluent (artificial intelligence)
In artificial intelligence, a fluent is a condition that can change over time. In logical approaches to reasoning about actions, fluents can be represented in first-order logic by predicates having an argument that depends on time...
s. A domain in which the door is closed, the light is off, and the door is opened at time 1 can be directly represented in logic by the following formulae:
The first two formulae represent the initial situation; the third formula represents the effect of executing the action of opening the door at time 1. If such an action had preconditions, such as the door must not be locked, it would have been represented by
. In practice, one would have a predicate for specifying when an action is executed and a rule for specifying the effects of actions. The article on the situation calculusSituation calculus
The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991...
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.
 |
 |
 |
 |
Indeed, another set of conditions that is consistent with the three formulae above is:
 |
 |
 |
 |
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 explicitly specify that all conditions not affected by 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 does not change from time 0 to time 1:
The frame problem is that one such frame axiom is necessary for every pair of action and condition such that the action does not affect the condition. In other words, the problem is that of formalizing a dynamical domain without explicitly 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
Yale shooting problem
The Yale shooting problem is a conundrum or scenario in formal situational logic on which early logical solutions to the frame problem fail. The name of this problem derives from its inventors, Steve Hanks and Drew McDermott, working at Yale University when they proposed it. In this scenario, Fred ...
, 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.
Solutions to the frame problem
In the following, how the frame problem is solved in various formalisms is shown. The formalisms themselves are not presented in full: what is presented are simplified versions that are however sufficient to show how the frame problem is solved.The fluent occlusion solution
This solution was proposed by Erik SandewallErik Sandewall
Erik Sandewall is a Swedish Professor in the Chair of Computer Science at Linköping University since 1975. He is known for his pioneering research in artificial intelligence.- Education :Erik Sandewall received the B.A. and Ph.D...
, who also defined a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
for the specification of dynamical domains; therefore, such a domain can be first expressed in this language and then automatically translated into logic. In this article, only the expression in logic is shown, and only in the simplified language with no action names.
The rationale of this solution is to represent not only the value of conditions over time, but also whether they can be affected by the last executed action. The latter is represented by another condition, called occlusion. A condition is said to be occluded in a given time point if an action has been just executed that makes the condition true or false as an effect. Occlusion can be viewed as “permission to change”: if a condition is occluded, it is relieved from obeying the constraint of inertia.
In the simplified example of the door and the light, occlusion can be formalized by two predicates
and . The rationale is that a condition can change value only if the corresponding occlusion predicate is true at the next time point. In turn, the occlusion predicate is true only when an action affecting the condition is executed.In general, every action making a condition true or false also makes the corresponding occlusion predicate true. In this case,
is true, making the antecedent of the fourth formula above false for ; therefore, the constraint that does not hold for . Therefore, can change value, which is also what is enforced by the third formula.In order for this condition to work, occlusion predicates have to be true only when they are made true as an effect of an action. This can be achieved either by circumscription or by predicate completion. It is worth noticing that occlusion does not necessarily imply a change: for example, executing the action of opening the door when it was already open (in the formalization above) makes the predicate
true and makes true; however, has not changed value, as it was true already.The predicate completion solution
This encoding is similar to the fluent occlusion solution, but the additional predicates denote change, not permission to change. For example, represents the fact that the predicate will change from time to . As a result, a predicate changes if and only if the corresponding change predicate is true. An action results in a change if and only if it makes true a condition that was previously false or vice versa.The third formula is a different way of saying that opening the door causes the door to be opened. Precisely, it states that opening the door changes the state of the door if it had been previously closed. The last two conditions state that a condition changes value at time
if and only if the corresponding change predicate is true at time . To complete the solution, the time points in which the change predicates are true have to be as few as possible, and this can be done by applying predicate completion to the rules specifying the effects of actions.The successor state axioms solution
The value of a condition after the execution of an action can be determined bythe fact that the condition is true if and only if:
- the action makes the condition true;
- the condition was previously true and the action does not make it false.
A successor state axiom is a formalization in logic of these two facts. For
example, if
and are twoconditions used to denote that the action executed at time
wasto open or close the door, respectively, the running example is encoded as
follows.
This solution is centered around the value of conditions, rather than the
effects of actions. In other words, there is an axiom for every condition,
rather than a formula for every action. Preconditions to actions (which are not
present in this example) are formalized by other formulae. The successor state
axioms are used in the variant to the situation calculus
Situation calculus
The situation calculus is a logic formalism designed for representing and reasoning about dynamical domains. It was first introduced by John McCarthy in 1963. The main version of the situational calculus that is presented in this article is based on that introduced by Ray Reiter in 1991...
proposed by
Ray Reiter.
The fluent calculus solution
The fluent calculusFluent calculus
The fluent calculus is a formalism for expressing dynamical domains in first-order logic. It is a variant of the situation calculus; the main difference is that situations are considered representations of states. A binary function symbol \circ is used to concatenate the terms that represent facts...
is a variant of the situation calculus. It solves the frame problem by using first-order logic
terms, rather than predicates, to represent the states. Converting
predicates into terms in first order logic is called reification
Reification
Reification generally refers to bringing into being or turning concrete.Specifically, reification may refer to:*Reification , making a data model for a previously abstract concept...
; the
fluent calculus can be seen as a logic in which predicates representing the
state of conditions are reified.
The difference between a predicate and a term in first order logic is that a term is a representation of an object (possibly a complex object composed of other objects), while a predicate represents a condition that can be true or false when evaluated over a given set of terms.
In the fluent calculus, each possible state is represented by a term obtained by composition of other terms, each one representing the conditions that are true in state. For example, the state in which the door is open and the light is on is represented by the term
. It is important to notice that a term is not true or false by itself, as it is an object and not a condition. In other words, the term represent a possible state, and does not by itself mean that this is the current state. A separate condition can be stated to specify that this is actually the state at a given time, e.g., means that this is the state at time .The solution to the frame problem given in the fluent calculus is to specify the effects of actions by stating how a term representing the state changes when the action is executed. For example, the action of opening the door at time 0 is represented by the formula:
The action of closing the door, which makes a condition false instead of true, is represented in a slightly different way:
This formula works provided that suitable axioms are given about
and , e.g., a term containing two times the same condition is not a valid state (for example, is always false for every and ).The event calculus solution
The event calculusEvent calculus
The event calculus is a logical language for representing and reasoning about actions and their effects first presented by Robert Kowalski and Marek Sergot in 1986.It was extended by Murray Shanahan and Rob Miller in the 1990s....
uses terms for representing fluents, like the fluent calculus, but also has axioms constraining the value of fluents, like the successor state axioms. In the event calculus, inertia is enforced by formulae stating that a fluent is true if it has been true at a given previous time point and no action changing it to false has been performed in the meantime. Predicate completion is still needed in the event calculus for obtaining that a fluent is made true only if an action making it true has been performed, but also for obtaining that an action had been performed only if that is explicitly stated.
The default logic solution
The frame problem can be thought of as the problem of formalizing the principle that, by default, "everything is presumed to remain in the state in which it is" (Leibniz, "An Introduction to a Secret Encyclopædia", c. 1679). This default, sometimes called the commonsense law of inertia, was expressed by Raymond ReiterRaymond Reiter
Raymond Reiter , was a Canadian computer scientist and logician. He was one of the founders of the field of non-monotonic reasoning with his work on default logic, model-based diagnosis, closed world reasoning, and truth maintenance systems...
in default logic
Default logic
Default logic is a non-monotonic logic proposed by Raymond Reiter to formalize reasoning with default assumptions.Default logic can express facts like “by default, something is true”; by contrast, standard logic can only express that something is true or that something is false...
:
(if
is true in situation , and it can be assumed that remains true after executing action , then we can conclude that remains true).Steve Hanks and Drew McDermott
Drew McDermott
Drew McDermott is a Professor of Computer Science at Yale University. He was born in 1949, and lived in the Midwestern United States , for four years, and in Brazil .-Education:...
argued, on the basis of their Yale shooting
Yale shooting problem
The Yale shooting problem is a conundrum or scenario in formal situational logic on which early logical solutions to the frame problem fail. The name of this problem derives from its inventors, Steve Hanks and Drew McDermott, working at Yale University when they proposed it. In this scenario, Fred ...
example, that this solution to the frame problem is unsatisfactory. Hudson Turner showed, however, that it works correctly in the presence of appropriate additional postulates.
The answer set programming solution
The counterpart of the default logic solution in the language of answer set programmingAnswer set programming
Answer set programming is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers -- programs for generating stable...
is a rule with strong negation:
(if
is true at time , and it can be assumed that remains true at time , then we can conclude that remains true).Action description languages
Action description languageAction description language
In artificial intelligence, Action description language is an automated planning and scheduling system in particular for robots. It is considered an advancement of STRIPS. Pednault proposed this language in 1987...
s elude the frame problem rather than solving it. An action description language is a formal language with a syntax that is specific for describing situations and actions. For example, that the action
makes the door open if not locked is expressed by:-
causes 
if 
The semantics of an action description language depends on what the language can express (concurrent actions, delayed effects, etc.) and is usually based on transition systems.
Since domains are expressed in these languages rather than directly in logic, the frame problem only arises when a specification given in an action description logic is to be translated into logic. Typically, however, a translation is given from these languages to answer set programming
Answer set programming
Answer set programming is a form of declarative programming oriented towards difficult search problems. It is based on the stable model semantics of logic programming. In ASP, search problems are reduced to computing stable models, and answer set solvers -- programs for generating stable...
rather than first-order logic.
Related problems
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 problemQualification problemIn philosophy and AI , the qualification problem is concerned with the impossibility of listing all the preconditions required for a real-world action to have its intended effect. It might be posed as how to deal with the things that prevent me from achieving my intended result...
- ramification problemRamification problemIn philosophy and artificial intelligence , the ramification problem is concerned with indirect consequences of an action. It might be posed as how to represent what happens implicitly due to an action or to control secondary and tertiary effects within the same period...
- relevance problem
- temporal projection problem
The frame problem in philosophy
In philosophy, the frame problem is about rationality in general, rather thanformal logic in particular. The frame problem in philosophy is therefore the
problem of how a rational agent bounds the set of beliefs to change when an
action is performed.
See also
- Common senseCommon senseCommon sense is defined by Merriam-Webster as, "sound and prudent judgment based on a simple perception of the situation or facts." Thus, "common sense" equates to the knowledge and experience which most people already have, or which the person using the term believes that they do or should have...
- Defeasible reasoningDefeasible reasoningDefeasible reasoning is a kind of reasoning that is based on reasons that are defeasible, as opposed to the indefeasible reasons of deductive logic...
- Non-monotonic logicNon-monotonic logicA non-monotonic logic is a formal logic whose consequence relation is not monotonic. Most studied formal logics have a monotonic consequence relation, meaning that adding a formula to a theory never produces a reduction of its set of consequences. Intuitively, monotonicity indicates that learning a...
- Linear logicLinear logicLinear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter...
External links
- 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
- The History of the Frame Problem covers the history of the frame problem up to 2001.