A Model of Events and Processes

1 Introduction

Representing and reasoning about events (or actions) has been a continuing problem for researchers in Artificial Intelligence (AI). What apparently makes it so hard is the difficulty in describing, in a tractable and natural way, the effects that events have- or, more particularly, do not have - on the world.

The standard approach within AI is to assume that, at any given instant, the world is in a particular world state. Various properties or propositions may hold of these states. A given world state has no duration; the only way the passage of time can be observed is through some change of state. The world changes its state by the occurrence of events.

A representation of events has to allow us to deter­ mine the outcome of performing an event in some given world state - that is, what propositions hold in the re­ sulting world state given that certain ones hold in the initial state. The normal way to do this is to introduce a formalism, such as the situation calculus [McCarthy and Michael Georgeff Australian Artificial Intelligence Institute 1 (}rattan Street Carlton, Victoria Hayes, 1969], to describe world states and the proposi­ tions that hold in those states. Then one writes down certain axioms about how the performance of a given event affects the propositions holding in the world.

·This work was supported in part by a Generic Indus­ try Research and [; __ dopment Grant from the Australian Department of Industry, Technology and Commerce and by Carlton and United Breweries Ltd.

There are two problems here. The first is that, in any sizable domain, there are a large number of proper­ ties that do not change from one state to the next, and writing down the axioms to express these facts is sim­ ply untenable. This is what is conventionally known as the frame problem. The second problem is that, in most real-world domains, the effects of an event can be quite complex, depending on the situation in which the event is performed and the causal properties of the domain. This is known as the ramification problem. These prob­ lems become even more severe when we allow events to be performed in parallel (concurrently), as one then has to be able to specify the results of performing any event in conjunction with every other set of possible events.

Most of the recent approaches to these problems utilize nonmonotonic reasoning mechanisms. There are numer­ ous ways this can be done, including nonmonotonic logic, circumscription, closest possible worlds (or models), and circumscriptive ignorance. These are complex devices, and every now and then someone finds a significant flaw in one or other approach [Hanks and McDermott, 1987].

We believe that much of the problem rests with view­ ing events as transitions between world states. Clearly, the performance of an event results in the world under­ going a transition from one state to another. But, in reality, an event affects only a small part of the world, and the model of events we choose should reflect this localization property. This paper proposes a model of events and processes based on this idea.

2 Informal Description

We consider the world to consist of a set of properties or relations among individuals. A world state is defined to be an assignment of truth or falsity (or, more gener­ ally, some value) to each of these properties. We view an event or action as a black box that has certain input ports and certain output ports. The input and output ports are associated with properties of particular indi­ viduals, and the values obtaining at these ports repre­ sent the values of the associated properties. The aim is to specify the transition table for the input and output ports of the event, rather than the transition table for the world as a whole.

To determine what state transitions are possible given an occurrence of an event, we simply require that the properties associated with the input and output ports of the event have the specified values in the initial and final states, respectively. What happens to other properties depends on what other events are, or are not , occurring at the same time.

Of course, all that we are doing here is specifying ex­ plicitly which properties are affected by an event and which are not. But this is very important. Most rep­ resentations or formalisms for describing events do not explicitly specify the domain of influence of an event; in­ stead, they determine the scope of influence by resorting to nonmonotonic mechanisms.

Such explicit specification, however, would seem to prevent solution of the ramification problem - the man­ ner in which the occurrence of a given event affects the world can be very complex and extensive. To handle this problem, we introduce notions of causality and process. Intuitively, although the domain of influence of a partic­ ular event may be quite limited, the event can cause the occurrence of other events or processes and in this way have a far more extensive effect upon the world.

3 Modelling Events

We base our model of events on situation semantics [Bar­ wise and Perry, 1983]. We consider a set of individuals or objects I and a set of n-ary properties F over these indivi~uals . A situation type (or, simpl~, ;ituation) is an assignment of values V to a set of properties from F. Each assignment in a given situation s is called a constituent of s . For example,

is a situation in which door1 is open 1 and the distance between room1 and room2 is 8; nothing is said about other individuals or the values of other properties.

A state is a complete situation where all property val­ ues for all individuals are specified. We let se represent the n~ll situation (i.e., the situation with no constituent). We will denote the set of all possible states in a given domain by W. An example of a state in the living-room world introduced by Ginsberg and Smith [1988] is given as A1 in the Appendix.

A situation s is coherent if s does not assign two dif­ ferent values to any property. Situations s and t are compatible if their union is coherent. A sequence of sit­ uations is called a history.

An atomic event type (or simply event) is a mapping from an event name to a pair of situation types. 2 For an event e, the first element of this pair is called the pre­ condition of e, denoted pre( e), and the second element the postcondition of e, post( e). The properties compris­ ing the precondition and postcondition of e are called, respectively, the domain of e, denoted dom(e), and the range of e, ran( e) .

1 The symbols t and frepresent true and false, respectively. 2 This definition can be generalized to allow sets of tran­ sitions between situation types without affecting the results given in this paper.

For example,

denotes an atomic event type representing the opening of doorl. An example of an event from the living-room world is given as A2 in the Appendix.

We let eu = (se,st)· If either the precondition or postcondition of an event is not coherent, we denote the eve?t by e+. Intuitively, eu corresponds to a no-op and e+ IS an event that can never be performed.

An event e can occur in a history between adjacent situations s and t if and only if pre( e) is contained in s and post(e) is contained in t. Intuitively, the precondi­ tion of the event must be satisfied in the initial situation and the postcondition must be satisfied in the resulting (final) situation.

It is important to note that the precondition of an event acts like a guard; that is, the event simply cannot occur unless the precondition is satisfied. This is differ­ ent to many event formalisms in AI, in which the event can occur without the precondition being satisfied, but possibly with unpredictable results.

4 Concurrent Events

~onsider two events occurring concurrently (i.e., occur­ rmg between the same two situations) in any given his­ tory. It follows directly from the condition on event occurrence given above that the preconditions of both events must be compatible and that their postconditions must be compatible. Intuitively, two events can be per­ formed concurrently provided they do not interfere with one another.

We can also define new events consisting of the com­ position of two or more concurrent atomic events. More formally, we represent the concurrent combination of two atomic events e1 and e2, denoted by e.jle2, as

The resulting event can only occur if both its pre­ condition and postcondition are coherent; otherwise, it reduces to the event e+. An example of a concurrent event is given as A3 in the Appendix.

As the union of two situations is itself a situation, it follows that the concurrent event e1lle2 is also an atomic event. It can therefore be combined concurrently with other atomic events. The operator II can be shown [Bele­ grinos, 1991] to be reflexive, commutative and associa­ tive, with eu and e+ playing the role of the unit and zero elements, respectively. With the above definition, we can therefore replace any set of concurrently occurring events e1, e2, . .. en by the single atomic event edle2ll· .. lien. We denote the closure of a set of atomic events E under the operator II by E.

Elsewhere [Belegrinos, 1991] we develop a method for representing more general classes of events using a greater range of event operators. For the present discus­ sion, however, atomic events are sufficient.

5 Performing Events

We have already stated conditions that have to be sat­ isfied for an event to occur in a particular history. We now introduce further constraints upon events and the situations over which they occur.

Intuitively, we wish to only allow changes in proper­ ties from one situation to the next if an event occurs that brings about that change [Georgeff, 1987]. In our event representation, it is an immediate consequence that the value of any property outside the range of the events occurring between the two situations will remain un­ changed.

Consider a pair of adjacent situations s and t in a given history. Let the set of all (concurrent) atomic events oc­ curring between these situations be represented by the single atomic event e, as defined above. Then the follow­ ing conditions must be observed between the situations sand t :

where ulq represents the restriction of u to the properties in Q and R is the set of properties in the situation t.

Note that the resulting situation t is fully determined by the event e and the initial situation s, provided s in­ cludes all the properties in t not included in the range of e. In the particular case when s and t are states (i.e., complete situations), e fully specifies the transi­ tion between the states. We will denote this state by result(e, s). Formally, we have

Note that result is a partial function and is undefined for some states. In particular, we write result(e, s) = ..L if pre( e) is not compatible with s .

Because the domain of influence of an event is fully prescribed, describing events and their effects upon the world is not subject to the frame problem. That is, the effects of an event can be fully delineated without having to use either frame axioms or nonmonotonic mechanisms [Georgeff, 1987].

Now consider the occurrence of an event e, possibly concurrently with other events from a set of events E. The set of all possible transitions between states, called the transition relation of e with respect to W and E, is given by

The set T. corresponds to the conventional view of events in the AI literature, i.e., as transition relations over world states [McDermott, 1982]. It is straightfor­ ward to prove that Te,lle, = T., n T.,, as expected.

While this indicates that, for every event e in a spec­ ified domain of world states W and events E, there is a corresponding transition relation, the converse is not true. This is quite important. It means that our notion of an event is more restrictive than notions in which arbi­ trary transitions are allowed. But we can represent any transition relation as a set of atomic events, and thus can represent any possible world history.

Moreover, the fact that our notion of events is more restrictive allows for simpler logical representations and possibly more effective reasoning techniques. For example, the model of events as proposed can be used to pro­ vide a formal semantics for the standard STRIPS rep­ resentation [Fikes and Nilsson, 1971] of events and is suggestive of its straightforward extension for reasoning about concurrent events. Provided that one has some means for specifying any domain-specific constraints on the occurrence of events, and extends the STRIPS rep­ resentation to allow event sets and concurrency, the ap­ proach is fully general. The model proposed here can also be used for providing the formal semantics for other more powerful logics of events and actions.

6 Constraints Among Events

The above model of events is quite general and can be used to represent arbitrary histories of events and situa­ tions. However, to reason about events and their possible ramifications, we need to add to this representation some means for specifying domain-specific constraints among events.

6.1 Processes

The world can be viewed as consisting of various mech­ anisms or causal relationships which place constraints upon the events that can be performed. These con­ straints determine both which events can or must occur concurrently and which events can or must occur sequen­ tially. Most AI formalisms have limited expressive capa­ bility for describing these kinds of causal and temporal relations among events (a notable exception being the work of Lansky [1987]). To model these constraints on behaviour in a fully general way, we therefore introduce the notion of process.

While there are a number of different process models that would be suitable to this end, we choose herein to use the model of Communicatine; Sequential Processes (CSP) as introduced by Hoare l1985J. Following this approach, we represent a process as a pair of Sets. The first set, called the alphabet of the process, is the set of atomic events in which the process can engage. The alphabet of a process Pis denoted by a(P). The second set, called the traces of the process, is a set of sequences of atomic events.

Each trace describes the behaviour of the process up to a particular point in time, and each event that ap­ pears in a trace is a possibly concurrent combination of the atomic events contained in the alphabet of the pro­ cess. The traces of a process Pare denoted by traces(P) and the trace that consists of the sequence of events m1 followed by m2 and so on up to mn is denoted by <m1, m2, ... , mn >. The first event of a trace m I<> is denoted by m1 and the trace which results from re­ moving the first event of m is denoted by m'.

This notion of process is important in a number of ways that parallel our representation of events. First, it depends on an explicit representation of the events that can possibly engage in the process, as defined by the pro­ cess alphabet. Second, it is local. That is, it does not attempt to define the constraints between events as they occur globally, but restricts attention to their local influ­ ence over one another. The fact that an event e2 directly follows another event e1 in a process P does not prevent other events, not in the alphabet of P, from occurring be­ tween the occurrences of e1 and e2. These ideas are im­ portant for the definition of process concurrency, which we introduce below, and are essential to providing com­ positionality of the representation. Moreover, the ability to represent localized constraints on events is critical for achieving computational tractability [Lansky, 1988].

Rather than specifying the traces of a process directly, Hoare introduces an equivalent method for representing processes. This method consists of the following recur­ sive rules.

1. The process STOPB (where B is a set of atomic events and a(STOPB) =B) denotes a process that never performs any of the events in B.
2. The process e --+ P (where e E a(P)) denotes a process that performs the event e and then behaves like P.
3. The process e1 --+ Pt I e2 --+ P2 (where a(Pt) = a(P2) and e1 E a(Pt), e2 E a(P2) and e1 'I e2) denotes a process that first performs either e1 or e2 and then behaves like P1 if e1 was performed first and like P2 if e2 was performed first.

The above rules can be conveniently expressed using the notation P = e : B --+ P(e), where B is a set of atomic events and P( e) is an expression denoting a pro­ cess for each of the different events e in B. The process e : B --+ P( e) denotes a process that first performs an event e E B and then behaves like P(e). The traces of this process are expressed as follows:

6.2 Concurrent Processes

Different agents (or machines) and the environment in which they are situated can be modelled by different pro­ cesses. It remains to specify how these processes evolve when they are brought together. For this we need the notion of concurrent processes.

The definition we adopt is similar to that of Hoare. That is, events that are unique to one process can be performed whenever that process is ready to perform them and events that are in the alphabets of more than one process must be performed simultaneously (syn­ chronously) . However, we extend Hoare's approach to allow the simultaneous occurrence of events of different types.

Formally, we represent the concurrent combination of two processes Pt and P2, denoted PdiP2, as follows:

The expression m!a is the restriction of the events in m to the events in a. If no events in m are contained in a, m!a = <>.

6.3 Relationship to Situation Histories

The notion of process as defined above allows us to repre­ sent arbitrary constraints among events 3 and to compose these in various ways. We now have to determine how these sequences of events relate to situation and state histories.

We do this by extending the notion of event occurrence between two situations within a given history. In partic­ ular, we say that an event trace can occur over a given in­ terval within a given history just in case each element of the trace can occur between successive situations in the interval. More formally, we have e = < e1, e2, ... , en > can occur over an interval s = so, Bt, .·· , Sn of a history if and only if ei can occur between situations Bi-1 and Bi for i = 1, ... n. 4

If we have a set of concurrent processes P represent­ ing the constraints among all the events of a given do­ main, the traces of P will fully determine which events can occur from one moment to the next. Thus, for any such trace to occur in a particular history, the conditions given as Equation 1 in Section 5 must also be satisfied. In the case that the history is over complete states, it follows that each trace of P determines a unique history, given the state of the history in which P is initiated.

Given a set of concurrent processes P, we will say a trace e = < e1, ... , en> of P is realizable with respect to a state s E W if and only if

result( en' (result( en-b .. . (result( el' s)) .. . ))) ::j;l. where we let result(e, 1.) = 1.. We take the empty trace to be realizable with respect to any state.

