Incremental Tractable Reasoning about Qualitative Temporal Constraints

1 Introduction

Constraint-based qualitative temporal reasoning is a widely studied area of AI in which the most prominent approaches are Allen's Interval Algebra (IA) [1983] and Vilain and Kautz's Point Algebra (PA) [1986]. Given a CSP of tempo­ ral constraints, fundamental reasoning problems are deciding sati sfiability of the CSP, finding a solution, and computing its "minimal labels". These problems are NP-hard for the full IA, while they are polynomial for PA and for several frag­ ments of lA, such as Nebel & Bi.irckert [1995] ORD-Horn subalgebra, which is the unique maximal tractable subclass of IA containing all the basic relations.

In many applications of temporal reasoning we are in­ terested in "dynamic" or on-line reasoning. For instance, given an initial (possibly empty) CSP of temporal constraints, whenever a new constraint is asserted, we want to in maintain a solution of the CSP, rather than recomputing it from scratch using a "static" algorithm.

The design of algorithms for dynamic polynomial prob­ lems is an important research field in operation research and theoretical computer science (e.g., [Ausiello et al., 1991]). A dynamic problem can be either semi-dynamic or fully­ dynamic. In the semi-dynamic version we deal with informa­ tion that is incrementally given (or decrementally retracted).

In the fully-dynamic version, we deal with both assertions and retractions. Typically, the worst-case performance of an algorithm for a dynamic problem is specified in terms of its amortized complexity for a single operation (assertion or re­ traction), that can be defined as the average runtime per oper­ ation over a worst-case sequence of operations [Tarjan, 1985].

The large majority of the algorithms that have been devel­ oped for reasoning within tractable classes of qualitative tem­ poral constraints are static. In this paper we investigate the incremental version of some reasoning problems for PA and ORD-Horn, discussing the behavior of existing techniques and proposing new ones. Given a sequences of O(n 2 ) input constraints involving n variables, our incremental algorithms improve the total runtime required for processing s using ex­ isting techniques by a factor of O(n) or O(n 2 ).

In Section 2 we give the necessary background on PA and IA. In Section 3, after analyzing the use of a path-consistency algorithm for incremental satisfiability checking, we propose new incremental algorithms for finding a solution of a CSP over either PA or ORD-Horn, and for computing the minimal labels of a CSP over PA. Finally, in Section 4 we briefly dis­ cuss the fully-dynamic version of the problems considered, and we mention further results and future work.

2 Background on PA and lA

Vilain and Kautz's Point Algebra [1986] consists of three basic relations between time points ( <, >, = ), all possible unions of them(~, 2':, f:-, and?, where? is the universal rela­ tion), and of the empty relations (0). Allen's Interval Algebra [1983] consists of thirteen basic relations between temporal intervals, all possible unions of these relations, and the empty relation. PA and IA are closed under the operations union (U), intersection (n), difference (\), converse (~), and composi­ tion ( o ). The first four operations are defined in the standard way. The composition for two relations can be derived from the transitivity tables of the basic relations in PA and lA.

A qualitative temporal constraint satisfaction problem (or briefly temporal CSP) in our context is a set of constraints of the kind xRy, where x andy are either point variables or interval variables, and R is either a PA-relation (if x and y are point variables) or an !A-relation (otherwise).

Given a temporal CSP 8 over either PA or IA, a funda­ mental reasoning problem is deciding the satisfiability of e. e is satisfiable if and only if there exists a solution fore, i.e., an assignment of temporal values to the variables of e (ratio­ nal numbers for point variables, pairs of rational numbers for interval variables) such that all the constraints in e are satisfied . The problem of deciding the satisfiability of 8 will be called PSAT, if 8 is over PA, and !SAT if 8 is over IA. The problem of finding a solution for 8 will be called PSOL, if 8 is over PA, and I SOL otherwise.

A related reasoning problem is finding a scenario that re­ fines a given temporal CSP. A scenario of a CSP 8 is a satisfi­ able refinement of 8, where the constraints between all pairs of variables are basic relations. A CSP 8' is a refinement of 8 if and only if 8' and 8 involve the same variables, and for every pair of variables (x, y) such that xR'y E 8' and xRy E 8, R' ~ R. 1 Any scenario of a satisfiable temporal CSP over PA (IA) identifies a total order u of the point (in­ terval endpoint) variables of the CSP that is consistent with the constraints of the scenario, and in which point (interval endpoint) variables that must have the same interpretation are mapped to the same position. Clearly, from u we can derive a solution for the CSP by just assigning to the points (end­ points) of u numbers consistent with their relative order. 2

