next up previous
Next: Elaboration tolerance Up: Actions and other events Previous: Actions and other events

Situation calculus and the real world

 

There have been many formulations of situation calculus.

[MH69] regarded a situation as a snapshot of the world at some instant of time. Such a system could not be known and described completely, but a person or program could know facts about a situation, i.e. the values of some fluents, and could infer some consequences of some actions from these facts. Situations are examples of rich entities, i.e. entities involving more detail than can be specified. Poor entities have finitely describable structures.

However, theories of action and changegif often use a more limited notion of situation. Thus Raymond Reiter [Rei01] and his colleagues regard situations as the nodes of a tree based at an initial situation S0 and whose edges branching from a situation s are the actions that may be taken in s. Other researchers, including Murray Shanahan [Sha97] and myself, use S0 as just a name for some situation whose consequences are of interest.

The viewpoint of this article is that a situation s is arbitrary element of a space Sits of situations, i.e. s bears the same relation to Sits as a group element bears to a group. Situation calculus theories relate situations, fluents and action by axioms, i.e. are abstract structures satisfying the theory.

A robot can use a poor situation calculus theory T to decide what to do in a world of rich situations. For example, the robot's blocks world theory may only allow specifying that one block is on another, not where it is located on the other. Suppose we have a mapping Observe from a subset of rich situations to poor situations. When the robot observes a world situation s to which the theory T applies, it obtains a poor situation tex2html_wrap_inline1192 . Using the theory T, the robot infers that a certain action a will advance its goal. It then performs an action Execute(a) in the world. If the theory T corresponds to the world properly, Result(Execute(a),s) will be an improved situation.

It isn't the purpose of this paper to develop a theory of the correspondence between rich real world situations and those of limited sitcalc domains. However, the way we formalize sitcalc is motivated by the hope of making these correspondences in a later theory.

Whether an event is external depends on the theory. If we can formulate when an event e will occur, then we can make our theory more powerful by including an occurrence axiom for that event. If we assume a deterministic world, the limiting case is a theory in which all events are internal.

Aarati Parmar pointed out that the semantics of an action theory is changed by the presence of Occurs axioms. Without Occurs, the interpretations are trees branching for the different events possible in a situation. With Occurs an interpretation must say which event occurs, so the interpretations are linear. The actual scenarios are sometimes mixed. The interpretations branch at the external actions and are linear where an Occurs axiom determines what internal action occurs.

There are two main reasons for leaving some events external. One is lack of knowledge. Since I don't know whether it will rain tomorrow, I leave Rains as an external event.

The second is when choice is involved. I can take the umbrella or leave it at home. Maybe someone who knew me much better than I know myself could write occurrence axioms that determine which I will do. However, his theory of my actions might well have the following form: McCarthy will use a theory in which whether he takes his umbrella is an external event. Then he will compute the utility of the two possible actions. Which action he will take in s depends on whether

  equation376


next up previous
Next: Elaboration tolerance Up: Actions and other events Previous: Actions and other events

John McCarthy
Wed Feb 6 16:27:33 PST 2002