Temporal Projection and Explanation
Proceedings of the Eleventh International Joint Conference on Artificial Intelligence. Planning, Scheduling, Reasoning About Actions. Pages 906-910.
© 1989 International Joint Conferences on Artificial Intelligence
Abstract
We propose a solution to problems involving temporal projection and explanation (e.g., the Yale shooting problem) based on the idea that whether a situation is abnormal should not depend upon historical information about how the situation arose. We apply these ideas both to the Yale shooting scenario and to a blocks world domain that needs to address the qualification problem.
- Baker, 1989)
- Andrew B. Baker . A simple solution to the Yale shooting problem. In Proceedings of the First International Conference on Principles of Knowledge Representation and Reasoning, 1989.
- Finger, 1987)
- Jeffrey J . Finger . Exploiting Constraints in Design Synthesis. PhD thesis, Stanford Univer- sity, Stanford, CA, 1987.
- Gelfond, 1988)
- Michael Gelfond. Autoepistemic logic and formalization of common-sense reasoning. In Proceedings 1 g99 Non-monotonic Reasoning Work- shop, American Association for Artificial Intelli- gence, Munich, 1988.
- Ginsberg, 1987)
- Matthew L. Ginsberg. Readings in Nonmonotonic Reasoning. Morgan Kaufmann, Los Altos, CA, 1987.
- Ginsberg, 1989)
- Matthew L. Ginsberg. Situations and Descriptions. Technical Report, Stanford Univer- sity, 1989.
- Ginsberg and Smith, 1988)
- Matthew L. Ginsberg and David E. Smith. Reasoning about action I: A possi- ble worlds approach. Artificial Intelligence, 35:165- 195, 1988.
- Hanks and McDermott , 1987) Steve Hanks and Drew McDermott . Nonmonotonic logics and tempo- ral projection. Artificial Intelligence, 33:379-412, 1987.
- Haugh, 1987)
- Brian Haugh. Simple causal minimiza- tions for temporal persistance and projection. In Proceedings of the Sixth National Conference on Ar- tificial Intelligence, pages 218-223 , 1987.
- Kautz, 1986)
- Henry A. Kautz. The logic of persistence. In Proceedings of the Fifth National Conference on Artificial Intelligence , pages 401-405 , 1986.
- [Lifschitz, 1986] Vladimir Lifschitz. On the semantics of STRIPS. In Proceedings of the 1986 Workshop on Planning and Reasoning about Action, Timberline, Oregon, 1986.
- [Lifschitz, 1987a] Vladimir Lifschitz. Formal theories of action. In Proceedings of the 1987 Workshop on the Frame Problem in Artificial Intelligence, Lawrence, Kansas, 1987.
- [Lifschitz, 1987b] Vladimir Lifschitz. Pointwise circum- scription. In Matthew L. Ginsberg, editor, Readings in Nonmonotonic Reasoning, Morgan Kaufmann, Los Altos, CA, 1987.
- [Lifschitz and Rabinov, 1989] Vladimir Lifschitz and Arkady Rabinov. Miracles in formal theories of ac- tion. Artificial Intelligence, 38:225-237, 1989.
- [McDermott, 1987] Drew McDermott. A critique of pure reason. Computational Intelligence, 3:151- 160, 1987.
- [Shoham, 1986] Yoav Shoham. Chronological igno- rance. In Proceedings of the Fifth National Confer- ence on Artificial Intelligence, pages 389-393, 1986.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
The paper [1987) by Hanks and McDermott describing the Yale shooting problem has generated such a flurry of responses that it is difficult to imagine what another one can contribute. The points raised by Hanks and McDermott, both formal and philosophical, have been discussed at substantial length elsewhere.
It is not our intention to enter here into the philosoph ical portion of this discussion. Rather, the contribution we hope to make is technical. In [Hanks and McDer mott, 1987), the authors raise a specific technical ques tion: How is a certain form of temporal reasoning to be modelled? They go on to demonstrate that none of the then existing descriptions of action using nonmonotonic reasoning is suitable, and proceed from this observation to draw more far-reaching conclusions regarding the role of formal methods in AI. A discussion of these philosoph ical issues is outside the intended scope of this paper.
Since the initial circulation of Hanks' and McDer mott's ideas in 1985, a variety of researchers have pro posed solutions to the technical challenge they raised [Baker, 1989, Gelfond, 1988, Haugh, 1987, Kautz, 1986, Lifschitz, 1987a, Lifschitz, 1987b, Lifschitz and Rabinov, 1989, Shoham, 1986, and others] . Unfortunately, subse quent analysis (most of it over coffee tables) has shown most of these intended solutions to be flawed for one or another technical reason.
We begin in the next section by presenting a brief description of the Yale shooting problem itself, and a variant that appears in [Baker, 1989). The description given is in fact somewhat simpler than that presented in [Hanks and McDermott, 1987), but still retains all of the troublesome features of the original . In Section 3, we go on to describe proposed solutions, and investigate their technical shortcomings. - The formal underpinnings of our own ideas are pre sented in Section 4, and we return to the Yale shooting scenario in Section 5, showing that our notions can be used to solve both the original problem and the variant presented in Section 2. In Section 6, we extend our ideas to deal with the qualification problem in a simple blocks world scenario. Concluding remarks are contained in Section 7.
·This work has been supported by the Rockwell Palo Alto Laboratory, by General Dynamics, and by NSF under grant number DCR-8620059. The first author is supported by an AFOSR graduate fellowship .
2 The Yale shooting
The Yale shooting problem involves reasoning about a sequence of actions . In order to keep our notation as manageable as possible, we will denote the fact that some fluent f holds in a situation s by writing simply
A situation will be written as an ordered sequence of actions
(We write the last action first so that we can append new actions to the front of the sequence.) The initial situation is written simply as (), corresponding to the empty sequence of actions.
The Hanks-McDermott problem involves an individ ual, often named Fred, and a gun. Fred may or may not be alive, and the gun may or may not be loaded. In the initial situation, however, Fred is alive and the gun 1s loaded:
We are also told that in any situation in which the gun is loaded, firing it will kill Fred. We write this as :
where we are using (als) to construct the result of per forming the action a in the situation s. Finally, we are given a frame axiom:
In other words, unless the action a is abnormal in that it potentially reverses the fluent f in the situation s, f will persist through the execution of the action. We will presumably minimize the extent of the abnormality predicate using any of the formal approaches to nonmon otonic reasoning [Ginsberg, 1987). 1
Now suppose that in the initial situation, we wait and then fire the gun. Does Fred die? In other words, what can we say about
Remarkably, we can say very little about it. Our in tuition is that the shooting action should be abnormal, and should cause Fred's aliveness to be terminated. In other words, we should be able to derive
from the domain description given by (1)-(4) .
Unfortunately, we cannot do th:s . As Hanks and Mc Dermott noticed, all that we can actually derive is the disjunction
This is saying that either Fred becomes not alive after the shooting action, or the waiting action causes the gun to become unloaded. If our intention is merely to minimize abnormality, there is no way to select between these two possibilities . 2 As this sort of a minimization is all that is effected by any of the existing formalizations of nonmonotonic reasoning, all of these formalizations are incapable of concluding that Fred is dead after we shoot him.
Causal reasoning of this sort , where one reasons for ward in time from a fixed initial state, is called "tem poral projection" by Hanks and McDermott in [1987] . Before we turn to the various solutions that have been proposed to the temporal projection problem, let us dis cuss its dual , the temporal explanation problem [Hanks and McDermott, 1987].
This involves reasoning backward from information given about some state in the future . Here is an example similar to one introduced by Kautz in [1986) :
In this example, which we call the "murder mystery," we drop the axiom (2) saying that the gun is loaded in the initial situation, and replace i t with a statement to the ~ffect that if we fire the gun and then wait, Fred will be dead:
1 Our formulation is slightly different from that presented in [Hanks and McDermott, 1987]. We use it because: (1) It is as natural a description of the domain as that given by Hanks and McDermott in [1987], (2 ) In the original description, it was impossible to conclude ·holds(alive, (shoot,vait )) in either extension, since there were no axioms relating alive to the fluent dead used in [Hanks and McDermott , 1987], and (3) The description appearing in [Ha~ks and -~cDerm~tt, 1987] requires t he introduction of an axwm exphc1tly statmg that the shoot action leads to an abnormality for the alive predicate. This explicit analog to STR IP S delete lists will make it difficult to ext end this approach to more complex domains [Ginsberg and Smith, 1988, Lifschitz , 1986].
2 In our formulat ion, there is also a third possibility, namely ab(vait , alive, () ), where Fred dies while we wait to shoot him. This possibility will have no effect on the ar guments to be presented in this paper.
Given this information; is it legitimate to conclude that the gun was loaded in the initial situation after all?
One would expect so, although this conclusion, as in the original Yale shooting problem, is not sanctioned by circumscription. The reason is that we are unable to distinguish between extensions with
where Fred dies when we shoot him, and those with
where Fred dies acausally during the waiting action. In deed even if we could select the abnormality appearing in (6), it would not follow from this that the gun was actually loaded before the shooting action took place.
3 Solutions
The collection of proposed solutions to the original Yale shooting problem fall into roughly two groups. One set of researchers [Kautz, 1986, Lifschitz , 1987b, Shoham, 1986] suggests resolving the ambiguity underlying the problem by appealing to temporal information; another [Haugh, 1987, Lifschitz, 1987a, Lifschitz and Rabinov, 1989] suggests modifying the domain description so as to capture the notion of causality directly.
3.1 Temporal orders
The first idea involves selecting among competing ex tensions based on a temporal order. Thus we might prefer the extension in which ab(shoot, alive, (wait)) holds over that in which ab(wait,loaded,()) holds on the grounds that ab( wait, loaded, ()) refers to an ear lier time than does ab( shoot , alive, (wait)) . This is the older of the two approaches, and is in fact endorsed by Hanks and McDermott as a possible solution in [1987] ; the proponents of this approach argue that there can be no causal reason for the earlier abnormality.
Unfortunately, this approach can be used for temporal projection problems only. In the murder mystery, where we need to select between
and
the chronological approaches favor the second extension, a choice that is at odds with our intuition.
One might hope that one could use "reverse chro~o logical minimization" to deal with tem~oral_ expl~natwn problems, now preferring those extenswns m wh1ch the abnormality occurs as early as possible. Unfortunately, reverse chronological minimization remains unable to conclude that the gun was actually loaded in the murder mystery. In addition, it seems extre~ely unlike!~ ~hat problems of practical interest will adm1t a clear dl~tmc tion between these two aspects of temporal reasomng.
Other proposed solutions [Haugh, 1987, Lifschitz, 1987a, Lifschitz and Rabinov, 1989] have involved reformulat ing the original domain description in a way that cap tures the notion of causality directly. Loosely speaking, these approaches proceed by indicating ezplicitly that the shooting action causes Fred to become not alive, and by saying that no change can occur unless there is a causal explanation for that change.
Hanks and McDermott raise a variety of philosophical objections to this reformulation. Principally, they argue that nonmonotonic formalisms were introduced to enable us to give intuitive descriptions of things like the frame axiom. It would be unfortunate if they needed to resort to descriptions of causality that were (at least to Hanks' and McDermott's eyes) anything but intuitive after all.
In addition, it will in general J:>e impossible to explic itly list all possible causal connections; some will be con sequences of constraints on the situation that arises when an action is executed. 3 The causal approaches suggest that this problem can be addressed by minimizing the extent of the causes predicate instead of minimizing ab normality.
This does not work in an situations, however. The simplest one in which it fails is probably Hanks' and McDermott's original description of the Yale shooting problem, in which the gun is initially unloaded and there is a load action that loads it:
The intent of the above axiom is that the load action causes the fluent loaded to become true.
Now we also introduce a fluent dead, along with a domain constraint saying that Fred is dead if and only if he is not alive:
Finally, we have an axiom saying that shooting the gun causes Fred to become not alive:
Now, we would like to be able to conclude that since shooting the gun causes Fred to become not alive, it also causes him to die:
Unfortunately, this does not follow. Another possible minimization of the causes predicate is one in which the load action causes Fred to die, and the theory needs to be modified in a way that disallows this choice. Although a variety of suggestions have been made to address this problem, none of them is completely satisfactory at this point .
4 Situations and states
Note, however, that the causal approaches do correctly conclude that the gun was loaded in the murder mys tery, since this is the only explanation that avoids the introduction of a new causal rule.
3 This is known as the ramification problem [Finger, 198 7, Ginsberg and Smith, 1988].
The causal approaches work because they describe ac tions not directly in terms of situations, but in terms of the values of various fluents in those situations. Because of this, they have no reason to introduce an abnormality into sin order to avoid one in (waitls).
In [Baker, 1989], this observation led to .the argument that the simplest way to solve the Yale shooting problem is simply to allow the function that computes the result of an action to vary. It is shown there that this idea can indeed be used successfully; the ideas we are about to present are a natural outgrowth of this earlier work. 4
Another way to understand the problem is as follows: When we attempt to minimize abnormalities of the form
we are not minimizing over situations so much as we are over action sequences; we might just as well be minimiz ing a function
This sort of a minimization, however, completely misses the intuition that we are hoping to capture - our intent is to think of a situation not as a sequence of actions, but instead in terms of the values taken by various fluents.
In order to make this explicit , we will make a distinc tion between a situation, such as (wait), and a state, which will be described simply in terms of fluent values . If a fluent f changes value when an action a is performed in a situation s, we will think of the abnormality not as a function of the situation s, but as a function of the state corresponding to it.
In order to formalize this, we introduce a subscript onto the frame axiom (4):
The subscript indicates that it is a situation that is being considered abnormal.
In order to connect situations to the state vectors de scribing them, we introduce a predicate
that is intended to capture the notion that the situation s is described by the state vector v. The intention here is that v contains enough information to determine the value assigned by s to any particular fluent f. In the Yale shooting domain, v might contain two entries, cor responding to the values of the alive and loaded fluents respectively; the value of any other fluent, such as dead, can be computed from these two. 5
4 We also avoid several problems with the approach in [Baker, 1989]. Varying the value of a function is at odds with the unique names assumption, and makes it difficult to implement the suggestions in [Baker, 1989]; the work we are presenting assumes the validity of the unique names assump tion, in accordance with most work in logic programming. We also avoid the introduction of the temporal order used in [Baker, 1989], although this is a less substantial matter .
5 The conditions that the state completely describe the sit uation and that the user supply the system with a description of the describes predicate are fairly restrictive ones. In a forthcoming paper [Ginsberg, 1989], one of us will discuss an extension of these ideas that uses partial descriptions only.
We now say that abnormal situations correspond to abnormal state vectors:
We also need an axiom saying that for any given state vector v, there is some situation s(v) that is described by it :
(Note that this axiom says only that some situation is described by the state vector v; in actuality many situ ations may be.)
Instead of minimizing ab, , we minimize ab.,, allowing all other predicates to vary. That's all there is to it.
5 The shooting domain
As an example, we return to the Yale shooting domain, which we have axiomatized using (3), describing the shooting action, and (7), describing the predicate dead. We also capture the describes predicate as:
We begin by noting that it is a consequence of the above axioms that
In other words, the shooting action is abnormal in any situation where Fred is alive and the gun is loaded.
To see this, suppose we denote by s0 the situation s[alive, loaded] . It follows from (12) that
so that
holds( alive, s0 ) 1\ holds(loaded, so), and therefore
and
Applying (11) , we obtain (13) .
No other state vectors or actions will be abnormal if abv has its minimal extent , so we conclude that
and therefore that
where the initial situation () is given by (1) and (2) . It follows that the gun remains loaded during the wait ac tion, and Fred .dies. The murder mystery is also solved correctly, since it is only by assuming holds(loaded, () ) that we can avoid increasing the extent of the abv pred icate.
6 The blocks world
The ideas we have presented can be tested much more thoroughly if we consider a somewhat more complex dcr main of discourse . Let us therefore turn our attention to a simple blocks world domain containing three blocks, A, Band C.
In this domain, there is an action move( b, l) that takes a block band relocates it at a location l . However, rather than treat the requirements that both the block and the target location be clear as preconditions to the move ac tion, we will view them as qualifications to it. This leads us to describe the move action as:
where the loc(b, l) means that the block b is located at l.
The subscripts q and s on the abnormality predicate indicate respectively that it is a qualification abnormal ity that is being considered, and that the qualification is being described for situations as opposed to state vec tors. As in Section 4, we introduce:
and minimize abqv instead of abq· .
In order to keep our notation uniform, we introduce a subscript f into the "frame" axioms (10) and (11), obtaining
Now when we do the minimization, we minimize abqv preferentially over ab f v. If we were not to do so, then we could avoid all violations of the frame axiom simply by assuming that all actions were qualified! We write our circumscription policy as
Returning to the blocks world, we have the domain constraints
saying respectively that only one block can be in any particular location, that a block can be in only one place at a time, and that no block can be on top of itself.
Next , we describe a situation by giving the locations of the three blocks:
Finally, although the move action has no explicit pre conditions , it can be qualified if either the block being moved or the target location is not clear:
At this point, our description is complete. (The action of moving a block to itself is qualified by virtue of the fact that the success of the action is in direct conflict with (20).) But there is one additional subtlety we need to consider. Consider again the axiom (12) saying that every description corresponds to some situation; what situation corresponds to the state [l1, h, 12], where both A and B are located at l1?
In light of the domain constraint ( 18) indicating that only one block can be at any particular location, there is no such situation. It follows that ( 18) and ( 12) are in conflict; what we really wanted to say in (12) is that ev ery consistent description has some associated situation. We therefore weaken (12) to become
and minimize inconsistent . Since whether or not a state vector is inconsistent should be determined before considering the qualification or frame problem, our re vised circumscription policy is
Note that the predicate inconsistent appears nowhere else in our domain description; specifically, we do not need to axiomatize a notion of consistency. The determination of the consistency of any particular state vector is handled automatically by the circumscription.
Note also that the ramification problem is handled by. this approach. Thus, for example, if we move a block from one location to another, we are able to conclude that the block is no longer at its original location with out introducing an additional axiom to this effect - the conclusion is a consequence of the relocation, together with the axiom (19) saying that the block can be in only one location at a time .
7 Conclusion
We hope that the simplicity of the solution we have sug gested will defuse some of the arguments that McDer mott has recently raised against formal work on com monsense reasoning [McDermott, 1987). Indeed, the de scription of action we have developed seems rather more robust than a procedural description of action such as that proposed in [Hanks and McDermott, 1987). The ramification problem is well-treated, we do not need to supply an explicit "delete" list of those facts that an ac tion makes abnormal, and it is possible to incorporate qualifications into our description. To the best of our knowledge, the description we have presented is the only one capable of representing the blocks world of Section 6 using a nonmonotonic description of the frame axiom and an implicit description of ramifications in terms of domain constraints.
Much work remains to be done, however. For exam ple, all of the situations we have examined in this paper have been "complete," in that we have been able to com pute the state vectors associated with them. If we are to incorporate our description of action into a general purpose planner, however, we will need to work with situations about which we have only partial knowledge, such as situations in which the goal has been achieved, or in which some subgoal has been accomplished. Prelimi nary results in this direction are the focus of [Ginsberg, 1989) .
We will also need to extend our results to deal with more sophisticated ontologies of time and action. Al though space does not allow us to discuss these matters here, these issues present no substantial difficulty for the approach that we have described. Essentially, the con tribution we have made is to notice that we must avoid being syntactically trapped into minimizing abnormal ity over actions as in (9), and must instead be careful to ensure that we perform the minimization over the combinations of fluents and values to which these action sequences correspond. This observation is independent of the representation we choose for time or action, and extends easily to integer- or real-valued time and to con current actions .
Acknowledgement
We are grateful to Pat Hayes, David Israel, Paul Mor ris, Karen Myers, Eunok Paek, Yoav Shoham and Dave Smith for many stimulating discussions , and are espe cially indebted to Vladimir Lifschitz for careful conver sations during a Stanford faculty retreat .
@inproceedings{ijcai1989p145,
title = {Temporal Projection and Explanation},
author = {Baker, Andrew B. and Ginsberg, Matthew L.},
booktitle = {Proceedings of the Eleventh International Joint Conference on
Artificial Intelligence, {IJCAI-89}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {N. S. Sridharan},
pages = {906--910},
year = {1989},
month = {8},
note = {Planning, Scheduling, Reasoning About Actions},
url = {https://ijcai.org/proceedings/1989/145},
}
TY - CPAPER TI - Temporal Projection and Explanation AU - Baker, Andrew B. AU - Ginsberg, Matthew L. T2 - Proceedings of the Eleventh International Joint Conference on Artificial Intelligence, IJCAI-89 PB - International Joint Conferences on Artificial Intelligence PY - 1989 SP - 906 EP - 910 UR - https://ijcai.org/proceedings/1989/145 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: