Qualitative Temporal Reasoning with Points and Durations

1 Introduction

Representing and reasoning about temporal knowledge is essential for many areas of Artificial Intelligence. Several constraint-based systems for temporal reasoning have been proposed, mainly concentrated on two kinds of for­ malisms: qualitative approaches [Allen, 1983; Vilain and Kautz, 1986) and quantitative or metric systems [Dean and McDermott, 1987; Dechter et al., 1991). Later ef­ forts [Meiri, 1991; Kautz and Ladkin, 1991] have been done on integrating both qualitative and quantitative information between time points and intervals in a sin­ gle constraint-based computational model for temporal reasoning. Systems supporting duration reasoning have been proposed as well. Allen [1983) has designed a du­ ration reasoning system that allows relative information

*This work was funded by the spanish CICyT through grant TIC95-0604

(e.g. interval I took longer than interval J) and repre­ senting uncertainty. Duration information is encoded in a network orthogonal to the interval relationship net­ work, but total consistency of this network is not guar­ anteed. Temporal constraints on durations are not usu­ ally managed in point-based formalims. Barber [1993] presented a duration-based temporal model with metric constraints. But this model is restricted in the sense that no disjunctive qualitative constraints are allowed.

We present here a qualitative temporal reasoning sys­ tem that takes both points and durations as primitive ob­ jects and allows relative and indefinite information. We formaly define a point duration network, PDN for short, as a structure formed by two PA networks separately but not independently, since ternary constraints are in­ troduced for relating point and duration information. In section 2 we adapt some of the concepts developed for the point algebra networks, such as consistency and min­ imality, for the new point-duration model. In section 3 we propose some reasoning task for PD networks and prove that the problem of determining consistency in a PDN is NP-complete. A simpler and polynomial-time decision problem is introduced for a restricted kind of PD networks. Finally we suggest how to determine con­ sistency and find minimal network with an exponential­ time algorithm for the general case.

2 Definitions

In this section we review Vilain and Kautz's [1986) point algebra (PA) and PA networks for representing qualita­ tive relations between points. Then we will see how we can augment PA networks with additional variables that represent durations (or elapsed time) between any two points of time, and additional relations expressing re­ lative information concerning durations (e.g. duration between temporal points x; and Xj is less than duration between points Xk and xm)·

The point algebra (PA) is a relation algebra [Tarski, 1941] whose elements are the possible subsets of T = { <, >, = }, where T is the set of (mutually exclusive)

primitive or basic qualitative temporal relations that can be hold between any two points of time.

A PA network is a network of binary relations [Mon­ tanari, 1974] where the variables X1, ... , Xn represent time points having the same domain, that may be, for example, the set Q of rational numbers, and the binary relations between variables are of the form R;j , where R;j is a relation of the point algebra that constraints the possible values for variables x; and Xj.

2.1 Point Duration Networks {PDN)

We define a point duration network, PDN for short, as a struture EPD = (Np, ND, Rel(P, D)) formed by two PA networks N p and N D and a set of ternary constraints relating points and durations together, where

• N p is determined by a set P = { x1, ... , Xn} of point variables that. take values over the rational numbers and a set

of binary relations between points of time.

• N D is given by a set D = { d;j 11 ~ i < j ~ n} of duration variables, again over the rationals, and a set

of binary relations between durations.

• Rel(P,D) = {~ij ~ 4)311 ~ i,j ~ n} such that

We refer to Rel(P), Rel(D) and Rel(P, D) alto­ gether as EpD-constraints.

We can represent indefinite information both in the N p and N D networks, since the relations R;j and R;j,km are allowed to be a disjunction of primitive relations in T . Each duration variable d;j represents time elapsed between two temporal points x; and x j. It does not supposes anything about the relative position of points x; and x j. This information is encoded in the N p net­ work. In order to properly compare the magnitude of separation between points, we consider durations must take non-negative values and so we use the euclidean dis­ tance to model durations between points. Consequently, equations d;j ~ lx; - Xj I impose ternary constraints that show the influence of points over durations and vicev­ ersa. Since d;j = lx; - Xj I = lxj - xd = dj; we need only one duration variable d;j ( i < j) for representing time elapsed between any two points x; and Xj. Hence, variable dj; would be redundant and it is not considered as part of durations set D .

