\overline{1}

A SIMPLE DECLARATIVE LANGUAGE FOR DESCRIBING NARRATIVES WITH ACTIONS

To appear in the Journal of Logic Programming Special Issue on Reasoning about

Actions (Spring 1997)

ANTONIOS KAKAS AND ROB MILLER

▷ We describe a simple declarative language E for describing the effects of a series of action occurrences within a narrative. E is analogous to Gelfond and Lifschitz’s Language A and its extensions, but is based on a different ontology. The semantics of E is based on a simple characterisation of persistence which facilitates a modular approach to extending the expressivity of the language. Domain descriptions in A can be translated to equivalent theories in E. We show how, in the context of reasoning about actions, E’s narrative-based ontology may be exploited in order to characterise and synthesise two complementary notions of explanation. According to the first notion, explanation may be partly modelled as the process of suitably extending an apparently inconsistent theory written in E so as to establish consistency, thus providing a natural method, in many cases, to account for conflicting sets of information about the domain. According to the second notion, observations made at later times can sometimes be explained in terms of what is true at earlier times. This enables domains to be given an alternative characterization in which knowledge arising from observations is appropriately separated from other aspects of the domain. We also describe how E domains may be implemented as Event Calculus style logic programs, which facilitate automated reasoning both backwards and forwards in time, and which behave correctly even when the knowledge entailed by the domain description is incomplete. ◁ 1. INTRODUCTION

Address correspondence to ANTONIOS KAKAS, Deptment of Computer Science, University of Cyprus, 75 Kallipoleos Street, P.O. Box 537, CY-1678 Nicosia, CYPRUS.

Email: antonis@turing.cs.ucy.ac.cy or ROB MILLER, Department of Computing, Imperial College, 180 Queen’s Gate, London SW7 2BZ, U.K. Email: rsm@doc.ic.ac.uk, http://wwwlp.doc.ic.ac.uk/UserPages/staff/rsm/rsm.html An earlier version of this paper (August 1995) appeared as a joint Imperial College / University of Cyprus Research Report (Imperial College Research Report Number DoC 95/12)

This paper largely concerns narrative reasoning, that is, reasoning about actions which actually occur at various times, and reasoning about the properties that hold or do not hold at different times as a consequence of such occurrences. The importance of narrative reasoning has been recognised elsewhere (see [2], [34] or [31]). For example, to deal with observations a formalism must allow the representation of a narrative, since phenomena can only be ‘observed’ at actual times. In the context of the Situation Calculus it makes little sense to state that Fred is observed to be alive in the ‘hypothetical’ or ‘projected’ situation

Result(Shoot, Result(W ait, Result(Load, S0)))

unless there is some extra mechanism to relate the sequence of actions Load - W ait - Shoot to the time at which the observation took place.

For the purposes of discussion, we will informally define a narrative-based formalism as a formalism in which the structure or flow of time is represented independently from the notion of an action, and in which actions are ‘embedded’ in this independent structure using an explicit notion of an action occurrence. Examples of such formalisms are Allen’s interval-based approach [1], Sandewall’s Features and Fluents framework [36] (where a series of action occurrences are captured as a schedule) and Kowalski and Sergot’s Event Calculus [24]. On the other hand, formalisms such as McCarthy and Hayes’ Situation Calculus [29], Dynamic Logics (see for example [18]) and Gelfond and Lifschitz’s Language A [16] are not narrative-based. This is not to say that they cannot be extended to deal with narrative information (see for example [34], [31] or [26]). But the notions of an independent flow of time and of an action occurrence are not central to their underlying ontology.

In [16] and [17], Gelfond and Lifschitz proposed a particular methodology for research into reasoning about action. The authors introduced the Language A as a “simple declarative language for describing actions”, and suggested that, by describing general translation procedures from A domains into other formalisms, an insight could be gained into the comparative possibilities and limitations of each approach. The success of this idea is exemplified in a paper by Kartha [21], which uses translations from A to show the equivalence of three well-known characterisations of the Situation Calculus for a whole class of domains. The primary intention of A was to provide a language and semantics simple enough to be regarded as uncontroversial and intuitive, even if (initially) somewhat limited in expressivity. Of course, the ‘neutrality’ of any such language, used as a measuring stick for other formalisms, will inevitably be compromised to some extent by the necessity of choosing a particular ontology as a starting point. The ontology underlying the Language A is inherited from the Situation Calculus.

This paper shows that the methodology described above need not be limited to this particular ontology. Our central aim is to propose and develop a simple declarative language for describing narratives, called E, based not upon the ontology of the Situation Calculus, but instead upon a narrative-based ontology similar to that of the Event Calculus. Furthermore, we aim to use E as a specification for developing logic programs for automated reasoning about action and change in a principled manner. We believe that the use of, and comparison between, different ontologies is vital in the study of reasoning about action. Central issues such as the frame problem, the ramification problem and the qualification problem all take on different flavours when set in different ontological contexts. Comparisons between approaches can help reveal which aspects of these problems are fundamental, and which are merely the product of a particular method of representation.

In particular, the notion of persistence (or ‘inertia’) is somewhat different in a narrative setting. A simple declarative characterisation of persistence is central to the semantics of E described below. This semantics, like that of A, is modeltheoretic, and the characterisation of persistence is achieved by listing three specific conditions which each model must satisfy. The definition of a model is intended to be modular in the sense that, in future extensions to E, further conditions or constraints not relating to persistence may simply be added. (To illustrate this point, two simple extensions to E are given in an appendix.) The semantics gives rise to a notion of entailment which is independent from any particular method of derivation or computation. Thus the Language E helps differentiate between the ontological commitments of the Event Calculus and the computational mechanisms provided by its original logic programming setting. In this respect it serves a purpose similar to that of the formalisms described in [40], [41] and [7].

The paper is organised as follows. In Section 2, we describe the basic syntax and semantics of E, give some examples and discuss some general properties of the formalism. In Section 3 we show a correspondence between the Languages A and E by describing a sound and complete translation from theories written in A into Language E domain descriptions. We also briefly discuss the relationship between E and the Language L_{0}, a narrative extension of A recently proposed by Baral, Gelfond and Provetti [5] [6]. In the next three sections, we use E to characterise two complementary notions of explanation in temporal domains. In Section 4, we show how explanation may be partly modelled as the process of extending an apparently inconsistent theory written in E so as to establish consistency. In particular, we show that the syntax and semantics of E allows a class of ‘narrative-based’ explanations to be identified in a natural way. We also show how different preference relations between explanations can be combined with the simple object-level definition of entailment described previously in order to define a meta-level semantics with both an abductive and a deductive flavour. In Sections 5 and 6 we show that observations made at later times may also sometimes be explained in terms of what is true at earlier times. To do this, we identify a special class of E domain descriptions, and separate out observations from these theories. In Section 7 we describe how E domains may be implemented as Event Calculus style logic programs. We do this in a way which avoids potential problems when the information entailed by the domain is ‘incomplete’, which could otherwise be caused by logic programming’s implicit completion of the HoldsAt predicate. These programs also encode a limited form of reasoning backwards in time. Finally, in Section 8 we show how, for a particular class of domains, we may use some of the notions of explanation developed earlier to add a meta-level component to these implementations, in order to facilitate a more ‘complete’ form of automated temporal reasoning.

2. A CLASS OF LANGUAGES FOR DESCRIBING NARRATIVES OF AC-TION OCCURRENCES

First, we will describe the basic syntax of the Language E. Strictly speaking, E represents a family of languages, all of which use a basic ontology and vocabulary of fluents (properties), actions and time points. The progression of time is represented by an ordering relation over the set of time points. Time may either be continuous or progress via discrete steps, and need not necessarily be linear.

Definition 2.1. [Domain Language] A domain language is a tuple ⟨Π, ⪯, Δ, Φ⟩, where ⪯ is a partial (possibly total) ordering^{1}defined over the non-empty set Π of time points, Δ is a non-empty set of action constants, and Φ is a non-empty set of fluent constants.

Except where the context implies otherwise, for the remainder of the paper we assume a particular domain language E = ⟨Π, ⪯, Δ, Φ⟩. We will often write T_{1} ≺ T_{2} to mean T_{1} ⪯ T_{2} and T_{1} ≠ T_{2}.

Definition 2.2. [Fluent literal] A fluent literal of E is an expression either of the form F or of the form ¬F, where F ∈ Φ.

Three types of statements are possible within E. C-propositions (“c” for “causes”) express the conditions under which particular actions can potentially initiate or terminate periods (i.e. intervals) in which a property holds. H-propositions (“h” for “happens”) indicate that a particular action occurs at a particular time, and tpropositions (“t” for “time point”) express that a particular property holds at a particular time.

Definition 2.3. [c-proposition] A c-proposition in E is an expression either of the form

A initiates F when C

or of the form

A terminates F when C

where F ∈ Φ, A ∈ Δ, and C is a set of fluent literals of E.

Notation: We shall often write c-propositions of the form “A initiates F when ∅” and “A terminates F when ∅” as “A initiates F ” and “A terminates F ” respectively.

Definition 2.4. [h-proposition] An h-proposition in E is an expression of the form

A happens-at T

where A ∈ Δ and T ∈ Π.

Definition 2.5. [t-proposition] A t-proposition in E is an expression of the form

and A.

1We mean ‘partial ordering’ in the usual mathematical sense, i.e. ⪯ is reflexive, transitive and anti-symmetric. ⪯ should not be regarded as representing partial knowledge about a total order – our formalism would have to be modified to cope with this type of incomplete information.

Although it might be argued that time is in fact linear, so that ⪯ should always be a total ordering, we consider partial orderings here for the sake of mathematical generality, and because in Section 3 a particular partially ordered set is useful in showing a correspondence between the Languages E

L holds-at T

where L is a fluent literal of E and T ∈ Π.

Definition 2.6. [Domain description] A domain description in E is a triple ⟨γ, η, τ⟩, where γ is a set of c-propositions, η is a set of h-propositions^{2}, and τ is a set of t-propositions in E.

The semantics for E is expressed by defining the notion of an interpretation, and stating when an interpretation qualifies as a model for a given domain description. In the definitions below, an interpretation is defined simply as a mapping of fluent/time-point pairs to true or false (i.e. a holds relation). A model is an interpretation that respects four properties. The first three of these are intended to characterise a ‘commonsense’ notion about the persistence of properties as time progresses. In particular, they encapsulate the idea that all points at which a property starts (ceases) to hold are earmarked by an initiating (terminating) action occurrence – in other words, actions are the only mechanisms for change^{3}. This is stated explicitly in condition (1) of Definition 2.10. Conditions (2) and (3) confirm that the terms initiate and terminate have their intended meanings, relative to this ‘commonsense’ principle.

Definition 2.7. [Interpretation] An interpretation of E is a mapping

H : Φ × Π ↦ {true, false}

Definition 2.8. [Point satisfaction] Given a set of fluent literals C of E and a time point T ∈ Π, an interpretation H satisfies C at T iff for each fluent constant F ∈ C, H(F, T) = true, and for each fluent constant F′ such that ¬F′ ∈ C, H(F′, T) = false.

Definition 2.9. [Initiation/termination point] Let H be an interpretation of E, let D = ⟨γ, η, τ⟩ be a domain description, let F ∈ Φ and let T ∈ Π. T is an initiation-point (respectively termination-point) for F in H relative to D iff there is an A ∈ Δ such that (i) there is both an h-proposition in η of the form “A happens-at T ” and a c-proposition in γ of the form “A initiates F when C” (respectively “A terminates F when C”) and (ii) H satisfies C at T.^{4}

Definition 2.10. [Model] Given a domain description D = ⟨γ, η, τ⟩ in E, an interpretation H of E is a model of D iff, for every F ∈ Φ and T, T′, T_{1}, T_{3} ∈ Π such that T_{1} ≺ T_{3}, the following properties hold:

2Thus, since η can include more than one h-proposition that refers to the same time point, E allows for a limited form of concurrency (its semantics forces the assumption that concurrently performed actions do not interfere, for example to cancel each other’s effects). In contrast A does not allow any concurrency, whereas its extension A_{c} [4] allows for a more general form of concurrency.

3This principle might be considered too strong for some domains, e.g. those involving continuous change. In this case, some distinction will be required between those properties which naturally persist (frame fluents in Lifschitz’s terminology) and those which do not.

4According to this definition, not all initiation and termination points will be points of change of the fluent within a particular model. For example, if a fluent already holds before an initiationpoint it will remain unchanged. Thus in Sergot’s terms [37] the semantics uses “weak” initiation and termination (but see footnote, Appendix A.1).

1. If there is no initiation-point or termination-point T_{2} for F in H relative to D such that T_{1} ⪯ T_{2} ≺ T_{3}, then H(F, T_{1}) = H(F, T_{3}).

2. If T_{1} is an initiation-point for F in H relative to D, and there is no terminationpoint T_{2} for F in H relative to D such that T_{1} ≺ T_{2} ≺ T_{3}, then H(F, T_{3}) = true.

3. If T_{1} is a termination-point for F in H relative to D, and there is no initiation-point T_{2} for F in H relative to D such that T_{1} ≺ T_{2} ≺ T_{3}, then H(F, T_{3}) = false.

4. For all t-propositions in τ of the form “F holds-at T ”, H(F, T) = true, and for all t-propositions of the form “¬F holds-at T′”, H(F, T′) = false.

Definition 2.11. [Consistency] A domain description is consistent iff it has a model.

Definition 2.12. [Entailment] A domain description D entails the t-proposition “F holds-at T ”, written “D ⊧ F holds-at T ”, iff for every model H of D, H(F, T) = true. D entails the t-proposition “¬F holds-at T ” iff for every model H of D, H(F, T) = false.

In keeping with our adopted methodology, two important simplifying assumptions are implicitly included in the above semantics. First, the information about the general effects of actions, expressed as c-propositions, is assumed to be complete. An analogous assumption is made about the e-propositions in a Language A theory. Second, the information about the occurrence of actions, expressed as h-propositions, is also assumed to be complete. (There is no directly analogous assumption in the definition of a Language A model, since the notion of an action occurrence is not included in its ontology.) Clearly, both these assumptions will be sources of nonmonotonicity in the language. The h-propositions not only give complete information about which actions occur, but (since ⪯ is assumed to be well-defined) also give complete information about the order and timing of these occurrences^{5}.

Condition (4) in Definition 2.10 above expresses pointwise constraints on a model which arise from the inclusion of t-propositions in the domain description. We envisage other such constraints being added in future, more expressive extensions of E. Such extensions might also require refinements to the definitions of an interpretation or of an initiation or termination point. But we expect the characterisation of persistence encapsulated in conditions (1)-(3), which can be regarded as the ‘core’ of the semantics, to remain unaltered. To remain faithful to the methodology we are using, we wish here to keep the syntax and semantics of E as simple as possible, even at the loss of some expressivity. However, to illustrate this modular aspect of the semantics we have included two simple extensions to E in Appendix A (relating to ‘qualifications’ and ‘ramifications’ of action occurrences).

5Relaxing these assumptions would be an interesting area for future research, but would inevitably lead to a more complex semantics. For example, it would be straightforward to allow for incomplete knowledge about the order and timing of action occurrences by using temporal variables in h-propositions, and including a fourth type of proposition in domain descriptions with which to express ordering constraints between these variables. An interpretation would then include a mapping (i.e. variable assignment) from temporal variables to time points as a second component.

The following two examples illustrate the effects of our model-theoretic characterisation of persistence.

