Efficient Temporal Reasoning through Timegraphs

1 Introduction

Temporal reasoning is an important task in many areas of AI, including planning, natural language processing and expert systems. In several applications, temporal knowledge may be expressed in terms of collections of binary relations between intervals or points. Tempo­ ral reasoning tasks include determining the consistency (satisfiability) of such collections, finding a consistent scenario (an interpretation for all the temporal variables involved) and deducing new relations from those that are known (or computing their closure). Since Allen's work on binary interval relations [Allen, 1983], numerous re­ searchers have addressed temporal reasoning in terms of constraint propagation techniques [Ladkin and Maddux, 1988; Vilain et a/., 1990; van Beek and Cohen, 1990; Dechter et al., 1991]. The main problem with these techniques is their scalability. The problems of deter­ mining the satisfiability and of computing the closure of a set of assertions in Allen's interval algebra (IA) are NP-complete [Vilain et a/., 1990]. Restricting IA to the Lenhart Schubert Computer Science Department University of Rochester Rochester, NY 14627, USA schu bert@cs .rochester .ed u

·The authors thank James Allen for drawing their atten­ tion to the problem of scalability and for many fruitful dis­ cussions. The work of the first author was carried out in part in the context of the MAlA project at IRST, with the sup­ port of Oliviero Stock, and of CNR PF Sistemi Informatici e Calcolo Parallelo. The second author was supported by Rome Lab contract F30602-91-C-0010.

"pointizable" lA (PIA), i.e. to the set of relations in lA that can be translated into conjunctions of point rela­ tions between the endpoints of the intervals, makes these problems tractable. Algorithms have been developed for PIA running in O(n 2 ) space and O(n 2 ) time for deter­ mining consistency [van Beek, 1990] and O(n 4 ) time for computing the closure [van Beek and Cohen, 1990] (for n points). Unfortunately these bounds are still unac­ ceptable for domains in which a large data-base of rela­ tions needs to be managed [Allen and Schubert, 1991]. Recently, other approaches based on graph algorithms have been proposed whose main characteristic is that of providing better performance in practice compared to the more traditional constraint-based approaches [Miller and Schubert, 1990; Ghallab and Mounir Alaoui, 1989; Dorn, 1992; Golumbic and Shamir , 1992] .

