Scalable Temporal Reasoning

1 Introduction

Most of the challenging AI problems exhibit a computational complexity that is inherently intractable. In a seminal paper, Jerry Hobbs [1985] proposed a parsimonious reasoning mode based on different granularities of representation structures. He suggests to have a hierarchy of theories available- shal­ low ones that come with cheap computations, more sophis­ ticated ones that require increasing costs. Hence, a trade-off between expressiveness and computational resources is man­ aged by shifting between different granularity levels. The in­ trinsic mechanism needed in such a model are switching op­ erators that move from one representational layer to the other.

The necessity to account for different granularities in tem­ poral reasoning has been widely acknowledged in diverse applications such as natural language understanding [Nakhi­ movsky, 1988] or planning [Sathi et al., 1985]. Nevertheless, granularity has often only been considered as an addendum to temporal reasoning schemes [Bettini et al., 1997]. In con­ tradistinction, we treat granularity as a fundamental notion, one that underlies the relation between the most common temporal reasoning formalisms.

We here build on the notion of Generalized Temporal Net­ works (GTNs) as introduced by Staab [1998b]. GTNs (cf. Section 3 for an overview) constitute a highly expressive con­ straint formalism. They subsume several widely known tem­ poral reasoning approaches [Allen, 1983; Vilain et al., 1989; Kautz and Ladkin, 1991; Dechter et al., 1991; Meiri, 1996; Badaloni and Berati, 1996] and integrate them in a common

UdoHahn

