Reasoning About Actions in Narrative Understanding

1 Introduction

Formal approaches to model reasoning about changing environments have a long tradition in AI. This research area was initiated by McCarthy [McCarthy, 1969], who claimed that reasoning about actions plays a fundamen­ tal role in common sense. Trying to build language understanding programs not only underscores the im­ portance of reasoning about actions, but also suggests that the the set of situations and the kinds of inferential processes required are richer than has been traditionally studied in formal approaches.

Language understanding requires sophisticated reason­ ing about actions and events. The world's languages have a variety of grammatical and lexical devices to construe, direct attention and focus , and control inferences about actions and events. Consider the meaning of stumbling in the following newspaper headline "Indian Government stumbling in implementing Liberalization Plan". Clearly, the speaker intends to specify that the liberalization plan is experiencing some difficulty. More­ over, the grammatical form is + VP-ing suggests that the difficulty facing the plan is ongoing and the final out­ come of the plan is indeterminate. Compare this to the subtle meaning differences with grammatical and lexical modifiers on the same root verb such as has stumbled or starting to stumble. Most reader's are likely to infer after reading this sentence that the government's liber­ alization policy is likely to fail , but this is only a default causal inference that is made in the absence of informa­ tion to the contrary. Finally, how does stumble, whose basic meaning is related to spatial motion and obstacles get interpreted in a narrative about international eco­ nomic policies?

We have implemented a computational model that is able to reason about action and event descriptions from discourse fragments such as the one above. The system uses an active event representation that also seems to provide natural and cognitively motivated solutions to classical problems in logical theories of reasoning about actions. We first present the main features of our rep­ resentation and show that it provides a computational model for existing formalisms for reasoning about ac­ tions. We then suggest how looking at story understand­ ing sets up fairly strong desiderata for logical approaches to reasoning about actions both in terms of the fine­ grained event and action distinctions and the kinds of real- time inferences required.

2 The Action Model

Our action theory comprises of two central components; 1) an executing representation of actions (called x­ schemas) based on extensions to Petri Nets and 2) a Be­ lief Net model of state that captures and reasons about complex dependencies between state variables.

2.1 An Executing Semantics of Actions

We represent actions as a modified class of high-level Petri Nets [Reisig, 1985] called x-schemas. The most relevant features of Petri nets for our purposes are their ab ility to model events and states in a distributed system and the clean manner in which they capture sequential­ ity, concurrency and event-based asynchronous control.