Any temporal CSP 8 involving n variables can be pro­ cessed using a cubic time algorithm that refines 8 to an equiv­ alent path consistent CSP [Montanari, 1974]. A CSP is path consistent if for every subset of constraints involving three variables i, j, and k, the relation R;k between i and k is stronger or equal than (i.e., is a subset of) the composition of R;j and Rjk.

A temporal CSP is minimal if, for every pair of variables i, j, the relation R;k between i and k is the strongest relations between i and k that is entailed by the CSP, i.e., for each basic r;j relation in R;j there exists a scenario for the CSP in which R;j is refined to r;i. We call the problem of computing the minimal CSP PM IN for PA, and I MIN for IA.

From a computational point of view, PA and IA have dif­ ferent properties. The reasoning problems introduced above are polynomial for PA, while they are NP-hard for IA [Vi­ lain and Kautz, 1986]. In particular, PSAT and PSOL can be solved in O(n 2 ) time using van Beek's method [1992], while PMIN requires O(n 4 ) time [van Beek, 1992; Gerevini and Schubert, 1995]. These techniques use a graph-based repre­ sentation of the CSP that in [ Gerevini and Schubert, 1995] is called temporally labeled graph (TL-graph). A TL-graph is a graph with a set of labeled edges, where each edge connects a pair of distinct vertices v, w representing the point variables of the temporal CSP. The edges are either directed and la­ beled :S or <, or undirected and labeled =f. (=-constraints are represented by a pair of :::;-constraints). van Beek's method for finding a scenario for a satisfiable CSP of FA-constrains is based on first identifying the strongly connected components (SCC) of the TL-graph representing the CSP [Cormen et al., 1990] using only its :S-edges. Each SCC is then collapsed into a single vertex representing an equivalent class of vari­ ables that must be interpreted with the same temporal value. If we omit the =f.-edges from the resultant graph, we obtain a directed acyclic graph that we call the induced precedence graph of the CSP. From a topological sort of the vertices of this graph we can easily derive a scenario for the CSP. 3

1 Without loss of generality we assume that, if no information between x and y is provided, R is the universal relation, and that for every pair of variables (x, y) such that xRy E e, yR~ X E e.

2 E.g., we assign an integer ito the points in the first position of u, i + 1 to the points in the second position, etc. If we have a solution, we can derive a total order (and hence a scenario) in a trivial way.

Enforcing path-consistency to a temporal CSP requires cubic time and is sufficient to decide PSAT [Ladkin and Maddux, 1988], but it does not solve PMIN. In order to solve PM IN for a CSP over PA, in addition to enforce path­ consistency to it, we need to identify particular 4-variable constraint subsets of the path consistent CSP containing a :::;-constraint that should be refined to "<". Such subsets are called forbidden sub graphs in [van Beek, 1992] and =f.­ diamonds in [Gerevini and Schubert, 1995].

Regarding IA, several tractable fragments have been iden­ tified. The Simple Interval Algebra (SIA) [van Beek, 1992; Ladkin and Maddux, 1988] is formed by the !A-relations that can be translated into a conjunction of FA-constraints be­ tween interval endpoints. All reasoning problems for a CSP n over SIA can be solved by applying the corresponding al­ gorithms to the FA-translation of !1. The most interesting tractable fragment of IA is Nebel and Biirckert's ORD-Hom class [1995]. ORD-Hom subsumes SIA and is the unique maximal tractable sub-algebra of IA containing all the basic relations. Each constraint C over ORD-Hom can be trans­ lated into a set of disjunctions of FA-constraints of the form p = q, p :S q or p =f. q, where p and q are endpoints of in­ tervals in C, and at most one literal is of type "=" or ":S". Given a temporal CSP n over ORD-Hom, 1r1 (!1) will denote the CSP of FA-constraints formed by the unary disjunctions (FA-constraints) in the point translation of all interval con­ straints in n.

Like PSAT, !SAT for ORD-Hom can be decided in cubic time by using a path-consistency algorithm. !SOL for ORD­ Hom can be solved in square time, if the input CSP is known to be path consistent[Gerevini and Cristani, 1997], in cubic time otherwise [Ligozat, 1996].