Example 2.1. This example is intended to illustrate the necessity of including the first condition in Definition 2.10 of a Language E model above. It concerns vaccinations against a particular disease. Vaccine A only provides protection for people with blood type O, and vaccine B only works on people with blood type other than O. Fred’s blood type is not known, so he is injected with vaccine A at 2 o’clock and vaccine B at 3 o’clock. For simplicity we will model time as the real number line with the usual ordering relation, so that for this example, E_{v} = ⟨ℜ, ≤, {InjectA, InjectB}, {P rotected, T ypeO}⟩. The domain description D_{v} consists of two c-propositions, two h-propositions and a single t-proposition:

InjectA initiates P rotected when {T ypeO}
InjectB initiates P rotected when {¬T ypeO}
InjectA happens-at 2
InjectB happens-at 3
¬P rotected holds-at 1

If we now consider some time later than 3 o’clock, say 4 o’clock, we can see intuitively that Fred should be protected. Now by condition (1), in all models of D_{v} Fred’s blood group remains constant, so that in any given model, by condition (2), Fred becomes protected either at 2 o’clock or at 3 o’clock. Consequently,

D_{v} ⊧ P rotected holds-at 4

Had condition (1) not been included in the definition of a model, it would have been possible to construct a model, for example, in which Fred’s blood type “mysteriously” changed from ¬T ypeO to T ypeO at 2.30, thus rendering both vaccinations ineffective.

Example 2.2. This example shows that the Language E can be used to infer information about what conditions hold at the time of an action occurrence, given other information about what held at times before and afterwards. It is similar to Baker’s ‘murder mystery’ scenario [3]. Let E_{ys} = ⟨ℜ^{+}, ≤, {Shoot}, {Alive, Loaded}⟩, where ℜ^{+} signifies the non-negative real numbers, and let the domain description D_{ys} consist of a single c-proposition, a single h-proposition and two t-propositions:

Shoot terminates Alive when {Loaded}
Shoot happens-at 2
Alive holds-at 1
¬Alive holds-at 3

Since by condition (4) in any model H of D_{ys}, H(Alive, 1) ≠ H(Alive, 3), then by condition (1), in all models an action must occur at some time point between 1 and 3 whose initiating or terminating conditions for the property Alive are satisfied at that point. The only candidate is the Shoot occurrence at 2, whose condition for terminating Alive is Loaded. Hence

D_{ys} ⊧ Loaded holds-at 2

Indeed, by applying condition (1) again, it is easy to see that for all n, n ≥ 0,

D_{ys} ⊧ Loaded holds-at n

Two properties of E will prove useful later. The first is that E is monotonic as regards addition of t-propositions to domain theories (although, as observed earlier, not as regards addition of h-propositions or c-propositions). That is to say, if H is a model of a domain description ⟨γ, η, τ⟩ and τ′ ⊆ τ, H is also a model of ⟨γ, η, τ′⟩. This follows directly from Definition 2.10. The second property of interest concerns the deterministic nature of actions’ effects within a narrative, and is somewhat analogous to Lin and Shoham’s notion of epistemological completeness [27]. Provided the domain description under consideration is consistent and contains no finite intervals of time in which an infinite number of actions occur, then the set of fluents which hold at any point T completely determines the set of fluents which hold at any later time point. This claim is made precise in the following definition and proposition.

Definition 2.13. [Occurrence Sparsity] Let D = ⟨γ, η, τ⟩ be a domain description written in a language E = ⟨Π, ⪯, Δ, Φ⟩. D and η are occurrence-sparse iff for any two points T_{1}, T_{2} ∈ Π there are only a finite number of h-propositions in η of the form“A happens-at T ” such that T_{1} ⪯ T ≺ T_{2}.

Proposition 2.1. Let D be an occurrence-sparse domain description written in a language E = ⟨Π, ⪯, Δ, Φ⟩, and let T_{1}, T_{2} ∈ Π be such that T_{1} ⪯ T_{2}. Let H and H′ be models of D such that for all F ∈ Φ, H(F, T_{1}) = H′(F, T_{1}). Then for all F ∈ Φ, H(F, T_{2}) = H′(F, T_{2}).

Proof. See Appendix B.1

The occurrence of infinite numbers of actions in a finite period of time leads to interesting and/or unexpected results in many formalisms for reasoning about action. For a general discussion of this complex issue, the reader may refer to Davis [9]. However, for the remainder of this paper, we restrict our attention to domain descriptions which are occurrence-sparse, and thus deterministic in the sense of Proposition 2.1.

3. SIMULATING THE LANGUAGE A AS A CLASS OF LANGUAGE E DO-MAINS

Because they use different ontologies, any correspondence between the Languages A and E must inevitably be expressed in rather artificial terms. In this section we show that Language A domains can be simulated or re-formulated as Language E domains with a branching structure ⟨Π, ⪯⟩ of time points, analogous to the branching ‘tree’ of situations often incorporated in formulations of the Situation Calculus. Since the Language A is not narrative-based and so does not directly include the notion of action occurrences, in our re-formulation an appropriate action occurrence has to be ‘built in’ at each point in this tree structure. In situation calculus terms, we must ensure that for each situation S in the tree, the action A ‘occurs’ between the situations S and Result(A, S). To express this, we need to insert an extra time-point between S and Result(A, S) – in graphical terms, we need to be able to refer to the arcs connecting the situation nodes in the tree. This is achieved in a simple way below by considering ‘doubled’ sequences of actions. Sequences of even length correspond to nodes of the tree structure (i.e. to situations), and sequences of odd length correspond to the inter-connecting arcs. A temporal ordering relation is then defined on both nodes and arcs.

Definition 3.1. [Δ-sequence] Given a set Δ of action constants, a Δ-sequence of Δ is defined inductively as follows:

• The empty sequence ⟨⟨ ⟩⟩ is a Δ-sequence

• For each A, A′ ∈ Δ, the singleton sequence ⟨⟨|A|⟩⟩, the sequence ⟨⟨|A|, A⟩⟩ and the sequence ⟨⟨|A|, A, |A′|⟩⟩ are all Δ-sequences

• For each A_{1}, …, A_{n} ∈ Δ, ⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}⟩⟩ is a Δ-sequence

• For each A′ ∈ Δ and for each Δ-sequence ⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}⟩⟩, ⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}, |A′|⟩⟩ is a Δ-sequence

Definition 3.2. [Δ-ordering] Given a set Δ of action constants and the corresponding set Π_{Δ} of all Δ-sequences, the Δ-ordering ≤_{Δ} over Π_{Δ} is defined as follows

• For all S ∈ Π_{Δ}, ⟨⟨ ⟩⟩ ≤_{Δ} S

• For all ⟨⟨α_{1}, …, α_{n}⟩⟩ ∈ Π_{Δ} and for all m such that 1 ≤ m ≤ n,

⟨⟨α_{1}, …, α_{m}⟩⟩ ≤_{Δ} ⟨⟨α_{1}, …, α_{n}⟩⟩

Examples: Suppose Δ = {W ait, Load, Shoot}. The Δ-sequence

⟨⟨|Load|, Load, |W ait|, W ait, |Shoot|, Shoot⟩⟩

corresponds to the Situation Calculus term

Result(Shoot, Result(W ait, Result(Load, S0)))

and (regarding situations as arranged in a branching tree structure) the Δ-sequence

⟨⟨|Load|, Load, |W ait|, W ait, |Shoot|⟩⟩

corresponds to the inter-connecting arc between the situations

Result(W ait, Result(Load, S0))

and

Result(Shoot, Result(W ait, Result(Load, S0)))

Regarding the ordering ≤_{Δ}, it is easy to see that, for example

⟨⟨|Load|⟩⟩ ≤_{Δ} ⟨⟨|Load|, Load⟩⟩
⟨⟨|Load|, Load⟩⟩ ≤_{Δ} ⟨⟨|Load|, Load, |W ait|, W ait, |Shoot|, Shoot⟩⟩

Notation: We shall sometimes refer to the Δ-sequence

⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}⟩⟩

simply as A_{1}, …, A_{n} and refer to the Δ-sequence

⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}, |A′|⟩⟩

as A_{1}, …, A_{n}, |A′|. Notice that in this notation

A_{1}, …, A_{n}, |A′| ≤_{Δ} A_{1}, …, A_{n}, A′

The next definition allows us to express that, in general, the action A′ occurs at A_{1}, …, A_{n}, |A′|, so that the effects of A′ are apparent at the following time point A_{1}, …, A_{n}, A′.

Definition 3.3. [Complete occurrence set] Let E = ⟨Π_{Δ}, ≤_{Δ}, Δ, Φ⟩, where Π_{Δ} is the set of Δ-sequences of Δ and ≤_{Δ} is the Δ-ordering over Π_{Δ}. The set η_{Δ}, called the complete occurrence set of Δ, is the set of all h-propositions of E either of the form

A happens-at ⟨⟨|A|⟩⟩

or of the form

A_{n} happens-at ⟨⟨|A_{1}|, A_{1}, …, |A_{n−1}|, A_{n−1}, |A_{n}|⟩⟩

The following proposition shows a sense in which the Language A may be regarded as a special case of the Language E.

Proposition 3.1. Let D_{A} be a consistent theory written in a language A in the sense of [16], with a set of action constants Δ and a set of fluent constants Φ. Let E = ⟨Π_{Δ}, ≤_{Δ}, Δ, Φ⟩, where Π_{Δ} is the set of Δ-sequences of Δ and ≤_{Δ} is the Δ-ordering over Π_{Δ}. Let D_{E} be the domain description ⟨γ, η_{Δ}, τ⟩ in E defined as follows:

• η_{Δ} is the complete occurrence set of Δ

• For each v-proposition in D_{A} of the form “L after A_{1}; …; A_{m}” there is a t-proposition in τ of the form “L holds-at A_{1}, …, A_{m}”, and for each vproposition in D_{A} of the form “ initially L” there is a t-proposition in τ of the form “L holds-at ⟨⟨ ⟩⟩”

• For each F ∈ Φ, then for each e-proposition in D_{A} of the form “A causes F if L_{1}, …, L_{n}” there is a c-proposition in γ of the form “A initiates F when {L_{1}, …, L_{n}}”

• For each F ∈ Φ, then for each e-proposition in D_{A} of the form “A causes ¬F if L_{1}, …, L_{n}” there is an c-proposition in γ of the form “A terminates F when {L_{1}, …, L_{n}}”

Then for each F ∈ Φ and each A_{1}, …, A_{n} ∈ Δ • D_{E} ⊧ F holds-at ⟨⟨ ⟩⟩ if and only if

D_{A} entails initially F

• D_{E} ⊧ ¬F holds-at ⟨⟨ ⟩⟩ if and only if D_{A} entails initially ¬F

• D_{E} ⊧ F holds-at A_{1}, …, A_{n} if and only if D_{A} entails F after A_{1}; …; A_{n}

• D_{E} ⊧ ¬F holds-at A_{1}, …, A_{n} if and only if D_{A} entails ¬F after A_{1}; …; A_{n}

Proof. Let R be the unique transition function such that there is a model (σ_{0}, R) of D_{A} (for definitions see [16]). Let σ ⊆ Φ be a set of fluent constants. For each F ∈ Φ and A_{1}, …, A_{n}, A′ ∈ Δ let the interpretation H_{[σ,R]} be defined as follows:

• H_{[σ,R]}(F, ⟨⟨ ⟩⟩) = H_{[σ,R]}(F, ⟨⟨|A′|⟩⟩) = true if and only if F ∈ σ

• H_{[σ,R]}(F, ⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}⟩⟩) =

H_{[σ,R]}(F, ⟨⟨|A_{1}|, A_{1}, …, |A_{n}|, A_{n}, |A′|⟩⟩) = true
if and only if F ∈ R(A_{n}, R(A_{n−1}, …, R(A_{1}, σ) …))

Clearly, for each σ ⊆ Φ, H_{[σ,R]} is a model of ⟨γ, η, ∅⟩, and H_{[σ,R]} is a model of D_{E} = ⟨γ, η, τ⟩ if and only if (σ, R) is a model of D_{A} in the sense of [16]. Since D_{E} is occurrence-sparse, by Proposition 2.1 all models of D_{E} are of this form, so that there is a one-to-one correspondence between models of D_{A} and such models of D_{E}, and the proposition follows directly from the definition of H_{[σ,R]}.

We conclude this section with some brief remarks about the relationship between E and the Language L_{0} recently introduced by Baral, Gelfond and Provetti in [5], and discussed in more detail in [6]. L_{0} is a ‘narrative’ extension to A which uses A’s underlying Situation Calculus based ontology. Conceptually, it is close to the extension of the Situation Calculus described by Pinto and Reiter in [34]. Both are concerned with describing and reasoning about an ‘actual path’ through the ‘tree of situations’.

A model of an L_{0} domain description is a pair (Ψ, Σ). The “Ψ” component roughly corresponds to the notion of a (partial) “transition function” in a Language A model. For a given domain, Ψ is characterised by a collection of effect laws in L_{0}, which is equivalent to a set of e-propositions in A and may be translated into a Language E domain description of the form ⟨γ, η_{Δ}, τ⟩ as described in Proposition 3.1. Given such a translation, the “Σ” component of an L_{0} model can be regarded as an assignment of the situation symbol s_{N} (always included in L_{0}’s vocabulary) to a particular Δ-sequence δ_{N} in Π_{Δ}, together with an assignment of each other situation symbol s_{i} to a Δ-sequence δ_{i} such that δ_{i} ≤_{Δ} δ_{N}. (In Pinto and Reiter’s terms, δ_{N} represents the ‘actual path of situations’.) To be acceptable, the assignment δ_{N} must be of minimal length, subject to certain constraints which are expressed as fluent facts, occurrence facts and precedence facts. For example, the occurrence fact “A_{1}, A_{2} occurs-at s_{i}” constrains δ_{N} to be of the form ⟨⟨α_{1}, …, α_{i}, |A_{1}|, A_{1}, |A_{2}|, A_{2}, …, α_{n}⟩⟩ (where ⟨⟨α_{1}, …, α_{i}⟩⟩ is the Δ-sequence δ_{i} assigned to s_{i}), and the precedence fact “s_{i} precedes s_{j}” expresses the constraints δ_{i} ≤_{Δ} δ_{j} and δ_{i} ≠ δ_{j}. The minimal length requirement for δ_{N} corresponds to the minimisation of the occurs predicate in Pinto and Reiter’s extended Situation Calculus.

A number of other papers which discuss the relationship between the Situation Calculus and the Event Calculus have recently been published, see for example [25], [30], [35] and [44].

4. DEALING WITH INCONSISTENT DOMAINS BY EXPLANATIONS

Like the Language A, the Language E provides a very rigid way of specifying the effects of actions. Each separate effect has to be explicitly described by a cproposition (analogous to an e-proposition in the Language A), and the definition of entailment does not facilitate the inference of any other effects. For example, without an explicit representation of the statement “the action occurrence A terminates the property P ” the statement “P is true before A, but false afterwards” gives rise to an inconsistency. This is in contrast to some other approaches to representing persistence, such as representations in circumscribed predicate calculus, which in this respect are more flexible. The Language E is similarly rigid in its representation of a narrative – all action occurrences must be explicitly represented by an h-proposition.

