The Ramification Problem in the Event Calculus

Introduction

The ramification problem, that is to say the frame problem in the context of actions with indirect effects, has attracted considerable attention recently [McCain & Turner, 1995], [Lin, 1995], [Gustafsson & Doherty, 1996], [Sandewall, 1996], [Shanahan, 1997], [Thielscher, 1997], [Kakas & Miller, 1997], [Denecker, et al., 1998]. The purpose of this paper is to demonstrate that the standard benchmark scenarios for the ramification problem can be handled by the event calculus, as presented in Chapter 16 of [Shanahan, 1997], without introducing any significant new logical machinery.

Following [Shanahan, 1997], this article presents the event calculus in the first-order predicate calculus, augmented with circumscription. In this form, it can be used to represent a variety of phenomena, including concurrent action, actions with non-deterministic effects, and continuous change [Shanahan, 1997].

The event calculus can also be used to represent actions with indirect effects, as shown in [Shanahan, 1997]. However, certain types of domains are problematic. These involve the instantaneous propagation of interacting indirect effects, as exemplified by Thielscher's circuit benchmark [1997]. Staying within the framework of the event calculus, and introducing just two new predicates and two new axioms, this article presents a general technique for representing actions with indirect effects that encompasses such domains.

1 Event Calculus Basics

The event calculus used in this paper is drawn directly from Chapter 16 of [Shanahan, 1997]. Its ontology includes these circumscriptions are equivalent to the predicate completions of Initiates, Terminates, Releases and Happens.

2 State Constraints

The ramification problem is the frame problem for actions with indirect effects, that is to say actions with effects beyond those described explicitly by their associated effect axioms. Although it's always possible to encode these indirect effects as direct effects instead, the use of constraints describing indirect effects ensures a modular representation and can dramatically shorten an axiomatisation. One way to represent actions with indirect effects is through state constraints, the focus of this section. These express logical relationships that have to hold between fluents at all times.

In the event calculus, state constraints are HoldsAt formulae with a universally quantified time argument. Here's an example, whose intended meaning should be obvious.

Note that this formula incorporates fluents with arguments. Actions may also be parameterised, as in the following effect axioms.

Terminates(Feed(x),Hungry(x),t)

(H2.1)

The incorporation of state constraints has negligible impact on the solution to the frame . problem already presented. However, state constraints must be conjoined to the theory outside the scope of any of the circumscriptions. Given a conjunction ~ of Initiates, Terminates and Releases formulae, a conjunction 11 of Initiallyp, InitiallyN, Happens and temporal ordering formulae, a conjunction 'I' of state constraints, and a conjunction Q of uniqueness-of-names axioms for actions and fluents, we're interested in,

CIRC[~ ; Initiates, Terminates, Releases] " CIRC[/1; Happens] "EC" 'I'" Q .

For the current example, if we let ~ be the conjunction of (H2.1) and (H2.2), 11 be the conjunction of (H3.1) to (H3.3), 'I' be (Hl.l), and Q be the conjunction of (H4.1) and (H4.2), we have,

CIRC[~ ; Initiates, Terminates, Releases] " CIRC[/1; Happens] "EC "'I'" Q t= HoldsAt(Happy(Fred),l1).

State constraints must be used with caution. As can be seen by inspection, Axioms (EC 1) to (EC6) enforce the following principle: a fluent that has been initiated/terminated directly through an effect axiom cannot then be terminated/initiated indirectly through a state constraint, unless it is released beforehand. Similarly, a fluent that holds at time 0 because of an Initiallyp formula cannot then be terminated indirectly through a state constraint, unless it's released beforehand, and a fluent that does not hold at time 0 because of an InitiallyN formula cannot then be initiated indirectly through a state constraint, unless it's released beforehand.

Suppose, in the present example, we introduced an Upset(x) event whose effect is to terminate Happy(x). Then the addition of Happens(Upset(Fred),12) would lead to contradiction. Similarly , the addition of InitiallyN(Happy(Fred)) would lead to contradiction.

State constraints are most useful when there is a clear division of fluents into primitive and derived. Effect axioms are used to describe the dynamics of the primitive fluents and state constraints are used to describe the derived fluents in terms of the primitive ones.

3 Effect Constraints

State constraints aren't the only way to represent actions with indirect effects, and often they aren't the right way, as emphasised by Lin [1995] and McCain and Turner [1995] . To see this, we'll take a look at the so-called "walking turkey shoot", a variation of the Yale shooting problem in which the Shoot action, as well as directly terminating the Alive fluent, indirectly terminates a fluent Walking.