In the rest of the paper, the incremental version of the rea­ soning problems for a temporal CSP is indicated by adding the prefix "I" to the name of the corresponding static problem, e.g., the incremental version of PSOL is 1-PSOL. Without loss of generality, we assume that the initial temporal CSP al­ ready involves all variables, possibly constrained only by the universal relation. Moreover, our amortized complexity anal­ ysis is based on input sequences of length quadratic in the number of the variables. These assumptions are discussed in an extended version of the paper [Gerevini, 2003].

3 Incremental Tractable Reasoning

3.1 Path-consistency for 1-PSAT and 1-ISAT

Although van Beek's method for solving PSAT requires only quadratic time, when we consider the incremental version of this problem (1-PSAT), enforcing path-consistency turns out to be more efficient than a simple iterative application of van Beek's (static) algorithm. In fact, we can use a path­ consistency algorithm like the one given in Figure 1 (PC), which was proposed in [Allen, 1983] and slightly reformu­ lated and improved in [Vilain and Kautz, 1986; Bessiere, 1996], to incrementally process a sequence of O(n 2 ) PA-

3 A topological sort for a DAG is a linear order u of its vertices such that if v is a successor of w in the graph, then v precedes w in u.

Algorithm: PC

Input: the matrix representation M of a temporal CSP over either PA or lA.

Output: fail, if enforcing path-consistency to the input CSP

generates the empty relation; the matrix representation of a path consistent CSP equivalent to the input CSP, otherwise.

1. Q:={(i,j)li<j}

2. while Q =f. 0 do

3.

select and delete an element from Q;

4.

5.

for k =f. i, k =f. j do

ifREVISE(i,j, k)then

6.

7.

if M[i , k] = 0 then return fail

else add (i, k) to the end of Q;

8.

if REVISE(k, i, j) then

9.

10.

if M[k, j] = 0 then return fail

else add (k , j) to the end of Q;

11. return M.

Subroutine: REVISE(i, k, j)

I. if M[i, k] or M [k , j] is the universal relation then return false ;

2. S := M[i, k] o M[k, j];

3. if M[i, j] <;:; S then return false

4. M[i, j) := M[i, j) n S; M[j, i] := M[i, j)-;

5. return true;

Figure I: A path-consistency algorithm for qualitative temporal constraints as formulated in [Bessiere, 1996].

constraints in O(n 3 ) total time (i.e., the amortized time com­ plexity per input constraint is linear). This is better than reap­ plying van Beek's algorithm after each constraint assertion, which requires O(n 4 ) total time. Similarly, for any frag­ ment of IA for which enforcing path-consistency is suffi­ cient to decide satisfiability, we can use PC to solve I-ISAT in O(n 3 ) total time, instead of O(n 5 ) . More precisely, Jet ( C1, C2, ... , Ck) be the sequence of the input constraints, G0 an initial (possibly empty) satisfiable temporal CSP, and Gi = Go u { Cj I j :::; i} (i > 0). 4 To decide the satisfiability of each Gi, we consider three cases:

• ( I) if the relation R of Ci = xRy is weaker than the relation R' of the corresponding constraint in Gi_1 , then clearly Gi is satisfiable, and no further processing is needed;
• if R n R' is the empty relation, then Gi is unsatisfiable and we return fail;
• if none of the previous cases holds, then, first we revise the relation between X andy toR' n R (and between y and x toR'~ n R~), and then we run PC on the resul­ tant revised CSP with step 1 modified so that Q initially contains only the item (x , y).

We call this simple method incremental path-consistency (IPC). This technique has the following important property, that will be exploited by the algorithms in the next sections. 5

Theorem 1 !PC solves I-PSAT and I-ISAT for ORD-Horn in 0 ( n 3 ) total time, where n is the number of temporal vari­ ables.

4 0o may already contain up to O(n 2 ) constraints different from the universal relation. For CSPs over PA k ::; 6 · (n 2 -n)/2, because we assume that there is no duplication in the input sequence, and there are at most 6 different input FA-constraints between any pair of variables (the empty and the universal relations are not valid input relations). Similarly, for CSPs over IA k ::; (2 13 - 2) · (n 2 - n)/2.

5 for lack of space we omit proof details, which are available in [Gerevini, 2003).

Proof. Since a pair (x, y) enters into Q only when the rela­ tions between x and y is revised, and each relation R can be revised at most twice, if R E PA, or at most 12 times, if R E IA, it follows that the total time complexity is O(n 3 ). 0