7 Causality

One of the most important relationships between events is that of causation. This is particularly so in our case, because it is by this mechanism that we can represent the ramifications of any given event. In this section, we show how to model causation using processes.

Following earlier work [Georgeff, 1987], we consider two types of causation: sequential and simultaneous. Let us first consider simultaneous causation. An atomic event e1 is said to simultaneously cause an atomic event e2 under conditions <P if, whenever e1 occurs and the condition <P holds, event e2 also occurs. This form of causation can be modelled by the following process:

where e.,t/> is an atomic event that tests if <P is false (i.e., has -.<P as its precondition).

This process is such that, whenever e1 is performed under condition <P, the event e2 is forced to occur con­ currently. However, if <P is not true, e1 can occur by itself. The third alternative branch in the above pro­ cess (i.e., as represented by the choice e2) is necessary so that the occurrence of e2 can occur unconstrained by the occurrence or otherwise of e1.

3 This is not quite true. The process model given here cannot represent nondeterministic machines. However, the extension to this case, which requires the notion of failure 8eb, is relatively straightforward.

4 A set of event traces can be considered a complex (i.e., non-atomic) event (see also the work of Lansky [1987]). The above definition thus defines under what circumstances such an event can occur in a history.

Sequential causation models the case in which the oc­ currence of an event e1 causes the subsequent occurrence of an event e2, though possibly other events may occur between the occurrences of these events. The causation may also be dependent upon some condition ¢ holding when e1 is performed. This form of causation can be represented by a process similar to that given above.