The effect axioms are inherited from the Yale shooting problem.

Now, how do we represent the dependency between the Walking and Alive fluents so as to get the required indirect effect of a Shoot action? The obvious, but incorrect, way is to use a state constraint.

HoldsAt(Alive,t) ~ HoldsAt(Walking,t)

The addition of this state constraint to the above formalisation would yield inconsistency, because it violates the rule that a fluent, in this case Walking, that holds directly through an Initiallyp formula cannot be terminated indirectly through a state constraint. (The same problem would arise if the Walking fluent had been initiated directly by an action.)

A better way to represent the relationship between the Walking fluent and the Alive fluent in the walking turkey shoot is through an effect constraint. Effect constraints are Initiates and Terminates formulae with a single universally quantified action variable. The constraint we require for this example is the following.

Terminates(a,Walking,t) ~ Terminates(a,Alive,t) (W4.1)

Notice that effect constraints are weaker than state constraints: the possibility of resurrecting a corpse by making it walk, inherent in the faulty state constraint, is not inherent in this formula.

Let L be the conjunction of (Wl.l), (Wl.2) and (W4.1). Let tl. be the conjunction of (W2.1) to (W2.5), and Q be the conjunction of (W3.1) and (W3.2). We have,

Effect constraints are adequate for the representation of many actions with indirect effects. But there is still a class of examples for which they don't work. Consider the following benchmark problem due to Thielscher [ 1997]. A circuit comprising a battery, three switches, a relay, and a light bulb is wired up as in Figure 1.

Five fluents represent the state of each component in the circuit: Switch1, Switch2, Switch3, Relay, and Light. Their initial configuration is as in Figure 1. There are various dependencies among the fluents. The light is on if switches one and two are closed. Switch two is open if the relay is on. Finally, the relay is on if switches 1 and 3 are closed. When switch 1 is closed, the relay becomes activated, switch 2 will open, and the light stays off. The awkward nature of this example derives from the fact that closing switch 1 has one indirect effect (closing the relay, which opens switch 2) that disables another indirect effect (the light coming on).

A first, naive attempt to formalise this example might include an effect constraint like the following.

Initiates(a,Light,t) ~ Initiates( a,Switch 1 ,t) A HoldsAt(Switch2,t)

But this formula is obviously a false start, because in this scenario, initiating Switch 1 also indirectly terminates Switch2, and the event calculus axioms entail that Switch2

still holds at the instant of termination. A better attempt would be the following effect constraint.

Initiates(a,Light,t) ~ Initiates(a,Switch1,t) A HoldsAt(Switch2,t) A -, Terminates(a,Switch2,t)

This formula is adequate for this particular scenario, but doesn't fully capture the dependency between the fluents . Suppose, for example, that switch 1 is initially closed, while switch 2 and switch 3 are initially open. Then closing switch 2 causes the light to go on, something not captured by this constraint. We need a counterpart to the above formula for this case.

Initiates(a,Light,t) ~

Initiates(a,Switch2,t) A HoldsAt(Switch1,t) A

-, Terminates(a,Switchl,t)

Once again, while this is adequate for the present example, it's not a general solution. In particular, neither of these formulae accounts for the possibility of independent but concurrent switch events.

In the following section, a method for representing the indirect effects of actions is presented whose generality is comparable to that of other recently published solutions to the ramification problem, but which doesn't require the development of significantly more logical machinery than is already present in the event calculus defined above.

4 Causal Constraints

Following a common practise in recent literature on the ramification problem, let's introduce some shorthand notation for expressing dependencies between fluents.

Definition 4.1. A fluent symbol is any string of characters starting with an upper-case letter. 0

Definition 4.2. Any fluent symbol is also a fluent formula. If<!> and 'If are fluent formulae, then so are -, <j>, <!> A 'If, <!> v 'If, <!> ~ 'If, <!> -t 'If and <!> H \jl. 0

Definition 4.3. Following the notation of [Denecker, et al., 1998], a causal constraint is a formula of the form,

initiatjn~ n ~ f3

or,

initiating n causes -, f3

where n is a fluent formula and f3 is a fluent symbol. 0 Here's a subset of the fluent dependencies in Thielscher's

circuit expressed using this notation.

jnitjatin~ Switch! A Switch2 ~Light

initiating Relay causes -, Switch2

initiating Switch! A Switch3 causes Relay

There are other dependencies in the circuit. For example, this set of dependencies neglects to specify the conditions under which the light goes off. But these can be ignored for the example narrative we're interested in here.

