next up previous

Introduction-Objectives of Situation Calculus

The logic approach to AI ([McCarthy, 1959] and [McCarthy, 1989]) is to make a computer program that represents what it knows about the world in general, what it knows about the situation it is in, and also its goals all as sentences in some mathematical logical language. It then infers logically what action is appropriate for achieving its goal and does it. Since 1980 it has been widely known that nonmonotonic inference must be included. The actions it can perform include some that generate sentences by other means than logical inference, e.g. by observation of the world or by the use of special purpose non-logical problem solvers.

Simpler behaviors, e.g. actions controlled by servomechanisms or reflexes can be integrated with logic. The actions decided on by logic can include adjusting the parameters of ongoing reflexive actions. Thus a person can decide to walk faster when he reasons that otherwise he will be late, but this does not require that reason control each step of the walking. gif

Situation calculus is an aspect of the logic approach to AI. A situation is a snapshot of the world at some instant. Situations are rich objects in that it is not possible to completely describe a situation, only to say some things about it. From facts about situations and general laws about the effects of actions and other events, it is possible to infer something about future situations. Situation calculus was first discussed in [McCarthy, 1963], but [McCarthy and Hayes, 1969] was the first widely read paper about it.

In this formalization of action in situation calculus, we treat three kinds of problem--narrative, planning and prediction.

Of these, narrative seems to be the simplest. A narrative is an account of what happened. We treat it by giving some situations and some events and some facts about them and their relations. Situations in a narrative are partially ordered in time. The real situations are totally ordered, but the narrative does not include full information about this ordering. Thus the temporal relations between situations in different places need only be described to the extent needed to describe their interactions.

In situation calculus as it was originally envisaged and has been used, events (mainly actions) in a situation produce next situations, e.g. s' = result(e,s). The original theory did not envisage more than one event occurring in a situation, and it did not envisage intermediate situations in which events occur. However, rarely did people write axioms that forbade these possibilities; it's just that no-one took advantage of them. gif

Our present formalism doesn't really change the basic formalism of the situation calculus much; it just takes advantage of the fact that the original formalism allows treating concurrent events even though concurrent events were not originally supposed to be treatable in that formalism. Gelfond and Lifschitz treat concurrent events in a different way from what we propose here.

In a narrative, it is not necessary that what is said to hold in a situation be a logical consequence (even nonmonotonically) of what was said to hold about a previous situation and known common sense facts about the effects of events. In the first place, in stories new facts about situations are often added, e.g. ``When Benjamin Franklin arrived in London it was raining''. In the second place, we can have an event like tossing a coin in which neither outcome has even a nonmonotonic preference.

Nevertheless, some narratives are anomalous. If we record that Junior flew to Moscow, and, in the next situation mentioned, assert that he is in Peking, a reader will feel that something has been left out, some Gricean implicature [Grice, 1989] has been violated. We want to introduce a concept of a proper narrative, but it isn't clear exactly what it should be. The fluents holding in a new situation should be reasonable outcomes of the events that have been reported, except for those fluents which are newly asserted, e.g. that it was raining in London when Franklin arrived. Perhaps the assertions that do not follow from previous events should sometimes be tagged as such. The word ``but'' does this in ordinary language, so maybe we want a but construction. Of course, ``but'' is used in discourses that are not narratives.

In interpreting the following formalizations, we regard situations as rich objects and events as poor. In fact, we are inclined to take a deterministic view within any single narrative. In principle, every event that occurs in a situation and every fact about following situations is an inevitable consequence of the facts about the situation. Thus it is a fact about a situation that a coin is tossed and that it comes up tails. However, such facts are only occasionally consequences of the facts about the situation that are actually stated in the narrative.

Perhaps narrative seems easy, since it is not yet clear what facts must be included in a narrative and what assertions should be inferrable from a narrative.

next up previous

John McCarthy
Thu Apr 27 22:02:22 PDT 2000