Other examples of causal processes are given as A4 in the Appendix.

8 Mapping Properties to Processes

We have introduced above a model for representing events aqd situations and for representing arbitrarily complex relations among those events. We have defined under what conditions an event or set of events can oc­ cur (or be performed), and how such occurrences affect the situations over which the event(s) take place.

This model can be used as a basis for the semantics of various logics and calculi for reasoning about events, sit­ uations, and plans. However, in some circumstances, it is desirable to be able to reason entirely within a process framework. Therefore, in this section, we describe how to transform the current representation into an equiva­ lent process representation.

Hoare's representation of processes is purely event based and contains no explicit representation of state properties. Determining the behaviour of a set of pro­ cesses is thus simply a matter of determining how the event traces of the participating process can be com­ bined, given the restrictions on event execution defined above. However, once we allow state properties to be introduced, events can indirectly influence one another through the effect one event has on the properties that affect performance of another. In essence, the state prop­ erties provide yet other constraints on the performance of events.

One way to represent the influence of state properties is to introduce further processes that force these con­ straints to be observed. We call such processes property processes, and introduce one for each property p in F. The property process for a property p can be viewed as an n state machine, where n is the number of values that can be assigned top. Each state represents a different value of p; the current state represents the current value of p. A change in state of the machine results by per­ forming an event e such that pre( e) is compatible with the current assignment top. The resulting state of the machine is the state which represents the value specified by post(e).