However, greater flexibility can be achieved, without altering the underlying semantics of E, by introducing the notion of an explanation. Clearly, the statement that “property P is true before A, but false afterwards” is easily ‘explained’ by the statement “A terminates P ”. In this section we model the task of explanation as the task of restoring consistency, in some principled or selective way, to an inconsistent collection of facts, represented as an inconsistent domain description in E. Under this view, explanation is a form of belief revision. The nonmonotonicity built into our language sometimes allows an inconsistent domain theory to be ‘revised’ simply by adding sets of propositions. We will call such sets ‘explanations’. In the present context, explanations may be either in narrative or in causal terms, or in both. In other words, a given set of facts may be explained away in terms of what has happened and/or in terms of what causes what.

In Sections 5 and 6 we will extend the notion of an explanation, showing how in the context of narrative reasoning it is sometimes appropriate to regard information about what holds at earlier times as an ‘explanation’ of what holds at later times.

4.1. Explanations in Terms of Action Occurrences

The first class of explanations we will consider are those which can be expressed entirely in terms of action occurrences, i.e. extra h-propositions. We will use a version of Kautz’s Stolen Car problem [23] as an illustration.

Example 4.1. Let E_{sc} = ⟨N , ≤, {P ark, Steal}, {P arked}⟩, where N signifies the natural numbers, and let D_{sc} be the domain description consisting of the following two c-propositions, single h-proposition and single t-proposition:

P ark initiates P arked

Steal terminates P arked

P ark happens-at 2

¬P arked holds-at 6

By itself, D_{sc} is inconsistent, since there is no terminating action occurrence

for the fluent P arked between 2 and 6. However, we may restore consistency by adding one or more h-propositions.

Definition 4.1. [h-explanation] Let D = ⟨γ, η, τ⟩ be a domain description. An hexplanation for D is a (possibly empty) occurrence-sparse set η_{ϵ} of h-propositions, such that ⟨γ, η ∪ η_{ϵ}, τ⟩ is consistent.

For example, the following are all h-explanations for D_{sc}:

{ Steal happens-at 3, Steal happens-at 4 }
{ Steal happens-at 4, P ark happens-at 8 }
{ Steal happens-at 5 }

Indeed, it is obvious that we may construct an h-explanation for D_{sc} containing as many h-propositions as we like. Clearly, extra mechanisms are needed which enable us to prefer some explanations to others. The following definition reflects a very simple, set-theoretic notion of preference. However, the definition could be modified for specific domains, for example to reflect the fact that we wish to regard some types of occurrence as more likely than others.

Definition 4.2. [Preferable h-explanation]^{6} Let η_{ϵ} and η′_{ϵ} be h-explanations for D. η_{ϵ} is preferable to η′_{ϵ} iff η_{ϵ} ⊂ η′_{ϵ}.

Having identified a class of explanations, such as the class of h-explanations in Definition 4.1, and a preference criterion such as that of Definition 4.2, it is possible to construct a corresponding meta-level, explanation-based ‘semantics’ similar to the semantics of Abductive Logic Programming [19], [20], [13]. We consider all possible extensions of a given domain description D with optimal explanations, and accept conclusions if and only if these hold in each such extension. This semantics can then be used to decide what can be safely ‘inferred’ from a seemingly inconsistent domain description.

Definition 4.3. [Optimal h-explanation] η_{ϵ} is an optimal h-explanation for D iff η_{ϵ} is an h-explanation for D and there is no other h-explanation η′_{ϵ} for D such that η′_{ϵ} is preferable to η_{ϵ}.

Definition 4.4. [h-model] Let D = ⟨γ, η, τ⟩ be a domain description. H is an hmodel of D iff there exists an optimal h-explanation η_{ϵ} for D such that H is a model of ⟨γ, η ∪ η_{ϵ}, τ⟩

Definition 4.5. [h-consistency] A domain description is h-consistent iff it has at least one h-model.

6In this definition and throughout the paper “⊂” is intended to mean “is contained in and not equal to”.

Definition 4.6. [h-entailment] The domain description D = ⟨γ, η, τ⟩ h-entails the t-proposition “F holds-at T ”, written “D ⊧_{h} F holds-at T ”, iff for every hmodel H of D, H(F, T) = true. D h-entails the t-proposition “¬F holds-at T ” iff for every h-model H of D, H(F, T) = false.

H-entailment is an abductive notion in the sense that optimal h-explanations are not derived from or entailed by a domain description, but are added to it (according to an external preference criterion). It also has a ‘deductive flavour’ in the sense that a t-proposition is entailed from a domain description simply if it is true in all h-models. And any procedure for verifying truth in all h-models will, explicitly or implicitly, have to take into account all optimal h-explanations.

The important point is that h-entailment is a meta-level concept, whereas the entailment relation defined in Section 2 is object-level. H-entailment is defined both in terms of object-level entailment and a particular preference criterion among explanations. Notice that Definitions 4.3 to 4.6 would still be applicable even if ‘hpreferability’ were to be defined differently (perhaps according to domain-specific considerations), but would yield different results.

A desirable property of any such meta-level entailment is that it should coincide with object-level entailment whenever the domain description is consistent. The following proposition shows that for h-entailment as defined Definition 4.6 above, this is indeed the case.

Proposition 4.1. Let D be a consistent domain description. Then H is a model of D if and only if H is an h-model of D.

Proof. The proposition follows directly from the observation that since D is already consistent, it has a unique optimal h-explanation ∅.

Returning to the Stolen Car problem, D_{sc} has three optimal h-explanations:

{ Steal happens-at 3 }
{ Steal happens-at 4 }
{ Steal happens-at 5 }

D_{sc} is therefore h-consistent, and has a total of six h-models (two corresponding to each optimal h-explanation), since in any h-model H, H(P arked, 0), H(P arked, 1) and H(P arked, 2) may either all be true or all be false. It is easy to see, therefore, that

D_{sc} ⊧_{h} P arked holds-at 3

and for all n ≥ 6,

D_{sc} ⊧_{h} ¬P arked holds-at n

Hence this example illustrates how the notion of h-entailment exploits the narrative ontology of E to give a natural and simple way to handle such apparently inconsistent domains.

H-entailment corresponds closely to Shanahan’s formulation of explanation-based temporal reasoning in [38]. The main difference is that whereas Shanahan’s concern is to abduce a single explanation for a given fact or observation, ours is to ‘safely’ infer new information by considering all (optimal) explanations. Shanahan’s work was partly based on earlier work by Eshghi [15] showing how planning could be formulated within an abductive Event Calculus framework. In Language E terms, an initial state I and goal state G can both be represented as sets τ_{I} and τ_{G} of t-propositions, domain information can be modelled as a set γ of c-propositions, and a plan can be regarded as a single h-explanation η_{e} for ⟨γ, ∅, τ_{I} ∪ τ_{G}⟩ such that ⟨γ, η_{e}, τ_{I}⟩ ⊧ ω for each ω ∈ τ_{G}.

Our notion of an h-model is also somewhat analogous to the description of a Language L_{0} model given by Baral, Gelfond and Provetti in [5] and [6] (see end of Section 3). An important difference here is that, whereas the requirement that action occurrences be minimal is ‘hardwired’ into L_{0}’s object-level semantics, our minimality requirement is to be found in the particular definition of h-preference, which could potentially be replaced by or extended with other, domain-specific preference criteria. Indeed, in the following section we give an example of a preference criterion among a class of explanations which is not entirely based around a simple notion of minimality.

4.2. Explanations in Terms of New Causal Rules

It will not always be possible to find an h-explanation for an inconsistent domain description D. In this section we briefly explore the possibilities of including both c-propositions and h-propositions in explanations. The discussion here is intended only to illustrate some of the problems relating to this – we are obviously trespassing into the related A.I. topic of learning. We will use the following (deliberately abstract) example to motivate the discussion:

Example 4.2. Let E_{ex} = ⟨N , ≤, {A_{1}, A_{2}}, {F_{1}, F_{2}}⟩, where N signifies the natural numbers, and let the domain description D_{ex} consist of three t-propositions:

F_{1} holds-at 4
F_{2} holds-at 5
¬F_{2} holds-at 10

This example is neither consistent nor h-consistent. To establish consistency in this case we need to consider explanations which include both narrative and causal information.

Definition 4.7. [hc-explanation] Let D = ⟨γ, η, τ⟩ be a domain description. An hc-explanation for D is a pair ⟨γ_{ϵ}, η_{ϵ}⟩, where γ_{ϵ} is a (possibly empty) set of cpropositions and η_{ϵ} is a (possibly empty) occurrence-sparse set of h-propositions, such that⟨γ ∪ γ_{ϵ}, η ∪ η_{ϵ}, τ⟩ is consistent.

For example, according to Definition 4.7 the following are all hc-explanations for D_{ex}:

1. ⟨{A_{1} terminates F_{2} when {F_{1}}}, {A_{1} happens-at 8}⟩

2. ⟨{A_{1} terminates F_{2}}, {A_{1} happens-at 8}⟩ 3. ⟨{A_{1} terminates F_{2} when {¬F_{1}}, A_{2} terminates F_{1}},

{A_{2} happens-at 7, A_{1} happens-at 8}⟩

What qualifies as a ‘reasonable’ preference criterion among hc-explanations? In practice such a criterion will probably be domain-specific. Nevertheless, it is interesting to speculate at an abstract level, if only to discover the complexity of some of the issues involved. A simple or liberal view (in the sense that it would allow a wide class of optimal hc-explanations) would be to prefer hc-explanation ϵ over hc-explanation ϵ′ only if ϵ’s set of c-propositions was strictly contained in ϵ′’s. However, this policy would not yield any preferences between the three hc-explanations in Example 4.2 above. Regarding D_{ex} as representing three observations at different time points, it seems reasonable that we should prefer explanations which account for the observed change in F_{2} but allow F_{1} to persist. This would, for example, cut out explanation (3) above. The use of E to describe the process of learning new c-propositions from such sets of observations is the subject of further investigation.

5. PROJECTION DOMAIN DESCRIPTIONS

In the following two sections, and again in Section 8, we focus attention on a particular sub-class of languages and domain descriptions, which we will call the class of projection languages and the class of projection domain descriptions respectively^{7}. We have three reasons for doing so. In this section, we will show that it is possible to state syntactically verifiable conditions under which projection domain descriptions are consistent. In Section 6 we will show how we can use projection domain descriptions to formulate a notion of explanation complementary to that of Section 4. And in Section 8 we will show how for a particular class of domains we can build on this idea to develop meta-level Prolog implementations which facilitate a ‘complete’ form of automated reasoning both backwards and forwards in time.

The defining characteristic of a projection language is that the set of time points includes a null or least element, which is given a special status as regards formulation of projection domain descriptions.

Definition 5.1. [Projection Language] A projection language is a domain language ⟨Π, ⪯, Δ, Φ⟩, where Π includes an element T_{0} (a null or least element) such that for all T ∈ Π, T_{0} ⪯ T.

In this section and the next, we assume that E = ⟨Π, ⪯, Δ, Φ⟩ is a projection language, and that T_{0} is the null element of Π. It will be convenient to identify a particular type of t-proposition which we will call an i-proposition (“i” for “initial”).

Definition 5.2. [i-proposition] An i-proposition in E is a t-proposition of the form

L holds-at T_{0}

where L is a fluent literal of E. We shall sometimes write this expression as

initially L Definition 5.3. [Projection domain description] A projection domain description in

7Note that the class of Situation-Calculus-style languages of the form ⟨Π_{Δ}, ≤_{Δ}, Δ, Φ⟩ defined in Proposition 3.1 of Section 3 are all examples of projection languages.

E is a triple ⟨γ, η, τ_{i}⟩, where γ is a set of c-propositions, η is a set of h-propositions, and τ_{i} is a set of i-propositions in E.

Thus projection domain descriptions are domain descriptions that only allow t-propositions about the initial time point T_{0}.

Example 5.1. The following projection domain description uses the projection domain language E_{ys} = ⟨ℜ^{+}, ≤, {Shoot}, {Alive, Loaded}⟩ of Example 2.2, where ℜ^{+} signifies the non-negative real numbers (so that T_{0} = 0).

Shoot terminates Alive when {Loaded}
Shoot happens-at 2
initially Alive
initially Loaded

At first sight it appears that the restriction of the set τ_{i} in the definition above to contain only i-propositions is a major limitation. However, in Section 6 we will describe a mode of reasoning involving both projection domain descriptions and extra sets of t-propositions which have been identified as ‘observations’ requiring explanation.

As stated above, one advantage of projection domains is that it is possible to characterise a whole class of such domains whose consistency can be easily verified. To state the appropriate proposition, we first need some extra definitions.

Definition 5.4. [Initial consistency] Let D = ⟨γ, η, τ_{i}⟩ be a projection domain description. D is initially-consistent iff there is no fluent constant F such that both the i-proposition “initially F ” and the i-proposition “initially ¬F ” are in τ_{i}.

The next definition is related to the notion of “e-consistency” defined by Denecker and De Schreye [11] in the context of the Language A.

Definition 5.5. [Conflicting actions] Let D be a domain description. The action constants A_{1} and A_{2} conflict in D iff D contains two c-propositions of the form “A_{1} initiates F when C_{1}” and “A_{2} terminates F when C_{2}” and there is no fluent symbol F′ in E such that both F′ ∈ C_{1} ∪ C_{2} and ¬F′ ∈ C_{1} ∪ C_{2}. When A_{1} = A_{2} = A we say that the action constant A self-conflicts in D.

Definition 5.6. [Fluent independence] Let D be a projection domain description. D is fluent-independent iff (i) there is no time point t and pair of h-propositions in D of the form “A_{1} happens-at t” and “A_{2} happens-at t” such that A_{1} and A_{2} conflict in D, and (ii) there is no h-proposition in D of the form “A happens-at t” such that A self-conflicts in D.

Definition 5.7. [Non-convergence] Let D be a domain description written in a language E = ⟨Π, ⪯, Δ, Φ⟩. D and E are non-converging iff for every three (not necessarily distinct) time points T_{1}, T_{2} and T_{3} in Π such that T_{1} ⪯ T_{3} and T_{2} ⪯ T_{3}, then either T_{1} ⪯ T_{2} or T_{2} ⪯ T_{1}.

Proposition 5.1. Let D be a projection domain description which is occurrencesparse, non-converging, initially-consistent, and fluent-independent. Then D is consistent.

Proof. See Appendix B.2.

6. OBSERVATIONS AND EXPLANATIONS

In Section 4 we linked the notion of an explanation to the idea of transforming an inconsistent domain description into a consistent one. Another aspect of explanation that we might want to capture in the context of temporal domains is to explain what holds at a later time in terms of what holds at an earlier time. For example, we might wish to consider the statement “Fred is not alive” as explained by the statement “the gun was loaded when he was shot”. This is an explanation of what holds at a later time in terms of what holds at an earlier time.

In this section we consider only a special case of this type of explanation, which arises specifically in the case of projection domain descriptions. We will regard information about what holds at the least time point T_{0} of a projection domain description as a potential explanation for observations about what holds at all later times. In doing so, we are implicitly according i-propositions a special status among t-propositions – rather than recording ‘observations’, i-propositions are here regarded as statements about what was true ‘in the beginning’ or ‘originally’ (implicitly, before anyone was around to start recording observations or performing actions). Other t-propositions are re-introduced not simply as additional statements of the domain description, but as observations that need to be explained (in terms of what was originally true and/or in terms of events that have occurred).

Definition 6.1. [o-proposition] An o-proposition in E is a t-proposition of the form

L holds-at T

where T ≠ T_{0}.

Definition 6.2. [Observation set] An observation set is a non-empty set of opropositions.

