# «Narratives in the Situation Calculus Rob Miller Murray Shanahan Department of Computing Department of Computing Imperial College Imperial College 180 ...»

Narratives in the Situation Calculus

Rob Miller Murray Shanahan

Department of Computing Department of Computing

Imperial College Imperial College

180 Queen's Gate 180 Queen's Gate

London SW7 2BZ, U.K. London SW7 2BZ, U.K.

email: rsm@doc. ic. ac. uk email: mps@doc. ic. ac. uk

WWW: http://laotzu.doc.ic.ac.uk/ WWW: http://laotzu.doc.ic.ac.uk/

UserPages/sta /rsm/rsm.html UserPages/sta /mps/mps.html February 1995

**Original paper in:**

Journal of Logic & Computation, Volume 4, Number 5, October 1994 (Special Issue on Actions and Processes) With addendum added February 1995 Abstract A narrative is a course of real events about which we might have incomplete information.

Formalisms for reasoning about action may be broadly divided into those which are narrativebased, such as the Event Calculus of Kowalski and Sergot, and those which reason on the level of hypothetical sequences of actions, in particular the Situation Calculus. This paper bridges the gap between these types of formalism by supplying a technique for linking incomplete narrative descriptions to Situation Calculus domain formulae written in the usual style using a Result function. Particular attention is given to actions with duration and overlapping actions. By illuminating the relationship between these two di erent styles of representation, the paper moves us one step closer to a full understanding of the space of all possible formalisms for reasoning about action.

Introduction The Situation Calculus 15] is one of A.I.'s oldest and best understood formalisms for representing change, but it has often been criticised for having limited expressive power. Recently, a number of authors have challenged this view, by showing how the Situation Calculus might be used to represent domains with continuous change and concurrent actions 23], 7], 14]. However, the representation of narrative information within the framework of the Situation Calculus has largely been neglected.

A narrative is an actual course of actions (or events1 ) about which we may have incomplete knowledge. One of the features of the Situation Calculus is that it operates at a more

**Abstract**

level than that of actual actions. It allows us, for example, to reason about the hypothetical situation which results from the performance of a sequence of hypothetical actions. In contrast, narrative-based formalisms, such as the Event Calculus of Kowalski and Sergot 11], the work of Allen 1] and that of Sandewall 19], operate at the level of actual events. In the latter kind of formalism, it is easy to represent facts about the actual occurrence of events and the properties that actually hold in the world.

The aim of this paper is to bridge the gap between the Situation Calculus and the narrative-based approach. In order to deal properly with narrative information in the Situation Calculus, some extra default reasoning must be used to account for incomplete information about the occurrence of actions, and a number of extra predicates, functions and axioms are required.

The paper is organised as follows. The rst section motivates the paper and describes an example of the kind of reasoning we wish to capture. We then go on to provide predicates, functions and axioms which will link an incomplete narrative description to any set of Situation Calculus domain formulae presented in the usual style using the Result function. Finally we adapt and extend this approach to deal with more complex narratives, involving actions with duration and overlapping actions.

A few words about notation. Throughout this paper, we use a many-sorted rstorder predicate calculus with equality. Variables begin with lower-case letters and constant and function symbols with upper-case letters. All variables in formulae are universally quanti ed with maximum scope unless otherwise indicated. Where we wish to refer to arbitrary predicate calculus terms or expressions, we sometimes use meta-variables beginning with Greek letters. For example, we might refer to arbitrary action terms 1 and 2. Non-logical axioms are labelled with names beginning with an upper-case letter, e.g. the frame axiom `(F1)', whereas derived sentences or expressions are simply numbered | `(1)', `(2)', etc. We use parallel and prioritised circumscription, with predicates, functions and constants allowed to vary (see for example 12]). The parallel circumscription of predicates and in a theory T with and allowed to vary is written as CIRC T ; ; ; ; ] If predicate is also circumscribed, at a higher priority than and, this is either written as CIRC T ; ; ; ; ] or as CIRC T ; ; ; ; ; ] ^ CIRC T ; ; ; ; ] The equivalence of the second expression to the rst is shown in 12].

We use the terms `action' and `event' interchangeably.