To keep the description of the property processes rela­ tively simple, we introduce the events ~ = ( {p: v} , se) and rt = ( se , {p: v}) for each different value v that can be assigned to p. Intuitively, ~ is an event that tests whether p has value v and rt assigns the value v to p. We let the set of all such events for the property p be denoted by Ep.

Any event can be described as a concurrent combina­ tion of ~ and r~ events with different p and v. This relationship can be captured by constructing a causal process for each event e, such that e causes the simul­ taneous occurrence of the events ~ (or rt), for each valuation of pin the domain (range) of e.

The property process PP for property p is then con­ structed as follows:

PP = initP -+ PP I· · · I initP -+ PP where tJl til v... ""' v1 , ... , Vn are the different assignments to p, in it~ , ... , in itt are distinguished atomic events, a(P~) = a(PCJ = {initt 1 , ··· initt.J U Ep, and where PC,= e: ce,-+ PC,(e), ce, =CC. U···UCC, .. ce .. = {;tt,, rt,, ~. llrt,} ce,; = {rt;, ~.llrt;} (j :/; i) and PC,(e) =PC; if e E ce,;

The purpose of the events initt, is simply to set the initial state of the property process; their form is straightforward and is given elsewhere [Belegrinos, 1991]. Intuitively, PC represents the state in which p has the value Vi and the events in CC .. represent those events '1 e E Ep that change the value of the property p from Vi to v; . Note that these processes correspond directly to the constraints used by Lansky [1987] to represent event properties, with the events rt playing the role of Lansky's "adders" ( v = t) and "deleters" ( v = f) for property p and ~ representing the constraints on event preconditions.

