Exploiting Domain structure to Achieve Efficient Temporal Reasoning

1 Introduction

Temporal reasoning (TR) has become identified in the literature, e.g. [Kautz and Ladkin, 1991], [Dechter d al., 1991], [Meiri, 1991], as a domain-independent prob­ lem of constraint satisfaction: given (1) a set of temporal individuals (time points and/or inter~als), (2) expl~cit constraints on their temporal separatiOn, and (3) Im­ plicit. constraints like the interval transitivity relations of [Allen, 1983] or the transitivi~y properties of Euclidean metric distance, compute the t1ghtest bounds on the sep­ aration of any two individuals. [Dean and McDermottj 1987], [Koomen, 1988], and [Kautz and Ladkin, 1991 report on implementations of these domain-independent algorithms.

·This work was supported in pa.rt by NSF gra.uts IRI9008670 a.nd IRI-9206733 a.nd by a.n NSF Gra.dua.te Research Fellowship. Thanks to Da.n Weld for commenting ou a.u ear­ lier dra.ft._

There have been two predominant approaches to tem­ poral reasoning. lntertJal-based systems, [Allen, ~9.83] take intervals to be the fundamental temporal ent1t1es, and allow the specification of qualitative constraints that hold between intervals. Systems based on time points [Dean and McDermott, 1987; Dechter eta/., 1991], on the other hand, take instants in time (points) to be the fundamental temporal entities, and allow both qualitative and metric constraints among those in~i­ viduals. (Constraints specify that the temporal das­ tance between two time points falls within some par­ ticular interval.) There has been a significant amount of work comparing these two approaches, and also some recent. work showing how the two frameworks can be unified [Vilain ct a/., 1989; Kautz and Ladkin, 1991; Meiri, 1991].

Analysis of these systems reveals a clear tradeoff be­ tween the expressive power of the constraint language and the worst-case running time_ of the constraint prop­ agation algorithm, t.radeoffs that hold regardless of the underlying representation. Detailed analysis of these result.s is beyond the scope of this paper, but shows that "simple" constraints 1 over either a time-point or time-interval-based syst.em admit an O(n 3 ) solution al­ gorithm, where n is the number of temporal individuals (points or intervals). Simple constraints cannot repre­ sent. certain disjunctive information, however, and al­ gorithms for processing sets of un.rest_ricte~ disjunctive constraints require time exponent.1al m n m the worst case.

1 See [Dechter et cd., 1991] a.ud [Vila.in et al., 1989] for a. precise definition of simple constraints. ~Da.vis, 198~] a.na.­ lyzes this tradeoff as well . We defer a. deta.iled compa.nson of

these systems to [Williamson a.nd Ha.nks, 1993].

Many application areas in AI do some sort. of tempo­ ral causal reasoning: reasoning about. changes in propo­ sitions, the occurrence of events, and so on. Planning, temporal project"ion, motivation analysis, and qualita­ tive simulation are prominent examples. Causal reason­ ing in turn requires temporal reasoning, t.o keep track of the durations of events, the time at. which propositions change state, and so on.

These formal results about. temporal-reasoning algo­ rithms are troublesome to programs that. do causal rea­ soning. Causal reasoning almost always involves some sort. of disjunction, as discussions in [Hanks, 1990a], [Dechter et a/., 1991], and [Weld and de Kleer, HJ89, Chapter 2] demonstrate, so simple temporal constraints will not generally suffice.

Moreover, the applicat.ion program may generate great. numbers of temporal individuals, and will call the TR module many times in the course of doing higher-level causal reasoning. Experiments in [Hanks, 1990b] show that projecting a plan of roughly 25 steps generates about 400 time points, and that about. 65% of the projec­ tor's time is spent performing temporal-reasoning tasks. Even the cubic TR algorithm will be unacceptable for most applications.

We must conclude, then, that domain-independent. or "uninformed" temporal reasoning is too slow t.o support. reasonable application-program performance. In this pa­ per we advance the idea that t.he ap.plicat.ion domain can provide the "information" that. allows temporal reason­ ing to be efficient . The temporal constraints imposed by an application, and the queries it. typically poses t.o the TR module, are structured and regular. A TR mod­ ule can exploit this structure and these regularities and by doing so can provide appropriate functionality while delivering acceptable performance.

