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 (later identified as a turkey) is initially alive and a gun is initially unloaded. Loading the gun, waiting for a moment, and then shooting the gun at Fred is expected to kill Fred. However, if inertia is formalized in logic by minimizing the changes in this situation, then it cannot be uniquely proved that Fred is dead after loading, waiting, and shooting. In one solution, Fred indeed dies; in another (also logically correct) solution, the gun becomes mysteriously unloaded and Fred survives.

Technically, this scenario is described by two fluents (a fluent is a condition that can change truth value over time): $alive$ and $loaded$. Initially, the first condition is true and the second is false. Then, the gun is loaded, some time passes, and the gun is fired. Such problems can be formalized in logic by considering four time points $0$, $1$, $2$, and $3$, and turning every fluent such as $alive$ into a predicate $alive(t)$ depending on time. A direct formalization of the statement of the Yale shooting problem in logic is the following one:

: $alive(0)$
: $\neg loaded(0)$
: $true \rightarrow loaded(1)$
: $loaded(2) \rightarrow \neg alive(3)$

The first two formulae represent the initial state. The third formula formalizes the effect of loading the gun at time $0$. The fourth formula formalizes the effect of shooting at Fred at time $2$. This is a simplified formalization in which action names are neglected and the effects of actions are directly specified for the time points in which the actions are executed. See situation calculus for details.

The formulae above, while being direct formalizations of the known facts, do not suffice to correctly characterize the domain. Indeed, $\neg alive(1)$ is consistent with all these formulae, although there is no reason to believe that Fred dies before the gun has been shot. The problem is that the formulae above only include the effects of actions, but do not specify that all fluents not changed by the actions remain the same. In other words, a formula $alive(0) \equiv alive(1)$ must be added to formalize the implicit assumption that loading the gun ''only'' changes the value of $loaded$ and not the value of $alive$. The necessity of a large number of formulae stating the obvious fact that conditions do not change unless an action changes them is known as the frame problem.

An early solution to the frame problem was based on minimizing the changes. In other words, the scenario is formalized by the formulae above (that specify only the effects of actions) and by the assumption that the changes in the fluents over time are as minimal as possible. The rationale is that the formulae above enforce all effect of actions to take place, while minimization should restrict the changes to exactly those due to the actions.

In the Yale shooting scenario, one possible evaluation of the fluents in which the changes are minimized is the following one.

This is the expected solution. It contains two fluent changes: $loaded$ becomes true at time 1 and $alive$ becomes false at time 3. The following evaluation also satisfies all formulae above.

{, cellpadding="5"
, $alive(0)$
, $alive(1)$
, $alive(2)$
, $alive(3)$
, -
, $\neg loaded(0)$
, $loaded(1)$
, $\neg loaded(2)$
, $\neg loaded(3)$

In this evaluation, there are still two changes only: $loaded$ becomes true at time 1 and false at time 2. As a result, this evaluation is considered a valid description of the evolution of the state, although there is no valid reason to explain $loaded$ being false at time 2. The fact that minimization of changes leads to wrong solution is the motivation for the introduction of the Yale shooting problem.

While the Yale shooting problem has been considered a severe obstacle to the use of logic for formalizing dynamical scenarios, solutions to it are known since the late 1980s. One solution involves the use of predicate completion in the specification of actions: according to this solution, the fact that shooting causes Fred to die is formalized by the preconditions: ''alive'' and ''loaded'', and the effect is that ''alive'' changes value (since ''alive'' was true before, this corresponds to ''alive'' becoming false). By turning this implication into an ''if and only if'' statement, the effects of shooting are correctly formalized. (Predicate completion is more complicated when there is more than one implication involved.)

A solution proposed by Erik Sandewall was to include a new condition of occlusion, which formalizes the “permission to change” for a fluent. The effect of an action that might change a fluent is therefore that the fluent has the new value, and that the occlusion is made (temporarily) true. What is minimized is not the set of changes, but the set of occlusions being true. Another constraint specifying that no fluent changes unless occlusion is true completes this solution.

The Yale shooting scenario is also correctly formalized by the Reiter version of the situation calculus, the fluent calculus, and the action description languages.

In 2005, the 1985 paper in which the Yale shooting scenario was first described received the AAAI Classic Paper award. In spite of being a solved problem, that example is still sometimes mentioned in recent research papers, where it is used as an illustrative example (e.g., for explaining the syntax of a new logic for reasoning about actions), rather than being presented as a problem.

See also

* Circumscription (logic)
* Frame problem
* Situation calculus

References

* M. Gelfond and V. Lifschitz (1993). Representing action and change by logic programs. ''Journal of Logic Programming'', 17:301–322.
* S. Hanks and D. McDermott (1987). Nonmonotonic logic and temporal projection. ''Artificial Intelligence'', 33(3):379–412.
* J. McCarthy (1986). Applications of circumscription to formalizing common-sense knowledge. ''Artificial Intelligence'', 28:89–116.
* T. Mitchell and H. Levesque (2006). The 2005 AAAI Classic Paper awards. "AI Magazine", 26(4):98–99.
* R. Reiter (1991). 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.
* E. Sandewall (1994). ''Features and Fluents''. Oxford University Press.

Logic programming
Knowledge representation
1987 introductions