Definition 6.3. [i-explanation] Let D = ⟨γ, η, τ_{i}⟩ be a projection domain description and let τ_{ob} be an observation set. An i-explanation for τ_{ob} in D is a set τ_{iϵ} of i-propositions such that ⟨γ, η, τ_{i} ∪τ_{iϵ}⟩ is consistent and such that for each p ∈ τ_{ob},

⟨γ, η, τ_{i} ∪ τ_{iϵ}⟩ ⊧ p

For simplicity, and in contrast to the discussion of Section 4, we do not include here any definition of preference between i-explanations, or any definition of optimality of an i-explanation. Our motivation for defining ‘i-entailment’ below is simply to maintain the distinction between observations and other aspects of the domain theory while allowing conclusions arising from observations to be properly characterised. As with h-entailment, we are concerned with capturing a ‘safe’ form of inference – in terms of abduction, we want to i-entailment to correspond to ‘entailment in all abductive extensions’.

It is important to point out, however, that for specific domains we might well wish to introduce a definition of preference among i-explanations, and build this into the definition of i-entailment in exactly the same way as h-preference is incorporated in the definition of h-entailment. For example, given the observation that “the car didn’t start after the ignition was turned”, we might prefer the explanations that “the battery was dead” or that “the car had no petrol” to the explanation that “the car had no engine”.

Definition 6.4. [i-model] Let D = ⟨γ, η, τ_{i}⟩ be a projection domain description and let τ_{ob} be an observation set. H is an i-model of D with τ_{ob} iff there exists an i-explanation τ_{iϵ} for τ_{ob} in D such that H is a model of ⟨γ, η, τ_{i} ∪ τ_{iϵ}⟩.

Definition 6.5. [i-consistency] Let D be a projection domain description and let τ_{ob} be an observation set. D is i-consistent with τ_{ob} iff there is at least one i-model of D with τ_{ob}.

Definition 6.6. [i-entailment] Let D be a projection domain description and let τ_{ob} be an observation set. D with τ_{ob} i-entails the t-proposition “F holds-at T ”, written “D, τ_{ob} ⊧_{i} F holds-at T ”, iff for every i-model H of D with τ_{ob}, H(F, T) = true. D with τ_{ob} i-entails the t-proposition “¬F holds-at T ” iff for every i-model H of D with τ_{ob}, H(F, T) = false.

The following proposition shows that the particular definition of i-entailment above amounts to a re-characterisation of entailment as defined in Section 2, keeping the distinction between observation sets and projection domain descriptions. Note, however, that the proposition would not necessarily hold if we were to incorporate a (domain-specific) notion of i-preference in the definitions above.

Proposition 6.1. Let D = ⟨γ, η, τ_{i}⟩ be an occurrence-sparse projection domain description and let τ_{ob} be an observation set. Then H is a model of ⟨γ, η, τ_{i} ∪ τ_{ob}⟩ if and only if H is an i-model of D with τ_{ob}.

Proof. See Appendix B.3

Example 6.1. Let E_{ysp} = ⟨ℜ^{+}, ≤, {Shoot}, {Alive, Loaded}⟩, where ℜ^{+} signifies the non-negative real numbers, and let the projection description D_{ysp} consist of a single c-proposition and a single h-proposition:

Shoot terminates Alive when {Loaded}
Shoot happens-at 2

Let τ_{ysp} be the observation set containing the following two o-propositions:

Alive holds-at 1
¬Alive holds-at 3

It is easy to see that there is a unique i-explanation for τ_{ysp} in D_{ysp}:

{ initially Loaded, initially Alive }

Hence for all n ≥ 0

D_{ysp}, τ_{ysp} ⊧_{i} Loaded holds-at n

The notions of i-explanation and h-explanation described in this section and in Section 4 are complementary and can be combined in an obvious way.

Definition 6.7. [ih-explanation] Let D = ⟨γ, η, τ_{i}⟩ be a projection domain description and let τ_{ob} be an observation set. An ih-explanation for τ_{ob} in D is a pair ⟨η_{ϵ}, τ_{iϵ}⟩, where η_{ϵ} is an occurrence-sparse set of h-propositions and τ_{iϵ} is a set of i-propositions, such that ⟨γ, η ∪ η_{ϵ}, τ_{i} ∪ τ_{iϵ}⟩ is consistent and such that for each p ∈ τ_{ob},

⟨γ, η ∪ η_{ϵ}, τ_{i} ∪ τ_{iϵ}⟩ ⊧ p

However, it is less obvious when one ih-explanation should be considered preferable to another. To conclude this section, we compare two preference relations for ih-explanations, both of which might be reasonable for particular classes of domains. We illustrate their different effects with an example. The following discussion lends further weight to the viewpoint that, although the object level semantics of Section 2 is domain-independent, decisions as to which explanations for inconsistent domains or for sets of observations should be preferred will, in general, be based partly on consideration of the specific domain.

The first preference relation we consider is as follows. It compares only the h-propositions in two given ih-explanations.

Definition 6.8. [Preferable ih-explanation] Let ϵ = ⟨η_{ϵ}, τ_{iϵ}⟩ and ϵ′ = ⟨η′_{ϵ}, τ′_{iϵ}⟩ be ih-explanations for τ_{ob} in D. ϵ is ih-preferable to ϵ′ iff η_{ϵ} ⊂ η′_{ϵ}.

Definition 6.9. [Optimal ih-explanation] ϵ is an optimal ih-explanation for τ_{ob} in D iff ϵ is an ih-explanation for τ_{ob} in D and there is no other ih-explanation ϵ′ for τ_{ob} in D such that ϵ′ is ih-preferable to ϵ.

Definition 6.10. [ih-model] Let D = ⟨γ, η, τ_{i}⟩ be a projection domain description and let τ_{ob} be an observation set. H is an ih-model of D with τ_{ob} iff there exists an optimal ih-explanation ϵ = ⟨η_{ϵ}, τ_{iϵ}⟩ for τ_{ob} in D such that H is a model of ⟨γ, η ∪ η_{ϵ}, τ_{i} ∪ τ_{iϵ}⟩

Definition 6.11. [ih-entailment] Let D be a projection domain description and let τ_{ob} be an observation set. D with τ_{ob} ih-entails the t-proposition “F holds-at T ”, written “D, τ_{ob} ⊧_{ih} F holds-at T ”, iff for every ih-model H of D with τ_{ob}, H(F, T) = true. D with τ_{ob} ih-entails the t-proposition “¬F holds-at T ” iff for every ih-model H of D with τ_{ob}, H(F, T) = false.

Example 6.2. This example involves a video-recorder with an automatic timer. Suppose Fred returns home one evening and wishes to check if his video-recorder has automatically started recording his favourite TV show. Although he cannot look inside the recording machine to check if it is recording directly, he knows that if the machine is working, when the timer triggers it will both turn the ‘record’ light on and begin recording. Fred also knows that if the machine is not working it can be repaired. When Fred left home, the record light was not on. When he returns, the light is on, and Fred concludes that the machine is recording.

We can represent Fred’s domain knowledge with a projection domain description D_{rec} consisting of three c-propositions:

T imerT rigger initiates LightOn when {W orking}
T imerT rigger initiates Recording when {W orking}
Repair initiates W orking

Fred’s observations, that the recording light was of when he left home but is on when he returns, are represented by the observation set τ_{rec}:

{¬LightOn holds-at T_{L}, LightOn holds-at T_{R}}

where T_{L}, T_{R} ∈ Π represent the times at which Fred left and returned home respectively. It is easy to see that all optimal ih-explanations for τ_{rec} in D_{rec} are of the form

⟨{T imerT rigger happens-at T },
{initially W orking, initially ¬LightOn}⟩

for some T ∈ Π such that T_{L} ⪯ T ≺ T_{R}, so that

D_{rec}, τ_{rec} ⊧_{ih} Recording holds-at T_{R}

and hence the notion of ih-entailment correctly models Fred’s reasoning in this respect.

In the example above, Fred can also use ih-entailment to reason that his videorecorder was functioning properly at time T_{L} (and indeed at any time point whatsoever), i.e.

D_{rec}, τ_{rec} ⊧_{ih} W orking holds-at T_{L}

In doing so, Fred rejects ih-explanations in which an extra Repair action occurs at some time before the T imerT rigger action. It is a matter of debate as to whether, for this domain, it is reasonable to do this. But it is not hard to formulate an alternative preference criterion among ih-explanations which does not cause such alternatives to be rejected:

Definition 6.12. [\overline{Preferable} ih-explanation] Let ϵ = ⟨η_{ϵ}, τ_{iϵ}⟩ and ϵ′ = ⟨η′_{ϵ}, τ′_{iϵ}⟩ be ih-explanations for τ_{ob} in D. ϵ is \overline{ih}-preferable to ϵ′ iff η_{ϵ} ⊂ η′_{ϵ} and τ_{iϵ} = τ′_{iϵ}.

In other words, explanations are only “\overline{ih}-comparable” if they contain the same i-propositions. Assuming definitions exactly analogous to Definitions 6.9, 6.10 and 6.11 for an optimal \overline{ih}-explanation, an \overline{ih}-model, and \overline{ih}-entailment respectively, it is easy to see that all optimal ih-explanations are also optimal \overline{ih}-explanations, but that (for the example above) optimal \overline{ih}-explanations can also be of the form

⟨{Repair happens-at T′, T imerT rigger happens-at T },
{initially ¬W orking, initially ¬LightOn}⟩

for some T′, T ∈ Π such that T_{L} ⪯ T ≺ T_{R} and T′ ≺ T. Hence, although (as for ih-entailment)

D_{rec}, τ_{rec} ⊧\overline{ih} Recording holds-at T_{R}

Fred cannot use \overline{ih}-entailment to conclude that his video-recorder was working when he left the house.

It is not hard to think up examples either where ih-entailment or where \overline{ih}- entailment seems more plausible. The choice seems to depend on whether (for the particular domain) one is more concerned with assuming as few action occurrences as possible (ih-entailment), or whether one is more concerned with giving equal consideration to all possible initial conditions, even in the face of observations at later times (\overline{ih}-entailment).

7. LOGIC PROGRAMS FOR E DOMAINS

In the following two sections we discuss the implementation of Language E domains. In this section we study how we can construct Event Calculus style logic programs from domain descriptions in general. In Section 8 we show how, for a class of projection domain descriptions, (simplified versions of) these programs can be enhanced using standard Prolog ‘second-order’ programming techniques.

In the original Event Calculus there was an implicit assumption that all predicate definitions were complete. In other words, it was assumed that for each predicate its negation (negation as failure) was true whenever the positive instance did not hold. Although the semantics of E incorporates an analogous assumption for hpropositions and c-propositions, this assumption does not extend to t-propositions (equivalent to Holds or HoldsAt literals in Event Calculus programs) – it is possible for a domain description D to be ‘incomplete’ in the sense that, for some fluent constant F and time T, neither “F holds-at T ” nor “¬F holds-at T ” is entailed by D.

However, we can partly avoid the implementation difficulties that this creates by representing negative fluent literals inside the HoldsAt predicate. In the program translations defined below, the t-proposition “¬F holds-at T ” is represented by the positive literal HoldsAt(Neg(F), T), whereas the negative literal not HoldsAt(F, T) is simply interpreted as ‘the t-proposition “F holds-at T ” is not provable’. In this and other respects, the translation method here is similar to that in [30]. Analogous techniques are used in [16], [14] and [4], although not with Event Calculus style programs.

Given that our aim is to develop programs able to deal correctly with the form of incompleteness described above, it is useful to first consider incomplete or partial interpretations for a domain description and examine what can be computed from these.

Definition 7.1. [Partial interpretation] A partial interpretation of E is a partial mapping

I : Φ × Π ↦ {true, false}

In the discussion which follows, we assume that Definitions 2.8 and 2.9 of ‘point satisfaction’ and an ‘initiation’ or ‘termination point’ are extended to cover partial interpretations as well as interpretations. In addition, we need counterparts to these notions which deal with cases where I(F, T) is undefined.

Definition 7.2. [Possible point satisfaction] Given a set of fluent literals C of E and a time point T ∈ Π, a partial interpretation I possibly satisfies C at T iff for each fluent constant F ∈ C, I(F, T) ≠ false, and for each fluent constant F′ such that ¬F′ ∈ C, I(F′, T) ≠ true.

Definition 7.3. [Possible initiation/termination point] Let I be a partial interpretation of E, let D be a domain description, let F ∈ Φ and let T ∈ Π. T is a possible initiation-point (respectively possible termination-point) for F in I relative to D iff there is an A ∈ Δ such that (i) there is both an h-proposition in η of the form “A happens-at T ” and a c-proposition in γ of the form “A initiates F when C” (respectively “A terminates F when C”) and (ii) I possibly satisfies C at T.

Let us denote the set of all partial interpretations by I. Motivated by Definition 2.10 of a model for a domain D, we can define an associated (partial) operator on I as follows.

Definition 7.4. [Operator F] Given a domain description D = ⟨γ, η, τ⟩ the partial operator F : I ↦ I is defined as follows: For any partial interpretation I ∈ I, and any F ∈ Φ, T ∈ Π,

1. (a) For any T_{1} ∈ Π such that T_{1} ≺ T, if there is no possible initiationpoint or possible termination-point T_{2} for F in I relative to D such that T_{1} ⪯ T_{2} ≺ T, then (F)(I)(F, T) = I(F, T_{1}).

(b) For any T_{2} ∈ Π such that T ≺ T_{2}, if there is no possible initiationpoint or possible termination-point T_{1} for F in I relative to D such that T ⪯ T_{1} ≺ T_{2}, then (F)(I)(F, T) = I(F, T_{2}).

2. If T_{1} is an initiation-point for F in I relative to D, T_{1} ≺ T and there is no possible termination-point T_{2} for F in I relative to D such that T_{1} ≺ T_{2} ≺ T, then (F)(I)(F, T) = true.

3. If T_{1} is a termination-point for F in I relative to D, T_{1} ≺ T and there is no possible initiation-point T_{2} for F in I relative to D such that T_{1} ≺ T_{2} ≺ T, then (F)(I)(F, T) = false.

4. If there is a t-proposition in τ of the form “F holds-at T ”, then

(F)(I)(F, T) = true,

and if there is a t-proposition of the form “¬F holds-at T ”,

(F)(I)(F, T) = false.

5. Otherwise (F)(I)(F, T) is undefined.

Note that this operator is not always defined, as it is possible for these rules to require the assignment of both true and false to (F)(I)(F, T) for some F and T.

It is easy to see that conditions (1) to (4) in the definition above correspond closely to conditions (1) to (4) of Definition 2.10 of a model. The following definition and three propositions show the relationship between Language E models and the operator F.

Definition 7.5. [The ordering ⊆] For any two partial interpretations I_{1}, I_{2} ∈ I, I_{1} is contained in I_{2}, written I_{1} ⊆ I_{2}, iff (i) for any F and T if I_{1}(F, T) = true then I_{2}(F, T) = true, and (ii) if I_{1}(F, T) = false then I_{2}(F, T) = false.

Proposition 7.1. Let D be a domain description. If D is consistent then any model H of D is a greatest (with respect to the ordering ⊆) fixed point of F.

Proof. The proof follows directly from the construction of F and the observation that since H is a total mapping the definition for possible initiation-point (respectively possible termination-point) coincides with that of initiation-point (respectively termination-point).

When a domain D is consistent we can apply the operator F iteratively to compute a partial interpretation that would be a subset of any model of D.