As a consequence of ternary constraints Rel(P, D), the PA networks N p and N D are not independent of each other and thus we cannot solve them as independent bi­ nary constraint satisfaction problems (CSP). Note that we use the term network for a 'EpD structure although this is not a network in a strict sense, since EpD does not describe a binary CSP. Alternatively, we could also consider the problem represented by EPD as a general (nonbinary) and continuous domain CSP whose varia­ bles are V = P U D, the domain of each variable is Q, and C = Rel(P) U Rel(D) U Rel(P, D) is the set of bi­ nary and ternary constraints. We prefer presenting the problem as two PA networks Np and ND separately but not independently since it clearer expresses the different meaning of point and durat ion variables and constraints, and also offers the possibility of borrowing some of the representation and reasoning techniques developed in the study of point algebra and binary networks. We follow an idea suggested by Allen (1983] when he proposes a duration reasoning system whose duration information is encoded in a network orthogonal to the interval rela­ tionship network.

2.2 Consistent and Minimal PDN

Given a PD network 'EPD = (Np, ND, Rel(P, D)) with n point variables, a n-tuple of the form

that denote the assignment X 1, ... , Xn to x1, .. . Xn re­ spectively, is a n-compound label [Tsang, 1993] for point variables. Similarly, a d-compound label for duration variables, where d = nx(;- 1 ) is ad-tuple which assigns d rationals values to d duration variables, i.e.,

A pair C = ( C p , CD) is a consistent instantation of the PD network EPD if an only if the assignments to point and duration variables given by Cp and CD satisfy all the EpD-constraints, what means that,

The (n +d)-tuple

satisfiying conditions {1) is a solution tuple of the net­ work EPD ·

A PDN is consistent if at least one solution tuple ex­ ists. Otherwise the network is inconsistent. A consistent PD network EpD represents a (n + d)-ary relation 'EpD­

