Managing Efficiently Temporal Relations Through Indexed Spanning Trees

1. Introduction

Temporal knowledge is essential in several AI tasks, such as planning and reasoning on actions, on past and future events, and on dynamic situations. Temporal knowledge requires a specific representation if one wants to correctly grasp the notion of causality. As for other types of knowledge, this representation should be consis­ tent and complete, and should provide a good trade-off between expressive power and complexity. The efficien­ cy criteria is very important for real-time applications, such as those of reactive planning and execution control that motivated this work [Ghallab], where time is an object of representation and reasoning as much as a con­ straint.

Acknowledgement: This work was supported by the EEC under the ESPRIT project Pl560 (SKIDS) and by the French National Research Program GRECO/PRC-IA

A particular set of representations were found to have some nice properties: reijied logic approaches pro­ posed in [McDermott] and [Allen 84] and formally stud­ ied in [Shoham] and [Tsang]. The common feature of these representations is the use of couples: <logical for­ mula ell, temporal qualification of ell>. They require a so­ called Time-Map Manager (TMM) that is in charge of retrieval in and updating of a knowledge base of tempo­ ral relations. In a typical application, a TMM will be put at a very low level and in heavy use, it has to be very efficient

Of the above set of representations, the Algebra of Temporal Intervals [Allen 83] is the most popular repre­ sentation: it is appealing for its expressive power and ease of implementation. It has however a major draw­ back: the consistency problem for a set of Interval Alge­ bra relations is NP-complete [Vilain]. But of resorting to exponential algorithms, this leads to the use of a tran­ sitive closure propagation algorithm that is defective because of:

• a completeness problem: it may accept an inconsis­ tent set of relations as being consistent; and
• a complexity problem: it runs in O(n 3 ), a too high complexity for a real application.

As it was argued in [Vilain] one can solve the com­ pleteness problem by restricting the expressive power to a sub-class of Interval Algebra, that class equivalent to the Time Point Algebra. For those two representations the propagation algorithm is complete.

This paper addresses the complexity problem. It describes a representation and a set of algorithms for a TMM, called Indexed Time Table (IxTen. that has the following properties:

• it relies on a particular Time Point Algebra that has the same expressive power as the restricted sub-class of [Vilain],
• it is guaranteed to be complete,
• it permits non-monotonic updatings of the knowl­ edge base, i.e. both addition and removal of rela­ tions, and
• it leads to a very efficient TMM that is shown

experimentally to be of linear time and space com­ plexity for both operations, retrieval and updating.

The proposed representation and approach are described in the next section. Main algorithms are detailed and discussed in section 3. Extensive empirical results, that characterize the performances of the pro­ posed TMM and permit to favorably compare it to those described in the litterature, are summarized in section 4. Some extensions to this TMM for dealing with numeri­ cal constraints are fmally considered.

2. Representation

2.1. Approach

The role of a TMM in a temporal reasoning system is the achievement of the following two tasks:

• (i) retrieval: find whether two events in the knowl­ edge base are temporally related and how, and
• (ii) updating: add or remove events and temporal rela­ tions to the knowledge base while maintaining its consistency.

As for other types of binary constraints, a natural representation for a set of temporal relations is a net­ work where nodes are time tokens (i.e. intervals or instants) and arcs are labeled by the constraints relating two nodes. Two directions can be pursued:

• either using a complete graph where all possible relations between all pairs of nodes are propagated and explicitly maintained: this makes task (i) triv­ ial in 0(1), and requires a costly propagation algo­ rithm in O(n 3 ) for monotonic updatings;
• or using a network where the only arcs are those of the explicit knowledge of the problem: this simplifies task (ii) but requires for task (i) a cost­ ly search through possible pathes of the network.

The approach proposed here is a trade-off between these two directions. It relies on the efficient combina­ tion of 2 principles:

• adding to the time-network a particular data struc­ ture, a maximal spanning tree with an adequate indexing scheme, that permits a very efficient com­ putation of ancestral information, this greatly sim­ plifies task (i), and
• restricting the propagation of new relations to a small subset of nodes in the network in order to perform task (ii) efficiently.

2.2. Time lattice

Of the two possible and equivalent representations that lead to a tractable polynomial problem, i.e. restricted interval algebra and time-point algebra, we choose the second one. Although this choice was motivated by effi­ ciency considerations, it has other advantages:

• there is no simple characterization of the subset of relations that falls into the restricted interval

algebra: input data has to be compared to the com­ plete list of 187 such relations compiled in [Granier]); but, for the user's convenience, one may provide intervals and some useful relations as primitives of the input language and translate them internally into time-points relations;