We are interested in the problem of efficiently man­ aging large data sets of qualitative temporal relations in the Point Algebra (PA) [Vilain et a/., 1990] . The elements of P A are the set of relations { <, >, =, :S .~.#.:S>,0}, through which all the relations of the PIA can be represented [Ladkin and Maddux, 1988] . Our approach is based on ideas derived from a tempo­ ral reasoning system developed in the context of nat­ ural language comprehension [Schubert et a/., 1987; Miller and Schubert, 1990]. In this system temporal rela­ tions are represented through graphs, called timegraphs, whose vertices represent points and whose edges rep­ resent temporal relations. The main characteristics of timegraphs are their partitioning into a set of chains, which are sets of linearly ordered points, and their use of a metagraph structure to guide the search processes across the chains. One advantage of this approach is that the space complexity can be linear in the number of stip­ ulated relations. The other advantage is the efficiency in terms of computation time in domains such as planning [Allen et a/., 1991] and story understanding in which the temporal data tend to fall naturallr into chain-like ag­ gregates [Miller and Schubert, 1990]. Essentially this is because the "worlds" described in stories and plans con­ sist of individuals (or sets of related individuals) each moving through a course of actions and events, creating a trajectory in time. Building timegraphs in practice takes much less time than computing closure (the mini­ mal network in constraint propagation terminology), and the amount of time spent in querying relations is nearly constant.

In this paper we present new algorithms for building timegraphs from sets of relations in the Point Algebra. Among them there is an algorithm for dealing efficiently with ''not equal" relations (=F) which were not considered in previous timegraph algorithms. To our knowledge, the only authors who have proposed algorithms for reason­ ing efficiently with =F relations are Ghallab and Mounir Alaoui [1989] and van Beek and Cohen [1990]. Neither has treated the problem quite satisfactorily. In fact, the correctness of the algorithm proposed by van Beek [1990] is based on a lemma whose proof given in [van Beek and Cohen, 1990], we show to be incorrect. However, we provide a new proof for the lemma which shows that van Beek's algorithm is indeed correct. In [Ghallab and Mounir Alaoui, 1989] the =F relations are only partially treated as the proposed algorithms cannot derive some strict orderings induced by =F relations.

Section 2 introduces our framework formally; Section 3 shows the algorithms for building a timegraph and for querying relations; Section 4 reports experimental re­ sults we have from TG-II, a system in which the algo­ rithms described in the previous sections have been im­ plemented; Section 5 gives conclusions and future work.

2 Representing temporal relations through graphs

In this section we introduce the definitions and the­ orems on which the proposed approach is based . A path of length n is a sequence of n triples (vo,lt,vt), ... ,(vn-t,ln,vn) where v; (0 :$ i :$ n) are ver­ tices and li (1 :$ j :$ n) are labels (relations) on edges.

Definition 2.1 A temporally labeled graph ( TL-graph) is a graph with at least one vertex and a set of labeled edges, where each edge ( v, I, w) connects a pair of distinct vertices v, w. The edges are either directed and labeled :$ or <, or undirected and labeled :f .

We assume that every vertex of a T L-graph has at least one name attached to it . If a vertex has more than one name, then they are alternative names for the same time point. The name sets of any two vertices are re­ quired to be disjoint.

Definition 2.2 In a T L-graph we call a path a :$-path if each label/; is :$or <. A $-path is a <-path if at least one of these labels is <.

Definition 2.3 A $-path (<-path) of length n, n ~ 1, is a $-cycle (<-cycle) ifvo = Vn. A TL-graph is acyclic if it does not contain any $-cycle.

Definition 2.4 A T L-graph is consistent if its vertices can be interpreted as elements of a totally ordered set (with ordering <)satisfying the constraints imposed by the edges.

Theorem 2.1 A T L-graph is consistent iff it does not contain any <-cycle, or any $-cycle that has two vertices connected by an edge with label# .

Proof (sketch): The "only if' direction is obvious from irreflexivity of <, and from equality of vertices on a $­ cycle. The "iP' direction is proved by induction on the number of #-edges. When there are none, the absence of <-cycles guarantees consistency. In the induction step, we note that we can consistently add (v,#,w) just in case we can consistently add ( v, <, w) or consistently add (w,<,v). We use the former if there is a $-path from v to w, and the latter otherwise, obtaining a situation covered by the induction assumption. 0

Definition 2.5 A TL-graph contains an implicit < re­ lation v < w if there is no <-path from v to w and either there is an edge between v and w with label :f and a $-path (but no <-path) from v tow (see Figure l.a)); or there exist two vertices s and t such that there is an edge between s and t with label =F and $-paths (but no <-path) from v to s, stow, v tot, and t tow (see Figure l.b)). The graphs isomorphic to the one given in Figure l.b) are called :f diamonds.

Definition 2.6 An explicit graph for a given T £-graph G is an acyclic T £-graph logically equivalent to G and with no implicit < relations.

Theorem 2.2 An explicit TL-graph entails v :$ w iff there is a $-path from v to w; it entails v < w iff there is a <-path from v to w, and it entails v =F w iff there is a <-path from v to w or from w to v, or there is an edge (v, :f, w) .

Proof (sketch): This is easy to establish for the case where there are no #-edges. When there are #-edges, the idea is to show that if there is no $-path (<-path) from v to w, we can "decide" any #-edge (making it a <-edge in one direction or the other) without creat­ ing cycles, without creating a $-path (<-path) from v to w, and without forfeiting the "explicit graph" prop­ erty. Thus all the :f-edges can be decided, and we end up with a consistent graph that entails the original one, yet doesn't en tail v :$ w ( v < w) . The reason we can avoid creating a $-path (<-path) from v to w is that if both ways of deciding a #-edge gave such a path, then a :f-diamond would have to be present (formed by v, w, and the vertices connected by the :f-edge), contrary to the "explicit graph" property. And the reason we don't forfeit the "explicit graph" property is that a <-edge re­ placing a :f-edge cannot create paths that support an implicit< relation (they can only support an explicit < relation).D