Proposition 7.2. Let D be a consistent domain description, let H be a model of D and let I be a partial interpretation such that I ⊆ H. Then F(I) ⊆ H.

Proof. The proof follows by comparing the different cases under which F applies with conditions (1)–(4) in Definition 2.10 of a model, and noticing that the following two properties hold for every T ∈ Π and F ∈ Φ: (i) if T is an initiation-point (resp. termination-point) for F in I then T is an initiation-point (resp. termination-point) for F in H and (ii) if T is not a possible initiation-point (resp. possible termination-point) for F in I then T is not an initiation-point (resp. termination-point) for F in H.

Proposition 7.3. Let D be a consistent domain description and let the sequence I_{0}, …, I_{n}, … of partial interpretations be defined as follows:

• I_{0} = ∅

• I_{n+1} = I_{n} ∪ F(I_{n}) for each countable ordinal n > 0.

Then there exists a least fixed point I^{+} of this sequence, and D entails any tproposition of the form “F holds-at T ” (resp. “¬F holds-at T ”) such that I^{+}(F, T) = true (resp. I^{+}(F, T) = false).

Proof. By Proposition 7.2 when D is consistent this sequence is well defined. Also, by construction the sequence is monotonic (with respect to the ordering ⊆ of Definition 7.5) and hence the least fixed point I^{+} exists. Again by Proposition 7.2 I^{+} ⊆ H for any model H of D and hence the result follows.

Given Proposition 7.3, we can use Definition 7.4 to ‘read off’ a logic program that implements F and computes consequences belonging to I^{+}. To simplify our definitions we assume that some logic program or external definition of the order relation ⪯ is available.

Definition 7.6. [Ordering program] Given the language E = ⟨Π, ⪯, Δ, Φ⟩, the programP (Π, ⪯) is an ordering program for E iff

• for all T, T′ ∈ Π, P (Π, ⪯) succeeds on the query T ⪯ T′ if and only if T ⪯ T′, and finitely fails otherwise.

• for all T, T′ ∈ Π, P (Π, ⪯) succeeds on the query T ≺ T′ if and only if T ≺ T′, and finitely fails otherwise.

• None of the following predicate symbols appear in P (Π, ⪯):

HoldsAt, Given, ClippedBetween, HappensAt, PossiblyInitiates, Initiates, PossiblyTerminates, Terminates, AffectedBetween.

We will also need the following preliminary definitions.

Definition 7.7. [lp-term and lp-complement] Given a fluent literal L of E = ⟨Π, ⪯, Δ, Φ⟩, the lp-term of L, written λ(L), is defined to be

• Pos(F) if L = F for some F ∈ Φ

• Neg(F) if L = ¬F for some F ∈ Φ

and the lp-complement of L, written \overline{λ(L)}, is defined to be

• Neg(F) if L = F for some F ∈ Φ

• Pos(F) if L = ¬F for some F ∈ Φ

Definition 7.8. [Finite domain description] The domain description ⟨γ, η, τ⟩ is finite iff γ, η and τ are all finite, and for each c-proposition in γ either of the form “A initiates F when C” or of the form “A terminates F when C”, C is also finite.

Our translation from domain descriptions to logic programs can now be given. In the definition below, the five clauses defining HoldsAt correspond to rules (1a)– (4) in Definition 7.4 of the operator F (Clauses (LP1a) and (LP1b) are ‘special cases’ of rules (1a) and (1b)). The use of negation-as-failure and fluent converses in the domain-specific clauses defining the predicates PossiblyInitiates and PossiblyTerminates reflects Definition 7.3 of a possible initiation and possible termination point.

Definition 7.9. [LP [D, P (Π, ⪯)]] Given a finite domain description D = ⟨γ, η, τ⟩ written in the language E = ⟨Π, ⪯, Δ, Φ⟩, and an ordering program P (Π, ⪯), the logic program LP [D, P (Π, ⪯)] is defined as the program P (Π, ⪯) augmented

\overline{26}

with the following general clauses

\begin{matrix}HoldsAt(l, t_{3}) ← & (LP1a) \\ Given(l, t_{1}), t_{1} ≺ t_{3}, not AffectedBetween(t_{1}, l, t_{3}). \end{matrix}

\begin{matrix}HoldsAt(l, t_{1}) ← & (LP1b) \\ Given(l, t_{3}), t_{1} ≺ t_{3}, not AffectedBetween(t_{1}, l, t_{3}). \end{matrix}

HoldsAt(Pos(f), t_{3}) ←  (LP2)

HappensAt(a, t_{1}), t_{1} ≺ t_{3}, Initiates(a, f, t_{1}), not ClippedBetween(t_{1}, Pos(f), t_{3}).

HoldsAt(Neg(f), t_{3}) ←  (LP3)

HappensAt(a, t_{1}), t_{1} ≺ t_{3}, Terminates(a, f, t_{1}), not ClippedBetween(t_{1}, Neg(f), t_{3}).

HoldsAt(l, t) ← Given(l, t).  (LP4)
ClippedBetween(t_{1}, Pos(f), t_{3}) ←  (LP5)

HappensAt(a, t_{2}), t_{1} ⪯ t_{2}, t_{2} ≺ t_{3}, PossiblyTerminates(a, f, t_{2}).

ClippedBetween(t_{1}, Neg(f), t_{3}) ←  (LP6)

HappensAt(a, t_{2}), t_{1} ⪯ t_{2}, t_{2} ≺ t_{3}, PossiblyInitiates(a, f, t_{2}).

AffectedBetween(t_{1}, l, t_{3}) ← ClippedBetween(t_{1}, l, t_{3}).  (LP7)

\begin{matrix}AffectedBetween(t_{1}, Neg(f), t_{3}) ← & (LP8) \\ ClippedBetween(t_{1}, Pos(f), t_{3}). \end{matrix}

\begin{matrix}AffectedBetween(t_{1}, Pos(f), t_{3}) ← & (LP9) \\ ClippedBetween(t_{1}, Neg(f), t_{3}). \end{matrix}

and the following domain-specific clauses

• For each t-proposition “L holds-at T ” in τ, the clause Given(λ(L), T).

• For each h-proposition “A happens-at T ” in η, the clause HappensAt(A, T).

• For each c-proposition “A initiates F when {L_{1}, …, L_{n}}” in γ, the clause

\begin{matrix}Initiates(A, F, t) ← \\ HoldsAt(λ(L_{1}), t), …, HoldsAt(λ(L_{n}), t). \end{matrix}

and the clause

\begin{matrix}PossiblyInitiates(A, F, t) ← \\ not HoldsAt(\overline{λ(L_{1})}, t), …, not HoldsAt(\overline{λ(L_{n})}, t). \end{matrix}

• For each c-proposition “A terminates F when {L_{1}, …, L_{n}}” in γ, the clause

\begin{matrix}Terminates(A, F, t) ← \\ HoldsAt(λ(L_{1}), t), …, HoldsAt(λ(L_{n}), t). \end{matrix}

and the clause

\begin{matrix}PossiblyTerminates(A, F, t) ← \\ not HoldsAt(\overline{λ(L_{1})}, t), …, not HoldsAt(\overline{λ(L_{n})}, t). \end{matrix}

Intuitively, given Propositions 7.1, 7.2 and 7.3 it is easy to see that the programs described above behave correctly for consistent domain descriptions, since Clauses (LP1a)–(LP4) either correspond exactly to or are just special cases of conditions (1a)–(4) in Definition 7.4. The following proposition^{8}confirms this intuition.

Proposition 7.4. Let P (Π, ⪯) be an ordering program for E, and let D be a finite domain description. Then for any fluent literal L of E and any T ∈ Π, if

LP [D, P (Π, ⪯)] ⊢_{SLDNF} HoldsAt(λ(L), T)

then

D ⊧ L holds-at T

Proof. See Appendix B.4

To a certain extent, the above logic programs overcome the two limitations of formalizations of action in normal logic programming identified by Gelfond and Lifschitz in [16]. That is to say, (i) if the values of some fluents at one or more time points are given, they facilitate automated reasoning about what holds at other time points before, afterwards or in between, and (ii) as shown by Proposition 7.4, the programs behave correctly even when the information entailed by their Language E specifications is incomplete.

However, although they are sound, the above logic programs do not compute all consequences of every domain under its semantics as given by Definition 2.10. This potential incompleteness is illustrated by the following example.

8In this and subsequent propositions, the symbol ⊢_{SLDNF} signifies the existence of an SLDNF derivation, defined as for example in [28]. However, for clarity of presentation, in proposition proofs we avoid working directly with this type of definition, and instead refer to SLDNF derivations using the usual (Prolog) programming terminology.

Example 7.1. Let E_{v} and D_{v} be the domain language and domain description respectively of Example 2.1, and suppose that P (ℜ, ≤) is an ordering program for E_{v}. Then the logic program LP [D_{v}, P (ℜ, ≤)] consists of the program P (ℜ, ≤) together with clauses (LP1a)–(LP9) of Definition 7.9 and the domain-specific clauses

\begin{matrix}Initiates(InjectA, P rotected, t) ← \\ HoldsAt(Pos(T ypeO), t). \end{matrix}

\begin{matrix}PossiblyInitiates(InjectA, P rotected, t) ← \\ not HoldsAt(Neg(T ypeO), t). \end{matrix}

\begin{matrix}Initiates(InjectB, P rotected, t) ← \\ HoldsAt(Neg(T ypeO), t). \end{matrix}

\begin{matrix}PossiblyInitiates(InjectB, P rotected, t) ← \\ not HoldsAt(Pos(T ypeO), t). \end{matrix}

HappensAt(InjectA, 2).

HappensAt(InjectB, 3).

Given(Neg(P rotected), 1).

As it stands, the query HoldsAt(Pos(P rotected), 4) will fail on this program even though the corresponding t-proposition is entailed by its specification. Notice however that the query can be made to succeed by adding either Given(Pos(T ypeO), n) or Given(Neg(T ypeO), n) to the program for some time point n < 2. The example also illustrates the necessity of using the PossiblyInitiates and PossiblyTerminates predicates. Had the program definition of ClippedBetween been given simply in terms of Initiates and Terminates, the query HoldsAt(Neg(P rotected), 4) would succeed, even though the t-proposition “¬P rotected holds-at 4” is not entailed by D_{v}. Finally, notice that the success of the goal HoldsAt(Neg(P rotected), 0) (trivially) demonstrates the utility of this type of program for reasoning backwards in time.

8. META-LEVEL PROGRAMS FOR COMPUTING I-ENTAILMENT

In this section we show how, for a class of domains, we can exploit the meta-level characterisation of i-entailment given in Section 6 to build meta-level programs which facilitate a more ‘complete’ form of reasoning (both backwards and forwards in time) than the object-level programs of the previous section. The important characteristic of the programs given below is that they maintain the distinction between observations, which are dealt with at the meta-level, and other parts of the domain theory.

The object-level programs upon which our meta-level implementation is built are simplified versions of the programs described in Section 7. The simplification is possible because of the following property of projection domain descriptions. If D is a projection domain description which contains either the i-proposition “initially F ” or the i-proposition “initially ¬F ” for every fluent constant F, then D is ‘complete’ in the sense that it has at most one model (this follows from Proposition 2.1). If E is non-converging, and D is fluent-independent, D has exactly one model (this follows from Proposition 5.1). Hence, in the case where D is also finite (so that there are only a finite number of fluent constants in E), it is not hard to construct a simplified Event Calculus style program for D enabling complete automated reasoning forwards in time from the initial time point T_{0}. For reasons which will shortly become apparent, we will represent the (‘complete’ set of) i-propositions of D in list form inside a three-argument version of the HoldsAt predicate, rather than with a Given predicate as previously. In Definition 8.2 below, HoldsAt(M, L, T) should be read as “D ⊧ L holds-at T, where M is (a list representation of) the set of i-propositions in D”.

It is easy to see that clauses (EC7)–(EC11) which define HoldsAt are a simplification of clauses (LP1a)–(LP9) in Definition 7.9. Here it is not necessary to distinguish between the predicates Initiates (resp. Terminates) and PossiblyInitiates (resp. PossiblyTerminates), and clauses (LP1a), (LP1b) and (LP4) can be condensed into the single clause (EC7). This is because, at the (object) level of calls to the HoldsAt predicate, complete information is available about what holds at the initial time point T_{0}, and we are only interested in reasoning forwards in time from this point. Incompleteness and reasoning backwards in time are instead dealt with at the meta-level.

We wish to construct a program able to test whether a particular t-proposition is i-entailed by some projection domain description D′ (which, unlike D above, may not have an i-proposition for each fluent) together with some observation set τ_{ob}. All that remains to be done is to define a meta-level program able to use the HoldsAt predicate to test the truth of the t-proposition in each extension of D′ with a ‘maximal’ i-explanation for τ_{ob}. (It is sufficient to consider only maximal i-explanations, i.e. those which mention every fluent in the language, because of the monotonicity of E as regards addition of t-propositions to any domain description – see the remarks at the end of Section 2.) This is achieved in a straightforward way by clauses (EC1)–(EC6) in Definition 8.2 below. In this definition, IHoldsAt(L, T) should be read as “D′, τ_{ob} ⊧_{i} L holds-at T ”. IExplanation(M) should be read as “M is a (maximal) i-explanation for τ_{ob} in D′”.

In Definition 8.2, a Prolog-like syntax for lists is used. Thus the term [] represents the empty list and the term [Head|Remainder] represents a non-empty list whose first element is Head. Suitable definitions of the standard list predicates Member and Append are assumed. The two meta-level (or ‘second-order’) predicates Setof and F orall are also used. To summarise their functions, F orall(Condition, Goal) succeeds if for all solutions of Condition, Goal succeeds. Setof(X, Goal, Instances) succeeds if Instances is the set of instances of X for which Goal succeeds, where sets are represented as (possibly empty) lists without repetitions. For practical details of the use of these predicates in the context of Prolog programming, the reader may consult [42]. (It is also assumed that the predicates IHoldsAt, IExplanation, P ermutation, and ConsistentW ithObservations do not appear in the ordering program P (Π, ⪯).)

Definition 8.1. The domain language E = ⟨Π, ⪯, Δ, Φ⟩ is fluent-finite iff the set Φ is finite.

Definition 8.2. [EC[D, τ_{ob}, P (Π, ⪯)]] Let D = ⟨γ, η, τ⟩ be a finite projection domain description written in a fluentfinite projection language E = ⟨Π, ⪯, Δ, Φ⟩. Let T_{0} be the null element of Π, and let P (Π, ⪯) be an ordering program for E. Let τ_{ob} be a finite observation set. The logic program EC[D, τ_{ob}, P (Π, ⪯)] is defined as the program P (Π, ⪯) augmented with the following general clauses

\begin{matrix}IHoldsAt(l, t) ← & (EC1) \\ F orall(IExplanation(m), HoldsAt(m, l, t)). \end{matrix}

IExplanation(m) ←  (EC2)

Setof(l, (Initially(l)), i),

Setof(f, (F luent(f), not Initially(Pos(f)), not Initially(Neg(f))),

p),

P ermutation(p, c), Append(c, i, m), ConsistentW ithObservations(m).

P ermutation([], []).  (EC3)
P ermutation([f|r1], [f|r2]) ← P ermutation(r1, r2).  (EC4)
P ermutation([f|r1], [Neg(f)|r2]) ← P ermutation(r1, r2).  (EC5)

