Reasoning about Actions, Narratives and Ramifications

Antonis Kakas

Department of Computer Science, University of Cyprus,
75 Kallipoleos Street, P.O. Box 537, CY-1678 Nicosia, CYPRUS
Email: antonis@turing.cs.ucy.ac.cy WWW: http://www.ucy.ac.cy/ucy/cs/webPages/PEOPLE/faculty/kakas.htm

Rob Miller

Department of Computer Science, Queen Mary and Westfield College,
University of London, Mile End Road, London E1 4NS, U.K.
Email: rsm@dcs.qmw.ac.uk WWW: http://www.dcs.qmw.ac.uk/~rsm/



Summary

This paper shows how the Language E [Kakas and Miller, 1997] may be extended to deal with ramifications, and how domain descriptions written in this extended language may be translated into Event Calculus style logic programs. These programs are shown to be sound even when only incomplete information is given about some initial state of affairs.

The Language E was developed partly in response to the Language A [Gelfond and Lifschitz, 1993], which was introduced as the first in a family of "action description languages". Action description languages (such as A) inherit an ontology from the Situation Calculus, whereas the Language E inherits its ontology (which includes an independent flow of time) from Kowalski and Sergot's Event Calculus [Kowalski and Sergot, 1986]. E can therefore be regarded as a basic or kernel "event description language". It was developed in the belief that the use of, and comparison between, different ontologies is important in the study of formal reasoning about actions. The semantics of E, like that of A, is model-theoretic, and divorced from computational considerations.

The Basic Language E

The paper begins by reviewing the basic Language E. E's vocabulary includes a set of fluent constants, a set of action constants, and a partially ordered set of time-points. Basic Language E domain descriptions can include three types of propositions: t-propositions ("t" for "time point"), h-propositions ("h" for "happens"), and c-propositions ("c" for "causes"). For example, the following domain description (about taking a photograph) contains 1 t-proposition, 3 h-propositions and 2 c-propositions:

¬Picture holds-at 1
Load happens-at 2
Look happens-at 5
Take happens-at 8
Load initiates Loaded
Take initiates Picture when {Loaded}

The model theoretic semantics of E ensures that (for example) this domain description entails the t-proposition

Picture holds-at 10

The notions of an "initiation point" and a "termination point" are central to E's semantics. For example, in all models of the above domain, 2 is an initiation point for "Load" and 8 is an initiation point for "Picture". Time can be discrete or continuous, and need not be linear. Indeed, as a special case time may be modelled as a branching structure of sequences of action constants. This allows the "simulation" in E of the Language A, by writing and reasoning about t-propositions such as

Picture holds-at [Load, Look, Take]

Describing Indirect Effects in E

The remainder of the paper discusses an extension of E to include a forth type of statement called an r-proposition ("r" for "ramification"). R-propositions express permanent constraints or relationships between fluents. In formalisms which allow for such statements, the effects of actions may sometimes be propagated via groups of these constraints. This gives rise to the "ramification problem", i.e. the problem of adequately and succinctly describing these propagations of effects whilst retaining a solution to the frame problem.

R-propositions are statements of the form

L whenever {L1, ..., Ln}

The intended meaning of this statement is "at every time-point that {L1, ..., Ln}, L holds, and hence every action occurrence that brings about {L1, ..., Ln} also brings about L". Hence the semantics of E is extended so that from a static point of view r-propositions behave like classical constraints, but they are unidirectional in terms of the way they propagate temporal change initiated by action occurrences. This is achieved in the main by appropriately extending the definitions of an initiation and a termination point. These definitions are now recursive, or in terms of least fixed points. R-propositions thus provide a simple, succinct method of expressing domain constraints, and the corresponding semantics behaves in a satisfactory way for a range of examples found in the literature.

The use of r-propositions is illustrated in the paper with two examples. The second of these is Thielscher's electric circuit example [Thielscher, 1997]. This example is of interest because it presents difficulties for what Thielscher describes as "categorisation-based" approaches to ramification. In the (Language E version of the) example, the permanent configuration and dynamic behaviour of an electric circuit is described by r- and c-propositions such as

Light whenever {Switch1, Switch2}
Relay whenever {Switch1, Switch2}
¬Switch2 whenever {Relay}
CloseSwitch1 initiates Switch1
OpenSwitch1 terminates Switch1
CloseSwitch2 initiates Switch2 when {¬Relay}

If "Switch2" already holds (i.e. switch number 2 is connected) and a "CloseSwitch1" action occurs, say at time-point T1, the extended semantics of E ensures that (in all models) the effect of this event is propagated through the first of the r-propositions above, so that "Light" becomes true. This is because the least fixed point definition of an initiation point ensures that T1 is an initiation-point for "Switch1", and hence (by the recursive definition) an initiation point for "Light" by the first r-proposition above.

Logic Program Translations

The paper gives a translation method from E domain descriptions into logic programs, and gives a proof of the correctness of the translation (as regards derivation of t-propositions) for a wide class of domains. As in [Kakas and Miller, 1997], over-zealous application of logic programming's closed world assumption is avoided by representing negated fluents inside a meta-level "HoldsAt" predicate. For example, "Relay holds-at 2" is translated as "HoldsAt(Pos(Relay),2)" and "¬Relay holds-at 2" is translated as "HoldsAt(Neg(Relay),2)". C-propositions such as "CloseSwitch2 initiates Switch2 when {¬Relay}" are translated into two clauses:

    Initiates(CloseSwitch2,Switch2,t) <- 
                           HoldsAt(Neg(Relay),t).

    PossiblyInitiates(CloseSwitch2,Switch2,t) <- 
                           not HoldsAt(Pos(Relay),t).

The first of these clauses gets used to compute changes in the truth value of "Switch2" and other fluents via occurrences of "CloseSwitch2". The second gets used in the computation of persistence of truth values. (Similar techniques are used in a number of other logic program translations of action formalisms.)

A soundness property is proved for the logic program translations of a general class of domain descriptions, which may include r-propositions. It is stated in terms of SLDNF-derivability: if there is a finite SLDNF derivation of "HoldsAt(Pos(F),T)" (respectively "HoldsAt(Neg(F),T)") from the program, then "F holds-at T" (respectively "¬F holds-at T") is entailed from the original domain description.

For the examples given in the paper, these logic programs are more-or-less directly executable in Prolog. The relevant Prolog listings are available at http://www.dcs.qmw.ac.uk/~rsm/abstract15.html


Summary of:
Antonis Kakas and Rob Miller, "Reasoning about Actions, Narratives and Ramifications", Linköping Electronic Articles in Computer and Information Science, Vol. 2(1997): nr 12. http://www.ep.liu.se/ea/cis/1997/012/. October 16, 1997. Also posted and under public review in the News Journal of Electronic Transactions on Artificial Intelligence (ETAI), http://www.ida.liu.se/ext/etai/.