We demonstrate our approach by considering a par­ ticular causal reasoning problem, a simplified version of plan projection under uncertainty [Hanks, 1990a] and [Hanks, 1990b]. We define formally the plan lan­ guage used by the projector and a corresponding struc­ tured representation for the temporal information it. generates. The representation, called lticmn:ltical in­ terval constraints (HIC), combines time point. and in­ terval information in a nested format. that. mirrors the structure of the projector's plans. We implement. a temporal-constraint. propagator using the HIC represen­ tation, then run experiments by instantiating a sim­ ple prot"ection algorithm using our HIC propagator, Dean's 1987] time-map manager, and Kautz and Lad­ kin's [1991] MATS system as subroutines. The HIC sys­ tem runs faster by orders of magnitude; furthermore, its performance degrades more slowly as problem size in­ creases.

2 The Plan Projection Problem

[Hanks, 1990a] discusses the problem of projecting to­ tally ordered sequences of actions under uncertainty. U n­ certainty about .the state of the world or the effec.t.s of au action means that an action sequence (plan) may have many possible outcomes. The projector builds a sct:rwr·io trn: 2 , whieh is a temporal trace of the plan's execution. Eaeh path through the tree, a chronicle, is one possi­ ble, internally coherent. course of execution. The projec­ tion problem is to control branching in the scenario tree while still being able extract. useful information about the plan's effects.

We will simplify the projection problem somewhat:

• Instead of the probabilistic representation in [Hanks, 1990a] we will use a three-valued truth as­ signment. tr·uc, false, unknown for each proposition. A world state then consists of propositions along with their truth assignments. Any proposition not tr·uc or false is assumed to be unknown.
• A simple action eonsist.s of a name and a set of out­ comes. Each outcome is a pair, (condition, effect). The condition describes the world states in which t.he corresponding effect. will be realized-a condi­ tion is a set of propositions. The corresponding ef­ feet. eonsist.s of a dumtion (a time interval) and a set of proposition/truth-value pairs.

The idea is that if, at execution time, all of a condi­ tion's propositions are tr·ue, then all of the effect. 's propositions will take on the corresponding truth value. We require that an action's conditions be mu­ tually exdusive and exhaustive, so at execution time exaet.ly one out.eome will be realized. The projec­ tor may not. know which one, however, since one or more o{J.he aet.ion's conditions may have truth value unknotJm. Projecting a simple action will cause a braneh in the seenario tree each time more than one of an action's outcomes has a condition that evaluates to tntc or unknown.

• From the simple actions we define complex actions representing sequential, parallel, conditional, and it­ erated execution of simple act.ions 3 .

If a1, a2, ... an are actions and P is a proposition, then the following are actions too:

• (while P a1)

The projection algorithm is presented with an initial world state and an act.ion. It. projects the action fully, branehing every time a Sl!baction has multiple possible outcomes.

Consider, for example, projecting a plan such as (seq a b c d) . Suppose that. the projector can identify a sin­ gle outeome for eaeh aet.ion except. c, 4 which has two possible out.eomes. Figure 1(a) shows what the scenario tree would look like. The nodes in the tree represent the outeomes of the primitive actions in the plan. There are two ehronicles, representing the two possible courses of exeeution .

2 This structure is similar to au en11isionment graph, [Davis, l!J!JO, Chapter 4] .

3 [Shaw, 1989] uses similar program-description operators.

4 Tha.t is, exactly one condition for a, b, and d evaluates to true.

Figure 1: Projection Example

The projector may then have to answer questions both about the states of propositions at various points of time-"is P true when action A is executed?" "is G true when the plan finishes executing?" -and also tem­ poral queries like "how long will the plan take to ex­ ecute?" and "will this segment of the plan take more than 15 minutes?'' We address queries only of the lat­ ter type, and furthermore, will concentrate mainly on temporal queries involving the distance separating time points within the same chronicle.

We will next describe the Hierarchical Interval Con­ st.raint structure, which is an attempt to mimic the sorts of temporal structures generated by the projector .

3 Hierarchical Interval Constraints

A hierarchical interval constraint. (HIC) represents an interval of time, and may comprise one or more subin­ tervals. Subintervals, if any, are also represented by HICs. The interval's duration-its minimum and maxi­ mum temporal length-depends on the two sorts of in­ formation: the durations of its subintervals, and the in­ terval's type. HIC types represent common temporal rea­ soning structures, some of which cannot be represented as simple temporal constraint graphs.

Formally, a HIC is a 3-tuple (r, CT, 6) , where

• T E {simple, sequence, selection, par·allcl} is the HIC type,
• CT = (h,I2 , ... ) is a list of sub-HIC's (or childn:n), and
• 6 = [61, 6h] is the temporal distance (duration) con­ straint denoted by the HIC.