It is worth noting that, as pointed out by Bessiere [Per­ sonal Communication, 1997], the O(n 3 ) time complexity of Ligozat's algorithm [ 1996] for finding a scenario of a path consistent CSP over ORD-Hom follows from Theorem 1.

3.2 An Algorithm for I-PSOL

For the incremental version of PSOL (I-PSOL) the simple application from scratch of van Beek's static algorithm [1992] after each constraint assertion requires O(n 4 ) total time. 6

In this section we propose an algorithm for solving I­ PSOL in O(n) amortized time, i.e., the total time complexity for processing a sequence on O(n 2 ) constraint assertions is O(n 3 ) . The algorithm is based on maintaining a topological sortS for the precedence graph of the input CSP in which the constraints are incrementally given. Let Si- 1 be a topological sort for I:i-1 (I:i-1 is satisfiable). When we process a new constraint ci we perform two main operations:

• (i) we check whether I:i = I:i-i U { Ci} is satisfiable;
• (ii) if I:i is satisfiable, we update Si-1 to derive Si.

As we have seen, (i) can be solved in O(n 3 ) total time by using IPC. Regarding (ii), there are two related difficulties to address: ci induces an edge (or precedence constraint) in the precedence graph that invalidates Si- 1 ; if the relation of Ci is "=" or":::;", new equalities may be generated (i.e., in the TL-graph representation a new SCC may be generated, and the precedence graph should be revised accordingly). The algorithm lNCREMENTAL-PA-SOL given in Figure 2 accom­ plishes (i) and (ii) taking these cases into account. The rest of this section is devoted to the description of the algorithm.

The current path consistent CSP is represented by a matrix M, while the current topological sort is represented by an ar­ ray T such that T[j] = v if and only if v is the j-th element of the sort. Ord( v) denotes the position of v in the topolog­ ical sort (i.e., the index of v in T). lNCREMENTAL-PA-SOL uses a modification ofiPC, called IPC-1, in which each vari­ able has a flag (EQ) which is set to false before running INCREMENTAL-PA-SOL. The EQ-flag of a variable v is re­ vised to true if the relation of the new input constraint is "=" and v is one of its variables, or if during the propagation of the new input constraint, the relation between v and any other variable is revised to"=". The second case is handled in IPC-1 by using an extension of the subroutine REVISE in which, if M[i, j] is revised to"=", then EQ[i] and EQ[j] are set to true. Clearly, this modification does not increase the complexity of the incremental path-consistency method.

If the relation of the new PA-constraint xRy is in { <, :::; } , then xRy may induce a precedence constraint x -< y for Si that is not satisfied in Si_1 . (Similarly for R E {>, ;:::} inducing y -< x.) This is the case when I:i is satisfiable, Ord(x) > Ord(y) (orOrd(y) > Ord(x)), andxRy induces no new equality in I:i (i.e., the set E of step 3 is empty).

6 A temporal CSP over PA may involve O(n 2 ) constraints with relation different from "?", and each of these can be revised at most twice by additional input constraints.

Algorithm: lNCREMENTAL-PA-SOL Input: the matrix representation M of the path consistent CSP of ~i - l; a topological order T for the precedence graph G of ~i- 1; a new PA-constraint xRy. Output : A solution for ~i = ~i-1 U {xRy }, if ~i is satisfiable, fail otherwise. I. M := IPC-l(M,xRy); 2. if M =fail then return fail;