Remark. This theorem has two important conse­ quences. One is that it enables us to write linear time procedures which obtain the strongest relation between two points entailed by an explicit graph (called the mini­ mal /abe/by van Beek and Cohen [1990]) .Secondly, it pro­ vides the basis for a new proof of their Lemma 1 in [1990] stating that any path-consistent nonmininmal network of relations 1 taken from PA must include a four-vertex subgraph isomorphic to the graph in Figure l.b). The value of this new proof lies in the fact that the one given by van Beek and Cohen is not correct. This becomes evident if one observes that the four-vertex constraint network obtained by replacing the ~-paths in Figure l.b) with~ edges and adding the edge (v,{<,=},w) is not the only four-vertex path consistent network that, up to isomorphism, can be derived in the last step of the proof of van Beek and Cohen. In fact, the network ob­ tained by replacing (v,{<,=},u) with (v,{<,=,>},u) and (u, { <, = }, w) with (u, { <, =, > }, w) is another pos­ sible network. This contradicts what van Beek and Co­ hen assert at the end of their proof.

We will show how linear time procedures for querying relations can be designed in section 3.5, while a new proof of van Beek's lemma is available to the interested reader in [Gerevini and Schubert, to appear] an extended version of this paper.

3 The construction of a timegraph

Given a set S of binary relations in the Point Algebra we first build aT £-graph whose vertices correspond to the variables (time points) inS, and whose edges correspond to the relations (note that = relations are translated by creating only one vertex for each set of explicitly equated variables, and labelling that vertex with that set of vari­ ables). From the TL-graph we then form a timegraph whose definition is:

Definition 3.1 A timegraph is an acyclic T £-graph par­ titioned into a set of time chains, such that each vertex is on one and only one time chain. A time chain is a ~-path, plus possibly transitive edges connecting pairs of vertices on the ~-path.

Distinct chains of a timegraph can be connected by cross-edges (these, and certain auxiliary edges, will also be called metaedges). Vertices connected by cross-edges are called cross-connected vertices (or metavertices 2 ). The construction of a timegraph from a T £-graph con­ sists of four main steps: consistency checking, ranking of the graph, formation of the chains and making explicit implicit < relations.

1 A network is minimal if there is exactly one labelled edge for each pair of distinct vertices and all the labels are mini­ mal. A path-consistent network is one in which for any three vertices u, v, w, any of the possible relations { <, >, =} al­ lowed by the label of the edge joining u and v is consistent with the labels joining u and w, and v and w.

2 This is a slight departure from the terminology of [Schu­ bert et al., 1987; Miller and Schubert, 1990].

3.1 Checking consistency

Determining the consistency of a TL-graph G=(V,E), where V is the set of vertices and E is the set of edges, can be accomplished by two steps. The first step consists of the identification of all the strongly connected com­ ponents (SCC) of the T £-graph derived from G ignoring the ::j; relations. The second step consists of checking if any of the SCCs contains a pair of vertices connected by an edge with label <, or ::j;. It can be shown from The­ orem 1 that a T £-graph is consistent if and only if such a SCC does not exist. When the graph is consistent, each sec can be collapsed into any arbitrary vertex v within that component. All the cross-component edges entering or leaving the component are transferred to v. The edges within the component can be eliminated and a supplementary set of alternative names for v is gener­ ated. It is clear from the definition of a sec that the resulting graph is acyclic and that this resultant graph (along with the sets of alternative names) is logically equivalent to the original one. It is well known that the computation of the SCCs can be accomplished in time 0( n + e) (where n is the number of vertices and e the number of edges) using Tarjan's algorithm [Cormen et al., 1990]. Checking the existence of<, ::j; edges between vertices in a sec and collapsing each sec into a single vertex are linear tasks in the number of the edges. It follows that the global time complexity is 0( e). This provides a proof of the next theorem (a similar theorem is also given by van Beek [1990]):

