Editing Frame problem (section)

==Description==
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 [[proposition]]s <math>\mathrm{open}</math> and <math>\mathrm{on}</math>. If these conditions can change, they are better represented by two [[Predicate (computer programming)|predicate]]s <math>\mathrm{open}(t)</math> and <math>\mathrm{on}(t)</math> that depend on time; such predicates are called [[fluent (artificial intelligence)|fluent]]s. A domain in which the door is closed and the light off at time 0, and the door opened at time 1, can be directly represented in logic {{clarify|reason=What kind of logic? [Old reason: If ordinary predicate logic is meant, what is the purpose of the 'true →' in the 3rd formula? If some other logic (situation calculus?) is meant, it should be stated explicitly here, together with the purpose of the 'true →' (e.g. some empty action?) in that logic.] (Changed, although it might need to be reverted.)|date=August 2013}} by the following formulae:

:<math>\neg \mathrm{open}(0)</math>
:<math>\neg \mathrm{on}(0)</math>
:<math>\mathrm{open}(1)</math>

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 being unlocked, it would have been represented by <math>\neg \mathrm{locked}(0) \implies \mathrm{open}(1)</math>. In practice, one would have a predicate <math>\mathrm{executeopen}(t)</math> for specifying when an action is executed and a rule <math>\forall t . \mathrm{executeopen}(t) \implies \mathrm{open}(t+1)</math> 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.

:{|
| <math>\neg \mathrm{open}(0)</math> &nbsp; &nbsp;  || <math>\mathrm{open}(1)</math>
|-
| <math>\neg \mathrm{on}(0)</math>   || <math>\neg \mathrm{on}(1)</math>
|}

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

:{|
| <math>\neg \mathrm{open}(0)</math> &nbsp; &nbsp;  || <math>\mathrm{open}(1)</math>
|-
| <math>\neg \mathrm{on}(0)</math>   || <math>\mathrm{on}(1)</math>
|}

The frame problem is that specifying only which conditions are changed by the actions does not entail 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:

:<math>\mathrm{on}(0) \iff \mathrm{on}(1)</math>

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.{{clarify|reason=Shouldn't then the frame axiom be the following modification of the above rule: '∀t.executeopen(t)→open(t+1)∧(on(t+1)↔on(t))' ? In contrast, the formula 'on(0)↔on(1)' seems to be too particular taylored to the 'executeopen(0)' situation.|date=August 2013}} 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 (logic)|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 axiom]]s, etc.; they are explained below. By the end of the 1980s, the frame problem as defined by McCarthy and Hayes was solved{{clarify|reason=Mention the (combination of) approach(es) by which the frame problem was solved.|date=August 2013}}. 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.