3. E :=set of the point variables x such that EQ[x] =true (E is a global variable used also in UPDATE-TSORT); 4. if E is empty then 5. if R E { <,:::;}and Ord(x) > Ord(y) then 6. UPDATE-TSORT(T,x,y) ; 7. if R E {>, 2:} and Ord(y) > Ord(x) then 8. UPDATE-TSORT(T,y ,x) 9. else collapse the vertices of Gin E to x; 10. S :={vI v '/. E- {x} 1\ Ord(y):::; Ord(v ):::; Ord(x)}; II. L := list of the variables in S topologically sorted using G; 12. for j := Ord(y) to Ord(x) -lSI+ 1 do 13. T[j] := Pop(L) ; Ord(T[j]) := j; 14. for j := Ord(x)- lEI+ 2 to V(G) do 15. T[j] :=T[j + IEI-1]; Ord[T[j]] :=j;

16. return an ass ignment to the variables in ~i consistent with T. Subroutine: UPDATE-TSORT(T, x, y) (The topological sort T for ~i-I is updated using the new prece­ dence constraint x -< y, and it becomes a topological sort for~;. ) I . shift:= I; 2. L := a list containing only y ; 3. for i:= Ord(y) + 1 to Ord(x) do 4. if M[y , T[i]] E { <, :'S} then 5. add T[i] to the end of L; 6. shift := shift + I; 7. else Ord(T[i]) := i -shift; 8. T[i- shift] := T[i]; 9. for i:= Ord(x)-shift+l to Ord(x) do 10. z := Pop(L); T[i] := z; Ord(z ) := i;

Under these conditions, the new constraint requires to update Si-1, which is accomplished by steps 4-8. Specifically, if the induced precedence constraint is x -< y, we run the sub­ routine UPDATE-TSORT(T, x, y), which revises the current topological sort (T) in the following way.?

UPDATE-TSORT considers each temporal variable v such that Ord(y) S Ord(v) S Ord(x). (Notice that the only part of Si- 1 than can be invalidated by x -< y regards the variables from T[Ord(y)] to T[Ord(x)] .) If ~i entails y S v, then in si y (and hence also x ) must precede v, because in the precedence graph there is a path from y (x) to v. Since by step I of the main algorithm M is the path consistent CSP of ~i' these entailment can be checked in constant time by simply looking up at the appropriate entries of M (step 4 of the subroutine). The v-variables that must follow x are added to the end of a list L that initially contains only y. Once all variables in the relevant part of Si_1 have been considered, those that are in L should be postponed, while the others can be anticipated. In particular, if a variable is not added to L, we can shift it backward a number of positions equal to the number of items currently in L (which is given by the value of shift). This is done by steps 3-8 of the subroutine, while steps 9-10 move forward the variables in L to the positions ofT that were occupied by the variables shifted backward. Notice that when UPDATE-TSORT(T, x, y) terminates, the relative order of the variables that entered into L, as well as of those that were shifted backward, are not changed in the revised topological sort. Figure 3 shows a simple example.

7 UPDATE-TSORT is similar to a technique used by Marchetti et al. [ 1993] in the context of an algorithm for detecting cycles in a DAG.

If xRy induces new equalities (E is not empty), then the variables in E, together with those possibly represented by them, form an equivalence class. Step 9 collapses the ver­ tices in the precedence graph G of ~i- 1 corresponding to the variables in E into a single representative vertex x, transfer­ ring to x all incoming and outgoing edges of the collapsed vertices. In order to update T, we need now to reorder the variables from T[Ord(y)] to T[Ord(x)] that have not been collapsed. These variables are topologically ordered using G by step 11, and assigned to T in positions from Ord(y) to Ord(x) -lEI+ 1. Then, steps 13 and 14 shrinks T by shifting backward the variables appearing after x in T, starting from position Ord( x) - I El + 2 and with a shift equal to the num­ ber of variables (vertices) eliminated from G (i .e., lEI - 1). Figure 4 gives an example illustrating steps 9-15.

Theorem 2 INCREMENTAL-FA-SOL solves 1-PSOL in O(n 3 ) total time, where n is the number of temporal vari­ ables.

Proof (sketch). Correctness of the algorithm follows from Theorem I and the discussion in the description of the algo­ rithm. By Theorem 1 step 1 requires O(n 3 ) total time. The other most costly steps are 9, 11 requiring O(n 2 ) time. They are performed at most 0 ( n) times for any input sequence. 0

3.3 An Algorithm for I-PM IN

The simple use of van Beek's (static) algorithm for PM IN af­ ter each constraint assertion to solve I-PM IN requires O(n 6 ) total time. In this section we propose an algorithm for solv­ ing I-PM IN, INCREMENTAL-PA-MIN, requiring 0(n 4 ) total time. This is the best possible worst-case complexity bound.

In order to maintain a CSP over PA minimal when a new PA-constraint xRy is given, in addition to enforce path­ consistency, we need to identify and remove all possibly :f:-diamonds that are generated (see Figure 5). Since :f:­ diamonds consist only of constraints of type :S and :f:, clearly a new constraint can generate additional :f:-diamonds only if R n R' E { =, :S, 2:, :f:}, where R' is the relation between x andy in the minimal CSP of :Ei-l·

Let ~i-l be minimal CSP of :Ei-l, and f;i of the path con­ sistent CSP of ~i-1 U { xRy }. If R n R' E { =, :S, 2:} (and R C R'), then the new constraint and its propagation can generate new :S-constraints in f;i· It is easy to see that any new possible :f:-diamonds in f;i must involve one of these new :S­ constraints. Hence, in order to make f;i minimal, it suffices to identify and eliminate all diamonds involving one of these constraints. Figure 5 shows the only four possible types of :f:­ diamonds that can be generated in f;i by the new constraint x :S y. Note that cases (1) and (2) are symmetric and can be reduced to the same case (analogously for (3) and (4)).

If RnR' = ":f:" (and R c R'), then the propagation of xRy cannot give rise to new :f:-constraints, and hence in order to make f;i minimal, it suffices to identify and eliminate all new diamonds involving x :f: y.

