ABSTRACT
Artificial intelligence.—In 1969, while working on a logical formalism (→LOGIC) called situation calculus for reasoning about the actions of a robot R (→ACTION, ROBOTICS), John McCarthy and Patrick Hayes came up against the following difficulty, which they named the frame problem. Action a, say R moves from A to B, has preconditions (R is in A) and effects (R is in B). If a is performed in situation s, the result is situation s′=exec (s, a), and if t(p, s) means that proposition p is true in situation s, we have
Suppose R is red in situation s, that is,
and one asks what color it is in situation s′. The frame problem lies in the fact that (1) and (2) do not allow us to answer this question. The list of a’s effects would have to state that the color of R remains unchanged. Imagine the number of similar facts that would have to be included in the description of every action! One idea for avoiding such an enumeration would be to store in s′ the truth value of propositions not listed among the effects of a. But this would not be suitable since one would conclude that in s′= (location (R), A) was still true.