Formulae like these are intended to have an intuitive meaning. The translation into the event calculus detailed below could be thought of as one attempt to give them a precise semantics. Alternatively, these formulae can be thought of simply as syntactic sugar for more long-winded event calculus formulae of the particular form defined below.

4.1 Causal Constraints in the Event Calculus

The key to correctly representing causal constraints in the event calculus is first to introduce new events that update each fluent whose value is dependent on other fluents, and second to write formulae ensuring that these events are triggered whenever those influencing fluents attain the appropriate values. (A related proposal is made by Pinto [ 1998] in the context of the situation calculus.)

To guarantee the instantaneous propagation of the effects of such events, they must be triggered not just when the influencing fluents already have their appropriate values, but also when they are about to get those values thanks to other events occurring at the same time. This motivates the introduction of four new predicates, Started, Stopped, Initiated and Terminated. The formula Started(f:3;t) means that either f:3 already holds at 't or an event occurs at 't that initiates f:3 . Conversely, the formula Stopped(f:3,'t) means that either f:3 already does not hold at 't or an event occurs at 't that terminates f:3. The predicates Started and Stopped are defined by the following axioms.

Note that at the instant of a fluent's transition from one value to another, we have both Stopped and Started at the same time.

The formula Initiated(f:3,'t) means that f:3 has been "started" at 't in the above sense, and furthermore no event occurs at 't that terminates f:3. Likewise, the formula Terminated(f:3,'t) means that f:3 has been "stopped" at 't in the above sense, and no event occurs at 't that· initiates f:3 . The predicates Initiated and Terminated are defined by the following axioms.

To represent the causal constraints in Thielscher's circuit example, we introduce three events, LightOn, Open2 and CloseRelay, which are triggered under conditions described by the following formulae.

Initiated(Switch2,t) Started(Switch2,t) " Initiated(Relay ,t)

Initiated(Switch3,t)

These triggered events govern the transition of fluents from one value to another when certain conditions come about, as prescribed by the corresponding causal constraints. Hence the need for the Stopped and Started conditions in the above formulae. These ensure that an event occurs only at the time of the transition in question. The effects of these events are as follows. A Close! event is also introduced.

UNA[Switchl, Switch2, Switch3, Relay, Light]

(L4.2)

As the following proposition shows, this formalisation of Thielscher's circuit yields the required logical consequences. In particular, the relay is activated when switch 1 is closed, causing switch 2 to open, and the light does not come on.

Proposition 4.4. Let 1: be the conjunction of (L2.1) to (L2.4), /).be the conjunction of (Ll.l) to (Ll.3) with (L3.1) to (L3.6), 'I' be the conjunction of (CCI) to (CC4), and Q be the conjunction of (L4.1) and (L4.2). We have,

Proof. From CIRC[:E ; Initiates, Terminates, Releases] we get the completions of Initiates, Terminates and Releases. From CIRC[/:l ; Happens] we get the completion of Happens, namely,

At the time of the first event, the fluents Switch2 and Switch3 hold and the fluents Switchl, Relay and Light don't hold.

First we prove that the Closel event at time 10 is the first event. Consider any t < 10. There can't be a Closel event at t, since, from [4.5], the only Closel event is at 10. Since we have --, HoldsAt(Switchl,t) and only a Closel event can initiate Switchl, we have --, Initiated(Switchl,t), so, from [4.5], there can't be a LightOn or CloseRelay event at t. Since we have --, HoldsAt(Relay,t) and there can't be a CloseRelay event at t, we have --, Initiated(Relay,t), and therefore, from [4.5], there can't be an Open2 event at t. From [ 4.5], this exhausts all the possible types of event, so there can't be any event occurrence at timet. So the CloseJ event at time JO is the first event.

Now we prove that a Closel event, a CloseRelay event and an Open2 event all occur at time 10, but that no LightOn event occurs at time 10. We know directly from [4.5] that a CloseJ event occurs at 10. Therefore, since there is no type of event that can terminate Switch J, we have Initiated(SwitchJ,JO), given (L2.4). We know that Stopped(Relay,JO) since we have --, HoldsAt(Relay,JO), and since we have HoldsAt(Switch3,10), we also have Initiated(Switch3,10). So, from [ 4.5], we know that a CloseRelay event occurs at 10. Since a CloseRelay event occurs at 10 and there is no type of event that can initiate Relay, we have Initiated(Relay,lO), given (L2.3). We also know that HoldsAt(Switch2, 10) and therefore Started(Switch2,JO) . So, from [4.5], we know that an Open2 event occurs at time JO. Since there is an Open2 event at JO, which, from (L2.2), terminates Switch2, we have --, Initiated(Switch2,10), and therefore, from [4.5] there cannot be a LightOn event at 10.