1 Incomplete Narratives | An Example Consider the following scenario. Before breakfast one morning, a lecturer, Mary, checks her briefcase to make sure her lecture notes are inside, which indeed they are.

She eats her breakfast, and a short while later carries her briefcase to college. Mary knows that exactly those belongings which were in her case when she left home are at work with her. So she concludes that, at the end of this sequence of event occurrences, her lecture notes are safely at college. However, shortly after she sits down at her desk, her husband telephones to apologise for accidentally removing her notes from the briefcase before she left for work. With her new knowledge of her husband's actions, Mary concludes that her notes are not at college.2 Two main forms of reasoning feature in this story. To begin with, Mary employed a solution to the frame problem to conclude that her lecture notes were at college.

She assumed that her breakfast, whatever other e ects it may have had, did not a ect the whereabouts of the notes, and that they were still in her briefcase when she set o for work. Second, at each stage in her reasoning, Mary assumed that the events she knew about were the only events that took place. That is to say, she used a form of default reasoning to cope with her potentially incomplete knowledge of the actual narrative of events.

We will not be directly concerned here with the frame problem, but rather with the problem of representing and reasoning about incomplete narrative descriptions, in particular in the context of the Situation Calculus. Let's try to represent the lecture notes example in the Situation Calculus. Following the usual practise, there will be sorts in our language for situations (with variables s, s0, s1, etc.), action types (with variables a, a0, a1, etc.) and uents (with variables f, f0, f1, etc.), and the term Result( ; ) will denote the situation which results from performing an action of type in situation. The formula Holds( ; ) represents that uent holds in situation. The situation constant S0 will be used to denote an initial situation.

To represent the lecture notes example, we use three action types: Eat, Carry and Take, denoting respectively the actions of eating breakfast, carrying the briefcase to work and taking the notes from the briefcase. Two uents are needed: Work and Case, denoting respectively that the notes are at work and in the briefcase. The following formulae represent what Mary knows about the domain.

Holds(Work; Result(Carry; s)) Holds(Case; s) (Ex1) :Holds(Work; Result(Carry; s)) :Holds(Case; s) (Ex2) :Holds(Case; Result(Take; s)) Holds(Case; s) (Ex3) Holds(Case; S0) (Ex4) In order to derive useful conclusions from these formulae, we need to add a frame axiom ((F1) below), and to adopt a solution to the frame problem which minimises Ab properly. We will adopt Baker's solution3 3], and will include `existence-of-situations' This story is similar to the Glasgow{Moscow problem described in 16].