Definition 1 . The basic x-schema: An x-schema consists of places( P) and Transitions ( T) connected by weighted directed arcs A (A E (P x T) U (T x P) ). Each arc a;j E A has weight Wij ( Wij E N ) . In­ put Arcs *T ( *T E (P x T)) connect Input Places to Transitions. Output Arcs T * ( T * E (T x P)) connect Transitions to Output Places. Arcs are typed as enable arcs [ , inhibitory arcs I , or resource arcs R .

X-schemas have a well specified real-time execution se­ mantics where the next state function is specified by the firing rule. In order to simulate the dynamic be­ havior of a system, a Marking (distribution of tokens in places (depicted as dark circles or numbers)) of the x-schema is changed accord ing to the following firing rule.

Definition 2 . Execution Semantics of the basic x-schema A transition T is said to be enabled if no inhibitory arc i E I of T has a marked source place and all sources of enable arcs e E E of T are marked and all input arcs p E R have at least Wpt tokens at their source place, where Wpt is the weight of the arc from P to T . The firing of an enabled transition T , removes wpr tokens from the source of each non­ inhibitory, non-enabled input arc P and places wrp tokens in each output place of T.

X-schemas cleanly capture sequentiality, concurrency and event-based asynchronous control; with our exten­ sions they also model hierarchy, stochasticity and pa­ rameterization (run-time bindings). Besides typed arcs (Definition 1) , the following two extensions to the basic Petri net are designed to allow us to model hierarchical action sets with variables and parameters:

First, tokens carry information (i.e. they are individ­ uated and typed) and transitions are augmented with predicates which select tokens from input places based on the token type, as well as relate the type of the tokens produced by the firing to the types of tokens removed from the input .

Second, transitions are typed. Figure 1 shows the four types of x-schema transitions, namely stochastic, dura­ tive, instantaneous and hierarchical transitions. An in­ stantaneous transition(shown as dark rectangles) fires as soon as it is enabled. A timed transition (shown as rect­ angles) fires after a fixed delay or at an exponentially distributed rate . Hierarchical transitions (depicted as hexagons) , activate a subnet, wait for its return , or time­ out.

Theor em 1 . [Narayanan, 1997] An x-schema is for­ mally equivalent to bounded High Level Generalized Stochastic Petri Net {HLGSPN). The reachability graph of a marked x-schema is isomorphic to a semi-markov process.

2.2 A Belief Net Model of States

Our representation of states must be capable of model­ ing causal knowledge and be able to support both belief updates and revisions in computing the global impact of new observations and evidence both from direct ob­ servations and from action effects. Our implementation of the agent's state uses Belief Networks [Jensen, 1996].

Belief networks consist of a set of variables and a set of directed links. Each variable has a finite set of mu­ tually exclusive states. The variables together form a DAG (Directed Acyclic Graph). To each variable A with parents E1 ... En there is attached a conditional probability table P(AIE1, ... En) _1

For a Belief Net E,. , the following theorem allows us to calculate the joint probability P(U) from the condi­ tional probabilities in the network.

Theorem 2 . The Chain Rule[Jensen, 1996] Let E,. be a BN over U = (A1 ... An) . Then the joint proba­ bility distribution P( U) is the product of all conditional probabilities specified in E,. .

where pa(A;) is the parent set of A;

2.3 Temporal Projection

We now turn to one of the central issues in reasoning about action, i.e. the temporal projection problem. The problem consists of computing a final state Sn+l that results from executing the action set S = [a 1 , ... an] in a given initial state sa . The solution to this problem in our action model follows.

1 Note that the CPT entries could instead use the rank­ ing function method of K. -calculus [Goldszmidt, 1992], where probabilities are mapped onto a quantized logarithmic scale which forms the basis of a ranking function.

Algorithm 1 Temporal Projection

1. Set initial Marking Mo. Vp E sa : Mo(P) = 1, Vp ~ sa: Mo(P) = 0 .
2. Fire enabled transitions Te 0 E T of M with initial marking Mo . The next state function described earlier takes the system to a new marking Minto . The state corresponding to this marking Sint = lfp : Mint(P) = 1: P E Sint, lfp: Ml(P) = 0: P ~ Sint ·
3. Run the belieLpropagate procedure to return the most consistent aposteriori assignment ( MAP ) of values to the state variables. The new state S1 corresponds to the marking M1 where lfp E S1 : MI(P)=1 , Vp~sl :MI(P)=O.
4. While 1 ::; i ::; n , do: Fire enabled transitions Te;_ 1 with marking M;. set Mint = *a; U M;. Run Step 3 to get S;+1 . Return Sn+I as the answer.

·

Steps 1, and 2 are essentially constant time, since our notion of state as a graph marking is inherently dis­ tributed over the network, so the working memory of an x-schema-based inference system is distributed over the entire set of x-schemas and state features. The result is a massively parallel solution to the projection problem. Step 3 requires belief propagation which is well known to be intractable for complex domain topologies. So in our model, executing actions is fast, parallel and reflexive, while propagating indirect effects with complex domain dependencies to achieve global consistency is hard. In addition, the central features of our action representa­ tion, namely that they are executing provides an elegant solution to the Frame Problem. Specifically, the action­ based executing action semantics allows frame axioms to be implicitly encoded in the structure of the net and the local transition firing rules .

3 Modeling Action Theories

Although the mechanisms outlined above were developed for language understanding, they seem to be useful for some of the problems discussed in the recent literature. We assume the reader is familiar with reasoning with the syntax of action models similar to [Gelfond & Lifschitz , 1993]. To keep the exposition simple, we will consider only propositional fluents and deterministic actions. As in ARD [Giunchiglia & Lifschitz, 1995] , we model both "inertial" (always C (where C is a formula)) and "de­ pendent" (A depends_on B ) fluents . The following rules present the basic encoding of action theories (as­ suming the syntax of the ARD theory) in our model.

1. Static Fluent names are places. Actions names are Transition labels . Preconditions are pre-sets ( *T ), direct effects are post-sets ( T *) of transitions. If the truth-value of a fluent f E F is true, in State S; , then the marking M;(f) = 1 . 2
2. Domain Constraints with inertial fluents are mod­ elled as instantaneous transitions . Statements in ARD , of the form always A ::J B , add an instan­ taneous transition with pre-set *TAB = A , post-set TAB* = A, B . Dependent fluents are modeled as arcs in the Agent state belief net. More precisely, the statement fi depends....on f; if fk , results in an arc from the variables representing f;, fk to /j . The CPT entries for /j are given by the appro­ priate constraints (including prior knowledge) .
3. Initially C, is modeled by assigning an initial marking where Vf E Fnc: Mo(f) = 1. V/;,fj E F , if J; depends....on /j , add an instantaneous transition TI:r with preset *TI:r = /j and post set TI:r* = /;, fi .

We now look at two standard examples from the liter­ ature that illustrate some issues with reasoning about actions. One is the standard "potato in the tailpipe" problem, and the other is · the "jumping into lakes" problem[Giunchiglia & Lifschitz, 1995].

Example 1 Potato in Tailpipe The state flu­ ents here are potato (potato in the tailpipe) , clog (tailpipe is clogged) . The actions are PuLp , Remove_p (put/remove potato in/from tailpipe) , Start (start the engine). The domain is characterized as PuLp causes potato, Remove_p causes ·potato Start causes runnmg, clog depends....on potato, always potato ::J clog . ·

Example 2 Wetness Here the idea is that Jump­ ing into a lake ( J umpi n) has the direct effect of being I nLake , and the indirect of making you Wet . Jump­ ing out gets you out of the lake, but you are still wet if you were in the lake. The domain is described in ARD as always Inlake ::J Wet , J umpi n causes I nLake , JumpOut causes ·InLake, Initially ·InLake. ·

The reader can easily verify that the construction rules above result in the models shown in Figure 3 and Fig­ ure 2 for Example 2 and Example 1 respectively.

Proposition 1 . The procedure above results zn a causal model for a domain description D (in the Syn­ tax of ARD) in that it satisfies all the causal laws in D . Furthermore, a value proposition of the form C after A is entailed by D iff Vc E C, c E S; where S; is the state that results after running the proJection algorithm on the action set A .

2 In general, the representation allows states with types and integer measure fluents, in which case the multi-set rep­ resenting the place would be marked by the appropriate num­ ber and type of tokens.

3.1 Ramifications, Inertial and Dependent Fluents

Indirect effects are quite naturally handled by our sys­ tem. Indirect effects that are "inertial fluents" get set by instantaneous transitions. In Figure 3, the di­ rect effect of Jumpln sets the fluent lnlake, which in­ stantaneously sets the value of the fluent Wet . Note that the fluent Wet persists unless some other action is taken (like drying) to change the value of this fluent. In contrast, note that in Figure 2, the truth value of the 'dependent fluent" clog is determined by the fluent potato. While the value proposition -,potato 1\ -,clog after puLpot ; remove_pot , is not entailed by the de­ scription depicted in Figure 2 (from the uniform prior for P(clogJ-,potato) ); if the domain theory contains the explicit knowledge initially -,clog 1\ -,potato, the propo­ sition is entailed by the model. 3

4 Understanding Language About Actions and Events

The frequency with which languages refer to events, the universality of such expressions, and the subtlety in the kinds of distinctions made have made the temporal char­ acter of events in language (called linguistic aspect) an object of study since Aristotle. Somewhat more recently, the complex and context-sensitive determination of as­ pectual status, or the internal temporal shape of an event has been the focus of much work [MS , 1988] .

Many languages have a variety of grammatical aspectual modifiers such as the English progressive construction

3 More generally, logical entailment can be viewed as the downward closure of the final marking.

(be + V-ing) which enable a speaker to focus on the ongoing nature of an underlying process while allowing for inferences that the process has started and that it has not yet completed. Similarly, one use of the perfect construction (has V-ed) allows a speaker to specify that some consequences of the described situation hold. For instance, the phrase I have lost my keys entails that the keys are still missing (unlike the phrase I lost my keys). Languages also have a variety of other means to express aspect including aspectual verbs like start, end, cease, continue, and stop and related grammatical forms.

To model the kinds of subtle semantic distinctions made by languages, actions and events can no more be atomic transitions. In fact, we have found that cross-linguistically language makes reference to a specific structure of actions and events, which captures regular­ ities that are relevant in the evolution of processes (en­ abling, inception, in-process, completion, suspension, re­ sumption, etc.) We call this structure the CONTROLLER (Figure 4). The controller abstraction seems to capture the basic temporal structure of people's conceptualiza­ tion of events. The semantics of aspect arises from the dynamic binding between verb-specific x-schemas and a controller that captures regularities in the evolution of complex events, shown in Figure 4.

In our language understanding system, the causal do­ main structure is encoded as connected x-schemas . Our domq.in model is a dynamic system based on inter-x­ schema activation, inhibition and interruption. In the simulation framework, whenever an executing x-schema makes a CONTROLLER transition, it potentially modi­ fies state, leading to asynchronous and parallel trigger­ ing or inhibition of other x-schemas. The notion of state as a graph marking is inherently distributed over the network, so the working memory of an x-schema-based inference system is distributed over the entire set of x­ schemas and state fluents . Of course, this is intended to model the massively parallel computation of the brain.

Figure 5 depicts a simplified x-schema model of walk­ ing and reacting to obstacles (the domain of stumbling).

For instance, during a walk (specified by a token in the ongoing phase of the WALK x-schema) encountering an unanticipated bump, you become unstable. 4 This may lead to a FALL unless you are able to simultaneously expend energy and STABILIZE, in which case you may resume the interrupted walk. If you are unable to STA­ BILIZE, and thus FALL, you will be down and hurt .

Now consider that this complex situation described above can be coded in a single lexical item stumble! First, notice that stumble can only occur during a STEP, and that it is a specific kind of interrupt to the step (i.e. the presence of a bump or stumbling block). But this by itself does not capture the intended meaning of stumble, since the inference (that the agent may fall) is routinely intended by the speaker. Furthermore, note that the fact that stumble is not a planned motion but an interrupt is important to infer that it is unintentional.

It should be clear that to model linguistic distinctions in event structure, we need much finer-grained distinc­ tions than those that been proposed in the literature for reasoning about actions. This is also consistent with the key observation in [MS , 1988] that aspectual phenom­ ena depend on a notion of event structure that captures contingency relationships among events. Our frame­ work of an active action semantics embodies a precise model of such inter-event contingency.

While our solutions to the problems of aspect are out­ side the scope of this paper, the following inter-schema activation, inhibition, and modification relationships are intended to give the reader an idea of the fine-grained nature of contingency relationships involved.

Definition 3 . Activation: Activation relationships between schemas correspond to the case where execut­ ing one schema causes the enabling, start or continued execution of another schema. We are able to distinguish concurrent from sequential activation.

4 ln fact , the simulation is of finer granularity in that it is during an ongoing STEP (subschema of WALK), that the interruption occurs. This is not shown to simplify exposition.

X activates Y (Act (X, Y) :X, Y E SS) if some sub­ set p of places marked in the result state P(Xr) of X ( p ~ P(Xr)) enable the start transition of Y ( p ~ *T(Ys) ). X enables Y if ( p * T(Ys) i.e. *T(Ys) ~ P(Xr )).

seq_enables(X, Y): done(X) 1\(p E P(Xr)) 1\ (p ~ *T(Y/)) conc_enables(X, Y): ongoing(X)/\(p E P(Xp))/\(p ~ *T(Y/)) inh_periodic(X) : seq_enables(X, X) mut....enables(X, Y) : seq_enables(X, Y) 1\ seq_enables(Y ,X)

Definition 4 . Inhibition: Inhibitory links prevent execution of the inhibited x-schema by activating an inhibitory arc. Again, our model is able to distinguish between concurrent and sequential inhibition as well as be able to model mutual inhibition and aperiodicity.

X inhibits Y ( Inh (X, Y) :X, Y E SS) if some subset p of places marked in the done state of· X P(Xr) ( p E P(Xr) ) are inhibitor arcs for the start transition of Y ( p ~ *T(Ys) ) . X disables Y if ( p * T(Ys) i.e. *Inh(Ys) ~ P(Xr )).

seq_disables(X, Y): done( X) 1\(p E P(Xr )) 1\ (p ~ *T(Ye-))

conc_disables(X, Y) : ongoing(X)/\(p E P(Xp))/\(p ~ *T(Ye-))

inh...a.periodic(X) : seq_disables(X, X) mut_disables(X, Y) : seq_disables(X, Y) 1\ seq _disables (Y ,X)

Definition 5 . Modification: Modifying relationships between x-schemas occur when the execution of the mod­ ifying x-schema results in setting the Agent State in such a way the the currently active modified x-schema under­ goes a controller state transition.

interrupts(X, Y): ongoing(Y) 1\(p E P(X))) 1\ (p :>

*T(Y";~h)) prevents( X, Y) enabled(Y) 1\ ·stm·t(Y) 1\ (p E P(Xr)) 1\ (p E *T(Y.-)) terminates( X, Y) : ongoing(Y) 1\ (p E P(Xr )) 1\ (p 2 *T(Y/)) resumes( X, Y) : suspended(Y) 1\ (p E P(Xr )) 1\ (p :> *T(Y";~t)) stops(X, Y) : (suspended(Y) V ongoing(Y)) 1\ (p E P(Xr)) 1\ (p 2 *T(Yc~ase))