Using a similar argument to the paragraph before last, we can show that no events occur after time JO. Given the events that occur at time JO, it's then straightforward to prove, from Axioms (EC2) and (EC5), that the fluent Relay holds at time 20, but the fluents Switch2 and Light do not. D

Let's briefly consider a couple of minor variations on this example. First, suppose we augment the formalisation with a Close2 action which initiates Switch2. Then the addition of the formula Happens(Close2,J5) will give rise to a contradiction, since we would have both a Close2 event at time J5 and, from (Ll.2), an Open2 event, enabling us to prove, for any timet after 15, both HoldsAt(Switch2,t) and --, HoldsAt(Switch2,15). In other words, switch 2 cannot be manually closed while switches J and 3 are closed, thanks to the relay.

Now consider the original narrative of events, but with a different initial situation, one in which switch 3 is open, then, as desired, we get a different result: the relay isn't activated, switch 2 doesn't open, so the light does come on.

Proposition 4.6. Retaining I., t::., '¥ and Q as above, let t::. be the conjunction of (L5.J) to (L5.5) with (L3.5). Then we have,

CIRC[~; Initiates, Terminates, Releases] A CIRC[t::.; Happens] A EC A'¥ A Q ~

HoldsAt(Light,20).

Proof. The proof is similar to that of Proposition 4.4. D

5 From Causal Constraints to Event Calculus

This section presents a general translation from the shorthand notation for causal constraints presented above into the event calculus, along the lines suggested by the preceding example.

Definition 5.1. A negated fluent symbol is a fluent formula of the form --, f3 where f3 is a fluent symbol. D

First we define the function T C· which translates a single causal constraint into a pair of event calculus formulae.

Definition 5.2. Let 'If be a causal constraint of the form,

initiating n causes y

where n is a fluent formula and y is either a fluent symbol or a negated fluent symbol. The translation T c(\j/) of \jl with new action name a is the pair (o,o), where o and o are defined as follows. Let TI' be TI with every negated fluent symbol --, f3 replaced by Terminated(f3,t) and every other fluent symbol f3 replaced by Initiated(f3,t). If y is a negated fluent symbol --, f3, then o is,

Terminates( a,f3, t) and 0 is, Happens(a,t) f- Started(f3,t) A TI'. Otherwise o is, Initiates( a,y,t) and o is, Happens(a,t) f- Stopped(y,t) A TI'. D

Next we define the function Tc*, which translates a set of causal constraints into a pair of conjunctions of event calculus formulae.

Definition 5.3 . Let <I> be a finite set of causal constraints {\j/J, ... , '1/n}. The translation Tc *(<I>) of <I> with new action names a1 to an is the pair (~A). where~ is OJ A ... A On and t::. is OJ A . .. A On, given that for any J ~ i ~ n, T c('lli) with new action name <Xi is (Oi,Oi). D

5.1 Limitations: The Gear Wheels Example

Although the technique described here can represent the indirect effects of many different types of actions, it does not work well in scenarios involving mutually dependent fluents, such as the following example, which is taken from [Denecker, et al., J998]. There are two interlocking gear wheels. If one is turning, the other must be turning, and if one is stationary, the other must be stationary. The example is formalised using two fluents, Turning! and Turning2.

initiating Turning J ~ Turning2

initiating Turning2 causes Turning!

initiating --,Turning! causes --, Turning2

initiating-. Turning2 causes-. Turning!

The proposed event calculus translation of these causal constraints does not yield the desired conclusions, as it cannot rule out phantom self-starting events that cause the wheel to turn. (Note, however, that this example can be correctly formalised using the state constraints of Section 2.) As illustrated in the next section, other examples with cycles of dependencies are handled more satisfactorily.

6 Vicious Cycles

Consider the modification of Thielscher's circuit depicted in Figure 2. This circuit incorporates a potentially vicious cycle of fluent dependencies. If switch 1 is closed, the relay is activated, opening switch 2, which prevents the relay from being activated. Given Axioms (CCI) to (CC4) in their present form, the formalisation of this scenario using causal constraints will yield inconsistency.

Here are the causal constraints ci>.

initiatin~ Relay ~ --, Switch2