(8 Text Understanding Lab Computational Linguistics Division Freiburg University D-79085 Freiburg, Germany

http://www.coling.uni-freiburg.de

framework. However, as Staab [1998b] concedes, reasoning at the most specific level of GTNs is not a panacea. What is lacking though is a mechanism that might mediate between the computation of complex temporal relations still requir­ ing resource-intensive constraint solvers at the high end of intractability, and the computation of simpler temporal rela­ tions for which tractable constraint systems might suffice. So, our goal is to extend the GTN framework such that a cas­ cade of constraint formalisms organized at different axes of expressiveness/computational complexity can be defined, to­ gether with operators for navigating this cascade to choose the appropriate level of constraint evaluation (cf. Section 4).

This scaling between different levels is also motivated by our natural language text understanding application [Staab and Hahn, 1997] that demands for reasoning in different tem­ poral granularities. The potential for abstraction is not lim­ ited to the internal representation and reasoning mode, but it is also useful for accessing the system from the outside via its interface (cf. Section 5). So, the ultimate goal is to support reasoning and access by uniform abstraction mechanisms.

The latter point deserves particular attention when basic re­ search results from the area of temporal reasoning are to move to public use, or even commercial applications. The availabil­ ity of flexible, easy-to-use, explanatory adequate interfaces has already proven to be a major asset in comparably com­ plex domains such as terminological reasoning (cf. McGuin­ ness and Patel-Schneider [1998]). In the framework of tem­ poral reasoning then, finding the right level of abstraction for querying is considered a crucial factor for enhanced us­ ability of temporal reasoners. Though very expressive mod­ els [Meiri, 1996; Staab, 1998b] might be required by the ac­ tual application, they usually do not lend themselves easily to communication with the human user or with high-level sys­ tem modules due to an overly fine grain size. In order to prop­ agate flexibility to the interface level, we abstract away irrel­ evant details from the low-level representations at the price of only approximate, though sufficiently explicit solutions. So, providing the right level of abstraction is also a matter of ade­ quacy of temporal reasoning, in general, and increased appli­ cability of temporal reasoners, in particular, rather than just a detrimental loss of expressiveness at the gain of lowering computation costs.

2 A Temporal Reasoning Scenario

In order to facilitate the understanding of the concepts we introduce, we here give an everyday scheduling problem that will be used throughout this paper for illustration purposes:

1. James is a shuttle driver for a major hotel in New York. Today's schedule posts Mr. Roget and Mr. Meyer from Paris, Mrs. Meyer from Philadelphia, and Mr. George from Sidney for transportation. The hotel's clerk told him that Mr. Roget and Mr. Meyer have tickets for different flights from Paris to NY. Mr. Roget is scheduled to arrive with the Concorde in NY at 3:00pm local time, and Mr. Meyer should arrive in NY two hours later. However, they currently try to arrange for shar­ ing a flight which would arrive in NY at 6:00pm local time. When Mr. Meyer arrives in NY he will immediately call his wife, Mrs. Meyer, who will get the next train to NY. Hence, she will be in NY less than 4 hours after her husband has arrived. Furthermore, Mr. George's flight leaves Sidney at l2:00pm lo­ cal NY time, and he has got a very long flight.

Problem: In which order must James service the guests?

3 The GTN Model

We here give a brief description of the GTN model, summa­ rizing those aspects relevant for the mechanisms of scaling­ the focus of this paper. A detailed explanation of GTNs and a comparison to related models is given in [Staab, 1998b].l

The GTN model builds on time point variables and re­ lations that describe restrictions between two or more vari­ ables at a time. A given network of relations is tightened by propagation, and thereby, conclusions are computed un­ til weakly generalized path consistency (WGPC) is reached. Relations consist of disjunctions of conjoined primitive con­ straints. Formally, a relation Rk comes in the following form:

Hereby, Pi,i,k,l = (Vi, Qi,j,k,l. vi) are constraints between the temporal variables Vi, vi E V, and Qi,j,k,l are intervals such that vi - Vi E Qi,j,k,l· Lk denotes the number of dis­ junctions of the relation Rk, and Ek denotes all pairs of time point variables between which a constraint of relation Rk may hold. The set of all relations {Rklk = 1 . . . M} is de­ noted by n; correspondingly, its topology £ is defined by {Ekik = 1 ... M}.

Thus, example (1) can be modeled in the following way:

1. a. l2:00pm: to
2. End of Mr. Roget's flight: t1
3. End of Mr. Meyer's flight: t2
4. Arrival of Mrs. Meyer in NY: f3
5. Beginning of Mr. George's flight: t4
6. End of Mr. George's flight: ts
7. If Mr. Roget arrives at 3:00pm, then Mr. Meyer ar­ rives two hours later; otherwise, they arrive together at 6:00pm: ((to, (3, 3], tt) /\ (tt, (2, 2), t2)) V ((to, (6, 6], h)/\ (t1, (0, OJ, t2))
8. Mrs. Meyer arrives less than 4 hours after her husband: (t2,(0,4),t3)
9. Mr. George has a very long flight:

(t4, ["very long", +oo), ts)

1. Mr. George's flight starts at !2:00pm: (to, (0, 0], t4 )

1 For proofs of the formal claims we make, cf. [Staab, 1998a].

In order to compose relations, propagate resulting restric­ tions, and determine when WGPC is reached, Staab [1998b] provides interval mappings,projection and subsumption. Re­ lying on these (and some other) auxiliary means, he states a constraint propagation algorithm that enforces WGPC on GTNs. This algorithm can be applied unaltered to the scaling problems we discuss here. We will now formally introduce those auxiliary means, because the notion of scalability we develop makes direct use of them.

First, we define the notion of projection:

Definition 1 The projection 7r : 2"R X £ I-t n is a binary function(7rx(Y) := 1r(y,x)). 7rE 9 (Rl /1. .·· 1\Rn) selects all constraints in R1 /1. .·. /1. Rn which affect the edges in E 9 . It is defined at three levels- that of simple conjoined constraints, of disjunctions of conjoined constraints, and of conjoined re­ lations. Its input is described by referring to sets (of tuples) K1, K2, and K3, respectively (Pk,l := 1\(v;,v;)EEk Pi,j,k,z):

An example for 1r is given in (4) which incorporates the information given in (3g):

Second, the GTN model allows for different interval struc­ tures from which the intervals Qi,j,k,l may be taken.

Definition 2 An interval structure I is a quadruple (I, D, o, n). I is a set of (semi-)intervals on a domain D. I is closed under the composition and intersection operators, o and n, respectively.

Most common are the structures IaJ = (IaJ, tQ, +, n) and Io = ( {( -oo, 0), ( -oo, 0], ( -oo, +oo), (0, +oo), (0, +oo), (0, 0]}, tQ, +, n), where (Qdenotes the rational num­ bers, IaJ all intervals on the rationals, + interval addition, and n set intersection.

In order to compose constraints from different interval structures, interval mappings are established that communi­ cate restrictions.

Definition 3 Interval mappings are functions 1-Lir ,I. : Ir I-t Is from one interval structure, Ir, to another one, Is, such that the following properties are fulfilled: Vi, j, k, l : (vi,Qi,j,k,t.Vj) => (vi,J.lir ,I.(/-LI.,IJQi,j,k,l)),vj)· If Dr= Ds. it is also required that Vi,j,k,l : (vi,Qi,j,k,l,Vj) => (Vi, /-Lir ,I. ( Qi,j,k,l), Vj ).

For instance, the resulting quantitative constraints in ( 4) are mapped onto a common ordinal one by J.LittJ ,Io:

Third, subsumption is used in order to compare models of GTN relations.

Lemma 5 If R1 !?..R2, then every model for the relation R2 that assigns values to time point variables in V is also a model for the relation R1.

For instance, the result in (4) subsumes the input given to 1r {(t 1 .f2)}, the result in (5) subsumes the result of ( 4), and due to the transitivity of subsumption the relation in (5) subsumes the one in (3g).

Finally, before proceeding with the topic proper of this pa­ per, we give the definition of an unambiguous GTN, a UGTN:

Definition 6 A UGTN is a GTN, where 'Vk = l...M: Lk = 1.

4 Abstraction at the Reasoning Level - Switching Between Levels of Granularity

The GTN model is the foundation for switching between dif­ ferent levels of reasoning. GTNs based on intervals from the reals, LaJ, bring about a very fine-grained level of tem­ poral reasoning as a general frame of reference. Switching to coarser models is possible relative to at least two dimensions: First, the dimension of interval structures of different granu­ larities permits such changes, e.g., abstractions from quanti­ tative constraints to qualitative, i.e., ordinal ones, like Io, or granularity changes between days, weeks and months as they have been described by Bettini et al. [19971. Second, one may consider disjunctions of conjoined constraints as already too sophisticated a level of representation. From such a level, it is, nevertheless, possible to move into a sparser theory, by using abstraction on the propositional level as investigated by Giunchiglia and Walsh [ 1992].

Figure 1 is an excerpt of a n~twork heterarchy of temporal reasoning schemes (with arrows pointing from less towards more expressive formalisms) . GTN(14J) and GTN(Io) denote GTNs based only on the interval structures IaJ and Io, respectively. STP and TCSP stand for non-disjunctive and disjunctive quantitative constraint systems, respectively, as described by Dechter et al. [1991].2 The term integra­ tion stands for the integration of TCSPs with Allen's model [Meiri, 1996]. TCSP-LPC (cf. Schwalb and Dechter [1997]) is not really a representation schema on its own. Viewed from a representational perspective, it is equivalent to TCSPs, but it propagates only a limited number of disjunctions in each step such that propagation, as a whole, remains polynomial in the number of relations.

This heterarchy mirrors the well-known trade-off between expressiveness and efficiency. Determining consistency is NP-hard in all formalisms, except for the point algebra and for STP networks (cf. Vilain et al. [1989], Dechter et al. [1991]). However, even approximating constraint propaga­ tion algorithms can be very expensive when large ranges are embodied in the network.

2 1n the formal framework of GTNs, for TCSPs we require Vk : IEk I = 1, and for STPs we assume Vk : IEk I = 1/\ Lk = 1.

We attempt to deal with this complexity bottleneck by pro­ viding smooth shifts among different levels of expressive­ ness. Following Hobbs's strategy that "idealization allows simplifications into tractable local theories", our proposal ap­ proximates given information by "simpler" one. These shifts are performed by two families of operators already introduced in the previous section: The first one, 1r E , takes interdepen­ dent constraints as input and disregards · their relationships, e.g., as with the disjunction in (4). The second one p.z I allows switching between different interval granularitie;,· ~: e.g., illustrated by collapsing information in (5).

As can be read off from the diagram, both idealizations ab­ stract from networks composed of detailed representations, with expensive constraint processing, to coarser representa­ tions, which allow for more efficient reasoning. Hence, ex­ pressiveness is traded off against efficiency. Disregarding structural interdependencies, e.g., allows the projection of GT N(Io) information into an efficiently solvable point al­ gebra. A coarser level of quantities, and thus a small overall range, is directly reflected by a tighter worst-case bound for constraint propagation (cf. Theorem 13 in [Staab, 1998b]).

The soundness of both abstraction operators is ensured by Definition 3 for operators p. and by Lemma 7 for operators 1r:

Lemma 7 For all E E £ and {R1 , ... , Rm} E iR: The constraints given by R1 1\. ... 1\. Rm entail the constraints given by 7rE({R11\. .. . I\ Rm}).

Let us now illustrate the use of these abstraction mecha­ nisms by considering the temporal reasoning problem given in (1). In order to retrieve qualitative ordering information, such as determining arrival orderings, it is often desirable to move down the heterarchy from GTN(74J) to a point algebra. This is done for two relevant pieces of knowledge, viz. for (3g) by the combination of (4) with (5), and for (3h) by (6).

From (5) and (6) we may easily read off that Mr. Roget, Mr. Meyer and Mrs. Meyer arrive just in this order, the men may even arrive simultaneously.

Given that we have neglected knowledge about durations, we do not know how Mr. George's arrival is ordered with respect to the other ones. What is needed is reasoning at the level of TCSPs - on the one hand:

From (4) and (7) we derive:

1. (to, [5, 5], t2) V (to, [3, 3], t2) V (to, [8, 8] , t2) V (to, [6, 6] , t2)

From (8) and (3h) we conclude:

On the other hand, one needs to account for background knowledge about the duration of flights. Assuming an inter­ val structure (like the ones in Clementini et al. [1997]) refer­ ring to flights of "short", "medium", "long", and "very long" time extension, a common grounding between "very long" and hour units may be that "very long flights" take at least 15 hours. With this information and with (9), one may conclude, finally, that Mr. George will arrive last.

Though for most temporal reasoning mechanisms the two families of abstraction operators, 1r and J..L, play the major role, one may think of alternative operators, too. For instance, Schwalb and Dechter [1997] encountered the TCSP fragmen­ tation problem by restricting propagation to (almost) convex constraints. An operator T that abstracts from general non­ convex relations into a limited number of convex disjunctions may render constraint propagation more efficient. However, the disadvantage remains that the resulting network does not have a similarly relevant status as, say, an interval algebra, for which path consistency has been determined.

With these abstraction operators, problems stated at one level are mostly lifted onto a coarser level of reasoning. How­ ever, going the other way round may also prove fruitful. Rea­ soning at the coarser level is cheap and all the conclusions that are inferred at the coarser level also hold at a finer grain size. Very often the switch backwards is given by the identity operation 3 , e.g., between GTNs based on Io and IIIJ·

5 Abstraction at the Interface LevelGeneralizing by Approximating Relations

Increased expressiveness and the application of powerful ab­ straction mechanisms that mediate between different preci­ sion levels of reasoning may actually aggravate the applica­ tion of a temporal reasoning system. While thirteen quali­ tative interval relations in Allen's calculus or disjunctions of interval constraints in TCSPs may already pose non-trivial problems for a human to deal with, GTN relations have an even more complicated structure. Thus, GTN relations are often too unwieldy to be used in a temporal query language or by a module of a larger system, though an application may actually require their use. For instance, a text understanding and generation system dealing with the scheduling problem as given in (1) may need to account for complex propositions such as (3g). This means that high-level conceptual represen­ tation structures, e.g., "a very long flight " or "X arrives after Y" , that are typically employed by such a system must be translated to low-level GTN expressions when in-depth tem­ poral reasoning is required.

3 0ne notable exception arises when granularity levels are not directly comparable, e.g., month vs. week (cf. Bettini et al. [1997]).

To bridge the conceptual distance, we here introduce an interface level that abstracts from unnecessary details and, hence, generalizes to the relevant distinctions that need to be made. In doing so, we provide definitions of abstracting rela­ tions that are used to move from the interface level down to the reasoning level- and in the reverse direction. Switching from the interface to the reasoning level, e.g., when posing a query to a temporal reasoning system, one simply has to ex­ pand the definition of the abstracting relation. Table 1 shows some examples of such "macro" definitions. Switching back, i.e., outputting an abstracted relation to the interface level, e.g., as an answer to a query posed by a "naive" user, requires reasonable criteria for the selection of those interface rela­ tions that are best suited to abstract from a given low-level re­ lation. We here define two notions of "best approximations":

Definition 8 Let a set of abstracting relations be given by R~ , ... ,R~.

A relation Rf is a smallest upper approximation of a rela­ tion R with regard to R~, ... , R~, iff Rf ~ R and there is no R'J, i -:/:- j such that Rf ~ R'J ~ R.

A relation Rf is a greatest lower approximation of a rela­ tion R with regard to R~, ... , R~. iff Rf .1 R and there is no R'J, i -:/:- j such that Rf .1 R'J .1 R.

This definition may yield several smallest upper and great­ est lower approximations. A unique upper approximation is given by the conjunction of the best upper bounds, while a unique lower approximation is given by the disjunction of the best lower bounds.

We do not present an algorithm here for computing the approximating relations, since its appropriateness depends heavily on the abstracting relations being given and the tem­ poral reasoning system being used. Two obvious problems may illustrate these interdependencies: First, for abstracting relations with quantitative parameters the proper instantiation of free parameters with actual values in the corresponding re­ lation allows for redundant variation. Symmetric relations like "time point t1 is at most 1 unit away from h " require particular care, since the equivalent "time point t2 is at most 1 unit away from t1" does not yield any new information. Second, additional constraints. are needed to control proper instantiation of an abstracting relation. For instance, the defi­ nition A in Table 1 should be supplemented by the restriction that Ab and Ae really form an interval. Though, in princi­ ple, all pairs of time points may determine an interval that one could talk about, in practice, this generality should be avoided. Another additional constraint considered plausible for . all abstracting relations is the unique name assumption which prevents, e.g., the unification of the three variables a, b, c in the abstracting relation F from Table 1.

Let us now illustrate our notion of generalization with two examples. Assume we want to mine the GTN resulting from (3) for interesting complex rules. For our first example, we are interested in temporal rules on how the arrival time of Mr. Roget influences the schedule of Mrs. Meyer appearing after him. Then, we add an unconstrained relation Rz to the GTN withEz :={(to, tt), (t1, t3)}. Composing (in the way defined by Staab [1998b]) the relation given in (3g) with the one from (3h) and projecting the result onto Rz yields:

Generalizing this relation, obviously, only the abstracting relations D, E and F may apply (cf. Table 1), since the other ones require intervals instead of time points (e.g., A and B) or a different number of time points (viz. four as in C). Approx­ imating "from above", abstracting relation F does not gener­ alize (1 0) at all, while "Time points to, t1, t3 appear in this order" is the best generalization, since it is more specific than the corresponding instantiation of E. An approximation "from below" fails, because none of the abstracting relations is more specific than the relation in example (10).

Correspondingly, we may ask how Mr. George's arrival correlates with those of Mr. Roget and Mr. Meyer. Given that we have only qualitative information about the length of Mr. George's flight, it seems most appropriate to reason entirely on a qualitative interval structure. For the sake of brevity, we may here ignore many of the intricating presup­ positions involved in algebraic operations on qualitative du­ rations (cf. Clementini et al. [1997]) and simply present the result derived from the corresponding inference process:

This result is generalized ("from above and below") by "Time point t 5 being at least a medium time after t 1 corre­ lates with t 5 being at least a medium time after time point t2"·

Conceptualizations at the interface level are of particular value for combining single evidence and generalizing it. In our text understanding application, e.g., we represent graded information like "hard disk A is faster than hard disk B" by GTN relations (cf. Staab and Hahn [1997]). Most of these relations can be handled by a comparatively inexpensive rep­ resentation formalism. However, we also have to deal with much more complex utterances like "up from a block size of 32 KB the data throughput decreases from 800 KB!s to less than 600 KB!s", which require more expressive representa­ tions, and, hence, costly reasoning. By flexibly assigning reasoning tasks to the least expensive representation level the entire understanding process might still be executed within feasible bounds. When just few of the represented GTN rela­ tions are complex, which is the case most of the time, reason­ ing at the finer levels remains feasible. Only if complicated GTN relations abound, one must resort to reasoning at coarser levels as an approximation - and eventually to an abstract­ ing interface level that makes generalizations accessible to the user instead of a myriad of tiny bits of detail.

6 Related Work

The scalability of temporal reasoning, as a static notion, is already inherent to the hierarchy of calculi discussed in Sec­ tion 4. It derives from the fact that these constraint systems stand for different levels of expressiveness. As the arrows in Fig. 1 indicate there are rather limited calculi (e.g., point alge­ bra [Vilain et al., 1989]), ones with increased expressiveness (e.g., Allen's calculus [Allen, 1983] or TCSPs [Dechter et al., 1991]) and fairly general ones (such as integration mod­ els for Allen's calculus with metrical reasoning [Kautz and Ladkin, 1991; Meiri, 1996; Badaloni and Berati, 1996]). As a framework for our research, we have introduced a very gen­ eral model, viz. GTNs, whose expressiveness exceeds that of all previously mentioned calculi. So this hierarchy lays down the foundations for formalizing temporal constraints at differ­ ent levels of granularity. Weaker constraint systems may be an appropriate choice for applications which require less spe­ cific constraints and offer on their bonus side the tractability for certain reasoning algorithms.

Using this trade-off between expressiveness and compu­ tational complexity in a strategic manner leads to the idea to navigate this graph of different levels of expressiveness on demand - depending on the needs of the particular ap­ plication. The idea to dynamically shift between less ex­ pressive and computationally cheaper systems and more ex­ pressive though computationally more expensive ones during run-time is the starting point of our work, and has been on the research agenda for quite a long time (cf. Hobbs [1985], Sathi et al. [1985], Nakhimovsky [1988]). This flexible manouvering between granularities as a principle method rather than as an impeding side conditions constitutes the main difference between our approach and common reason­ ing systems that implement several metric systems.

For instance, Bettini et al. [1997] have extended STP net­ works in order to represent interval structures from a large range of granularity levels. Thereby, they have even included non-contiguous structures (e.g., business days). As an ap­ proximating reasoning algorithm they propagate constraints in parallel networks of single granularities. Operators that map constraints between granularities communicate between the different networks. However, propositional abstraction, such as defined by our operator 1r is neglected in their ap­ proach as well as in other temporal reasoning systems.

This negligence may even be a drawback with regard to performance issues. Approaches for efficient temporal reasoning use, e.g., approximating propagation mechanisms [Schwalb and Dechter, 1997] or heuristics that optimize the search process [Stergiou and Koubarakis, 1998]. Though our proposal still lacks comparable empirical evidence, we can guarantee the determination of criteria important for the in­ ferencing task (e.g., consistency for point algebra, path con­ sistency for qualitative relations) in polynomial time, when granularities are switched to compute coarser results first, and refinements at more precise levels are postponed to subse­ quent rounds. Optimized schemes like those in [Schwalb and Dechter, 1997; Stergiou and Koubarakis, 1998] may still not terminate and, if they are terminated from outside due to ex­ hausted time budgets (as set up by anytime devices, cf. Rus­ sell and Zilberstein [1991]), the network cannot be asserted to be in a similarly well-defined state as a cascade of G1Ns at different granularities.

A complementary proposal has been made by Euzenat [1995], who permits to represent seemingly contradictory in­ formation at different levels of granularity, e.g., at some given level one may perceive that two intervals meet, while at a finer level one may recognize that the first is just a tiny bit before the second. His abstraction operators reflect how perception may change by switching between different levels.

7 Conclusion

In this paper, we defined operators for transient moves be­ tween different abstraction levels of temporal reasoning. Op­ erators that were originally devised for constraint propaga­ tion, viz. 1r, J.L, ~, are used in our scalability framework for switching smoothly between different granularities as far as the reasoning proper and communication via interfaces are concerned. Furthermore, we proposed macro definitions to achieve abstraction by approximating relations at the inter­ face level, a research issue that to the best of our knowledge has not been dealt with so far.

The major open issue is then when to bring what level of abstraction into play. In our opinion, there is no general solu­ tion to this problem. In the research environment we work in, a natural language text understanding system, the appropriate choice of adequate abstraction levels often comes with the author's choice of specific linguistic expressions occurring in the text, their corresponding semantic interpretation and the progression of the text (cf. Matsushita et al. [1998]). Hav­ ing fixed such a starting point, we proceed from the cheapest level possible and tum to more expressive and expensive lev­ els only when this is needed for proper text understanding.

Acknowledgements. S. Staab was a member of the Graduate Program Hwnan and Machine Intelligence at Freiburg University, which was funded by DFG.