We expect our approachto representingnarratives to work equally well with many other solutions axioms ((B1){(B4) below). We also assume that the necessary uniqueness-of-names axioms for uents and actions, and a domain closure axiom for uents, are present.

To brie y summarise Baker, the frame problem is overcome (avoiding such di culties as the Yale Shooting Problem) by minimising the predicate Absit (which appears in Axiom (B3) below) at a higher priority than the predicate Ab, whilst allowing S0 and the Result function to vary. The functions And and Not are used to form `generalised uents' (a super-sort of uents) representing combinations of uents and their negations. Axioms (B1){(B4) together with the minimisation of Absit guarantee that any such combination of uents allowed by the domain theory holds in at least one situation. This is necessary in order to ensure that the minimisation of Ab behaves correctly. (See 3] for details.) Holds(f; Result(a; s)) $ Holds(f; s)] :Ab(a; f; s) (F1) Holds(And(g1; g2); s) $ Holds(g1; s) ^ Holds(g2; s)] (B1) Holds(Not(f); s) $ :Holds(f; s) (B2) Holds(g; Sit(g)) :Absit(g) (B3) Sit(g1) = Sit(g2) ! g1 = g2 (B4) The traditional way to use the above formulae to model Mary's reasoning in the lecture notes example is to show that the formula Holds(Work; Result(Carry; Result(Eat; S0))) is true. But how do we then assimilate the new fact that a Take action took place some time after S0 and before the Carry action? We can of course also prove the formula :Holds(Work; Result(Carry; Result(Take; Result(Eat; S0)))) But we can show this at any time, either before we assimilate the extra Take event or afterwards. Mary's reasoning, on the other hand, is clearly non-monotonic. At rst, she concludes that her notes are at work, but she retracts this conclusion when she learns of the extra Take event. We want to be able to capture this.

The traditional use of the Situation Calculus does not incorporate the idea of a narrative of actual events. For the lecture notes example, and for countless similar examples, we need some way of asserting the fact that an action of a given type actually takes place at a given time. Conclusions about what uents hold when are then no longer expressed in terms of the Result function, they are expressed in terms of narrative time. The next section presents the basis of an approach to the representation of narratives in the Situation Calculus.

to the frame problem, because of our methodology of strictly separating narrative knowledge from domain knowledge.

2 Narratives and the Result Function To make our approach to narratives work, we need to introduce a new sort for times, with variables t, t0, t1, etc. We will consider only interpretations in which this sort is interpreted by the non-negative reals, and in which the comparative predicates (,,, and ) have their usual meanings for real numbers. A new predicate is also required. The formula Happens( ; ) represents that an action of type occurs at time. (Action occurrences are thus instantaneous. Later, we will adapt our approach in order to represent action occurrences with duration.) Finally, a new function is introduced. The term State( ) denotes the situation at time. Now we have the following axiom which forms the link between narrative descriptions and the Result function.

State(t) = Result(a1; State(t1)) (N1) Happens(a1; t1) ^ t1 t ^ :9a2; t2 Happens(a2; t2)^ a1 6= a2 _ t1 6= t2] ^ t1 t2 ^ t2 t]] Axiom (N1) says that the situation at time t is Result(a1; State(t1)) if action a1 happens at t1 and no other action happens between t1 and t. Note that the righthand-side of (N1) is false if an action takes place concurrently with a1 (we assume actions of the same type do not occur concurrently). We will discuss concurrent and overlapping actions in more detail later on.

We also need an axiom to describe the situation that obtains at all times before the occurrence of the rst action within a narrative.

State(t) = S0 :9a1; t1 Happens(a1; t1) ^ t1 t] (N2) A narrative of events is now represented as a set of Happens formulae. The lecture notes example might be rendered as follows.

Happens(Eat; 8) (Occ1) Happens(Carry; 9) (Occ2) Now, in addition to the minimisation we use to solve the frame problem, we need to minimise Happens, representing the assumption that no events occur other than those which are known to occur. We will minimise Happens in parallel with Ab, allowing Result and State to vary. As mentioned above, we include Baker's existenceof-situations axioms in our domain descriptions, and minimise Baker's predicate Absit at a higher priority. For this example it can easily be seen that minimising Happens will not interfere with the minimisation of Ab. The minimisation of Happens will give us the conclusion Happens(a; t) $ a = Eat ^ t = 8] _ a = Carry ^ t = 9]] (1) From this we can derive Holds(Work,State(10)), as shown in Figure 1. But if we now add (Occ3) below, representing the additional fact that a Take action occurred between 8 and 9, we can no longer draw this conclusion.

**By (F1), (Ex1), (Ex2), (Ex3) and (Ex4):**

Holds(Work; Result(Carry; Result(Eat; S0))) (i)

**By (1), (N2) and (i):**

Holds(Work; Result(Carry; Result(Eat; State(8)))) (ii)

**By (1):**

:9a2; t2 Happens(a2; t2) ^ a2 6= Eat _ t2 6= 8] ^ 8 t2 ^ t2 9] (iii)

**By (N1), (Occ1) and (iii):**

State(9) = Result(Eat; State(8)) (iv)

**By (i) and (iv):**

Holds(Work; Result(Carry; State(9))) (v)

**By (1):**

:9a2; t2 Happens(a2; t2) ^ a2 6= Carry _ t2 6= 9] ^ 9 t2 ^ t2 10] (vi)

**By (N1), (Occ2) and (vi):**

State(10) = Result(Carry; State(9)) (vii)

**By (v) and (vii):**

Holds(Work; State(10)) (viii) Figure 1 | Derivation of Holds(Work; State(10)) Happens(Take; 8:5) (Occ3) Instead of (1), minimising Happens now gives Happens(a; t) $ (2) a = Eat ^ t = 8] _ a = Carry ^ t = 9] _ a = Take ^ t = 8:5]] With (2), we can no longer prove Holds(Work; State(10)), which is just the outcome we were seeking. (Indeed, we can now derive :Holds(Work; State(10))).