initiating Switch! A Switch2 A Switch3 causes Relay

Let (L,Ll) be Tc *(ct>) with new action names Open2 and CloseRelay. Then Ll is the conjunction of the following Happens formulae, and L is the conjunction of the following Initiates and Terminates formulae.

Here are the customary uniqueness-of-names axioms.

Proposition 6.1. Let L be the conjunction of (Vl.l) and (V1.2), Ll be the conjunction of (Vl.l) and (Vl.2) with (V3.1) to (V3.5), '¥be the conjunction of (CCI) to (CC4), and Q be the conjunction of (V4.1) and (V4.2). The following formula is inconsistent.

CIRC[L; Initiates, Terminates, Releases] A CIRC[il ; Happens] "EC A '¥ " Q.

Proof. From CIRC[Ll ; Happens] we get,

[a= Closel At= 10] v

[a= Open2 A Started(Switch2,t) A Initiated(Relay,t)] v

[a= CloseRelay A Stopped(Relay,t) A Initiated(Switchl,t) A Initiated(Switch2,t) A Initiated(Switch3,t)].

Using the techniques of the proof of Proposition 4.4, we can show that the formula entails that the first event occurs at time 10. At time 10, Switch2 and Switch3 hold, but Switch! and Relay do not hold. We know that a Closel event occurs at 10. Now suppose no Open2 event occurs at 10. Then, since Open2 is the only event type that can terminate Switch2, we have Initiated(Switch2,10), which, since we have Stopped(Relay,lO), Initiated(Switchl,10) and Initiated(Switch3,10), entails that a CloseRelay event occurs at 10 from [6.2]. But if a CloseRelay event occurs at 10, then we have lnitiated(Relay,lO) and, from [6.2], an Open2 event also occurs at 10, which contradicts out initial assumption.

So an Open2 event must occur at 10. But then, from [6.2], we must have Initiated(Relay,10). From (CC3) and [6.2], this entails that a CloseRelay event must occur at 10. From [6.2], this gives us Initiated(Switch2,10). But since an Open2 event occurs at 10, which terminates Switch2, this contradicts (CC3). Therefore the formula has no models. D

Note that the cycle in this example is only "dangerous" if switch 3 is initially closed. If switch 3 is initially open, the correspondingly modified theory is consistent, and yields the expected conclusion that the relay remains inactive after the Close1 event.

Arguably, inconsistency is not the most desirable response to an example with a vicious cycle. A formalisation that yielded non-determinism instead would at least permit other useful conclusions to be drawn. Moreover, suppose the initial state of switch 3 is unknown, and (V3.3) is omitted. Then, the threat of inconsistency ensures that InitiallyN(Switch3) follows from the theory, even though no InitiallYN formula to that effect is included. This seems a little counter-intuitive.

On the other hand, the aim of formalisation should be to avoid inconsistency. The fact that inconsistency can result here simply from selecting an inappropriate initial state for switch 3 indicates that the wrong level of abstraction has been chosen for representing this particular domain. If we want to represent it in earnest (not just for illustrative purposes), a level of abstraction should be chosen in which every possible narrative that is itself consistent results in a consistent theory. (In the present case, this would demand the inclusion of explicit delays in the model.)

Concluding Remarks

The works of Lin [1995], of Gustafsson and Doherty [ 1996], and of Thielscher [ 1997] all share an important feature with the present paper. In each case, an existing predicate calculus-based action formalism, respectively the situation calculus, the fluent calculus, and PMON, is extended to handle actions with indirect effects. Moreover, in [Lin, 1995] and [Gustaffson & Doherty, 1996], as in the present article, circumscription policies are deployed which minimise parts ofthe theory separately.

The solution to the ramification problem offered in the present article is also based on an existing predicate calculus action formalism, namely the event calculus. As such, it doesn't demand the introduction of any new semantic machinery. Moreover, the proposal is conservative in the sense that it only adds to the existing calculus, the extension comprising four new axioms and four new predicates. With these axioms in place, the proposed solution is little more than a novel style of writing certain event calculus formulae.

No formal assessment has yet been undertaken of the range of applicability of the proposed solution to the ramification problem, as recommended by [Sandewall, 1996]. This, along with a more formal comparison with other approaches, would be a good topic for future research.

Acknowledgments

Thanks to Patrick Doherty, Rob Miller, Michael Thielscher, Kristof Van Belleghem and Mark Witkowski for discussions related to the topic of this paper. Thanks also to the anonymous referees who spotted flaws in an earlier version of the paper.