\begin{matrix}ConsistentW ithObservations(m) ← & (EC6) \\ F orall(Observation(l, t), HoldsAt(m, l, t)). \end{matrix}

\begin{matrix}HoldsAt(m, l, t_{3}) ← & (EC7) \\ Member(l, m), not ClippedBetween(m, T_{0}, l, t_{3}). \end{matrix}

HoldsAt(m, Pos(f), t_{3}) ←  (EC8)
HappensAt(a, t_{1}), t_{1} ≺ t_{3}, Initiates(m, a, f, t_{1}),
not ClippedBetween(m, t_{1}, Pos(f), t_{3}).
HoldsAt(m, Neg(f), t_{3}) ←  (EC9)
HappensAt(a, t_{1}), t_{1} ≺ t_{3}, Terminates(m, a, f, t_{1}),
not ClippedBetween(m, t_{1}, Neg(f), t_{3}).
ClippedBetween(m, t_{1}, Pos(f), t_{3}) ←  (EC10)
HappensAt(a, t_{2}), t_{1} ⪯ t_{2}, t_{2} ≺ t_{3},
Terminates(m, a, f, t_{2}).

ClippedBetween(m, t_{1}, Neg(f), t_{3}) ←  (EC11)
Happens(a, t_{2}), t_{1} ⪯ t_{2}, t_{2} ≺ t_{3},
Initiates(m, a, f, t_{2}).

and the following domain-specific clauses

• For each fluent constant F ∈ ϕ, the clause

F luent(F).

• For each i-proposition “initially L” in τ_{i}, the clause

Initially(λ(L)).

• For each o-proposition “L holds-at T ” in τ_{ob}, the clause

Observation(λ(L), T).

• For each h-proposition “A happens-at T ” in η, the clause

HappensAt(A, T).

• For each c-proposition “A initiates F when {L_{1}, …, L_{n}}” in γ, the clause

\begin{matrix}Initiates(m, A, F, t) ← \\ HoldsAt(m, λ(L_{1}), t), …, HoldsAt(m, λ(L_{n}), t). \end{matrix}

• For each c-proposition “A terminates F when {L_{1}, …, L_{n}}” in γ, the clause

\begin{matrix}Terminates(m, A, F, t) ← \\ HoldsAt(m, λ(L_{1}), t), …, HoldsAt(m, λ(L_{n}), t). \end{matrix}

Example 8.1. Let E_{ysp}, D_{ysp} and τ_{ysp} be the domain language, domain description and observation set respectively of Example 6.1. Let P (ℜ^{+}, ≤) be an ordering program for E_{ysp}. Then the logic program EC[D_{ysp}, τ_{ysp}, P (ℜ^{+}, ≤)] consists of the program P (ℜ^{+}, ≤) together with clauses (EC1)–(EC11) of Definition 8.2 and the domain-specific clauses

Terminates(m, Shoot, Alive, t) ← HoldsAt(m, Pos(Loaded), t).

F luent(Alive).

F luent(Loaded).

Observation(Pos(Alive), 1).

Observation(Neg(Alive), 3).

HappensAt(Shoot, 2).

Although potentially somewhat inefficient, the programs described in Definition 8.2 are of interest because they enable sound derivations^{9}of t-propositions which would not be possible with the object-level logic programs given in the previous section. For example, it is easy to verify, either by inspection or using a Prolog interpreter, that

EC[D_{ysp}, τ_{ysp}, P (ℜ^{+}, ≤)] ⊢_{SLDNF} IHoldsAt(Pos(Loaded), 0)

Indeed, for a wide class of domains they are both sound and ‘complete’, in the sense of Proposition 8.1 below. Since any finite, consistent Language A domain as defined in [16] may be translated directly into a Language E projection domain description together with an observation set (see Section 3), finite A domains may also be given a meta-level implementation of this type^{10}.

Proposition 8.1. Let E = ⟨Π, ⪯, Δ, Φ⟩ be a fluent-finite, non-converging projection language, let P (Π, ⪯) be an ordering program for E, and let D = ⟨γ, η, τ_{i}⟩ be a finite, initially-consistent, fluent-independent projection domain description in E. Let τ_{ob} be a finite observation set. Then for any fluent literal L of E and any T ∈ Π,

EC[D, τ_{ob}, P (Π, ⪯)] ⊢_{SLDNF} IHoldsAt(λ(L), T)

if and only if

D, τ_{ob} ⊧_{i} L holds-at T

Proof. See Appendix B.5

As stated in Proposition 5.1, it is possible to verify the consistency of the class of projection domain descriptions described in Proposition 8.1 by a syntactic check. Note that we can now build on this proposition to check for i-consistency with a given observation set, simply by verifying the success of the unground call IExplanation(m). Finally, the style of the programs described in this section offers some clue as to how we might in principle implement a preference criterion added to the definition if i-entailment, by appropriately extending the program definition of IExplanation.

9In order to continue to refer to ‘SLDNF derivations’, we assume that the meta-level primitives Setof and F orall are appropriately re-interpreted (see [42] for details).

10Strictly speaking, the translation method described in Definition 8.2 is not applicable to the Language A type domain descriptions described in Section 3 Proposition 3.1. This is because the “complete occurrence set” of h-propositions is infinite (see Definition 3.3). But the appropriate modification to Definition 8.2 is trivial, and does not necessitate a significant change to the proof of Proposition 8.1. An example ordering program P (Π_{Δ}, ≤_{Δ}) is given in Appendix C together with the necessary changes to Definition 8.2.

9. CONCLUSIONS AND FURTHER WORK

Following the methodology of the Language A introduced in [16], we have presented a simple declarative language, E, for describing narratives with actions. E is based on a narrative ontology inherited from the Event Calculus, thus demonstrating that this methodology is not limited to the particular ontology of A. E’s semantics is based around a simple characterisation of persistence which facilitates a modular approach to extending the expressivity of the language. This characterisation relies heavily on the notion of a flow of time which is independent from any actions which may occur. The benefits of this become particularly apparent when representing domains where periods of time elapse in which a change may or may not have taken place. It is not necessary to ‘fill in’ time with an artificial ‘action’ such as a ‘W ait’.

The explicit notion of an action occurrence incorporated in E allows an important class of ‘narrative’ explanations (h-explanations) to be characterised in a simple way. These enable us to extend an otherwise inconsistent theory written in E so as to establish consistency, thus providing a natural method, in many cases, to account for conflicting sets of information about the domain. More generally, our formalisation of various notions of explanation within E illustrates that commonsense reasoning need not always be modelled as deduction at a single object level. Our results are built upon much previous work concerning the role of abduction in Artificial Intelligence and related areas. Once again we have demonstrated that reasoning from cause to effect can be modelled at the object level, whereas reasoning from effect to cause can be regarded as an essentially meta-level (for example abductive) activity. In the context of reasoning about action, causation is temporally directed. Hence in our work this distinction manifests itself in the fact that reasoning forwards in time is modelled as object-level deduction, whereas reasoning backwards in time is captured at the meta-level. The success of this approach lends extra weight to a developing consensus (see [8] for a general discussion) that observations should somehow be treated separately from other aspects of theories of action.

We have also shown how domains in E can be implemented in normal logic programming with extended versions of Event Calculus programs that behave correctly even when the knowledge entailed by the domain description is incomplete. These programs have the capability of reasoning backwards as well as forwards in time.

We can envisage at least three areas of future research relating to E. Firstly, in line with the methodology described in our introduction, we could use E as a ‘measuring stick’ to show correspondences between various narrative-based formalisms for reasoning about action, perhaps in the manner of Katha in [21]. Example candidates for comparison are the formalisms in [31], [34], [40] and [41].

Secondly, it would be interesting to investigate different styles of implementation as regards E domains. The approaches followed in this paper are based on a relatively simple use of normal logic programming and standard techniques within this. We could develop a more general implementation for computing entailment or i-entailment using abductive logic programming, building on the work in [10], [11],

[19] and [20]. The ‘abductive flavour’ of our definition of h-entailment suggests that abductive logic programming could be a useful implementation tool here as well.

Thirdly, the expressivity of E could be increased in various ways. We have already briefly indicated how E might be extended to partially deal with ramifications and qualifications (see Appendix A). Since E already allows for actions to occur concurrently within a narrative, it seems likely that the language could also be extended to allow for a theory of cancelling and combined effects of actions similar to that in [4]. It has already been pointed out [10] [12] [33] that a narrative based approach offers alternative ways to model non-deterministic effects of actions, and is a natural setting in which to model continuous change [39] [43] [32] [41]. Finally, we might extend the syntax and semantics of E to deal with incomplete information about the order and timing of action occurrences, perhaps building on the ideas in [10] and [12], and perhaps introducing temporal variables into the language in a manner similar to [5] and [6].

The utility and appeal of specialised declarative languages such as A and E lies in their simplicity. They are of sufficiently ‘high level’ to allow various issues to be aired without immediately becoming involved in technical details, and are perhaps best regarded as useful stepping stones towards the ultimate goal of developing comprehensive formal theories of action using general purpose representational mechanisms. Hence their capacity for retaining their simplicity when extended to cover more complex domains is a crucial measure of their utility.

Acknowledgements

We would particularly like to thank Marc Denecker, Yannis Dimopoulos, David Evans, Alessandro Provetti, Alessandra Russo, Fariba Sadri, Murray Shanahan and Eugenia Ternovskaia for helpful discussions on the topic of this paper, and for careful reading of earlier drafts. Thanks as well to the anonymous referees for their thoughtful and detailed comments, which helped considerably in improving the paper.

REFERENCES

1. James Allen, Towards a General Theory of Action and Time, Artificial Intelligence 23, Elsevier Science Publishers, pages 123-154, 1984.

2. Jonathan Amsterdam, Temporal Reasoning and Narrative Conventions, Proceedings of the 2nd International Conference on Knowledge Representation (KR 91), ed.s J. Allen, R. Fikes and E. Sandewall, Morgan Kaufmann, pages 15–21, 1991.

3. Andrew Baker, Nonmonotonic Reasoning in the Framework of the Situation Calculus, Artificial Intelligence 49, Elsevier Science Publishers, page 5, 1991.

4. Chitta Baral and Michael Gelfond, Representing Concurrent Actions in Extended Logic Programming, Proceedings IJCAI 93, Morgan Kaufmann, page 866, 1993.

5. Chitta Baral, Michael Gelfond and Alessandro Provetti, Representing Actions - I: Laws, Observations and Hypotheses (Short Version), in Working Notes of the AAAI Spring Symposium: Extending Theories of Action - Formal Theory and Practical Applications, Stanford University, California, USA, 1995.

6. Chitta Baral, Michael Gelfond and Alessandro Provetti, Representing Actions: Laws, Observations and Hypotheses, Journal of Logic Programming, Special Issue on Reasoning about Actions (this issue), 1996.

7. Iliano Cervesato, Luca Chittaro and Angelo Montanari, A Modal Calculus of Partially Ordered Events in a Logic Programming Framework, in Proceedings ICLP’95, pages 299-313, 1995.

8. James Crawford and David Etherington, Observations on Observations in Action Theories, in Working Notes of the AAAI Spring Symposium: Extending Theories of Action - Formal Theory and Practical Applications, Stanford University, California, USA, 1995.

9. Ernest Davis, Infinite Loops in Finite Time: Some Observations, Proceedings KR 92 (3rd International Conference on Principles of Knowledge Representation and Reasoning), Cambridge, Massachusetts, ed.s B. Nebel, C. Rich and W. Swartout, Morgan Kaufmann, 1992.

10. Marc Denecker, Lode Missiaen and Maurice Bruynooghe, Temporal Reasoning with Abductive Event Calculus, in Proceedings ECAI 92, Vienna, 1992.

11. Marc Denecker and Danny De Schreye, Reperesenting Incomplete Knowledge in Abductive Logic Programming, in Proceedings of the International Symposium on Logic Programming, 1993.

12. Marc Denecker, Knowledge Representation and Reasoning in Incomplete Logic Programming, PhD thesis, Department of Computer Science, K.U.Leuven, 1993.

13. Marc Denecker, A Terminological Interpretation of (Abductive) Logic Programming, in Proceedings of the Third International Conference on Logic Programming and Non-monotonic Reasoning, Lexington, KY, USA, Springer Verlag, 1995.

14. Phan Minh Dung, Representing Actions in Logic Programming and its Applications in Database Updates, Proceedings of the Tenth International Conference on Logic Programming, ed David S. Warren, MIT Press, pages 222-238, 1993.

15. Kave Eshghi, Abductive Planning with Event Calculus, Proceedings of the 5th International Conference and Symposium on Logic Programming, ed.s Robert Kowalski and Kenneth Bowen, MIT Press, pages 562–579, 1988.

16. Michael Gelfond and Vladimir Lifschitz, Representing Actions in Extended Logic Programming, Proceedings of the Joint International Conference and Symposium on Logic Programming, ed. Krzysztof Apt, MIT Press, page 560, 1992.

17. Michael Gelfond and Vladimir Lifschitz, Representing Action and Change by Logic Programs, Journal of Logic Programming, volume 17 numbers 2, 3 and 4, North-Holland, pages 301-322, 1993.

18. David Harel, Dynamic Logic, In Handbook of Philosophical Logic II: Extensions of Classical Logic, ed.s D. Gabbay and F. Guenther, Reidel, Boston, USA, pages 497-604, 1984.

19. Antonios Kakas and Paolo Mancarella, Generalized Stable Models: a Semantics for Abduction. Proceedings of the 9th European Conference on Artificial Intelligence, Stockholm, ed. L. Aiello, pages 385-391, 1990.

20. Antonios Kakas, Robert Kowalski and Francesca Toni, Abductive logic programming, Journal of Logic and Computation vol. 2 no. 6, pages 719-770, 1993.

21. G. Neelakantan Kartha, Soundness and Completeness Theorems for Three Formalizations of Action, Proceedings IJCAI 93, page 724, 1993.

22. G. Neelakantan Kartha, Two Counterexamples Related to Baker’s Approach to the Frame Problem, Artificial Intelligence 69, Elsevier Science Publishers, pages 379-392, 1994.

23. Henry Kautz, The Logic of Persistence, Proceedings AAAI 86, page 401, 1986.

24. Robert A. Kowalski and Marek J. Sergot, A Logic-Based Calculus of Events, New Generation Computing, vol 4, page 267, 1986.

25. Robert A. Kowalski and Fariba Sadri, The Situation Calculus and Event Calculus Compared, in Proceedings of the International Logic Programming Symposium (ILPS’94), 1994.

26. Vladimir Lifschitz, A Language for Describing Actions, in Working Papers of Common Sense ’93: The Second Symposium on Logical Formalizations of Commonsense Reasoning, pages 103-113, Austin, Texas, U.S.A., 1992.

27. Fangzhen Lin and Yoav Shoham, Provably Correct Theories of Action, in Proceedings AAAI 91, page 349, MIT Press, 1991.

28. John W. Lloyd, Foundations of Logic Programming, Springer Verlag, 1984.

29. John McCarthy and Patrick 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.

30. Rob Miller, Situation Calculus Specifications for Event Calculus Logic Programs, in Proceedings of the Third International Conference on Logic Programming and Non-monotonic Reasoning, Lexington, KY, USA, Springer Verlag, 1995.

31. Rob Miller and Murray Shanahan, Narratives in the Situation Calculus, in Journal of Logic and Computation, Special Issue on Actions and Processes, vol 4 no 5, Oxford University Press, 1994.