Theorem 3.1 A TL-graph can be recognized as being inconsistent, or if it is consistent, collapsed to a logically equivalent acyclic T L-graph (supplemented with disjoint sets of alternative names for the vertices) in O(e) time, where e is the number of edges.

3.2 Ranking the graph

Given aT £-graph G, we define the universal start time of G as a special vertex with no predecessors and with successors the set of vertices in G which have no other predecessors. Each edge leaving from the universal start time has label ~.

In accordance with the definition given by Ghallab and Mounir Alaoui in [1989], the rank of a vertex v is defined as the length of the longest ~-paths from the universal start time to v, times the distance increment k. (I.e., rank increases in steps of size k along maximal­ length paths.) In our terminology the rank of a vertex is also called the pseudotime of that vertex. The main purpose of the ranks is bounding the search at query time. In fact, using the ranks, it is often possible to obtain the strongest relation between two vertices that is entailed by the graph in constant time, i.e. without performing any search. We will show how this is possi­ ble in the next Section, while in Section 3.5 we discuss the query algorithms further. Figure 3 shows an algo­ rithm for computing the ranks for an acyclic T £-graph based on the DAG-longest-paths algorithm reported in [Cormen et al., 1990] and taking O(n +e) time.

INPUT: A consistent TL-graph G=(V,E), an integer k. OUTPUT: The ranks of the vertices in G. 1. topologically sort the vertices in G (using only <,$edges); 2. for each vertex v E V do rank(v) := -oo; 3. rank( univer&al-&tart-time) := 0; 4. for each vertex u taken in topologically sorted order 5. do for each vertex v such that ( u, { <, $}, v} EE do 6. ifrank(v) < rank(u) + k then rank(v) := rank(u) + k. Figure 3: An algorithm for computing the ranks.

INPUT: two vertices Vt and v2 on the same chain. OUTPUT: the strongest relation between v 1 and v2. if pseudo time( Vt) < pseudo time( v2) then if pseudotime( nextgrea.ter( vt)) :5 pseudo time( V2) then return Vt < v2 el&e return v1 < v2 el&e if pseudotime( nextgrea.ter( v2)) $ pseudotime( Vt) then return v2 < v1 el&e return V2 :5 Vt . Figure 4: Algorithm for determining the relation between vertices on the same chain of a. timegra.ph.

3.3 Forming the time chains and the metagraph

The main computational importance of time chains is that, given a pair of vertices belonging to the same chain, it is possible to compute the strongest relation entailed by the graph in constant time, while, in general, this task requires a graph search linear in the number of edges (unless of course we precompute all O(n 2 ) minimal la­ bels). The constant time algorithm is given in Figure 4. This result is achieved by using the pseudotimes of four vertices and an additional, possibly null, link for each vertex. Following [Miller and Schubert, 1990], we call this link the next greater link, defined in the following way:

Definition 3.2 Given a vertex v, the nextgreater of v (written nextgreater(v)) is the nearest successor v' of v that is on the chain of v such that v < v' is entailed by the graph. If v' does not exist, then nextgreater(v) is null.

We describe how the nextgreaters can be efficiently computed in the next Section. Since vertices on the same chain support constant time queries, it is desirable to keep the number of time chains to a minimum in building the timegraph. Another desirable constraint is that the number of cross-chain edges be minimal. Figure 5 shows an algorithm for creating a set of time chains from a given T L-graph that attempts to minimize the number of cross-chain edges and that works well in practice. It can be shown that the time complexity of the algorithm is O(n +e). Figure 7 shows three time chains formed by using the algorithm on the graph of Figure 2.

3.3.1 Computing the nextgreater links

The algorithm for computing the nextgreater links consists of two main steps. In the first step the nextgreater links for each vertex v are computed consid­ ering only edges connecting vertices on the same chain as