Example 3 Examples of contingency relations in the Walking Domain

TRIP seq_enables FALL 1\ STABILIZE. ·in_control(loc) enables FALL ·stable enables STABILIZE GRASPING(x) conc_enables HoLDING(x).

Energy(x) isa_resource for WALK

WALK is mut-exclusive to RuN. STABILIZE seq_disables FALL. In_control(Ioc) disables FALL GETUP resumes WALK. Standing enables WALK REACH(x) terminates WALK(x).

·

4.1 Metaphoric Reasoning about Actions and Events

We have seen how the structure of actions and events is grounded in fine-grained, dynamic representations. An­ other ubiquitous phenomenon in language[Lakoff, 1994], is the routine projection of such fine-grained seman­ tic distinctions across domains. Systematic metaphors project features of these representations (source) onto abstract domains such as economics (target) enabling linguistic devices to use embodied causal terms to de­ scribe features of abstract actions and processes.

Figure 6 shows an implemented system that uses pro­ jections of the action representation outlined earlier to interpret such sentences. In our model indirect effects of x-schema execution now not only propagate to depen­ dent source domain ftuents but may also be mapped by metaphor maps to other abstract domains (modeled as a temporally extended Belief Net).

Continuing with the stumble example, notice that in our model effects of spatial inferences such as stumbling leads to falling can felicitously be transferred to the abstract domain of economic policy through a conventionalized metaphor that falling r--+ failure, enabling the inference of plan failure. This inference context-sensitive and may be overridden by prior knowledge (in the target domain Belief Net) that the liberalization plan is succeeding.

5 Conclusion

This paper described a new framework for reasoning about actions that is motivated from story understand­ ing. One central feature of this framework is an ex­ tremely fine-grained action model with a real-time ex­ ecution semantics that is able to capture a much richer notion of contingency and causality than other models we are aware of. Another key feature is our model of state where complex dependencies between state vari­ ables are modeled as a Belief Network. We showed how this framework is able to reason about actions, ramifi­ cations with inertial and dependent ftuents, as well as inter-domain mappings which are crucial in story un­ derstanding. We believe that looking further into issues in narrative (such as into force-dynamics, modals, and mental spaces) can yield valuable insights that can help us build useful theories of reasoning about actions.

6 Acknowledgments

Thanks to J. Feldman, G. Lakoff and the NTL group at UC Berkeley and ICSI.