32. Rob Miller and Murray Shanahan,, Reasoning about Discontinuities in the Event Calculus, in L. C. Aiello, J. Doyle & S. C. Shapiro, ed.s, Principles of Knowledge Representation and Reasoning: Proceedings of the Fifth International Conference (KR’96), Morgan Kaufmann, 1996.

33. Javier Pinto, Temporal Reasoning in the Situation Calculus, PhD. Thesis, University of Toronto, 1994.

34. Javier Pinto and Raymond Reiter, Temporal Reasoning in Logic Programming: A Case for the Situation Calculus, Proceedings ICLP 93, page 203, 1993.

35. Alessandro Provetti, Hypothetical Reasoning about Actions: From Situation Calculus to Event Calculus, Computational Intelligence, volume 12, number 2, 1995.

36. Erik Sandewall, Feature and Fluents, Oxford University Press, 1994.

37. Marek Sergot, An Introduction to the Event Calculus, in Lecture Notes of the GULP Advanced School on Foundations of Logic Programming, (unpublished), Alghero, Sardinia, 1990.

38. Murray Shanahan, Prediction Is Deduction but Explanation Is Abduction, Proceedings IJCAI 89, pages 1055-1060, 1989.

39. Murray Shanahan, Representing Continuous Change in the Event Calculus, Proceedings ECAI’90, pages 598-603, 1990.

40. Murray Shanahan, A Circumscriptive Calculus of Events, Artificial Intelligence, vol. 77, pages 249-284, Elsevier Science Publishers, 1995.

41. Murray Shanahan, Solving the Frame Problem: A Mathematical Investigation of the Common Sense Law of Inertia, MIT Press (to appear), 1997.

42. Leon Sterling and Ehud Shapiro, The Art of Prolog, MIT Press, 1986.

43. Kristof Van Belleghem, Marc Denecker and Danny De Schreye, Representing Continuous Change in the Abductive Event Calculus, in Proceedings 1994 International Conference on Logic Programming, ed. P. Van Hentenrijck, pages 225-240, 1994.

44. Kristof Van Belleghem, Marc Denecker and Danny De Schreye, On the Relation Between Situation Calculus and Event Calculus, Journal of Logic Programming, Special Issue on Reasoning about Actions (this issue), 1996.

APPENDICES

A. EXTENDING THE EXPRESSIVITY OF E

Two extensions to the syntax and semantics of E are given in this appendix. This is in order to illustrate that the basic notion of a model, encapsulated in Definitions 2.7 to 2.10, may be modified to accommodate extra types of propositions, without altering the basic principle of persistence captured in conditions (1)-(3) of Definition 2.10. Both extensions are very simple, and although they are obviously related to aspects of the qualification problem and ramification problem respectively, it is not our intention to suggest that, in this short space, we have developed a comprehensive approach to these subtle and complex issues.

A.1. Describing Conditions under which an Action Cannot Occur

In some circumstances it may be possible to infer knowledge about the conditions at the time of an action occurrence from the fact that the action did occur. For example, given that we know that “at 2 o’clock the caretaker unlocked the door”, we might typically infer that (at 2 o’clock) “she had the key”. This is because it is impossible to unlock a door without a key, which might be expressed by a proposition such as

Unlock impossible-if {¬HasKey}

This motivates a general definition for a new type of proposition:

Definition A.1. [q-proposition] A q-proposition in E is an expression of the form

A impossible-if C

where A ∈ Δ, and C is a set of fluent literals of E.

Such propositions may be accommodated in the semantics of E by strengthening condition (4) of Definition 2.10 (which expresses simple pointwise constraints on a model), without changing in the basic notion of persistence encapsulated in conditions (1)-(3). Assuming that domain descriptions are now defined as a quadruple ⟨γ, η, τ, κ⟩, where γ, η and τ are as before, and κ is a set of q-propositions^{11}, the condition now becomes:

(a) For all t-propositions in τ of the form “F holds-at T ”, H(F, T) = true, and for all t-propositions of the form “¬F holds-at T ”, H(F, T) = false.

(b) For all pairs of h-propositions and q-propositions in η × κ of the form “A happens-at T ” and “A impossible-if C”, H does not satisfy C at T.

11Note that, if for every c-proposition “A initiates F when C” there is a q-proposition “A impossible-if C ∪ {F }”, in any model all initiation points for F are actual points of change for F. An analogous observation holds for termination points. Thus Sergot’s notions of strong initiation and strong termination [37] can be incorporated into E by addition of q-propositions where appropriate.

A.2. Describing Indirect Effects of Actions

The following extension to E is included to illustrate how Definition 2.9 of an initiation or termination point might be refined, without necessitating a change in the basic notion of persistence encapsulated in conditions (1)-(3) of Definition 2.10. Suppose that we wish to express simple constraints between fluents. To take a canonical example, suppose that we want to express that a room is stuffy when the window is closed and the ventilator blocked. This might be expressed by a proposition such as

Stuffy whenever {Closed, Blocked}

Hence we define a new type of proposition as follows:

Definition A.2. [r-proposition] An r-proposition in E is an expression of the form

L whenever C

where L is a fluent literal and C is a set of fluent literals of E.

We now need a recursive definition of an initiation point and of a termination point, since, for example, if the ventilator is blocked, the action of closing the window will (indirectly) initiate the property of the room being stuffy. The modified definitions below assume that domain descriptions are defined as a tuple ⟨γ, η, τ, κ, ρ⟩, where γ, η and τ are as before, κ is a set of q-propositions and ρ is a set of r-propositions.

Definition A.3. [Initiation/termination point for domains with r-propositions] Let H be an interpretation of E, let D = ⟨γ, η, τ, κ, ρ⟩ be a domain description, let F ∈ Φ and let T ∈ Π. T is an initiation-point (respectively termination-point) for F in H relative to D iff one of the following two conditions holds.

1. There is an A ∈ Δ such that (i) there is both an h-proposition in η of the form “A happens-at T ” and a c-proposition in γ of the form “A initiates F when C” (respectively “A terminates F when C”) and (ii) H satisfies C at T.

2. There is an r-proposition in ρ of the form “F whenever C” (respectively “¬F whenever C”) and a partition {C_{1}, C_{2}} of C such that (i) C_{1} is nonempty, for each fluent constant F′ ∈ C_{1}, T is an initiation point for F′, and for each fluent literal ¬F′ ∈ C_{1}, T is a termination point for F′, and (ii) there is some T_{2} ∈ Π, T ≺ T_{2}, such that for all T_{1}, T ⪯ T_{1} ⪯ T_{2}, H satisfies C_{2} at T_{1}.

Intuitively, condition (2) above states that in order find time points at which the fluent F becomes indirectly initiated via the r-proposition F whenever C, we need to look for points at which one or more of the conditions in C become satisfied, and at which the remaining conditions were already satisfied (and continue to be satisfied up to some point T_{2} beyond the point in question).

Condition (4) of Definition 2.10 is now:

(a) For all t-propositions in τ of the form “F holds-at T ”, H(F, T) = true, and for all t-propositions of the form “¬F holds-at T ”, H(F, T) = false.

(b) For all pairs of h-propositions and q-propositions in η × κ of the form “A happens-at T ” and “A impossible-if C”, H does not satisfy C at T.

(c) For all r-propositions in ρ of the form “L whenever C”, if H satisfies C at T then H satisfies {L} at T.

B. PROPOSITION PROOFS

B.1. Proof of Proposition 2.1

Proposition statement: Let D be an occurrence-sparse domain description written in a language E = ⟨Π, ⪯, Δ, Φ⟩, and let T_{1}, T_{2} ∈ Π be such that T_{1} ⪯ T_{2}. Let H and H′ be models of D such that for all F ∈ Φ, H(F, T_{1}) = H′(F, T_{1}). Then for all F ∈ Φ, H(F, T_{2}) = H′(F, T_{2}).

Proof: Proof is by induction on the number n of h-propositions in η of the form A happens-at T such that T_{1} ⪯ T ≺ T_{2}.

Base Case: If n = 0 then by the first condition in the definition of a model, for all F ∈ Φ, H(F, T_{2}) = H(F, T_{1}) = H′(F, T_{1}) = H′(F, T_{2}).

Inductive Step: Suppose that n > 0 and that the lemma is true for all m < n. Let F′ ∈ Φ be an arbitrary fluent constant. It is sufficient to show that H(F′, T_{2}) = H′(F′, T_{2}). Since D is occurrence-sparse there exists at least one T ∈ Π such that (i) T_{1} ⪯ T ≺ T_{2}, (ii) there is at least one h-proposition in η of the form “A happens-at T ”, and (iii) there is no h-proposition in η of the form “A happens-at T′” such that T ≺ T′ ≺ T_{2}. Let T_{h} be such a time point. By the inductive hypothesis, for all F ∈ Φ, H(F, T_{h}) = H′(F, T_{h}) and by construction there are no initiation or termination points T′ (for any fluent) in H or H′ such that T_{h} ≺ T′ ≺ T_{2}. There are three cases to consider (since in any model, F′ must be unaffected, initiated or terminated at T_{h}):

Case one: There is not both an h-proposition in η of the form “A happens-at T_{h}” and a c-proposition in γ either of the form “A initiates F′ when C” or of the form “A terminates F′ when C” such that H (and thus H′) satisfies C at T_{h}. Hence by the first condition in the definition of a model, H(F′, T_{2}) = H(F′, T_{h}) = H′(F′, T_{h}) = H′(F′, T_{2}).

Case two: There is both an h-proposition in η of the form “A happens-at T_{h}” and a c-proposition in γ of the form “A initiates F′ when C” such that H (and thus H′) satisfies C at T_{h}. Hence by the second condition in the definition of a model, H(F′, T_{2}) = true = H′(F′, T_{2}).

Case three: There is both an h-proposition in η of the form “A happens-at T_{h}” and a c-proposition in γ of the form “A terminates F′ when C” such that H (and thus H′) satisfies C at T_{h}. Hence by the third condition in the definition of a model, H(F′, T_{2}) = false = H′(F′, T_{2}).

B.2. Proof of Proposition 5.1

Proposition statement: Let D be an occurrence-sparse, non-converging, initiallyconsistent, fluent-independent projection domain description. Then D is consistent.

Proof: Let D = ⟨γ, η, τ_{i}⟩ be written in the projection language E = ⟨Π, ⪯, Δ, Φ⟩, and let T_{0} be the null element of Π.

Let M : Φ ↦ {true, false} be defined as follows. For each F ∈ Φ,

• M(F) = true if there is an i-proposition in τ_{i} of the form “initially F ”,

• M(F) = false otherwise.

M will be used to construct a model H of D such that for all F ∈ Φ, H(F, T_{0}) = M(F). Notice that since D is initially consistent, then for each F ∈ Φ such that there is an i-proposition in τ_{i} of the form “initially ¬F ”, M(F) = false.

Since D is occurrence-sparse and non-converging, each time point T ∈ Π has a unique, maximal, finite (possibly empty) sequence T_{1}, …, T_{n} associated with it such that T_{1} ≺ … ≺ T_{n} ≺ T and such that for each T_{i} there is an h-proposition in η of the form “A happens-at T_{i}”. Moreover, the unique such sequence associated with T_{n} is T_{1}, …, T_{n−1}. Therefore, it is possible to define an interpretation H of D inductively as follows. For each T ∈ Π and F ∈ Φ,

1. H(F, T) = M(F) if n = 0 (i.e. the sequence associated with T is empty),

2. H(F, T) = H(F, T_{n}) if n > 0 and there is no A ∈ Δ such that there is both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ either of the form “A initiates F when C” or of the form “A terminates F when C” such that H satisfies C at T_{n},

3. H(F, T) = true if n > 0 and there is an A ∈ Δ such that there is both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ of the form “A initiates F when C” such that H satisfies C at T_{n},

4. H(F, T) = false if n > 0 and there is an A ∈ Δ such that there is both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ of the form “A terminates F when C” such that H satisfies C at T_{n}.

The fact that D is fluent-independent guarantees that no fluent/time-point pair (F, T) satisfies both of conditions 3 and 4 above. Hence H is well defined, and is clearly a model of D.

B.3. Proof of Proposition 6.1

Proposition statement: Let D = ⟨γ, η, τ_{i}⟩ be an occurrence-sparse projection domain description and let τ_{ob} be an observation set. Then H is a model of ⟨γ, η, τ_{i} ∪ τ_{ob}⟩ if and only if H is an i-model of D with τ_{ob}.

Proof: Let D be written in the projection language E = ⟨Π, ⪯, Δ, Φ⟩, and let T_{0} be the null element of Π.

“If” half: Suppose H is an i-model of D with τ_{ob}. Then by the definitions of an model and of an i-model there exists some set τ_{iϵ} of i-propositions such that H is a model of ⟨γ, η, τ_{i} ∪ τ_{iϵ} ∪ τ_{ob}⟩. Hence, by the monotonicity of E as regards addition of t-propositions to domain descriptions (see the remarks at the end of Section 2), H is a model of ⟨γ, η, τ_{i} ∪ τ_{ob}⟩.

“Only if” half: Suppose H is a model of ⟨γ, η, τ_{i} ∪ τ_{ob}⟩. Let the set τ_{H} of ipropositions be defined as follows. For each F ∈ Φ,

• initially F ∈ τ_{H} iff H(F, T_{0}) = true
• initially ¬F ∈ τ_{H} iff H(F, T_{0}) = false

Clearly H is a model of ⟨γ, η, τ_{i} ∪ τ_{H}⟩ and, by Proposition 2.1, ⟨γ, η, τ_{i} ∪ τ_{H}⟩ ⊧ p for each p ∈ τ_{ob}, so that τ_{H} is an i-explanation for τ_{ob} in D. Hence H is an i-model of D with τ_{ob}.

B.4. Proof of Proposition 7.4

Proposition statement: Let P (Π, ⪯) be an ordering program for E, and let D be a finite domain description. Then for any fluent literal L of E and any T ∈ Π, if

LP [D, P (Π, ⪯)] ⊢_{SLDNF} HoldsAt(λ(L), T)

then

D ⊧ L holds-at T

The proof of this proposition which is given below uses induction on the ‘length’ length(α) of the SLDNF derivation α of HoldsAt(λ(L), T), where length(α) is defined in Definition B.1 below in terms of successful calls to HappensAt. It is defined so that each SLDNF sub-derivation of a HoldsAt sub-goal within α (which must have occurred within some call to Initiates, Terminates, PossiblyInitiates or PossiblyTerminates) has ‘length’ less than the top-level derivation α.

Definition B.1. [length(α)] Let α be a successful SLDNF derivation of the goal HoldsAt(λ(L), T) in LP [D, P (Π, ⪯)]. length(α) is defined inductively as follows:

length(α) = S + ∑_{β∈B_{α}} size(β)

where

• S is the number of successful calls to HappensAt at the top level of α, i.e. not called within a (negation-as-failure) finitely-failed subsidiary derivation of α.

• B_{α} is the set of all finitely-failed subsidiary derivations from negative calls (to ClippedBetween or AffectedBetween) appearing at the top level of α.

• size(β) = 0 if there is no successful call to HappensAt in any branch of β.

• size(β) = 1 + max({length(α′) | α′ ∈ A_{β}}) if there is a successful call to HappensAt inside β, where A_{β} is the set of all successful SLDNF derivations of a HoldsAt goal, called as a negated sub-goal in one of the branches of β^{12}.