Our algorithm for solving I-PM IN is given in Figure 6. It uses a modification of IPC, called IPC-2, which like IPC-1 is a revision of IPC to keep track of certain constraints gen­ erated by the propagation of xRy. IPC-2 adds all pairs of variables whose relation has been refined to "<" to a list L. L is a global variable that is initialized by Steps 1-2 of INCREMENTAL-PA-MIN to the list containing either (x, y), (y, x) or no pair. A pair of variables is added to L by the subroutine REVISE-2 of IPC-2, a modification of REVISE in which after step 4 we perform the following additional steps to update L:

• Algorithm: INCREMENTAL-PA-MIN Input: the matrix representation M of the minimal CSP of E;-;; a new PA-constraint xRy. Output: The matrix representation of the minimal CSP forE; = Ei-1 U {xRy}, ifE; is satisfiable, fail otherwise. 1. if R n M[x , y] = ":S" c M[x, y] then L := ((x, y)) else L := (); 2. if R n M[x, y] = "~" C M[x, y] then L := ((y, x)) else L := () ; 3. if R n M[x, y] = "#" C M[x, y] then N :=true else N:=false; 4. M := IPC-2(M, xRy ); 5. if M = fail then return fail; 6. for each ( u, v) E L do 7. for each w, z such that w # z and w, z # u, v do 8. if M[u, w] = M[v , z] = M[w, z] = ":S" 1\ M[v, w] = "#" 9. then M[u, z] := "<"; M[z, u] := ">"; 10. if M[w, u] = M[w, z] = M[z , v] = ":S" 1\ M[u, z] = "#" 11. then M[w, v] := "<"; M[v, w] := ">"; 12.if N then 13 for each w, z such that w # z and w, z # x, y do 14. if M[w, x] = M[w, y] = M[x, z] = M[y, z] = ":S" 15. then M[w, z] := "<"; M[z, w] := ">"; 16.return M .

Figure 6: Algorithm for solving 1-PMIN. Lis a global variable that is modified by IPC-2 as described in the text.

1. if M[i, j] = ":S" then add ( i, j) to L

6. else if M[j, i] = ":S" then add (j, i) to L

Step 4 of INCREMENTAL-PA-MIN runs IPC-2 to (a) decide PSAT for :Ei, (b) enforce path-consistency toM, and (c) up­ date L with the new implied :S-constraints. If :Ei is satisfiable, then steps 6-II identify all new :f:-diamonds that are gener­ ated in M by the new constraint x :S y. These diamonds are eliminated by revising to "<" or">" the relation of the "non-minimal" constraints (steps 9 & II). Finally, steps I3I5 eliminate all new :f:-diamonds involving x :f: y.

Theorem 3 INCREMENTAL-PA-MIN solves I-PM IN in O(n 4 ) total time, where n is the number of temporal vari­ ables.

Proof (sketch). Since the algorithm eliminates all new :f:­ diamonds, correctness follows from Theorem I and fact that any path consistent CSP over PA with no :f:-diamond is mini­ mal [Gerevini and Schubert, I995]. Complexity follows from Theorem I and the fact that the total number of pairs that can enter into Lis O(n 2 ). o

3.4 An Algorithm for 1-ISOL over ORD-Horn