(We may refer to the type, children, and duration of an arbitrary interval I as IT, I a, and I6 respectively.)

In the case when T = simple, the list CT must be empty, and the application must supply the duration 6. The du­ ration for a complex HIC (one whose type is not simple) is calculated according to the HIC's type and the dura­ tions of its children. See Table 1 for the specific definition of6 for each HIC type. A HIC's duration 6 is computed incrementally by the system when it. is defined, a process requiring time linear in the number of its children.

For example, imagine that we wish to reason about an action go-to-work, which will be carried out by performing one of two possible subactions: either by walk-to-work, taking from 30 to 40 minutes, or bike-to-work, taking from 10 to 15 minutes. We create simple HICs W and B to represent the last. two actions, and specify Wb = (30, 40] and B6 = [10, 15]. We then create a sdt:ction HIC, G, to represent the go-to-work action and specify that Ga = (B, W) . The system will calc.ulate that Gb = [10, 40] .

The dn;cur.dllnts of a HIC are its children, all their children, etc. (The terms par·ent and ancestor also have the obvious definition .) A HIC must. have at most one parent, and no HIC may be a descendant of itself; i.e. HICs must be properly nested. A top-level HIC is one that has no parent . A lt:af HIC has no children. Leaves must be type simple.

Our temporal reasoning module reasons about isolated time points in addition to these HIC structures. Time points may be useful to represent the occurrence of ex­ ogenous events, or to synchronize the plan's execution with known dock times. Time points are integrated with HIC struc.t.ures to form an arbitrary temporal constraint graph (TCG), with time points as the vertices and top­ level HICs as the edges. If all of the HICs were of type simplt: and sequence, the expressive power of the sys­ tem would be equivalent to a network consisting of sim­ ple temporal constraints as described in [Dechter et a/., 1UU1]. This is also equivalent to the constraints allowed by the TMM system [Dean and McDermott, 1987].

The additional HIC types, sdection and parallel, sig­ nificantly increase the expressive power of the system. They allow an application to represent and reason effi­ ciently about commonly occurring temporal situations which previously existing formalisms could only accom­ modate by resorting to more general, exponential-time algorithms. An example of this is the go-to-work situ­ ation desc.ribed above. Simple temporal constraint net­ works (in the technical sense of [Dechter et a/., 1991]) cannot represent this situation at all . General temporal constraint networks can find the more precise solution Gb = [10, 15] U [30, 40], but. are NP-Hard to solve.