INPUT: a. consistent TL-gra.ph G=(V,E). OUTPUT: G with vertices assigned to chains. 1. X := list of vertices in V; 2. for each vertex v E V chain(v):= nil; y := nil; c := 1; 3. Xmaz := a vertex in X with the highest rank; 4. y :=vI v E V, chain(v)=nil and (v,{<,$},xmaz) EE {preferring a vertex connected by a < edge}; 5. if y is not nil then begin 6. chain(y) := c; remove y from X; Xmoz := y; 7. goto 4 end 8. el.te if X is not empty then begin c := c + 1; goto 3 end. Figure 5: Algorithm for creating chains.

INPUT: a time chain C. OUTPUT: the local nextgreater links for C. 1. i := first vertex on C ; n := last vertex on C; 2. while ra.nk(i) <ra.nk(n) do 3. k := successor of i on C; strict := false 4. while (strict =false and rank(k) :5 rank(n)) do 5. S = {(j,{<,:;i},k)} I j E C and rank(i) $ rank(j) < rank(k); 6. if S is not empty then begin 7. r := the vertex with the highest rank in {start(e) I e E S}; 8. strict := true; 9. for each vertex t on C between i and r do nextgreater(t) := k; 10. i := successor of r on C end 11. else k:= successor of k on C end end. Figure 6: Algorithm for computing local nextgreaters.

v. In the second step these nextgreater links are refined by looking for cross-chain <-paths.

Figure 6 shows an algorithm for performing the first step for a single chain C that takes 0( nc + ec) time, where nc is the number of vertices on C and ec is the number of edges between those vertices. The function start(( v1 , I, v2)) indicates the vertex between v1 and v2 that has the minimum rank.

Since two vertices on the same chain may also be con­ nected via cross chain paths, it is clear that the first step is not sufficient for computing nextgreaters . The second step completes this task by performing a search for the <-paths that go from one cross-connected vertex of a chain to another on the same chain, starting with an out-going cross-edge and ending with an incoming cross­ edge. For example, in Figure 7 the nextgreater of a is c, but before the refinement it was f. Edges with no label have been assumed to be labeled $. The dotted edges represent the nextgreater links. The number labeling each vertex is the pseudotime obtained using increments of 1000.

The second step is in general the most time-consuming in the computation of nextgreaters; in fact since each search can cost O(e) time, the time complexity is O(n·e). However, for timegraphs it is possible to improve this bound significantly with a negligible cost in space com­ plexity (a constant factor). In order to do that, we need two new links for each cross-connected vertex v. The first points to the first successor of v on the same chain which has outgoing cross-edges, and the second points to the first successor of v on the same chain which has in­ coming cross-edges. We indicate the vertices pointed to by these two links with nextout(v) and nextin{v). Based on the meta vertices and the metaedges of the timegraph, together with these new links, we define the metagraph of a given timegraph T:

Definition 3.3 Given a timegraph T with underlying T L-graph G, the metagraph ofT is the graph G = (V, E) in which V={ vI vis a metavertex in T} and E={e I e is a cross-edge in T}U{nextout(vi), nextin(vi) I ViE V}.

It can be shown that G can be computed from T in O(n + e) time . The algorithm for refining the nextgreaters on a chain C, not reported for lack of space, takes O(nc+nce) time, where nc is the number of ver­ tices on C and nc is the number of metavertices on C. The global complexity of the algorithm for computing the nextgreaters is then: O((e- e)+ n + n. e) . But, in practice, this bound can be reduced since the search required for refining the nextgreater of a vertex v can be pruned whenever a vertex with a rank greater or equal to the rank of the current nextgreater of v is reached (by the definition of rank and by the way the chains are formed, it is not possible to have a path from a vertex v to a vertex with a rank equal or greater than the rank of v).

3.4 Dealing with "not equal" relations

Reducing a T L-graph (i.e. making explicit all the im­ plicit < relation by the addition of new edges with label < ) can be the most expensive task in the construction of a t imegraph. This is the same as in van Beek's approach whose algorithm [van Beek, 1990] takes O(n 2 · et;. + n 3 ) time, with n the number of time points, and et;. number of# relations. Fortunately, the data structures provided by a t imegraph allow this task to be accomplished more efficiently. Figure 1 shows the two cases of implicit < relations. An algorithm for the first case (Figure l.a)) is given in Figure 8. The time complexity of this algorithm is O(e;e · ( e + n + k)), where e;e is the number of ::f edges in the timegraph, e is the number of metaedges and k is the constant time required for determining the relation between points on the same chain. In fact , using the metagraph, the tests in step 2 and 3 can be performed in O(e + n + k) time (see Section 3.5).