Proof of proposition. Let α be a successful SLDNF derivation of the goal HoldsAt(λ(L), T) in LP [D, P (Π, ⪯)]. We will use induction on length(α) to show that, given the fixed point I^{+} as defined in Proposition 7.3, if LP [D, P (Π, ⪯ )] ⊢_{SLDNF} HoldsAt(λ(L), T) then if L = F for some F ∈ Φ then I^{+}(F, T) = true, and if L = ¬F′ for some F′ ∈ Φ then I^{+}(F′, T) = false. The proposition will then follow directly from Proposition 7.3.

Base Case (length(α) = 0): Clearly, if length(α) = 0 the query HoldsAt(Pos(F), T) (respectively HoldsAt(Neg(F′), T)) can succeed only on clauses (LP1a), (LP1b) or (LP4), as success on (LP2) or (LP3) would require length(α) ≥ 1. We consider each of these possibilities in turn:

(i) Success on (LP1a): Clearly, the success of Given(λ(L), T_{1}) for some T_{1} < T means that “L holds-at T_{1}” ∈ D and so I^{+}(F, T_{1}) = true (respectively I^{+}(F′, T_{1}) = false) by rule (4) in the definition of F. Also, since the call β to AffectedBetween fails with size(β) = 0, the unground sub-goal HappensAt(a, t_{2}) fails, so that there are no h-propositions in D. Hence there are no possible initiation points or possible termination points between T_{1} and T. Therefore, since I^{+} is a fixed point of F, rule (1a) of F applies to give I^{+}(F, T) = true (respectively I^{+}(F′, T) = false).

(ii) Success on (LP1b): The proof is exactly analogous to (i), but using rule (1b) of F in place of rule (1a).

(iii) Success on (LP4): Trivially, I^{+}(F, T) = true (respectively I^{+}(F′, T) = false) by rule (4) in the definition of F.

Inductive Step (length(α) = n): Suppose that the statement which we wish to prove is true for all SLDNF derivations α′ of all HoldsAt goals such that length(α′) < n. The query HoldsAt(Pos(F), T) (respectivelyHoldsAt(Neg(F′), T)) can succeed only on clauses (LP4), (LP1a), (LP1b) or (LP2) (respectively (LP3)). Again, we consider each of these possibilities in turn:

(i) Success on (LP4): Trivially, I^{+}(F, T) = true (respectively I^{+}(F′, T) = false) by rule (4) in the definition of F.

(ii) Success on (LP1a): Since the sub-goals Given(λ(L), t_{1}), t_{1} ≺ T succeed, I^{+}(F, T_{1}) = true (respectively I^{+}(F′, T_{1}) = false) by rule (4) in the definition of F (where T_{1} is the binding to t_{1}). It remains to show that there is no possible initiation point or possible termination point for F (respectively F′) between T_{1} and T, so that rule (1a) in the definition of F may be applied. Trivially, if the sub-goals HappensAt(a, t_{2}), T_{1} ⪯ t_{2} and t_{2} ≺ T in the body of each ClippedBetween clause collectively fail, there can be no such point. Now suppose these sub-goals succeed, binding t_{2} to T_{2}. Since the call AffectedBetween(T_{1}, λ(L), T_{3}) fails (so that the top level goal succeeds on clause (LP1a)), both of the calls PossiblyInitiates(A, F, T_{2}) and PossiblyTerminates(A, F, T_{2}) (respectively PossiblyTerminates(A, F′, T_{2}) and PossiblyInitiates(A, F′, T_{2})) fail. Hence, if there is a c-proposition in D of the form “A initiates F when C” or “A terminates F when C” (respectfully “A terminates F′ when C” or “A initiates F′ when C”), there is a fluent literal L_{p} ∈ C such that not HoldsAt(\overline{λ(L_{p})}, T_{2}) fails, i.e. HoldsAt(\overline{λ(L_{p})}, T_{2}) succeeds, say with SLDNF derivation α′, where length(α′) < n. By the induction hypothesis, if L_{p} = F_{p} then I^{+}(F_{p}, T_{2}) = false, and if L_{p} = ¬F′_{p} then I^{+}(F′_{p}, T_{2}) = true. In either case, the c-proposition is therefore not applicable in the definition of a possible initiation point or possible termination point of F (respectively F′) relative to I^{+}. Hence rule (1a) in the definition of F applies to give I^{+}(F, T) = true (respectively I^{+}(F′, T) = false) as required.

12We assume the convention that max(∅) = 0.

(iii) Success on (LP1b): The argument in this case is exactly analogous to case (ii), but using rule (1b) (instead of rule (1a)) in the definition of F.

(iv) Success on (LP2): In this case there exists a T_{1} ∈ Π, T_{1} ≺ T, such that for some A ∈ Δ the propositions “A happens-at T_{1}” and “A initiates F when {L_{1}, …, L_{k}}” belong to D, and each of the calls HoldsAt(λ(L_{1}), T_{1}), …, HoldsAt(λ(L_{k}), T_{1}) succeed. The successful SLDNF derivations of each of these calls are of length strictly less than n due to the successful call of HappensAt(A, T_{1}) in the root SLDNF derivation of HoldsAt(Pos(F), T). Hence by the inductive hypothesis, for each L_{i} = F_{i}, I^{+}(F_{i}, T_{1}) = true, and for each L_{j} = ¬F_{j}, I^{+}(F_{j}, T_{1}) = false. Hence T_{1} is an initiation point for F relative to I^{+}. By an argument exactly analogous to that in case (ii) above, we can show from the finite failure of ClippedBetween(T_{1}, Pos(F), T) that there are no possible termination points for F between T_{1} and T, so that rule (2) in the definition of F applies to give I^{+}(F, T) = true as required.

(v) Success on (LP3): The argument in this case is exactly analogous to case (iv), but using rule (3) (instead of rule (2)) in the definition of F to show that I^{+}(F′, T) = false.

B.5. Proof of Proposition 8.1

Lemma B.1. Let E = ⟨Π, ⪯, Δ, Φ⟩ be a fluent-finite, non-converging projection language, let P (Π, ⪯) be an ordering program for E, and let D = ⟨γ, η, τ_{i}⟩ be a finite, initially-consistent, fluent-independent projection domain description in E. Let H be a model of D. Let M be a ground list term such that the ground query Member(λ, M) succeeds iff there is a fluent constant F′ ∈ Φ such that either λ = Neg(F′) and H(F′, T_{0}) = false or λ = F′ and H(F′, T_{0}) = true. Then for all F ∈ Φ and T ∈ Π,

EC[D, ∅, P (Π, ⪯)] ⊢_{SLDNF} HoldsAt(M, Pos(F), T)

if and only if H(F, T) = true, and

EC[D, ∅, P (Π, ⪯)] ⊢_{SLDNF} HoldsAt(M, Neg(F), T)

if and only if H(F, T) = false.

Proof. Let T and F be an arbitrary time-point and fluent constant. Since D is finite and non-converging, T has a unique, maximal, finite (possibly empty) sequence T_{1}, …, T_{n} associated with it such that T_{1} ≺ … ≺ T_{n} ≺ T and such that for each T_{i} there is an h-proposition in η of the form “A happens-at T_{i}”. Proof is by induction on the length n of this sequence.

Base Case: Clearly, if n = 0 the queries HoldsAt(M, Pos(F), T) and HoldsAt(M, Neg(F), T) can succeed only on clause (EC7), and will succeed if and only if the queries Member(Pos(F), M) and Member(Neg(F), M) succeed respectively. By the second condition in Definition 2.10 of a model, H(F, T) = H(F, T_{0}), so that by definition of the list term M the lemma is true in the base case.

Inductive Step: Suppose that the lemma is true for all time-points whose associated sequences are of length m < n. Then in particular it is true for T_{n} whose associated sequence is of length n − 1. There are three cases to consider:

Case one: There is both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ of the form “A initiates F when C” such that H satisfies C at T_{n}. Hence by the third condition in the definition of a model, H(F, T) = true.

In this case, by the inductive hypothesis and the program definition of Initiates, the query HoldsAt(M, Pos(F), T) will succeed on clause (EC8) with the program variable t_{1} in the body of the clause bound to T_{n}. The query HoldsAt(M, Neg(F), T) will fail on clause (EC7) because the sub-goal ClippedBetween(M, T_{0}, Neg(F), T) will succeed on clause (EC11) with the program variable t_{2} in the body of the clause bound to T_{n}. The query HoldsAt(M, Neg(F), T) will fail on clause (EC9) because by the inductive hypothesis and fluent-independence of D it will fail on the sub-goal Terminates(M, a, F, T_{n}) for all bindings of the variable a provided by solutions to Happens(a, T_{n}). Hence in this case the lemma is true.

Case two: There is both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ of the form “A terminates F when C” such that H satisfies C at T_{n}. Hence by the third condition in the definition of a model, H(F, T) = false.

In this case, by the inductive hypothesis and the program definition of Initiates, the query HoldsAt(M, Neg(F), T) will succeed on clause (EC9) with the program variable t_{1} in the body of the clause bound to T_{n}. The query HoldsAt(M, Pos(F), T) will fail on clause (EC7) because the sub-goal ClippedBetween(M, T_{0}, Pos(F), T) will succeed on clause (EC10) with the program variable t_{2} in the body of the clause bound to T_{n}. The query HoldsAt(M, Pos(F), T) will fail on clause (EC8) because by the inductive hypothesis and fluent-independence of D it will fail on the sub-goal Initiates(M, a, F, T_{n}) for all bindings of the variable a provided by solutions to Happens(a, T_{n}). Hence in this case the lemma is also true.

Case three: There is not both an h-proposition in η of the form “A happens-at T_{n}” and a c-proposition in γ either of the form “A initiates F when C” or of the form “A terminates F when C” such that H satisfies C at T_{n}. Hence by the second condition in the definition of a model, H(F, T) = H(F, T_{n}).

Clearly in this case, by the inductive hypothesis and by the program definitions of Initiates and Terminates, the queries HoldsAt(M, Pos(F), T) and HoldsAt(M, Neg(F), T) can succeed on the clauses (EC8) and (EC9) respectively only with the variable t_{1} in the body of each clause bound to some timepoint T_{i} < T_{n}. Moreover, by the same argument, for all T′ < T_{n}, the queries ClippedBetween(M, T′, Pos(F), T) and ClippedBetween(M, T′, Neg(F), T) succeed if and only if the queries ClippedBetween(M, T′, Pos(F), T_{n}) and ClippedBetween(M, T′, Neg(F), T_{n}) succeed respectively. Hence the queries HoldsAt(M, Pos(F), T) and HoldsAt(M, Neg(F), T) succeed if and only if the queries HoldsAt(M, Pos(F), T_{n}) and HoldsAt(M, Neg(F), T_{n}) succeed respectively. Hence in this case the lemma is also true.

Statement of Main Proposition: Let E = ⟨Π, ⪯, Δ, Φ⟩ be a fluent-finite, nonconverging projection language, let P (Π, ⪯) be an ordering program for E, and let D = ⟨γ, η, τ_{i}⟩ be a finite, initially-consistent, fluent-independent projection domain description in E. Let τ_{ob} be a finite observation set. Then for any fluent literal L of E and any T ∈ Π,

EC[D, τ_{ob}, P (Π, ⪯)] ⊢_{SLDNF} IHoldsAt(λ(L), T)

if and only if

D, τ_{ob} ⊧_{i} L holds-at T

Proof: Let an initial assignment of D be defined as a function M : Φ ↦ {true, false} such that M(F) = true whenever there is an i-proposition in D of the form “initially F ”, and M(F) = false whenever there is an i-proposition in D of the form “initially ¬F ”. Since D is initially consistent there exists at least one such function, and by Propositions 2.1 and 5.1 there is a one-to-one correspondence between initial assignments of D and models of D. We may therefore unambiguously refer to the model H generated by the initial assignment M.

Clearly, successive solutions to the sub-goals

Setof(l, (Initially(l)), i),
Setof(f, (F luent(f), not Initially(Pos(f)), not Initially(Neg(f))), p),
P ermutation(p, c), Append(c, i, m),

in clause (EC2) bind the variable m to an appropriate list representation of each such initial assignment in turn. Given such a ground list term M′, by Lemma B.1, clause (EC6) and the definition of F orall, the goal

ConsistentW ithObservations(M′)

will succeed if and only if the model of D its corresponding initial assignment generates is consistent with each o-proposition in τ_{ob}. Hence successive solutions to the goal IExplanation(m) bind the variable m to a list representation of each initial assignment which generates an i-model of D with τ_{ob}. Hence the proposition is true by clause (EC1), Lemma B.1 and the definition of F orall.

C. AN ORDERING PROGRAM FOR ⟨Π_{Δ}, ≤_{Δ}⟩

This appendix concerns the practical details of implementing Language A domains as Event Calculus style Prolog programs in the manner of Section 8, given the intermediate translations to E domain descriptions as defined in Section 3.

The following ordering program P (Π_{Δ}, ≤_{Δ}) uses the Situation Calculus style terms

Result(A_{n}, Result(…, Result(A_{1}, S0) …))

and

Branch(A′, Result(A_{n}, Result(…, Result(A_{1}, S0) …)))

to represent the Δ-sequences “A_{1}, …, A_{n}” and “A_{1}, …, A_{n}, |A′|” respectively:

t_{1} ≺_{Δ} t_{2} ← ListF orm(t_{2}, l_{2}), Append([h|r], l_{1}, l_{2}), ListF orm(t_{1}, l_{1}).
t ⪯_{Δ} t.
t_{1} ⪯_{Δ} t_{2} ← t_{1} ≺_{Δ} t_{2}.
ListF orm(S0, []).
ListF orm(Branch(a, t), [B(a)|l]) ← ListF orm(t, l).
ListF orm(Result(a, t), [R(a), B(a)|l]) ← ListF orm(t, l).

In addition, the complete occurrence set of Δ is represented by a single clause which replaces all the domain-dependent ground HappensAt clauses of Definition 8.2:

HappensAt(a, Branch(a, t)).

The important feature of the above ordering program is that not only does it correctly deal with ground queries of the form “T ⪯ T′” (where T and T′ are Situation Calculus style representations of Δ-sequences as described above), but it also gives all correct solutions to queries of the form “t ⪯ T′” (where t is a variable). This enables the sub-goals in clauses (EC8)–(EC11) to be re-ordered as follows:

HoldsAt(m, Pos(f), t_{3}) ←  (EC8′)
t_{1} ≺ t_{3}, HappensAt(a, t_{1}), Initiates(m, a, f, t_{1}),
not ClippedBetween(m, t_{1}, Pos(f), t_{3}).
HoldsAt(m, Neg(f), t_{3}) ←  (EC9′)
t_{1} ≺ t_{3}, HappensAt(a, t_{1}), Terminates(m, a, f, t_{1}),
not ClippedBetween(m, t_{1}, Neg(f), t_{3}).

\begin{matrix}ClippedBetween(m, t_{1}, Pos(f), t_{3}) ← & (EC10′) \\ t_{2} ≺ t_{3}, t_{1} ⪯ t_{2}, HappensAt(a, t_{2}), Terminates(m, a, f, t_{2}). \end{matrix}

\begin{matrix}ClippedBetween(m, t_{1}, Neg(f), t_{3}) ← & (EC11′) \\ t_{2} ≺ t_{3}, t_{1} ⪯ t_{2}, Happens(a, t_{2}), Initiates(m, a, f, t_{2}). \end{matrix}

This re-ordering avoids problems that would otherwise arise from calls to HappensAt with an unground second argument.