Temporal queries re(luest. the distance between two time points, which may be the beginning or end of any hierarchical interval (known as tJirtual time points), or one of the isolated time points in the TCG.

We compute the temporal distance between two time points as follows :

• If the two time points are both endpoints of HICs that share some common ancestor we compute the distance from each time point. .to each end point. of that common ancestor. Although this requires time exponential ( 0{2d)) in the depth of nest.ing of the HICs, this is still at most linear in the number of descendants of the intervals' common ancest.or 5 .
• If the two time points are not end points of HICs that share a common ancestor, or if either of them is an isolated time point in the TCG, we have no choice but to propagate bounds through the entire graph. We use the Floyd-Warshall transitive closure algorithm, which is O(n 3 ) in the number of explicit. time points, but independent. of the number of HICs. (The algorithm requires only the lengths of the t.op­ lev,el HICs, which have been pre-computed.)

[Wil.liamson and Hanks, 1993] provides a complete dis­ cussion of the query algorithm and its computational complexity.

Our algorithm's computational advantage derives from the fact that it allows the application t.o represent. a temporal reasoning situation using the HIC framework almost exclusively-only a small number of explicit. time points are typically required. In fact most. queries do not. require solution of the solution the TCG at. all and even when the entire graph must be considered it. is much smaller than it would be if the same situation had been represented using existing, uninformed TR systems.

By letting the application provide information about. the structure of the TR task, HICs effectively allow the query algorithm to ignore constraints irrelevant. to the particular query. As a striking example, we shall con­ sider our plan projection application, which does not. re­ quire the construction of a TCG at. all, but. represents the projection scenario in a single nested HIC structure.

3.1 HICs in Plan Projection

HIC types simple, sequence, selection, and para/It:/ di­ rectly support the plan projection task. A simple HIC represents a single, atomic action. It has no sub­ intervals, and its temporal lengt.h (minimum and max­ imum) is supplied by the application. A sequmcc HIC represents two situations: a compound action composed of a number of sub-actions executed sequentially, as well as a series of adjacent actions each with a single outcome, In other words, a scenario tree with a single branch ap­ pears as a sequence interval constraint..

Selection HICs represent. actions that. have more than one possible outcome due to uncertainty: A sub-HIC is created for each possible outcome.

As an example, consider projection of the plan men­ tioned above, which gave rise to the chronicle tree in Figure 1(a). Figure 1(b) shows the corresponding HIC struct~re . The smallest boxes are simple intervals rep­ resentmg the outcomes of each primitive action. El is a selection HIC representing the fork in the scenario tree. The fact that it. is a selection HIC codes the information that exactly one of the branches will actually be realized at. execution time. Sl, S2 and S3 are sequence HICs Sl representing the temporal interval over which the en,tire plan is executed.

5 Assuming tha.t ea.ch non-lea.£ HIC has two or more children.

Queries to the temporal-reasoning module might ask about. the amount. of time separating any two time points: the beginning or end of any pair of the struc­ t.tue's intervals. Note again that neither the initial pro­ jection task nor queries involving the plans steps require const.ructiou of a temporal constraint graph. We rep­ resent the entire scenario tree in a single, nested HIC structure, meaning that. temporal queri~ will require at worst. time linear in the number of time points. In many cases the time required will be significantly less.

An example of the increased expressiveness of our sys­ tem is that. the duration of the entire plan can be ob­ tained with a single temporal query. Existing implemen­ tations based on simple temporal constraint networks would require the application t.o minimize and maximize over the durations of each individual chronicle to obtain the same information.

4 Empirical Results

We implemented our projector on top of three different T!t modules: our own HIC system, the Metric(Allen T1me System (MATS) of Kautz and Ladkin 1991], and the temporal reasoning component of Dean's [1987] TMM. All systems were implemented in Common Lisp, and t.est.s w·~re run on t.he same machine under similar loading. We will first. describe how we implemented the projector using the other two temporal-reasoning mod­ ules, then report. the comparative result.s.

TMM's temporal reasoning facility essentially builds a graph of time points constrained by simple interval met­ ric constraints. TMM allows no disjunctive constraints. We represented the projected plan's scenario tree by cre­ ating a pair of time points to represent the beginning and ending of each plan outcome, which were then con­ strained by t.he associated action's duration. The end point. of each outcome and the begin point(s) of the fol­ lowing out.come(s)·were constrained t.o be consecutive by adding the constraint. [0, 0] between them.

The MATS system integrates metric information into Allen's framework of qualitative interval relationships. I!· allows the creation of temporal intervals, specifica­ t.lon of their qualitative relationships, and specification of interval-valued metric constraints between the end points of intervals. We represented the scenario tree by creating an interval for each action outcome. The duration of "J.ch outcome's interval once again has the application-supplied duration. Intervals for successive outcomes are constrained t.o meet each other.

For each implementation we projected plans that gen­ erated scenario trees of various sizes. We then performed 100 random temporal queries on the resulting temporal structures. The plans were all less than ten steps long. We changed the number of possible outcomes in the sce­ nario tree by varying the number of possible outcomes for the first. action. In effect this introduced uncertainty early in the projection. The number of initial branches varied between one and eight; doubling the number of initial branches essentially doubles the size of the result.­ ing scenario tree.

We formed a temporal query by randomly choosing a chronicle from the tree, choosing two out.c.omes from that chronicle, and then choosing one of the end points of each of those outcomes. Table 2 shows the CPU time (in milliseconds on a DECst.at.ion 5000) required for pro­ jection and query processing.

Note that. the query time required by the MATS sys­ tem is cubic in the size of the scenario tree, making it. completely impractical for larger problems. (MATS also requires space quadratic in the size of the tree.) MATS spends almost all of its query-processing time in c.om­ puting the solution for the entire TCG, which is t.htm cached. MATS would therefore take essentially the same amount of time to process one query as it. did to process alllOO queries. TMM and HIC, on the other hand, c.om­ pute query answers incrementally, and would therefore process a single query roughly 100 times faster .

TMM's temporal reasoning mechanism required only linear time to answer queries, but. seemed to re<JUire quadratic time to construct the constraint graph ini­ tially; we discuss TMM's propagation mechanism below.

Our HIC system required only linear time for projec­ tion, and performed queries in sub-linear time. This is possible because the constraint network's structure al­ lows the query algorithm to isolate a particular chronicle and ignore the (irrelevant.) constraints in the others.

These results suggest. that. our system is capable of handling projection problems several orders of magni­ tude larger than either of the alternative implementa­ tions.

5 Related Work

[Kautz and Ladkin, 1991) and [Decht.er ct al., 1991) both present metric TR algorithms that are c.omplet.ely do­ main independent.. We noted above our opinion that these algorithms are mainly useful for pointing out explicitly the tradeoffs between expressive power and speed. We doubt that. either algorithm, implemented without problem-dependent. optimizations, will prove useful for applications of a reasonable size. 6

[Allen, 1983] introduces the notion of a r·cfa·cncc intc:r·­ va/7 as a means of controlling temporal inference. Each interval added t.o the database is assigned to one or more reference intervals, and the system caches the full inter­ val transitivity table for all the intervals c.ont.ained within a given reference interval. To infer the relationships be­ tween two intervals that do not share a reference interval the system searches for a path between the two intervals, restricting its search to reference intervals alone. Allen discusses the possibility of applying this idea to the prob­ lem of reasoning about events and processes, though he does not implement such a system. We provide an im­ plementation, and furthermore extend the temporal represent.at.ion to include quantitative as well as qualitative const.raint.s.

6 0n the other hand, the MATS implementation a.va.ila.hle through [Kautz and La.dkin, 1991] is extremely elegant ami easy to use, and so provides a. nice vehicle for exploring sma.ll problems.

7 Allen in turn acknowledges [Kahn and Garry, 1977] .

The Timt t Jgic system of [Koomen, 1988) implements a temporal reasoning algorithm based on Allen's quali­ tative interval framework . It. provides an algorithm for building reference-interval structures automatically. In some sense Koomen's approach is diametrically opposed to our own. Both approaches recognize that an appli­ cation's c.onst.raint.s and queries exhibit. regularities, and furthermore that exploiting these regularities is crucial to achieving good performance. In Koomen 's system the application adds c.onstraint.s without communicating that st.mct.ure to the temporal database module; Timelogir. redisc.overs that. structure by constructing an appropri­ ate hierarchy of reference int.ervals. Our approach allows t.he application to communicate its temporal structure directly, which is then inc.orporat.ed into the structure of the temporal database itself.

Dean's [19!Jl) time-map manager (TMM) implements both causal and temporal reasoning patterns. Its temporal-reasoning mechanism constructs graphs whose nodes are time points connected by simple metric con­ straints. It. implements a hemistic, limited-depth search t.o infer t.he uwst. restrictive constraints binding any two poiut.s in the graph. Underlying this scheme is the as­ sumption that. paths through the constraint graph will be short. . The search can be quite efficient if the assump­ tion holds, but. if it. is violated-if the graph contains long paths or is highly connected-its performance can degrade t.o worse than the standard 0( n 3 ) algorithms. And since the algorithm abandons paths that exceed a constant. bound, it can potentially report incorrect re­ sults.

A second notable feature of TMM is its temporal in­ dexing scheme. This technique, which is also similar t.o reference intervals, allows the application to provide information about. the granularity of the temporal rea­ soning problem so that. time points can be indexed for more efficient. retrieval. This functionality is an impor­ tant step toward the kind of informed temporal reasoning necessary for realistic applications.

Our work also builds on the work in [Hanks, 1987], which was an early attempt to optimize a temporal database manager to perform tasks like temporal infer­ encing, temporally scoped database fetches, and hypo­ thetical reasoning about the future, under conditions of uncertainty and ignorance.

6 Conclusion

Formal explorations of temporal-reasoning algorithms have made the t.radeoffs between expressive power and computational efficiency extremely clear. The results point out. that. an application cannot use a domain­ independent temporal constraint. propagator and expect reasonable performance: reasonable functionality comes at the price of an exponential algorithm, and the algo­ rithms are too slow in the worst case even under the most restrictive limitations.

Our paper has shown how to build an efficient. t.empo­ ral rea.r;oning module by exploiting regularities both in the c.onst.raint.s typically added by the application and in the queries typically posed. We c.onsidered the prob­ lem of plan projection, and advanced a formal model of the problem's constraint structure. A temporal projec­ tor using an implementation of our model dramatically outperformed current domain-independent implementa­ tions in absolute terms, and furthermore showed better performance degradation as problem size grew.

It remains to be seen the extent to which our HIC model for temporal reasoning can be applied to other application domains, or whether a class of similar mod­ els can be developed for other applications. It. is d ear, however, that if a temporal-reasoning system is to be of practical value to a realistic implementation, it will have to have some model of its applications' behavior . Identifying a set of HIC-like structures offers a promising means of providing functionality midway between truly domain-independent. temporal reasoning and problem­ specific programs.