Narratives in the Situation Calculus

Rob Miller Department of Computing Imperial College 180 Queen’s Gate London SW7 2BZ, U.K. email: rsm@doc. ic. ac. uk

WWW: http://laotzu.doc.ic.ac.uk/ UserPages/staff/rsm/rsm.html

Murray Shanahan Department of Computing Imperial College 180 Queen’s Gate London SW7 2BZ, U.K. email: mps@doc. ic. ac. uk

WWW: http://laotzu.doc.ic.ac.uk/ UserPages/staff/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 different 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 events^{1}) 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 first 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 firstorder 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 quantified 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 first is shown in [12].

1We 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 effects it may have had, did not affect the whereabouts of the notes, and that they were still in her briefcase when she set off 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 fluents (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 fluent ϕ 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 T ake, denoting respectively the actions of eating breakfast, carrying the briefcase to work and taking the notes from the briefcase. Two fluents are needed: W ork 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(W ork, Result(Carry, s)) ← Holds(Case, s)  (Ex1)
¬Holds(W ork, Result(Carry, s)) ← ¬Holds(Case, s)  (Ex2)
¬Holds(Case, Result(T ake, 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 solution^{3} [3], and will include ‘existence-of-situations’ axioms ((B1)–(B4) below). We also assume that the necessary uniqueness-of-names axioms for fluents and actions, and a domain closure axiom for fluents, are present. To briefly summarise Baker, the frame problem is overcome (avoiding such difficulties 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 fluents’ (a super-sort of fluents) representing combinations of fluents and their negations. Axioms (B1)–(B4) together with the minimisation of Absit guarantee that any such combination of fluents 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.)

2This story is similar to the Glasgow–Moscow problem described in [16].

3We expect our approach to representing narratives to work equally well with many other solutions

[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(W ork, Result(Carry, Result(Eat, S0)))

is true. But how do we then assimilate the new fact that a T ake action took place some time after S0 and before the Carry action? We can of course also prove the formula

¬Holds(W ork, Result(Carry, Result(T ake, Result(Eat, S0))))

But we can show this at any time, either before we assimilate the extra T ake event or afterwards. Mary’s reasoning, on the other hand, is clearly non-monotonic. At first, she concludes that her notes are at work, but she retracts this conclusion when she learns of the extra T ake 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 fluents 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 ∧
¬∃a2, t2[Happens(a2, t2) ∧ [a1 ≠ a2 ∨ t1 ≠ 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 first action within a narrative.

State(t) = S0 ← ¬∃a1, 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.

\begin{matrix}Happens(Eat, 8) & (Occ1) \\ Happens(Carry, 9) & (Occ2) \end{matrix}

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.

Figure 1 — Derivation of Holds(W ork, State(10)) By (F1), (Ex1), (Ex2), (Ex3) and (Ex4): Holds(W ork, Result(Carry, Result(Eat, S0)))  (i) By (1), (N2) and (i): Holds(W ork, Result(Carry, Result(Eat, State(8))))  (ii) By (1): ¬∃a2, t2[Happens(a2, t2) ∧ [a2 ≠ Eat ∨ t2 ≠ 8] ∧ 8 ≤ t2 ∧ t2 < 9]  (iii) By (N1), (Occ1) and (iii): State(9) = Result(Eat, State(8))  (iv) By (i) and (iv): Holds(W ork, Result(Carry, State(9)))  (v) By (1): ¬∃a2, t2[Happens(a2, t2) ∧ [a2 ≠ Carry ∨ t2 ≠ 9] ∧ 9 ≤ t2 ∧ t2 < 10] (vi) By (N1), (Occ2) and (vi): State(10) = Result(Carry, State(9))  (vii) By (v) and (vii): Holds(W ork, State(10))  (viii)
Happens(T ake, 8.5)  (Occ3)

Instead of (1), minimising Happens now gives

\begin{matrix}Happens(a, t) ↔ & (2) \\ [[a = Eat ∧ t = 8] ∨ [a = Carry ∧ t = 9] ∨ [a = T ake ∧ t = 8.5]] \end{matrix}

With (2), we can no longer prove Holds(W ork, State(10)), which is just the outcome we were seeking. (Indeed, we can now derive ¬Holds(W ork, State(10))).

The intuition here is that, in the general case, the minimisation of Happens will not interfere with the minimisation policy chosen to overcome the frame problem, because the narrative part of any domain theory is clearly separable from the standard Situation Calculus part. Where the narrative description consists of a finite number of atomic Happens formulae, as in the example above, we verify this intuition with Theorem 1 below. This states that any such narrative description N together with any ‘standard’ Situation Calculus domain description T, circumscribed according to the policy described above, logically entails the circumscription of the domain description T on its own. It therefore preserves the solution to the frame problem. A proof is given in Appendix A, together with more precise descriptions of the form of T and N.

Theorem 1 If T is a domain description and N is a narrative description, then

(CIRC[T ∧ N ; Absit ; Ab, Happens, Result, Holds, S0, State] ∧
CIRC[T ∧ N ; Ab, Happens ; Result, S0, State]) ⊧

(CIRC[T ; Absit ; Ab, Result, Holds, S0] ∧ CIRC[T ; Ab ; Result, S0])

Proof (see Appendix A)

The theorem is no longer true if the narrative description N is allowed to contain information on what holds at times other than in the initial situation, i.e. if it can contain sentences of the form Holds(ϕ, State(τ)). Of course, we may have knowledge of what fluents hold at various times. To preserve the conditions necessary for the theorem, such knowledge may be assimilated using an abductive approach [21]. Alternatively, the techniques described by Crawford and Etherington [4] may be useful. Further discussion of the assimilation of Holds information is, however, beyond the scope of this paper.

3 Incomplete Action Orderings

The axioms above facilitate the description of narratives in which the exact order of events is not known. Consider the following extreme example, described by Hayes [9]. Two people meet, then go their separate ways, then meet again in a fortnight’s time. During that fortnight, they each participate in many events. There are two parallel narratives, and the events in one narrative are quite independent of those in the other. Within each narrative, we know how the events are ordered. But the relative orderings of events across narratives is unknown. How do we describe the situation which obtains when they meet again, using the Situation Calculus?

As Hayes points out, it would be very tedious to try to describe this situation using the Situation Calculus Result function, because of the incompleteness of our information about the relative orderings of events across the two narratives. We would have to use a large disjunction, with one disjunct for each possible interleaving of events. However, with the addition of the Happens predicate, the State function, and axioms (N1) and (N2), this example becomes relatively straightforward. Suppose there are n events in the first narrative and m in the second, and we know that all events happen before some time τ. Then the following sentences are adequate.

∃t1_{1}, …, t1_{n}[Happens(A1_{1}, t1_{1}) ∧ Happens(A1_{2}, t1_{2}) ∧ … ∧ Happens(A1_{n}, t1_{n}) ∧ t1_{2} > t1_{1} ∧ t1_{3} > t1_{2} ∧ … ∧ t1_{n} > t1_{n−1} ∧ τ > t1_{n}]

∃t2_{1}, …, t2_{m}[Happens(A2_{1}, t2_{1}) ∧ Happens(A2_{2}, t2_{2}) ∧ … ∧ Happens(A2_{m}, t2_{m}) ∧ t2_{2} > t2_{1} ∧ t2_{3} > t2_{2} ∧ … ∧ t2_{m} > t2_{m−1} ∧ τ > t2_{m}]

Because the above formulae allow concurrent actions, axiom (N1) does not permit us to draw any conclusions from them as they stand. To illustrate the point we are making in this section, we can add the following formula guaranteeing that no two actions occur concurrently, thus making Axiom (N1) applicable. In a later section, we will describe how to remove this restriction.

¬∃a1, t1, a2, t2[Happens(a1, t1) ∧ Happens(a2, t2) ∧ a1 ≠ a2 ∧ t1 = t2]

Although the statement of Theorem 1 as it stands does not cater for such narrative descriptions, both the theorem and the proof can be easily extended to cover theories containing such existentially quantified Happens formulae (see further remarks in Appendix A).

Let’s consider a variation of this example. Suppose Mary is in London and Joe is in New York. At 8am, Mary telephones Joe and wakes him up. After the call, both Mary and Joe get back to whatever they were doing before. During the day, Mary takes part in many events, and she knows exactly what those events are. It is quite appropriate for Mary to work under the assumption that no relevant events occur in her part of the world except the ones she knows about. When she puts her notes in her case she wants to be able to assume they will stay there. On the other hand, she hasn’t a clue what Joe is doing. Despite this, the blanket minimisation of Happens will insist that, because she doesn’t know what Joe is doing at all, Mary must infer that Joe is still awake at 12 noon, at 7pm, and so on. In fact, in the absence of further information, she will be able conclude that Joe remains awake for the rest of the week, and so on into the future.

Fortunately, it is a straightforward matter to make the minimisation of the occurrence of events more selective. We introduce a new predicate Happens∗ with the same arguments as Happens. We describe a narrative of events as before, but instead of minimising Happens, we minimise Happens∗. Our circumscription policy is now the following.

CIRC[T ∧ N ; Absit ; Ab, Happens, Happens∗, Result, Holds, S0, State] ∧

CIRC[T ∧ N ; Ab, Happens∗ ; Happens, Result, S0, State]

For the above example, we could write the following sentence.

[Happens(a, t) ∧ Location(a) = London] → Happens∗(a, t)

The term Location(α) denotes the place where an action occurrence of type α takes place. To complete the example, we need an axiom which says that fluents in a particular place are only affected by actions in that place. The term Location(ϕ) denotes the place at which a fluent ϕ holds.

¬[Holds(f, Result(a, s)) ↔ Holds(f, s)] → Location(a) = Location(f)

Now it is only necessary to distinguish in the domain formulae between actions taking place in London and those taking place elsewhere. The solution presented here only addresses the case where geographical separation entails both epistemic separation (Mary doesn’t know what Joe is doing) and causal independence (what Joe does cannot affect Mary), but it can easily be generalised. Indeed, it can be regarded as a specific application of the technique of scoped minimisation [6].

4 Concurrent and Divisible Actions

In the narrative Situation Calculus of the previous sections, we have represented action occurrences as being instantaneous, and our axiomatisation does not cover the case where two or more actions occur simultaneously. But for many domains it is not reasonable to regard action occurrences as instantaneous. And, especially where actions have a duration, we must be able to represent and reason about narratives in which actions occur concurrently, or where occurrences partially overlap. Recently, several authors have addressed the topic of extending the Situation Calculus to deal with concurrent actions and actions with duration [23], [7], [14]. In this section we extend our narrative Situation Calculus in a similar way by building on the work of Gelfond, Lifschitz and Rabinov [7].

In order to represent actions with duration, Gelfond et al. introduce the function symbol Duration mapping actions to numbers (i.e. lengths of time intervals), along with the constraint that all actions must have a positive duration, expressed as the axiom

Duration(a) > 0  (CD1)

Three further function symbols, Head, T ail and an infix operator ‘;’, all mapping onto actions, are then introduced in order to represent parts of actions, and to represent concatenations of actions (and of parts of actions). If α is an action and δ is a number such that δ < Duration(α), then the term Head(α, δ) denotes the first δ time units of α (‘doing α for δ seconds’), and the term T ail(α, δ) represents the remainder of α. Given two action terms α1 and α2, then the term α1; α2 represents the action of α1 immediately followed by α2. A fourth binary operator ‘&’ mapping pairs of actions to actions is used to describe the effects of actions when performed concurrently, so that the term α1&α2 represents ‘α1 performed concurrently with α2’.

In order to retain Baker’s solution to the frame problem, we extend Baker’s uniqueness-of-names requirement for atomic actions to cover compound action terms constructed with the functions Head, T ail, ‘&’ and ‘;’. However, these functions allow us to construct action terms, possibly representing several parts of several actions performed concurrently, in various different ways. We need to specify when these terms are equivalent. We therefore introduce an infix predicate ≈ with which to define equivalence classes of action terms. The Head, T ail, ‘&’ and ‘;’ operators and the equivalence predicate ≈ have various properties which are listed in full in Appendix B (Axioms (CD1)–(CD22)). One important property comes directly from the intended meaning of the operator ‘;’ and is captured by the following axiom:

Result(a1; a2, s) = Result(a2, Result(a1, s))  (CD5)

Another axiom states that equivalent actions have the same effects:

a1 ≈ a2 → Result(a1, s) = Result(a2, s)  (CD6)

Various axioms, such as (CD7)–(CD9) below, are included to show the circumstances under which action terms are equivalent.

0 < d < Duration(a) → a ≈ Head(a, d); T ail(a, d)  (CD7)
Head((a1; a2), Duration(a1)) ≈ a1  (CD8)

T ail((a1; a2), Duration(a1)) ≈ a2  (CD9)

To eliminate unwanted models consistent with its recursive definition, the equivalence predicate ≈ is circumscribed, at a higher priority than all other circumscribed predicates.

Given an action term α, we will refer to action terms constructed by one or more applications of the functions Head and T ail to α as horizontal components of α. For example, Axioms (CD8) and (CD9) show that α1 and α2 are horizontal components of α1; α2. Given action terms α1, α2 and α3, such that α1&α2 ≈ α3, we will refer to α1 and α2 as vertical components of α3. We will refer to a vertical component of a horizontal component of α simply as a component of α.

Where two or more actions are executed concurrently, some of their effects may cancel (for example, simultaneously heating and cooling a room, or pushing and pulling an object). However, we want to assume that in general, i.e. by default, this is not the case. Again we will adapt the ideas of Gelfond et al. and of Lin and Shoham [14], and include a four argument predicate Cancels in order to represent knowledge of this kind. Cancels(α2, α1, ϕ, σ) means that action α2 cancels the effect action α1 might otherwise have had on the fluent ϕ when the two actions are performed concurrently in situation σ. We will include a simple conservative theory of action cancellation, sufficient for the example that follows, which assumes that if an action α2 cancels the effect of α1 on ϕ, then all actions of which α2 is a component also cancel the effect of α1 on ϕ, and all horizontal components of α2 cancel the effect of α1 on ϕ:

[Cancels(a2, a1, f, s) ∧ a3 ≈ a2 ∧ 0 < d < Duration(a2)] →  (CD23)
[Cancels(a3, a1, f, s) ∧ Cancels(Head(a3, d), a1, f, s) ∧
Cancels(T ail(a3, d), a1, f, s) ∧ Cancels((a3&a4), a1, f, s) ∧
Cancels((a3; a4), a1, f, s) ∧ Cancels((a4; a3), a1, f, s)]

The following axiom will now enable us to infer the effects of partially overlapping and concurrent actions in narrative theories. It states that an action causes an effect if one of its vertical components causes the effect and no other vertical component or combination of vertical components cancels the effect:

\begin{matrix}Holds(f, Result(a, s)) ← & (CD24) \\ [a ≈ a1&a2 ∧ Holds(f, Result(a1, s)) ∧ ¬Cancels(a, a1, f, s)] \end{matrix}

We circumscribe Cancels, at a lower priority than Baker’s predicate Absit but at a higher priority than Ab, to represent the default assumption that in general actions do not cancel each other’s effects.

5 Narratives with Overlapping Actions

To illustrate how we may represent a narrative of partially overlapping action occurrences, we will slightly modify the example introduced earlier, of Mary carrying her briefcase to work. We will employ the same causal knowledge of the domain used before, represented by Axioms (Ex1)–(Ex4). We will suppose that Mary started eating her breakfast at time-point 8, finished at 8.5, set off for work at 9, and arrived at 10. Meanwhile, her husband started tampering with her briefcase at 8.25 and finished at 8.75, so that the events of Mary eating and her husband taking her notes partially overlapped. This narrative is illustrated in Figure 2. Our axiomatisation should be sufficient to show that the notes are not at work at 10.

Figure 2 — A Narrative with Overlapping Actions 8  Eat  8.5 8.25 T ake 8.75  9  Carry  10

In order to specify that an action occurs over a real time interval (τ1, τ2), we use a three-argument version of the predicate Happens — Happens(α, τ1, τ2) means that action α starts to occur at τ1 and finishes occurring at τ2. We constrain Happens as follows:

Happens(a, t1, t2) → Duration(a) = (t2 − t1)  (CN1)

Given a narrative of concurrent and partially overlapping actions, we must ensure the set of all action occurrences includes relevant compound action terms indicated by axioms (CD6)–(CD22). We thus include the following axioms:

a1 ≈ a2 → [Happens(a1, t1, t2) ↔ Happens(a2, t1, t2)]  (CN2)
[Happens(a1, t1, t2) ∧ Happens(a2, t1, t2)] ↔ Happens(a1&a2, t1, t2) (CN3)
0 < d < Duration(a) →  (CN4)
[Happens(a, t1, t2) ↔
[Happens(Head(a, d), t1, (t1 + d))
∧ Happens(T ail(a, d), (t1 + d), t2)]]

As before, Happens is minimised in parallel with Ab. We are now in a position to represent our example narrative. There are three ‘atomic’ action occurrences:

Happens(Eat, 8, 8.5)  (Con1)
Happens(T ake, 8.25, 8.75)  (Con2)
Happens(Carry, 9, 10)  (Con3)

As before, we will associate each time-point with a situation using the function State. For the example above, even though we have Happens(Eat, 8, 8.5), we do not wish to be able to conclude that State(8.5) = Result(Eat, State(8)), because the end of the Eat action occurrence overlaps with the beginning of a T ake occurrence. Rather, we should be able to derive the sentence:

State(8.5) =

Result(T ail(Eat, 0.25)&Head(T ake, 0.25), Result(Head(Eat, 0.25), State(8)))

In general, we need to transform narratives of overlapping actions into narratives of non-overlapping actions, as illustrated in Figure 3.

[figure: Figure 3 — Transforming an Overlapping Narrative; Head(Eat,0.25); T ail(Eat,0.25)&Head(T ake,0.25); T ail(T ake,0.25); T ake; 8.25; 8.75; Eat; 8; 8.5]

To do this, we will first introduce two predicates, Slice and P art. Given two action terms α1 and α2, Slice(α1, α2) means that α1 is a horizontal component of α2, and P art(α1, α2) means that α1 is a component of α2. Their definitions are given by the following axioms:

Slice(a1, a2) ↔ [a1 ≈ a2 ∨ [a1 ≈ Head(a2, d) ∧ d < Duration(a2)] (CN5)
∨ [a1 ≈ T ail(a2, d) ∧ d < Duration(a2)]
∨ [a1 ≈ Head(T ail(a2, d1), d2) ∧ (d1 + d2) < Duration(a2)]]
P art(a1, a2) ↔ [Slice(a1, a2) ∨ ∃a3, a4[Slice(a1, a3) ∧ a2 ≈ a3&a4]] (CN6)

To describe transformations such as that of Figure 3, we need to identify occurrences of action terms α which are maximal occurrences, in that any other action terms which occur during the same time are equivalent to a component of α. We introduce the predicate Happens†, where Happens†(α, τ1, τ2) means that the action α occurs maximally over the period (τ1, τ2). Happens† is defined in terms of Happens and P art:

Happens†(a, t1, t2) ↔  (CN7)
[Happens(a, t1, t2) ∧ ¬∃a1, t3, t4[Happens(a1, t3, t4)
∧ t1 ≤ t3 ∧ t4 ≤ t2 ∧ ¬P art(a1, a)]]

Finally, we state two axioms analogous to Axioms (N1) and (N2) introduced previously. Axiom (CN8) relates all time points before the start of the first action occurrence to the initial situation S0. Axiom (CN9) states that if an action α1 occurs maximally before τ, and no other action occurs before τ which ends after the end of α1, then the situation at τ is the result of α1 in the situation at the beginning of the α1 occurrence.

State(t) = S0 ← ¬∃a, t1, t2[Happens(a, t1, t2) ∧ t1 < t]  (CN8)
State(t) = Result(a1, State(t1)) ←  (CN9)
[Happens†(a1, t1, t2) ∧ t ≥ t2 ∧
¬∃a3, t3, t4[Happens(a3, t3, t4) ∧ t2 < t4 ∧ t4 ≤ t]]

As before, the axioms introduced to deal with narratives of concurrent and overlapping action occurrences are in addition to the axiomatisation of the Situation Calculus used by Baker. To summarise, the full set of domain independent axioms for the enhanced narrative Situation Calculus includes the frame axiom (F1) and the existence-of-situations axioms (B1)–(B4) required by Baker, Axioms (CD1)–(CD24) concerning the properties of action terms constructed with the functions Head, T ail, ‘&’ and ‘;’ and the cancellation of the effects of one action by another, and Axioms (CN1)–(CN9) concerning narrative aspects of the theory. Given a particular domain with a finite number of positive fluent constants F_{1}, …, F_{n} and action constants A_{1}, …, A_{m}, the domain dependent theory will include uniqueness-of-names and domain closure axioms for fluents, and uniqueness-of-names axioms for action terms.

As described above, we circumscribe various predicates. The overall circumscription policy can be summarised as follows. The infix predicate ≈, used to specify the equivalence of action terms, is circumscribed at a higher priority than all other circumscribed predicates. At the next highest priority (following Baker), the predicate Absit is circumscribed to ensure the existence of all situations consistent with the domain constraints and action descriptions of the theory. Next, the predicate Cancels is circumscribed to ensure that, by default, compound action terms inherit the effects of their components. At the lowest priority, the predicates Ab and Happens are circumscribed (varying the functions Result and State) to represent the default assumption that a given action does not affect a given fluent, and that, by default, a given action does not occur over a given time interval. Given a narrative domain theory D, and letting SYM denote the set of symbols containing S0 and all predicate and function symbols in D except the equality symbol, the circumscribed theory is thus

CIRC[D ; ≈ ; SYM]

∧CIRC[D ; Absit ; Holds, S0, Cancels, Ab, Happens, Result, State, Happens†] ∧CIRC[D ; Cancels > Ab, Happens ; Result, S0, State, Happens†]

For the lecture notes example, by definition of Happens† and minimisation of Happens we now have

\begin{matrix}Happens†(Head(Eat, 0.25); ((T ail(Eat, 0.25)&Head(T ake, 0.25)); & (3) \\ T ail(T ake, 0.25)), 8, 8.75) \end{matrix}

¬∃a, t1, t2[Happens(a, t1, t2) ∧ t1 < 8]  (4)

and

¬∃a3, t3, t4[Happens(a3, t3, t4) ∧ 8.75 < t4 ∧ t4 ≤ 9]  (5)

Hence by (CN8), (CN9), (3), (4) and (5)

\begin{matrix}State(9) = Result(Head(Eat, 0.25); ((T ail(Eat, 0.25)& & (6) \\ Head(T ake, 0.25)); T ail(T ake, 0.25)), S0) \end{matrix}

So by (CD5)

\begin{matrix}State(9) = Result((T ail(Eat, 0.25)&Head(T ake, 0.25)); & (7) \\ T ail(T ake, 0.25), Result(Head(Eat, 0.25), S0)) \end{matrix}

Minimisation of Ab gives

¬Ab(Head(Eat, 0.25), Case, S0)  (8)

So by the frame axiom (F1) and the initial condition (Ex4)

Holds(Case, Result(Head(Eat, 0.25), S0))  (9)

By (CD18), (CD22) and (CD7) (see Appendix B)

\begin{matrix}(T ail(Eat, 0.25)&Head(T ake, 0.25)); T ail(T ake, 0.25) ≈ & (10) \\ T ake&(T ail(Eat, 0.25); T ail(T ake, 0.25)) \end{matrix}

So by (CD24), (10), (Ex3), (9), (7) and minimisation of Cancels

¬Holds(Case, State(9))  (11)

The definition of Happens† and minimisation of Happens give

Happens†(Carry, 9, 10)  (12)

(CN9) and (12) give

State(10) = Result(Carry, State(9))  (13)

Finally, (13), (11) and (Ex2) give

¬Holds(W ork, State(10))  (14)

6 Concluding Remarks

We have shown how the Situation Calculus can be extended to cope with incomplete narrative descriptions. Our aim in doing this has been twofold. Adding a capacity to represent and reason about narratives to the Situation Calculus, as well as making it a more useful formalism, has made the difference between the Situation Calculus and narrative-based formalisms like Kowalski and Sergot’s Event Calculus [11] seem smaller than it did before. Our work has thus has facilitated more direct and detailed comparisons between different formalisms for reasoning about action.

An alternative approach to adding narratives to the Situation Calculus, along with some discussion of its relationship to the Event Calculus, is presented in [18]. Whilst our starting point has been the assumption that there is a unique situation for every time, theirs is the assumption that there is a unique start and end time for each situation. The two approaches are not incompatible, however. McCarthy [16] has also addressed the issue of narratives, introducing an Occurs predicate which serves a similar role to the Happens predicate in the present paper. Schubert [23] has addressed the frame problem in the context of the Situation Calculus including concurrent and divisible actions, suggesting a monotonic solution similar to that subsequently employed by Pinto and Reiter in [18]. Amsterdam [2] has also addressed the issue of representing narrative information, although not in the Situation Calculus, using a temporal logic with an extra operator with which to indicate where narrative information may be incomplete.

Our eventual goal should be a full understanding of the entire space of possible formalisms for reasoning about action (see for example [19]). Ultimately it should be possible to enumerate all the possible choices in the design of such a formalism, along with their merits and disadvantages. There is much room for further work in this direction, however. For example, one significant difference between the Situation Calculus, as it is traditionally presented in the literature, and the Event Calculus, is in the way persistence is dealt with. The Situation Calculus incorporates a frame axiom which ensures the persistence of fluents from one hypothetical situation to a successor hypothetical situation. The Event Calculus, on the other hand, has a narrative-based form of persistence. An axiom is included in the Event Calculus which ensures that a property holds from the actual event that initiates it until it is terminated by another actual event. An interesting hybrid formalism is described by Davis [5], in which domain formulae and frame axioms are narrative-based, but whose ontology is situation-based.

There is also room for further work in extending the approach to Situation Calculus narratives given in this paper. For instance, using variations of the Event Calculus with its narrative-based persistence, it is possible to represent examples which involve continuous change [20], [22]. Suppose we are told that someone releases a ball at a certain height from the floor at a given time. We can write Event Calculus formulae which fill in the rest of the narrative from this fragment. That is to say, they support the conclusion that the ball falls continuously for so many seconds, and that another event occurs when the ball hits the floor which ends this period of continuous change. They also determine the height of the ball at any time during the narrative. Gelfond et al. have outlined an approach to continuous change in the Situation Calculus [7], but it is not yet clear how examples like this can be dealt with using their approach.

We have not discussed implementation in the present paper. A method for translating a class of narrative Situation Calculus theories into normal logic programs with negation-as-failure, using the circumscription policy described above as a specification, is presented in [17], together with some preliminary results on the correctness and completeness of the translation.

Acknowledgements

The authors are grateful to Vladimir Lifschitz, John McCarthy, Javier Pinto and Mark Ryan for helpful discussions on the topic of this paper. Murray Shanahan is supported by an SERC Advanced Research Fellowship.

References

[1] J. F. Allen, Towards a General Theory of Action and Time, Artificial Intelligence, vol 23, page 123, 1984.

[2] J. Amsterdam, Temporal Reasoning and Narrative Conventions, Proceedings KR 91, ed.s J. Allen, R. Fikes, E. Sandewall, Morgan Kaufmann, 1991.

[3] A. B. Baker, Nonmonotonic Reasoning in the Framework of the Situation Calculus, Artificial Intelligence, vol 49, page 5, 1991.

[4] J. M. Crawford and D. W. Etherington, Formalizing Reasoning about Change: A Qualitative Reasoning Approach, Proceedings AAAI 92, page 577, 1992.

[5] E. Davis, Representations of Commonsense Knowledge, Morgan Kaufmann, 1990.

[6] D. W. Etherington, S. Kraus and D. Perlis, Nonmonotonicity and the Scope of Reasoning, Artificial Intelligence, vol 52, page 221, 1991.

[7] M. Gelfond, V. Lifschitz and A. Rabinov, What Are the Limitations of the Situation Calculus?, in Essays for Bledsoe, ed. R. Boyer, Kluwer Academic, page 167, 1991.

[8] S. Hanks and D. McDermott, Nonmonotonic Logic and Temporal Projection, Artificial Intelligence, vol 33, page 379, 1987.

[9] P. J. Hayes, The Second Naïve Physics Manifesto, in Formal Theories of the Commonsense World, ed.s J. R. Hobbs and R. C. Moore, Ablex, 1985.

[10] H. Kautz, The Logic of Persistence, Proceedings AAAI 86, page 401, 1986.

[11] R. A. Kowalski and M. J. Sergot, A Logic-Based Calculus of Events, New Generation Computing, vol 4, page 267, 1986.

[12] V. Lifschitz, Computing Circumscription, in Proceedings IJCAI 85, pages 121-127, 1985

[13] V. Lifschitz, Formal Theories of Action, in Readings in Nonmonotonic Reasoning, ed. M. L. Ginsberg, Morgan Kaufman, 1987.

[14] F. Lin and Y. Shoham, Concurrent Actions in the Situation Calculus, Proceedings AAAI 92, page 590, 1992.

[15] J. McCarthy and P. J. Hayes, Some Philosophical Problems from the Standpoint of Artificial Intelligence, in Machine Intelligence 4, ed.s D. Michie and B. Meltzer, Edinburgh University Press, 1969.

[16] J. McCarthy, Overcoming Unexpected Obstacles, Unpublished manuscript, 1993.

[17] R. S. Miller, Narratives in the Context of Temporal Reasoning, Imperial College Research Report DoC 94/3, available from Department of Computing, Imperial College, 180 Queen’s Gate, London SW7 2BZ, 1994.

[18] J. Pinto and R. Reiter, Temporal Reasoning in Logic Programming: A Case for the Situation Calculus, Proceedings ICLP 93, page 203, 1993.

[19] E. Sandewall, Features and Fluents, Technical Report LiTH-IDA-R-91-29, Linköping University, 1991.

[20] M. P. Shanahan, Representing Continuous Change in the Event Calculus, Proceedings ECAI 90, page 598, 1990.

[21] M. P. Shanahan, Explanation in the Situation Calculus, Proceedings IJCAI 93, page 160, 1993.

[22] M. P. Shanahan, A Circumscriptive Calculus of Events, to appear in Artificial Intelligence, 1994.

[23] L. Schubert, Monotonic Solution of the Frame Problem in the Situation Calculus: an Efficient Method for Worlds with Fully Specified Actions, in Knowledge Representation and Defeasible Reasoning, ed.s H. Kyberg, R. Loui and G. Carlson, Kluwer Academic Press, pages 23-67, 1990.

Appendix A: Proof of Theorem 1

We first give some definitions which allow us to describe more precisely what constitutes a ‘standard’ Situation Calculus domain description T.

Definition 2 Given a situation variable s, a formula is a holds in s literal if it is of the form

Holds(F, s)  or  ¬Holds(F, s)

where F is a fluent constant.

Definition 3 A formula is an action description if it is of the form

∀s[Holds(F, Result(A, s)) ← PRECON S]

or of the form

∀s[¬Holds(F, Result(A, s)) ← PRECON S]

where A is an action constant, F is a fluent constant, and PRECON S is a (possibly empty) conjunction of holds in s literals.

Definition 4 A formula is a domain constraint if it is of the form

∀s[λ(s)] where s is a situation variable, and λ(s) is a well-formed formula whose only variable and only situation term is s, where s is free everywhere in λ(s), and whose only literals are holds in s literals.

Definition 5 A formula is an initial conditions description if it is of the form

Holds(F, S0)  or  ¬Holds(F, S0)

where F is a fluent constant.

We also need the domain specific and domain independent axioms Baker uses to solve the frame problem. These axioms include uniqueness-of-names axioms for fluents and actions, and the existence-of-situations axioms (B1)–(B4). (Like Baker, we use Lifschitz’s ‘UNA’ shorthand for collections of uniqueness-of-names axioms [13]).

Definition 6 Given a language with a finite number of fluent constants F_{1}, …, F_{n}, and action constants A_{1}, …, A_{m} a formula T is a domain description if it is a conjunction of action descriptions, domain constraints, initial conditions descriptions, the frame axiom (F1), Baker’s existence-of-situations axioms (B1)–(B4), and uniquenessof-names axioms

UNA[F_{1}, …, F_{n}, And, Not] UNA[A_{1}, …, A_{m}]

Narrative descriptions are defined simply as follows.

Definition 7 A formula is an occurrence description if it is of the form

Happens(A, τ)

where A is an action constant and τ is a real number.

Definition 8 A formula is a narrative description if it is a conjunction of a finite number of occurrence descriptions, together with Axioms (N1) and (N2).

We prove Theorem 1 in two parts (Lemmas 11 and 12 below). We first prove that the minimisation of Ab is not affected by addition of narrative information. Second, we prove that the minimisation of Absit is unaffected. The proofs of both lemmas rely on the observation that, since Axiom (N1) is ineffective when action occurrences happen simultaneously, addition of groups of simultaneous action occurrences to a narrative will not impose any further restrictions on any possible denotation of the function State. We need the following two definitions to capture this idea concisely.

Definition 9 Given an occurrence description η of the form Happens(A, τ) which is one of the conjuncts in a narrative description N, η is isolated in N if there is no other occurrence description η′ of the form Happens(A′, τ), which is also a conjunct of N.

Definition 10 Given an occurrence description η which is one of the conjuncts in a narrative description N, η is simultaneous in N if it is not isolated in N.

Lemma 11 If T is a domain description and N is a narrative description, then

CIRC[T ∧ N ; Ab, Happens ; Result, S0, State] ⊧ CIRC[T ; Ab ; Result, S0]

Proof Uniqueness-of-names axioms allow us to consider only models in which actions are interpreted as themselves for the purposes of this proof, without loss of generality. We also only consider models where real numbers are interpreted in the usual way.

Suppose there are n isolated occurrence descriptions within N. We order these so that for each occurrence description η_{i} of the form Happens(A_{i}, τ_{i}), 1 ≤ i ≤ n − 1, τ_{i} < τ_{i+1}. Let SIM(N) be the set of simultaneous occurrence descriptions in N. For each i, 0 ≤ i ≤ n, a narrative description N_{i} is defined as follows. N_{0} = SIM(N) ∪ {(N1),(N2)} and for each i, 0 ≤ i < n, N_{i+1} = N_{i} ∪ {η_{i+1}}. Clearly N_{n} = N.

Let M be a model of CIRC[T ∧ N ; Ab, Happens ; Result, S0, State]. Then M is a model of T. Note that for all i, 1 ≤ i ≤ n, ⟨A_{i}, τ_{i}⟩ ∈ M∥Happens∥, since T ∧ N ⊧ Happens(A_{i}, τ_{i}). Similarly for all Happens(A′, τ′) ∈ SIM(N), ⟨A′, τ′⟩ ∈ M∥Happens∥.

Suppose M is not a model of CIRC[T ; Ab ; Result, S0]. Then there exists a model \overline{M} of T, differing from M only in the extensions of Ab, Result and S0, such that \overline{M}∥Ab∥ ⊂ M∥Ab∥. For each i, 0 ≤ i ≤ n, an interpretation \overline{M}_{i} is defined as follows:

• For all i, 0 ≤ i ≤ n, and for all π ∉ \{Happens, State\}, \overline{M}_{i}∥π∥ = M∥π∥.

• \overline{M}_{0}∥Happens∥ = \{⟨A′, τ′⟩ : Happens(A′, τ′) ∈ SIM(N)\}.

• For each i, 1 ≤ i ≤ n, \overline{M}_{i}∥Happens∥ = \overline{M}_{i−1}∥Happens∥ ∪ \{⟨A_{i}, τ_{i}⟩\}.

• For all τ ∈ ℜ, \overline{M}_{0}∥State∥(τ) = \overline{M}∥S0∥.

• For each i, 1 ≤ i ≤ n, \overline{M}_{i}∥State∥(τ) = \overline{M}_{i−1}∥State∥(τ) for all τ ≤ τ_{i}, and \overline{M}_{i}∥State∥(τ) = M∥Result∥(A_{i}, \overline{M}_{i−1}∥State∥(τ_{i})) for all τ > τ_{i}.

The above definition ensures that for each i, \overline{M}_{i} is a model of T ∧ N_{i}. In particular, \overline{M}_{n} is a model of T ∧ N. Furthermore for each i, \overline{M}_{i}∥Ab∥ = \overline{M}∥Ab∥ so that \overline{M}_{i}∥Ab∥ ⊂ M∥Ab∥, and in particular \overline{M}_{n}∥Ab∥ ⊂ M∥Ab∥. Since \overline{M}_{n} differs from M only in the extensions of Ab, Happens, Result and State, and \overline{M}_{n}∥Happens∥ ⊆ M∥Happens∥, \overline{M}_{n} is preferable to M contradicting the assumption that M is a model of CIRC[T ∧ N ; Ab, Happens ; Result, S0, State]. Therefore M is a model of CIRC[T ; Ab ; Result, S0].

Lemma 12 If T is a domain description and N is a narrative description, then

CIRC[T ∧ N ; Absit ; Ab, Happens, Result, Holds, S0, State] ⊧
CIRC[T ; Absit ; Ab, Result, Holds, S0]

Proof The proof is analogous to that of Lemma 11. In this case it is not necessary when constructing the contradiction to note that \overline{M}_{n}∥Ab∥ ⊂ M∥Ab∥ or that \overline{M}_{n}∥Happens∥ ⊆ M∥Happens∥, since the predicates Ab and Happens are allowed to vary in the circumscription of Absit.

Theorem 1 follows directly from Lemmas 11 and 12. We remarked in Section 3 that the theorem can be extended to cover narrative descriptions containing existentially quantified conjunctions of Happens and temporal ordering formulae similar to the example of that section. To extend the proof appropriately, we merely note that each variable assignment within an interpretation consistent with the partial orderings gives a specific ordering of all the Happens conjuncts within each formula. We may utilise this ordering to construct a series of models \overline{M}_{i} in the manner of the proof of Lemma 11.

Appendix B: Axioms For Divisible & Concurrent Actions

Duration of actions:

Duration(a) > 0  (CD1)
Duration(a1; a2) = Duration(a1) + Duration(a2)  (CD2)
0 < d < Duration(a) → Duration(Head(a, d)) = d  (CD3)
0 < d < Duration(a) → Duration(T ail(a, d)) = Duration(a) − d  (CD4)

Concatenation of actions and the Result function:

Result((a1; a2), s) = Result(a2, Result(a1, s))  (CD5)

Equivalent actions:

a1 ≈ a2 → Result(a1, s) = Result(a2, s)  (CD6)
0 < d < Duration(a) → a ≈ Head(a, d); T ail(a, d)  (CD7)
Head((a1; a2), Duration(a1)) ≈ a1  (CD8)
T ail((a1; a2), Duration(a1)) ≈ a2  (CD9)
a ≈ a  (CD10)
a ≈ b ↔ b ≈ a  (CD11)
[a ≈ b ∧ b ≈ c] → a ≈ c  (CD12)

\begin{matrix}[Duration(a1) = Duration(a2) ∧ Duration(a3) = Duration(a4)] & (CD13) \\ → [[a1 ≈ a3 ∧ a2 ≈ a4] → a1&a2 ≈ a3&a4] \end{matrix}

[a1 ≈ a3 ∧ a2 ≈ a4] → [a1; a2 ≈ a3; a4]  (CD14)

\begin{matrix}[0 < d < Duration(a1) ∧ 0 < d < Duration(a2) ∧ a1 ≈ a2] → & (CD15) \\ [Head(a1, d) ≈ Head(a2, d) ∧ T ail(a1, d) ≈ T ail(a2, d)] \end{matrix}

Duration(a1) = Duration(a2) → a1&a2 ≈ a2&a1  (CD16)

\begin{matrix}[Duration(a1) = Duration(a2) ∧ Duration(a2) = Duration(a3)] & (CD17) \\ → a1&(a2&a3) ≈ (a1&a2)&a3 \end{matrix}

a&a ≈ a  (CD18)
a1; (a2; a3) ≈ (a1; a2); a3  (CD19)

\begin{matrix}[Duration(a1) = Duration(a2) ∧ 0 < d < Duration(a1)] → & (CD20) \\ Head(a1&a2, d) ≈ Head(a1, d)&Head(a2, d) \end{matrix}

\begin{matrix}[Duration(a1) = Duration(a2) ∧ 0 < d < Duration(a1)] → & (CD21) \\ T ail(a1&a2, d) ≈ T ail(a1, d)&T ail(a2, d) \end{matrix}

\begin{matrix}[Duration(a1) = Duration(a2) ∧ Duration(a3) = Duration(a4)] & (CD22) \\ → (a1&a2); (a3&a4) ≈ (a1; a3)&(a2; a4) \end{matrix}

Cancellation of action effects:

[Cancels(a2, a1, f, s) ∧ a3 ≈ a2 ∧ 0 < d < Duration(a3)] →  (CD23)
[Cancels(a3, a1, f, s) ∧ Cancels(Head(a3, d), a1, f, s) ∧
Cancels(T ail(a3, d), a1, f, s) ∧ Cancels((a3&a4), a1, f, s) ∧
Cancels((a3; a4), a1, f, s) ∧ Cancels((a4; a3), a1, f, s)]

\begin{matrix}Holds(f, Result(a, s)) ← & (CD24) \\ [a ≈ a1&a2 ∧ Holds(f, Result(a1, s)) ∧ ¬Cancels(a, a1, f, s)] \end{matrix}

Addendum, February 1995

Axiom (CD23) is too strong. It should express only that if an action α2 cancels the effect of α1 on ϕ, then all horizontal components of α2 cancel the effect of α1 on ϕ. Axiom (CD24) should be correspondingly modified. The axioms should be:

\begin{matrix}[Cancels(a2, a1, f, s) ∧ a3 ≈ a2 ∧ 0 < d < Duration(a3)] → & (CD23) \\ [Cancels(a3, a1, f, s) ∧ Cancels(Head(a3, d), a1, f, s) \\ ∧ Cancels(T ail(a3, d), a1, f, s)] \end{matrix} \begin{matrix}Holds(f, Result(a, s)) ← & (CD24) \\ [a ≈ a1&a2 ∧ Holds(f, Result(a1, s)) ∧] \\ ¬∃a3[P art(a3, a2) ∧ Cancels(a3, a1, f, s)]] \end{matrix}

22