Gerevini and Cristani [I997] showed that ISOL for a path consistent CSP n over ORD-Hom can be solved in O(n 2 ) time by using a solution for the 1r1 -translation of r!. Figure 7 gives an algorithm solving I-ISOL for r! which exploits this property and uses INCREMENTAL-PA-SOL. Our algorithm requires O(n 3 ) total time, while the application from sketch of a known static algorithm each time a new constraint is as­ serted requires O(n 5 ) total time. This cost can be reduced to O(n 4 ) total time by using IPC combined with Gerevini & Cristani's algorithm, which is still one order worse than the complexity of the algorithm presented here.

Our algorithm uses a modification of IPC, called IPC-3, which again is a revision of IPC to keep track of certain con­ straints generated by the propagation of the new input con­ straint xRy. Given the path consistent CSP D of f!i_1 , the

Algorithm: INCREMENTAL-0RDHORN-SOL Input: the matrices M and M' representing the path consistent CSP D. of ni-t, and the path consistent CSP of 1r1 (D.), respectively; a topological order T for the precedence graph of 1r1 (D.); a new interval constraint xRy. Output: A solution forD;, if D; is satisfiable, fail otherwise. I. if (R n M[x, y]) c M[x, y] then 2. P := list formed by the constraints in 1r1 ( { xRy}) else P := (); 3. M :=IPC-3(M,xRy); 4. if M = fail then return fail ; 5. for each pSq E P do 6. if (S n M'[p, q]) c M'[p, q] then initialize the EQ-tlags and 7. run steps 1-15 of INCREMENTAL-PA-SOL(M', T ,pSq); 8. return an assignment to the interval endpoints in D; consistent withT.

path consistent CSP of 1r1 (f!), a topological order T for the precedence graph of 1r1 (!1), and a new interval constraint xRy, IPC-3 accomplishes the following tasks: (a) it decides ISAT for D;; (b) it updates f! to derive the path consistent CSP f!; of D; = f2;_ 1 U {xRy} ; (c) it derives a list P con­ taining the PA-constraints in 1r1 (f!;) that are not in 1rt(f!). P is a global variable that is initialized to the list formed by 1r1 ( { xRy}), if xRy refines the current relation between x and y in !1, and to the empty list otherwise (step 1). P is updated by the subroutine REVISE-3 of IPC-3, which is the same as REVISE in IPC, but with the important addition that, if M[i, j] is revised, then the PA-constraints in 1r1 ( { M[i , j]}) are added toP. Steps 5-7 incrementally update the path con­ sistent CSP of 1r1 (n) (M 1 ) with the constraints in P, as well as the topological sort T of its precedence graph.

Theorem 4 INCREMENTAL-0RDHORN-SOL solves I-ISOL for ORD-Horn in O(n 3 ) total time, where n is the number of temporal variables.

Proof (sketch). Correctness follows from Theorem 1, Theo­ rem 2 and the results on ORD-Horn given in [Gerevini and Cristani, 1997]. Complexity follows from Theorems 1, 2 and the fact that for any sequence of O(n 2 ) input constraints the total number of items entering into Pis O(n 2 ). D

4 Conclusions and Future Work

We have presented some algorithms for incremental tempo­ ral reasoning in the context of PA, SIA and ORD-Horn, im­ proving the complexity of existing techniques by a factor of O(n) or O(n 2 ). An interesting question is whether our tech­ niques can be used for the decremental and fully-dynamic versions of the reasoning problems considered. Clearly, when constraints can only be removed from a CSP, satisfiability is preserved and no processing is needed. Similarly, for main­ taining a solution. The decremental version of I-PM IN can be solved in O(n 5 ) total time by an algorithm similar to INCREMENTAL-PA-MIN (here omitted for lack of space).

Performing an interleaved sequence of constraint asser­ tions (refinements) and retractions appears to be intrinsi­ cally harder, and we conjecture that it requires algorithms with complexity higher than those presented here. For fully­ dynamic problems our techniques can be used to amortize complexity only for any subsequence of constraint assertions. E.g., consider an instance of the fully-dynamic version of PMIN in which we have k retractions during an input se­ quence of O(n 2 ) assertions. When we process a retraction, we can recompute from scratch the minimal labels, while as­ sertions are processed using our algorithm. The total time complexity is then O(kn 4 ), which is still more efficient than applying van Beek's static O(n 4 ) algorithm O(kn 2 ) times.

While in this paper we have not addressed I-IMIN for ORD-Horn, very recently we have proved that this problem can be solved in O(n 6 ) total time. Future work includes in­ cremental algorithms for other tractable classes [Krokhin et al., to appear] and a deeper study of fully-dynamic problems.