Given an arbitrary process P and a set of property processes as described above, it can be shown [Belegri­ nos, 1991] that the traces of P executed concurrently with the property processes are exactly those traces that would result from executing P, taking into account the influence of state properties. That is, the traces are ex­ actly the realizable traces of P.

9 Conclusions

The aim of this paper has been to determine the basic foundations for a theory of events, situations, and pro­ cesses that can be used for reasoning about arbitrarily complex dynamic domains. The essential elements of the approach are: (1) A model of events that explicitly represents the domain of influence of the event; (2) A model of processes that can represent arbitrarily com­ plex behaviours; (3) An extension of that process model to represent the influence of events upon state proper­ ties and the influence, in turn, of those properties upon other events; and (4) A representation of causality that allows the ramifications of a given event occurrence to be modelled.

We have also shown how to map the representation of a problem domain described in terms of high-level events, state properties, and causality into a more-or-less standard process model. Having done this, we can then draw on all the work in process theory and its application to help solve complex, real-world problems.

Although we have not directly addressed the frame problem, it should be clear that, by scoping the do­ main of influence of events, the problem as convention­ ally viewed will not arise. In essence, we have transferred the problem of reasoning about the effects of events and actions to one of reasoning about which events are occur­ ring at any given moment of time. While we believe that process models provide the basis for doing this reasoning in a tractable way, this claim has yet to be demonstrated. We also need to develop a logic of events and situations that is well suited to this model and to examine the se­ mantic foundations, in terms of this model, of previous formalisms .