In order to make implicit < relations of the second kind (Figure l.b) explicit, a number of ::f diamonds of the or­ der of et;. · n 2 may need to be identified in the worst case. However, for timegraphs only a subset of these needs to be considered. In fact it is possible to limit the search to the smallest ::f diamonds, i.e., the set of diamonds obtained by considering for each edge (v, :f, w) only the nearest common descendantsofv and w (NCD(v,w)) and their nearest common ancestors (NCA(v,w)). This is a consequence of the fact that, once we have inserted a < edge from a vertex in NCA(v,w) to a vertex in NCD(v,w), we will have explicit <-paths for all pairs of "diamond-connected" vertices. From the previous ob­ servation we can derive a criterion for pruning the search that in practice can give significant time savings. In fact the total number of diamonds that has to be considered is bounded by: L(v,'j!,w) I NCA(v,w) 1·1 NCD(v,w) j.

Figure 9 shows an efficient algorithm, based on the computation of the nearest common descendants and ancestors, for making the implicit < relation of # di­ amonds explicit. The algorithm uses the list OPEN as a supplemental data structure. Each item in OPEN is a pair ( v, q) where v is a vertex to be visited and q is an integer between 1 and 4 called the code of v. The codes of two vertices are combined using the COMBINE table. The time complexity is O(e), but exploiting the timegraph's data structures, we can obtain better per­ formance by limiting the search to the metagraph. This is because if {v, -:j;, w) is a transitive edge on a chain we have an implicit < relation of the first kind, and hence it is already considered by the algorithm of Figure 8. If it is a cross-chain edge, NCD(v, w) and NCA(v, w) must all be meta vertices. So, indicating with N C A( v, w) and with NCD(v, w) respectively the subset of NCA(v, w) and the subset of N CD( v, w) consisting only of metaver­ tices, the number of ::f diamonds to be considered is re­ duced to L(v,~,w)E~ I NCA(v,w) 1·1 NCD(v,w) j. The algorithm for computing NCA{v, w) ia analogous to the NCD algorithm and is not reported for Jack of space.

3.5 Query algorithms

Given an explicit T L-graph, Theorem 2.2 permits us to derive the strongest relation between two time points that is entailed by the graph, just by looking for all the paths connecting the two corresponding vertices. Fur­ thermore, in timegraphs there are four special cases in which those paths can be obtained in constant time. Given two points Pl ,P2 the first case is the one where p1 and p2 are alternative names of the same point (see Section 3). The second case is the one where the vertices VJ and v2 corresponding to PI, P2 are on the same chain (see Section 3.3). The third case is the one where v1 and v2 are not on the same chain and have the same rank, and there is no f; edge between them (the entailed rela­ tion is { <, =, >}). The fourth case concerns f; relations for which the search is localized to the edges between the two input vertices. In fact, as a consequence of mak­ ing implicit < relations explicit, a f; relation can be the strongest relation entailed by the graph if and only if there exists a cross-edge with label f; connecting them. In the remaining cases an explicit search of the gra-ph needs to be performed. If there exists at least one <-path from VJ to ."2· then the answer is v1 < v2 . If there are only :5-paths (but no <-paths) from v1 to v2 , then the answer is VJ $ v2. Analogously for paths from v2 to v1 . An algorithm for accomplishing this task can be derived by a slight adaptation of the single-source-longest-paths algorithm reported in [Cormen et al., 1990] . This algo­ rith.m has~ time co~plexity of O(n +e) but, exploiting agam the tlmegraph s data structures, and in particular the ranks and the metagraph, we obtain a complexity O(k + e + n), where k is the constant corresponding to the time required by the four special cases.

4 Experimental Results

The algorithms described in the previous Sections have been implemented in a system called TG-II (Timegraph II). In this Section we report some preliminary results from large scale tests we are currently conducting on a SUN Sparcstation 2. Table 1 reports statistics about building timegraphs for randomly generated consistent sets of relations. For each number n of time points considered, the test procedure generates n sets of re­ lations, each containing a number of relations equal to n · INT(Iog2n). The table reports the average CPU­ time for building the timegraph, the average number of chains, the average length of the chains and the average maximum length of the chains. Given a set S of n time points with indices 1, .. . , n, the first m points (S')-with m a random number between 1 and n - are chosen to represent distinct elements whose time order is the same as the order of their indices; the remaining n- m points (S") are randomly assigned to coincide with points inS'. Relations are generated randomly by choosing a pair i, j (i < j) of indices. Specifically, if both i and j are among the m distinct points, then the relation iRj is gener­ ated, where R is randomly taken from {< < -1-} with ,_,, ' the percentage off; relations kept low (below 2%) . If i or j (or both) is one of the n- m points in S", the corre­ sponding point in S' is considered. Since we were mostly interested in measuring TG-IFs performance with data sets likely to allow chain formation , the pairs of points were generated using a geometric distribution with ex­ pected value 3. More general experiments that use the uniform distribution are in progress.

. Figure ~0 cof!lpares the CPU-times for reducing #­ diamonds m a tlmegraph and in the corresponding net­ work of relations (van Beek's algorithm [1990]) . For each value marked on the curves 500 randomly generated data sets of$ relations were considered . Five not reducible f; relations (i .e. that do not induce any implicit < relation of Figure l.b)) were then added to each data set. The high efficiency of NCD-NCA compared to van Beek's al­ gorithm derives mainly from the fact that the number of i diamonds examined by NCD-NCA was nearly con­ stant for all the data sets generated. Other experiments show that querying a timegraph is on average a fast oper­ ation. For example, the average CPU-time over 100 000 . ' quenes on 100 randomly generated timegraphs with 500 points was 0.004 seconds. Finally, we should mention some recent experiments conducted by E. Yampratoom and J. Allen [to appear] comparing the performance of Timegraph I and II with several temporal reasoning sys­ tems ; the timegraph approach proved by far the most efficient for large data sets generated for the TRAINS

10

Figure 10: CPU-time for reducing ::/; diamonds. world [Allen and Schubert, 1991] .

5 Conclusions

In this paper we addressed the problem of scalability in temporal reasoning, proposing a collection of new al­ gorithms that are implemented in a temporal reason­ ing system called TG-II. With respect to the constraint propagation approach, in our system both space and time complexity are reduced significantly for many prac­ tical applications. In fact, the space complexity depends on the size of the set of the stipulated relations and on a limited number of -:/: relations (a subset of those forming :/:-diamonds), and not on the number of time points (as in the constraint propagation approach). Instead of com­ puting the closure of the set of relations, we build a time­ graph providing a collection of data structures that allow efficient deduction of relations at query time. Experi­ mental results show that building a timegraph is much faster than computing the minimal network and that, on average, querying relations is very efficient. The larger lesson here is that exploitation of the inherent temporal structure (in our case, the chain-like structure) of the information in certain important classes of domains can yield dramatic improvements in practical performance, vis a vis algorithms aimed at the worst case.

Current and future work concerns the design of effi­ cient algorithms for adding new relations to the time­ graph dynamically and the integration of metric rela­ tions 3 . We are also investigating an extension of the Point Algebra in order to include in a timegraph partic­ ular 3-point and 4-point relations which allow the repre­ sentation of "disjoint" relations. Unfortunately, it ap­ pears that to obtain any significant extensions, while retaining computational tractability, we need to sacri­ fice completeness, since we recently established that even consistency for graphs containing only relations of form "x < y" and "x strictly outside the interval formed by y, z" (where y < z) is NP-complete (Gerevini and Schu­ bert, 1993]. Thus we are exploring efficient, incomplete methods for such graphs.

3 These were handled in the original implementation of timegraphs [Schubert et al., 1987; Miller and Schubert, 1990], but as noted # was not handled and also < and :::; relations entailed via metric relations were not extracted in a deduc­ tively complete way.