• the particular intervals and relations that are responsible for an inconsistency are difficult to locate even when the propagation algorithm detects the inconsistency; this is straightforward in the proposed representation;
• numerical constraints are more easily taken into account by the time-point representation;
• it is easy to represent open intervals such as prop­ erties that become true at a known moment and remain until a contradiction is found ("persistance" in [Dean] ontology).

In a time-point algebra 3 elementary relations, before, equal and after, and their 5 disjunctive combina­ tions relate a finite set of instants or time-points. Instead of a network with arcs labeled by relations, we use 2 different types of unlabeled arcs:

• arc ( standing for the relation (before or equal), and
• arc * meaning the relation (before or after).

The 8 possible relations between 2 time-points are easily expressed as 0, 1 or 2 arcs relating two nodes.

A network of ( and * arcs corresponds to a consis­ tent set of relations if no pair of nodes, connected by a * arc, are involved in a loop through ( arcs. Such a loop describes a set of identical time-points that should be collapsed to a single node. Individual events correspon­ ding to this set are kept distinct but their simultaneity is recorded by connecting all of them to the same node in the time-map. Arcs :F do not require any propagation mechanism; they are looked for only when a collapsing decision has to be taken. For that reason we can keep arcs :F implicit in the network representation.

A consistent network where all possible collapsing operations have been performed contains only ( arcs and is loop-free. It thus defmes a partial order over the set of nodes. Since we can always add for convenience an ori­ gin time-point, we endup fmally with a network that is a rooted DAG, i.e. a time-lattice. Let us denote it L=(U,A) where U= {la, u, v, w, ... } is the set of time-

points, 1a is the root of L; and A is the set of ( arcs in L.

Point u precedes temporally (is before or equal) point v if there is a path in L going from u to v. Let us denote u (( v this fact ( (( is the transitive closure of ( ). Thus relating 2 points requires a search of a path in L . How can we speed-up such a search?

2.3. Indexed Spanning Tree of the Time-Lattice

It is well known that ancestral information can be computed in constant time for a tree correctly ordered, e.g. by preoder and postorder. To use such property 2 prob­ lems should be addressed: (a) how to map a time-lattice to a tree, and (b) classical orderings are not easily updat­ ed and maintained for a dynamically growing tree .

We solve the frrst problem by extracting from L a maximum spanning tree T defmed as follow:

• T is rooted at to and covers all nodes of L (it is not a free tree as is usually the case for a spanning tree);
• T contains a maximal number of arcs.

Let us denote by r(u) the rank of u in L, i.e. the length of the longest path in L from fo to u:

To compute T from L we first order the nodes in L according to their rank. This can be achieved by an O(IAI) breadth frrst search in L: all successors of nodes of rank k have their rank set to k+1, which may change previous­ ly computed ranks if longer pathes are found (some sim­ ple additional tests speed-up the procedure).

Let M be the maximal rank found in L. We start from any node z of rank M, put it in T, choose among its predecessors in L any node y of rank M-1 and put in T the arc (y,z) and the node y as the parent node of z: p(z)=y. This is repeated for a predecessor x of y such as r(x)=r(y)-1; arc (x,y) and node x are added to T. We keep on moving up along a path of maximal length until the root t 0 is put in T.

The procedure is repeated starting from a node of maximal rank among those not already in T. While pro­ cessing node u, if there is a choice between several of its predecessors, all at rank r(u)-1, we choose one not already in T and add it toT. If none remains, we choose among such predecessors one in T which has the least number of children in T, and attach a new path to the spanning tree. The procedure is repeated until all nodes ofLare put in T.

The generated tree has indeed a maximal number of arcs: in a spanning tree of L rooted at fo there is one and just one path from to to each node of L. Each such path in T goes through a maximal number of arcs.

Let s(u) be the set of children of u in T, and ~u) the set of its descendants in T (transitive closure of s). Our goal is to be able to compute as efficiently as possible ancestral information in T, i.e. whether v e ~u) . This is achieved through a particular indexing ofT.

To each node u is attached as index a sequence:

I(u)=[i 1 . i 2 . ... ik] of one or more integers that is defmed, while generating T, as follows:

• o nodes of the path (to .... , x, y, z) that was frrst put in T are indexed by their rank: l(z)=[M], l(y)=[M-1], I(x)=[M-2], ... , I(ta)=[O];
• 0 if l(u)=[i 1 . i 2 .... ik] and v e s(u) then:

Nodes of the frrst path put in T can be indexed while they are added to T. The other nodes are not indexed until their path is attached to T: indexing pro­ ceeds by moving from the attachment parent (already indexed) down along the path.

The addition or removal of a new node, as a leaf in the tree is straightforward; for an internal node, only some of its descendants will have to be reindexed. Prob­ lem (b) is thus correctly addressed.

An example will illustrate the complete procedure: figure l.a gives a lattice L with the rank of each node shown. A corresponding maximal spanning tree is drawn in figure l.b where the index of each node follows its label (some of the arcs of L that do not belong to T are shown in broken lines)

The main property of this indexing scheme is the fol­ lowing: for l(u)=[i 1 . i 2 .... ik], and I(v)=[j 1 . j 2 .... jh]

Thus, to relate 2 nodes u and v in T we frrst compare their rank

• if r(u)=r{v) then u and v are not related in T;
• if r(u) < r(v) : either condition (1) is satisfied: v is a descendant of u, or they are not related;
• if r(u) > r(v) : u and v are permuted before check­ ing condition (1).

Notice that the rank of a node is given by its index :

In the popular Dewey decimal notation k, the length of an index, grows while we go deeper in the tree, whereas in the proposed indexing scheme we try as much as possible to keep this length small and make the value of ~· the last element of an index, increases with the depth. This is because condition (1) is checked in O(k), the length of the smallest index.

In the worst case, all pathes will be attached to the root node: the maximum value of k can be proportional to the number of nodes at maximal rank in L. An unfavorable case is that of a balanced tree where k ~ log(n+1), n being the total number of nodes (if Tis bina­ ry there are n=2M+ 1 -1 nodes, those at the maximum rank M are indexed [M], [M-1 . 1], [M-2 . 2], [M-2 .1 .1], ... [0.1. .... 1]). However the proposed procedure maximizes the depth of T while minimizing heuristically its breadth (by chosing as a parent a fatherless node or one with the least number of children in T). This keeps the average value of k smaller than the log(n) case.

Let us remark that the complete procedure for extracting and indexing the maximal spanning tree, while efficient in O(IAI+n), is not used by the TMM but at initialization time.

2.4. Residue of the Time-Lattice

A precedence relation in L, such as u ( ( v , can be retrieved either

• through the spanning tree T if v e ~u) : this is checked easily; or
• through a path using some arcs of L not belonging toT.

To take care of this last case, residue arcs are processed by 2 operations:

• Eliminating redundant arcs: if (u,v) e A is an arc of L not belonging to T such as v e ~u) then this arc does not bring any useful information. It is redundant and can be eliminated. In figure 1 arcs (fo,d), (t 0 ,p), (d,t), (f,y), (x,z) are redundant
• Propagating non redundant arcs: 2 nodes may be linked by a path that mixes in any order arcs from T and non redundant residue arcs. To avoid mixing the 2 structures and simplify the retrieval of prece­ dence relations we propagate recursively a non redundant arc (u,v) to the parent node of u in T, unless v is already a successor of p(u) in T, i.e. if v e: ~u)) then an arc from p(u) to v is added. This is the case of arc (q,w) in figure l.b.

The exact procedure is described in section 3.2. It corresponds to the trade-off mentioned earlier between using a complete graph and keeping a minimal set of rela­ tions.

Let us call residue arcs the set obtained after elimi­ nation and propagation.

The important property here is that any residue arc (u,v) is such that r(u) < r(v). This is trivially true for arcs in L not belonging to T, it is also true for added arcs since the propagation goes only upward in T.

3. General algorithms

The procedures required for the 2 tasks of a TMM, retrieval of precedence relations and updating the time­ map, using the proposed representation, are formally described in this section. Let us first summarize our main notations, and make clear the distinction between the part of the time-lattice L covered by the spanning tree T and the residue part

In T we speak of the parent p(u) of a node u, its children s(u), its descendants ~u) and its ascendants; I(u) is its index and r(u) its rank. Only s, p and I are kept as data structures.

In the residue part, a(u) denotes the set of nodes linked to u by residue arcs . We will speak of the fol­ lowers and foregoers of a node for adjacency relations defined by such arcs.

We reserve successors and predecessors for the com­ plete lattice. Notice that s(u)na(u)=0: the successors of a node are partitioned into its children and its follow­ ers.

3.1. Retrieval: relating 2 points

The proposed representation permits to characterize a precedence relation by the following conditions:

A[(ve ~u)) v (ve a(u)) v (3 we a(u) I w((v)]

The 3 first conditions come from the fact that u pre­ cedes v in L if v is a descendant of u in T or if it is a fol­ lower of u. The last one is due to the property of the upward propagation mechanism:

V v e ~u), V we a(v) : we a(u) v we ~u) . all followers of a descendant of u are either the follow­ ers of u or its descendants; there cannot be a non descen­ dant node w of u linked to u through followers of a node v in ~u), that is not also linked to u through a(u).

The comparison algorithm between two points u and vis thus:

Notice that the recursive calls to Relate are pruned

when the rank of w reaches that of v

3.2. Updating: Adding new points and relations

Updating should be done such as to keep all the proper- · ties of the representation. Let us fllSt focus on the addi­ tion of points and relations in L (removal is considered in section 3.4). The additon of a point w and 2 relations u ( w ( v can be decomposed into 2 steps:

• add w as a child of u and give it the right index ; and
• add an aoc between w and v and update the tree and residue arc if necessary.

The fllSt operation is straighforward, is is achieved by procedure Addpoint bellow. The second operation involves 3 steps: a test, and eventually a propagation and a reindexation.

The test detennines whether v (( w, in this case, unless all points in every path from v to u can be col­ lapsed, the updating is impossible: w ( v cannot be inserted, it is inconsistent with the arcs in pathes between v to w. Inconsistent arcs are returned as output for further analysis.

The reindexation takes place if r(w) ~ r(v). In this case, to keep v on the longest path in the spanning tree, we give to v a new parent node w. Node v is removed from the children of p(v) and put as a follower of p(v); w becomes the new parent node of v; the descendants of v are reindexed. The reindexation algorithm computes the new index of each node according to the index of v, it then verifies if the followers of v have the right rank considering the new index of v, and, if not, it reindexes them. This is repeated recursively.

If r(w) < r(v), v is put as a follower of w. This residue arc is propagated to the parent of w, and recur­ sively to its ascendants that are not found by Relate linked to v. Notice that if tllere is a reindexation, there will be propagation of the arc between the old parent of v and v: all the fonner ascendants of v have to know that they are still linked to it

Addpoint(w ,u)

;Add a point w after the point u

• add w to s(u)
• cakulate index of w (from that of p(w))
• p(w) (- u

The reindex function reindexes all the descendants of v according to I(v). It then verifies that the ranks of the followers of v are not affected by the new index, if they are, they will be reindexed too. The algorithm is:

As we saw before, residue arcs have to be propagated to the ascendants of u to keep a link between them and v if there is none. To propagate the relation u ( v, the algo­ rithm will simply be:

until (v e ~u))) or (3 w e a(p(u)) I w (( v) do:

add v in a(p(u)), u (- p(u).

But in a special case, this algorithm stops before the propagation is complete: in the example of figure 2,

propagation of the relation fs ( tg will go on until t 4 · There we have 1a e a(t 4 ), and 1a (( tg. If we stop the algorithm, the propagation will be incomplete because we will not be able to Relate ~ and tg: tg E ~~). tgE a(~). and no element of a(~) has a link with tg. The propagation was stopped at t 4 because there are two pathes from it to tg: one direct through ls (t 6 e ~t 4 )) and the other one through ~· In this case we have to con­ tinue the propagation to be sure that all ascendants of 1s are really Related to tg. The relation is propagated to all the ascendants until 'o while avoiding it for ascen­ dants already related to the destination node. The algo­ rithm proposed is then:

The third step in this algorithm tests if there is a path from p(u) to v through residue arcs that contains a descendant of p(u). In this case we are in the conditions described previously. This test is described only in a mathematical formalism because its efficient implemen­ tation needs special care and some modifications in the Relate procedure that are of less interest here.

This algorithm runs a maximum of r(u) comparisons in the worst case, but in fact, in many cases, it will stop sooner: the algorithm stops as soon as p(u) is linked to v, this may happen very quickly, and then, the algorithm continues only if there is more than one path that links p(u) to v and if one of those pathes contains a -descendant of p(u). This is a very strong condition that may seldom occur.

3.3. Collapsing 2 points

When the points of a loop can be made identical (i.e. there is no -:~; arc between them), they are collapsed to one point This is done by keeping the point with the highest rank and linking it through all the relations han­ dled by the other points that are removed. This involves reindexing their successors, and modifying arcs and branches issued from their predecessors.

3.4. Removing points and relations

IxTeT enables removal of points and relations if needed. Removing a point u requires 2 operations: putting p(u) as parent of all the children of u and reindexing its descendants, and then, redirecting all the residue arcs pointing to u and to successors of u.

For removing a relation that is a branch of the tree from u to v, we have to find the predecessor of v with the highest rank, and put it as p(v). If no predecessor remains,\, is taken. Then, reindexation starts at v.

If the relation removed is a residue arc from u to v, v is just removed from a(u), this has to be propagated to the ascendants of u until one of them is related to v by another path than the one that contains u.

Notice that the reindexation used here is slightly different from Reindex: each step verifies if there is no predecessor with a higher rank than the new one, and in this case, changes the parent.

4. Experimental results

All the algorithms described in the previous section were implemented (on a Sun 4-260 in Sun Common Lisp), and tested [Mounir]. The workload for insertion of points and arcs in the lattice, and for retrieval or removal of relations between points were recorded.

Tests were made on 50 lattices, randomly . generated, and growing in size up to 2000 points. Each lattice was generated by adding at each step one point and k relations (algorithms Addpoint and Addrelation). We experi­ mented on data for k=2 to 5, without noticing a signifi­ cant change in performances. Average running times increased very slightly from k=2 to 3, then decreased for k=4 and 5. Results reported are for k=2. Figure 3 plots 20 average times, and 2 standard deviations, for retriev­ ing the relation between 2 random nodes. Each point is averaged over 2500 runs: 50 retrievals in 50 lattices.

The same information concerning the insertion of one relation (procedure Addrelation) is given in figure 4.

·

• the proposed TMM seems to be in average of lin­ ear complexity for both retrieval and insertion of relations; due to reindexation, the standard devia­ tion is however higher for insertion; indeed, if a relation is added near the root of the lattice, the part of the lattice to be reindexed may remain large despite the pruning heuristics, that are effi­ cient only in the average;
• the linearity constant is very low: our non opti­ mized Lisp implementation required:
• about .1 second to insert a new relation in a 2000 points lattice
• less than 70 millisecond to compare 2 points in a 2000 points lattice
• the space complexity of IxTeT seems also to grow linearly; a 2000 points lattice required less than 20000 memory units (cons cells).

In parallel with these experimentations, the propaga­ tion algorithm of [Allen 83] was implemented. Howev­ er we could not manage graphs larger than 80 intervals (less than 160 points): this algorithm is in O(n 2 ) space. Insertion in a graph of 50 intervals required about 4 to 5 seconds. Since insertion is in O(n 3 ) time, it would have a prohibitive cost for much larger graphs.

Experimental results of Allen's algorithms are reported in [Koomen] without giving running time. To give an idea, a graph of 101 intervals and 450 relations is processed by TimeLogic through llx10 5 calls to the basic constraint propagation function (performs some table lookups and unions of fixed length lists). If the graph is hierarchized 4.5x10S calls to this function are required. To our knowledge no work reported the appli­ cation of the transitive propagation algorithm for a graph of several hundred nodes.

5. Conclusion

lxTeT abilities for dealing with symbolic temporal knowledge can be extended to numerical quantitative con­ straints and to constant points (dates). All numeric relations and dates may be given with intervals precising earliest and latest possible occurrence or simply errors foreseen. Indeed it is easy to have in IxTeT an absolute referencing system by dates with qualitative relations. A point can be attached to a date. Arcs can be labeled by durations. The direct link that exists between durations and dates allows several deductions on the partial order of points. A lattice may have some nodes known as pre­ cise dates, others are variables linked with qualitative relations, and others have dates deduced from quantita­ tive relations.

In conclusion this paper presented an original approach for designing a TMM that has some interesting properties:

• it relies on a Time-Point Algebra that gives the
• same expressive power as the restricted Interval Algebra which permits completeness in polynomi­ al time;
• it makes use efficiently of a maximum spanning tree of the lattice together with a particular index­ ing scheme for checking in constant time ancestral information and for reducing and pruning the prop­ agation and search; this data structure gives a pre­ cise and dynamic hierarchy for the temporal rela­ tions;
• it is shown experimentally to be of linear space and time complexity for both operations, retrieval and updating, thus bringing a significant improve­ ment over known algorithm;
• it permits removal of points and relations from the time-map;
• it can deal with numerical knowledge attached to time.