Appendix

We illustrate here how our approach can be used to rea­ son about the living-room world introduced by Ginsberg and Smith [1988]. For simplicity, we consider only a subset of this world. In particular, we assume that the room contains a television, a plant, a shelf, and two ven­ tilation ducts located under the floor. If an object is on a duct, that duct is blocked; ifboth ductsare blocked, the room will become stuffy. We can represent this world by taking

F = {pos(tv), pos(plant), blocked( duct!), blocked( duct2), stu.ffy(room)},

where

pos can take the values {floor, shelf, duct!, duct2} and blocked and stuffy the values { t, f}.

The initial state of the world is represented by the state s as follows:

s = {pos(tv): shelf, pos(plant): duct2, blocked( ductl ): f , blocked( duct2): t , stuffy(room): f} (Al)

Suppose we can perform two events in this world: move the television from the shelf to ductl (denoted by ei) and move the plant from duct2 to the floor (denoted by e2) . We can represent these events and their concur­ rent combination as follows:

e1 = ( {pos(tv): shelf, blocked( duct!): f} , {pos(tv): ductl, blocked(ductl): t}) e2 = ({pos(plant): duct2, blocked(duct2): t}, {pos(plant ): floor , blocked( duct2) : f}) (A2) edle2 = ({pos(tv): shelf, blocked(ductl): f, pos(plant): duct2, blocked(duct2): t}, {pos(tv): ductl, blocked(ductl): t, pos(plant): floor, blocked( duct2): f}) (A3)

Let P A be an agent process that performs the event e1 followed by e2. That is, o:(PA) = {e1 , e2} and PA = e1 --+ e2 --+ STOP a(PA)·

The indirect effects (ramifications) of these events on the property stuffy(room) are handled by introducing the events estuffy and eclear, defined as follows:

ec1ear = (st , {stu.ffy(room): f}) estuffy = (st , {stu.ffy(room): t})

Depending upon which causal rules one adopts, we can force the room to become stuffy immediately the two ducts are blocked or some time after both are blocked. For this example, we will assume the former. This leads to the following causal processes:

Putting these processes together, it is not too hard to show that <init,,(edle~llestuJJy), (e2lleclear)> is the only realizable trace of P, where init, is the event that sets the initial state properties to s.

Acknowledgments

The authors wish to thank David Morley, Anand Rao, and Liz Sonenberg for their contributions to this work.