(n+d) ...--"""---.. p ~ Q x .. . x Q defined by the set of all solution tuples of'EPD·

Semanticaly, a consistent instantation of a network Epv is a description of a world where we can map points to a time line, in such a way, we not only preserve the rel­ ative position amongst points but also the relative mag­ nitude of separation between them.

Example 1 Let Epv be a PDN with three point varia­ bles, such that x1 < x2, x2 < xa and d12 > d2a (anyother variables are unconstrained). One consistent instantation to this network may be C = (Cp , Cv) , where

A PD network E:i.v = (Nf,,N~,Rel 5 (P,D)) so that every constraint from Rel(P) and Rel(D) is a primitive relation, is called a simple PDN.

A simple PD network E~D = (N~, Nf>, Rel 5 (P, D)) is a consistent scenario of Epv = (Np , Nv, Rel(P, D)) if an only if the following conditions hold,

1. P 5 = P, and D 5 = D
2. 't/R;j E Rel(P), R~ E Rel 5 (P): R~ ~ R;i
3. 'VR;j,km E Rel(D), R~,km E Rel 5 (D) : R~,km ~ R~,km
4. E:j,D is consistent

One consistent instantation C = ( C p, CD) of a PD network Epv determines a consistent scenario E:j,D. In­ deed, for every two values X; , Xj in Cp , just one prim­ itive relation R~ from T is satisfied, since primitive relations are mutually exclusive; so it is the case that x; R~ x j and R~ ~ R;i and hence we take RD as the new constraint between variables x; and Xj in Rel 5 (P) of E~N. In the same way, we take RD,km as the primitive relation of Rel 5 (D) that is satisfied by the assignment Dij, Dkm to variables d;j, dkm in CD.

Two PD networks E~D = (Nj,,N}y,Rezl(P,D)) and E~D = (N~, N'JJ, Rel 2 (P, D)) with the same variables are equivalent iff they have the same solutions, what means that E~v-P = E~v-P· Following Montanari's work [1974] on binary CSP, we can define a partial or­ dering among the equivalence class of all PD networks representing the same (n + d)-ary relation. The ordering relation, affecting only binary constraints, is defined as follows,

for every 1 ~ i, j, k, m ~ n. As well, we can define the intersection of two equivalent PD networks E~D and E~D as a new equivalent PD network Epv = E~vnE~D whose binary relations are given by,

for every 1 ~ i,j,k,m ~ n.

Given a PDN Epv, there exists a unique PDN, EWv, equivalent to Epv which is minimal with respect to ~ (the uniqueness is guaranteed because equivalent net­ works are closed under intersection, proofs can be found in [Montanari, 1974]}. EWv is the minimal point du­ ration network representing Epv-p and the binary re­ lations in EWv are called the minimal relations. Each binary and primitive relation in EWv is feasible [Van Beek, 1992], i.e, we can find a consistent instantation of EWv which satisfies the given relation.

3 Reasoning Task with PD Networks

Given a PDN, some of the reasoning task we can think about are:

• Determining consistency.
• Find the minimal relation between two point or du­ ration variables.
• Find the minimal network equivalent to a given one.

Van Beek [1992] gives exact algorithms for these pro­ blems in the context of PA networks. But, as we sug­ gested previously in section 2, these algorithms are not suitable for PD networks. We can see that with a very simple example.

Example 2 Let Epv be a PDN with three point varia­ bles, such that x1 < x2, x2 < xa and d13 < d12 (anyother variables are unconstrained). There is no consistent in­ stantation because it must be d13 = d12 + d2a , but since d23 ~ 0 it is not possible that d13 < d12 . So Epv is inconsistent although N p and N D, considered as inde­ pendent PA networks, are consistent.

3.1 Consistency in PND

From the above PDN reasoning task, the main one is to determine consistency since we can find a polynomial transformation from the latest tasks to the first one. This would be useful if we could check for consistency in polynomial time. But, unfortunately, this is not pos­ sible, as we show in the next theorem. Let CONS_PDN be the decision problem of determining if a given PDN is consistent or not.

Theorem 1 CONSYDN is NP-complete.

Proof: We follow the general procedure described by Garey and Johnson [1979] for devising an NP­ completeness proof for a decision problem. First we show CONS_FDN belongs to the class NP. This is easy, since for a YES instance of the problem, a nondeter­ ministic Turing machine needs only to guess a consis­ tent instantation and check in polynomial time that the assignments satisfy all the Epv-constraints. In a sec­ ond stage we must find a polynomial reduction of known NP-complete problem to CONS_PDN. We use GRAPH

COLORING for this purpose. An instance of this prob­ lem is a graph G = (V, E) and an integer k, and the question is: is there a mapping f : V ----+ {1, 2, ... , k} such that (v, w) E E implies f(v) #- f(w) ?

Given an undirected graph G = (V, E) with lVI = n and an integer k we show how to construct a PD net­ work Epn = (Np, Nn, Rel(P, D)) such that Epn has a consistent instantation if an only if there is a coloring of G using k colors. The set of point variables is

where each Xk+j , (j > 1) correspond to a vertex of V. The set of duration variables is

We impose two kinds of constraints between point va­ riables. First, t; < t;+l, V 1 ~ i ~ k. Second, for each vertex v E V associated with variable Xk+j we reqmre that

Our intention is that ]t;, ti+1 [ is associated with color i and just with constraints (2) a vertex v can be mapped to any of the k colors. Now we must avoid two vertices connected by and edge being mapped to the same color. That is why we introduce the following constraints on duration variables. For each edge ( v, w) E E with asso­ ciated variables Xk+j and Xk+m we require that

The above is clearly a polynomial transformation and finally we must show the equivalence of both problems. If there exists a consistent instantation of Epn, con­ traints on points and durations forces two points v, w with ( v, w) E E not to be assigned values on the same interval ]t;, t;+l [, V 1 ~ i ~ k. So it must be possible to map vertex v and w to different colors. Conversely, if the answer to the instance of GRAPH COLORING problem is yes, we can find a consistent instantation of Ep n . For example, we taket1 = 1 and t; = t;_ 1 +3, V 1 < i ~ k+ 1. Now , V 1 ~ i ~ k we take di(i+1) = 3. For the rest of point variables, corresponding to vertices of the graph we calculate the appropriate assignments in the follow­ ing way. For vertices mapped to the same color we can assign the same value to its corresponding point vari­ ables. Suppose now we have (v, w) E E . Then if Xk+j corresponds to v and Xk+m corresponds to w, then we can find apropriate values (even integer ones) from dif­ ferent "color intervals" such that d(k+j)(k+m) > 3 as we require. Finally we compute the remaining assignments for duration variables calculating the distance between implicated points. ·

3.2 Consistency in Simple PDN

CONS_PDN so belongs to NP. But, can we really find a deterministic algorithm that solves this problem?, or what is the same, is CONS_PDN decidible?. To an­ swer this question we propose a new decision problem CONS..SIMPLE_PDN: given a simple PDN, is the net­ work consistent? We now show this problem can be solved in polynomial time.

Theorem 2 CONS..SIMPLKPDN E P.

Proof: We prove this showing a polynomial time algo­ rithm that for a given simple PD network E~n returns YES when E~n is consistent and returns NO when E~n is inconsistent. The algorithm basicaly finds a consistent instantation of E~ n if the network is consistent and thus returns YES, or shows that no such instantation exists and returns NO. We associate a precedence graph [Meiri and Pearl, 1990] G< ,P = (Vp, Ep) to the PA network N $. The set of nodes Vp are labeled with the indices of point variables and for every two points x;, Xj E P ,

• if x; < Xj we add the arc i-+ j to Ep
• if x; > Xj we add the arc j-+ i to Ep and
• we add both i -+ j , j -+ i to Ep just in the case Xi= Xj .

Now we associate a precedence graph to the PA network NZ. We take Vn = {ij 11 ~ i < j ~ n} U {do}. Each node ij is associated with duration d;j and the special node do represents the null duration. The set En is cal­ culated looking at duration constraints Rel 5 (D), in a similar way we have done with Ep. And for every dura­ tion variable, it must be d;j 2: do, by distance properties. So we include in En an arc do -+ ij for each d;j in D . In what follows it is requiered that x; R;j Xj ¢:} Xj R;j - 1 x;, where - 1 is the inverse PA operation and always x; = x; . Similar assumptions are made for relations between du­ rations.

We show in figure 1 a function for determinig consis­ tency in a simple PDN, named Cons..Simple and use two auxiliary functions Same..SCC(SCCp , i, j) that return true if vertices i and j are in the same strongly connected component of G<,P and Same...SCC(SCCn, ij, km) that do the same with vertices ij , km of G < ,n . A third func­ tion Exist..Solution is used to find a consistent instan­ tation if possible and returns true, otherwise returns false. For simplicity we just show the algorithms for Cons..Simple and Exist..Solution. Lines 1 to 3 just check if the PA network N $ is consistent and we adapt here Meiri and Pearl's consistency algorithm [1990] . We can say the same with lines 8 to 10 with respect to the PA network NZ. The idea is that if two vertices are in the same sec this forces correspondig variables to be equal, otherwise E~D would not satisfy Rel(P) or Rel(D) and thus the PDN would be inconsistent .

1. Seep := strongly connected components in G< ,P;
2. for each i, j E Vp such that Same....SCC(Seep , i, j) do begin
3. if R;j =/;" =" then return (NO);
4. for each (k E Vp) and (k =/; i, j) do
5. if R;k,jk =/;" =" then return (NO);
6. ED := ED U {ij ~ do}
7. end;
8. seeD := strongly connected components in G< ,D;
9. for each ij , km E VD such that Same..SCC(SeeD, ij, km) do
10. if R;j,km =/;" =" then return(NO);
11. for each ij E VD such that Same....SCC(SeeD, ij, d0 ) do begin
12. if R;j =/;" =" then return (NO);
13. for each (k E Vp) and (k =/; i , j) do
14. if R;k,jk =/;" =" then return (NO) ;
15. end;
16. if Exist_Solution(I;~D, Seep, SeeD) then return (YES);
17. else return (NO);

If N$ and Ng are, we can say "independently con­ sistent" , we must finally prove if there is a consistent instantation that satisfies not only Rel(P) or Rel(D), but also relations in Rel(P, D). Lines 4 to 6 check two metric properties that must obey any two points vari­ ables that are equal. First if x; = Xj obviously for every other different point Xk it must be d;k = lx; - Xk I = lxi- xkl = djk· And second if x; = Xj then d;j = 0 and so d;j must be forced to be in the same sec that null duration do . And conversely, if d;i = 0 then x; = Xj and d;k = djk (lines 11 to 14) .

Next we show the code for Exist....Solution in figure 2. By the construction of G<,P and G<,D and since all the relations between points and durations variables are primitive, the topological orders we calculate after find­ ing the strongly connected components (lines 1,2), are always unique. Because of this, we can assign values to duration variables arbitrarily but according to the con­ straints in Rel(D) (line 4). Then we calculate values for point variables such that for every x;, xi, d;j it is the case that d;j = jx;- Xj I (line 7), so Rel(P, D) are satisfied. Notice there is no matter which Xj is taken in line 7,

1. Let Do < D1 < · · · < Dm be the topological order from seeD;
2. Let P1 < P2 < · · · < Pq be the topological order from seep;
3. for k = 0 tom do
4. for each ij in Dk let d;j := k;
5. for each i in P1 let x; := 1;
6. fork= 2 to q do
7. for each i in Pk let x; := Xj + d;j I* such that j is in Pk-1 *I
8. for every x;, Xj E P do
9. if not x; R;i Xj then return false;
10. return true;

Figure 2: Function Exist....Solution(I;~D' seep, seeD)

due to the check we do in line 5 of Cons....Simple. Indeed, it must be d;j = d;j' for each j,j' E Pk_ 1 . Finally we must prove if the instantiation we have calculated for point variables satisfies constraints in Rel(P) (lines 8 and 9) . If the function returns true then a consistent in­ stantiation has been found. Otherwise, no solution exists when the function returns false. Although the function Exist....Solution only return true or false we could easily modify the code to return also the solution tuple if it required.

Hence, Cons....Simple correctly check for consistency in a simple PDN and this is done in polynomial time. In fact, Cons....Simple is O(d 2 ), where d is the number of duration variables. This time is due mainly to the cost of computing SCCs in G< ,D which is O(IVD I+ lED I) if we use Tarjan's algorithm (1972]. Since G<,D is a complete graph O(IVDI +lED I)= O(d 2 ). The topological order in line 1 can be computed with a depth-first search on the directed acyclic graph with SCC_D as the set of vertices, with cost 0( d 2 ) in the worst case. ·

Once we know how to determine consistency in a sim­ ple PDN, we could devise an algorithm for the same task with a general PDN. We have to examine each simple PDN extracted from the general one and apply Cons....Simple until one consistent scenario is found . Of course this algorithm is exponential in the worst case, when the network is inconsistent. Another exponential­ time algorithm could be developed to find the minimal network using the result of the next theorem.

Theorem 3 Given I;pD = (Np, ND , Rel(P, D)), the network I;~D = (NJ', , NJ;,RelT(P,D)) with the same variables and binary relations given by,

where the union is over all the consistent scenarios ~~D of ~PD, is the minimal network equivalent to ~PD.

We omit the proof since a similar one can be found in [Dechter et al., 1991]. This theorem shows we can obtain the minimal network ~Wn and minimal binary relations by generating all the simple PDN from ~PD, checking for consistency with Cons..Simple and taking the union of primitive and feasible relations.

4 Conclusion

We have presented a qualitative temporal reasoning sys­ tem that takes both points and durations as primitive objects and allows relative and indefinite information. We have formally defined a PDN as a structure formed by two interconnected PA networks. This allows us to borrow and adapt some of the concepts developed for the point algebra networks, such as consistency and min­ imality. We have proved that the problem of determining consistency in a PDN is NP-complete and a simpler and polynomial-time decision problem for a restricted kind of PD networks has been introduced which is useful for cheking consistency and finding minimal network in the general case.

Despite the intractability of reasoning tasks with gen­ eral PD networks, we think these tasks may be useful in several areas such as scheduling and planning sys­ tems. The analysis of such systems requires the ability to specify and prove relations between critical states or actions and their durations. So, several strategies may be adopted to put this PD reasoning model to work in practical systems. One may be, for instance, to reach minimality both in N p and N D independently, and con­ secuently, accept its incompleteness. Or better, find how to restrict the information in a PDN so that we can obtain polynomial-time reasoning algorithms. The re­ stricted model, however, may be expressive enough to work well in practice. Actually we are working in this di­ rection and have found how restricting just the relations between points may lead to polinomial-time problems. We are also investigating how to integrate qualitative and metric information between points and durations and the possible aplications of these new models.