Constraint-based temporal reasoning, or CTR, came as a generalisation of discrete constraint satisfaction problems, or discrete CSPs [Montanari, 1974; Mackworth, 1977; Freuder, 1982], to continuous variables. Qualitative approaches to CTR include Allen’s [1983] highly influential Interval Algebra, and quantitative approaches to it include the equally influential framework of Temporal Constraint Satisfaction Problems, or TCSPs [Dechter et al., 1991]. Main research issues dealt with in CTR include:

1. the extraction of tractable subclasses, for which polynomial algorithms, incomplete for the general, subsuming language, become complete [Bessi`ere, 1996; Bessi`ere et al., 1996; Broxvall et al., 2002; Isli, 2001; Ligozat, 1996; Nebel and B¨urckert, 1995; van Beek, 1992]; and

2. the design of general algorithms, with an exponential worst-case computational complexity, but with a nice computational behaviour on known classes of real-life problems [Ladkin and Maddux, 1994; Ladkin and Reinefeld, 1992;

Nebel, 1997; Schwalb and Dechter, 1997; Stergiou and Koubarakis, 2000; van Beek, 1992; van Beek and Manchak, 1996].

The constraints of a Temporal Constraint Satisfaction Problem (TCSP) [Dechter et al., 1991] were first defined as being either unary or binary. Then, in the same article, the definition has been modified through the addition of a new variable referred to as the ”origin of the world” variable, which is used to binarize the unary constraints. This addition of an ”origin of the world” variable makes the constraints of a TCSP exclusively binary, with the consequence that a TCSP verifies then the properties of node- and arc-consistencies.

While the adding of an ”origin of the world” variable has the advantage of transforming the solving of an STP, i.e., a TCSP whose constraints are convex, into a shortest paths problem, it remains that, because a TCSP becomes then nodeand arc-consistent, it gets easy for one’s attention to immediately skip to the next higher local consistency, path-consistency, which is exactly what seems to have happened in [Dechter et al., 1991].

In this work, while we will keep the idea of having an ”origin of the world” variable, and of binarizing the unary constraints, making the constraints of a TCSP exclusively binary, we will look at the constraints between the ”origin of the world” variable and the other variables, as the (binarized) domains of these other variables. With this in mind, we de-fine a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains Arc-Consistency, or bdArcConsistency for short. We provide an algorithm achieving bdArc-Consistency for a TCSP, which we will refer to as bdAC-3, for it is an adaptation of Mackworth’s [1977] well-known arc-consistency algorithm AC-3. We show that if an STP is bdArc-Consistent, and its ”origin of the world” variable disconnected from none of the other variables, its binarized domains are minimal. We provide two polynomial backtrack-free procedures:

1. one for the task of getting, from a bdArc-Consistent STP, either that it is inconsistent or, in case of consistency, a bdArc-Consistent STP refinement whose ”origin of the world” variable is disconnected from none of the other variables;

2. the other for the task of getting a solution from a bdArcConsistent STP whose ”origin of the world” variable is disconnected from none of the other variables.

We then show how to use our results both in a general TCSP solver and in a TCSP-based job shop scheduler. From our work can be extracted a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Finally, we show that an existing adaptation to TCSPs of Mackworth’s [1977] path-consistency algorithm PC-2 is not guaranteed to always terminate, and correct it.

The rest of the paper is organized as follows. Section 2 is devoted to needed background. Section 3 defines our notion of binarized-domains Arc-Consistency (bdArc-Consistency) for TCSPs; provides, and studies the termination and the computational complexity of, our algorithm bdAC-3 achieving bdArc-Consistency for a general TCSP; shows the minimality result alluded to above; and ends with an important corollary providing a one-to-all all-to-one shortest paths algorithm of an IR-labelled directed graph. Sections 4 and 5 provide the two backtrack-free procedures referred to above. Section 6 provides a general TCSP solver using a weak version of bdArc-Consistency (wbdArc-Consistency) as the fil-tering procedure during the search, whose correctness is a direct consequence of our minimality result of Section 3. A TCSP-based job shop scheduler, which is an adaptation of the general TCSP solver but uses nevertheless bdAC-3 as the filtering procedure instead of a weak version of it, is described in Section 7. Section 8 is devoted to a discussion of the most related literature, and, in particular, provides an adaptation to TCSPs of the other three local consistency algorithms in [Mackworth, 1977]: the arc-consistency algorithm AC-1, and the path-consistency algorithms PC-1 and PC-2; it also corrects an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997]. Section 9 summarizes the work and provides some of its possible future directions.

Temporal Constraint Satisfaction Problems, or TCSPs for short, have been proposed in [Dechter et al., 1991] as an extension of (discrete) CSPs [Mackworth, 1977; Montanari, 1974] to continuous variables.

Definition 1 (TCSP [Dechter et al., 1991]). A TCSP is a pair P = (X, C) consisting of (1) a finite set X of n variables, , ranging over the universe of time points; and (2) a finite set C of Dechter, Meiri and Pearl’s constraints (henceforth DMP constraints) on the variables.

A DMP constraint is either unary or binary. A unary constraint has the form , and a binary constraint the form , where and are subsets of the set IR of real numbers, and and are variables ranging over the set IR seen as the universe of time points. A unary constraint may be seen as a special binary constraint if we consider an origin of the World (time 0), represented by a variable is then equivalent to ,with . Unless explicitly stated otherwise, we assume, in the rest of the paper, that the constraints of a TCSP are all binary. Furthermore, without loss of generality, we make the assumption that all constraints of a TCSP are such that i < j: if this is not the case for a constraint , we replace it with the equivalent constraint , where is the converse of (see the definition of converse below).

Definition 2 (STP [Dechter et al., 1991]). An STP (Simple Temporal Problem) is a TCSP of which all the constraints are convex, i.e., of the form being a convex subset of IR.

A universal constraint for TCSPs in general, and for STPs in particular, is of the form , and is equivalent to “no knowledge” on the difference . An equality constraint is of the form : it “forces” variables and to be equal.

We now consider an n + 1-variable TCSP P = (X, C), with , the variable representing the origin of the World. Without loss of generality, we assume that P has at most one constraint per pair of variables.

Definition 3 (network representation). The network representathon of P is the labelled directed graph of which the vertices are the variables of P, and the edges are the pairs of variables on which a constraint is specified. The label of edge is the set such that is the constraint of P on the pair of variables.

Definition 4 (matrix representation). The matrix representation of P is the -matrix, denoted by P for simplicity, defined as follows: ; and s.t. , for all such

that a constraint is spectfied on and ; , for all other pairs (i, j). Definition 5 ((consistent) instantiation). An instantiation of P is any n+1-tuple , representing an assignment of a value to each variable. A consistent instantiation, or solution, is an instantiation satisfying all the constraints: for all satisfies the constraint, if any, specified on the pair . Definition 6 (subnetwork). A k-variable subnetwork, n + 1, is any restriction of the network P to k of its variables and the constraints on pairs of those k variables. Definition 7 ((strong) k-consistency). For all k = 1 . . . (n + 1), P is k-consistent if any solution to any -variable subnetwork extends to any k-th variable; it is strongly k-consistent if it is j-consistent, for all .

Strong 1-, 2- and 3-consistencies correspond to node-, arc- and path-consistencies, respectively [Montanari, 1974; Mackworth, 1977]. Strong (n + 1)-consistency of P corresponds to decomposability [Dechter, 1992]. It facilitates the exhibition of a solution by backtrack-free search [Freuder, 1982].

The consistency problem of a TCSP, i.e. the problem of verifying whether it has a consistent instantiation, is NP-hard. Davis [1989] (cited in [Dechter et al., 1991]) showed that even the subclass of TCSPs in which the constraints are of length lower than or equal to 2 (i.e. they are of the form , with being a convex set or a union of two disjoint convex sets) is NP-hard (see also [Dechter et al., 1991], Theorem 4.1, Page 73). However, when the constraints of a TCSP are all convex, i.e. when we restrict ourselves to STPs, the consistency problem is polynomial [Dechter et al., 1991]. Moreover, in the case of STPs the classical path-consistency method [Montanari, 1974; Mackworth, 1977] leads to strong (n + 1)-consisteny [Dechter et al., 1991]. Definition 8 (converse). The converse of a DMP constraint is the DMP constraint such that such that . Definition 9 (intersection). The intersection of two DMP constraints and , on the same pair of variables, is the DMP constraint , with . Definition 10 (composition). The composition of two DMP constraints and , written , is the constraint , on the extreme variables and , such that s.t. c = a + b}. We will also say that the composition of the sets and is the set . Definition 11 (Minimal partition into convex subsets). Let S be a subet of . The minimal partition of S into convex subsets, or mPcs(S) for short, is the set mPcs(S) = such that is a partition of S into maximal convex subsets: for all : (1) is convex, and (2) for all convex set , if then is not a subset of S.

Applying PC even to a TCSP whose constraints are initially of length lower than or equal to 2, may lead to the so-called “fragmentation problem” [Schwalb and Dechter, 1997]: the constraints may be “fragmented”. Schwalb and Dechter [1997] gave a number of weak versions of PC, which are less effective but have the advantage of getting rid of the fragmentation problem. One of these versions is ULT (UpperLower Tightening), which we will also refer to as weak Path-Consistency, or wPC for short. It consists of PathConsistency (PC) in which the usual composition operation is replaced by weak composision. Definition 12 (Convex closure). The convex closure of a set , is the smallest convex set verifying . The convex closure of a TCSP constraint is the TCSP constraint . The convex closure of a TCSP P, cc(P), is the STP cc(P) = , with constraint of P}. Definition 13 (weak composition [Schwalb and Dechter, 1997]). The weak composition of two DMP constraints and , written , is the composition of their convex closures; i.e., is equal to .

tively, ) as the path-consistency operation (respectively, the weak path-consistency operation) on triangle . Applying path consistency (respectively, weak path-consistency) to a TCSP consists of repeating, until stability is reached or inconsistency is detected, the process of applying the path-consistency operation (respectively, the weak path-consistency operation) to each triangle of variables. We will also refer to the (weak) path-consistency operation as a relaxation step. Example 1 illustrates some of the introduced notions, including the fragmentation problem. Example 1. Let P = (X, C) be a TCSP, with X =

[10, 15]}, and the network representation given by Figure 1:

Figure 1: The network representation of the TCSP of Example 1.

4. If, instead of the path-consistency operation, we used the weak path-consistency operation, we would get , which does not fragment the label on edge .

Remark 1. Let be a triangle subnetwork of a TCSP P, with |mPcsmPcsand |mPcs: 1. the worst-case computational complexity of the path-consistency operation, , on triangle is ; 2. the worst-case computational complexity of the weak path-consistency operation, , on triangle is ; and 3. if and are convex, the worst-case computational complexity of both operations is O(1). See Appendix A for details.

A distance graph is a complete labelled (weighted) directed graph G = (V, E, w), where V is the set of vertices (nodes), is the set of edges, and w is a labelling (weight) function from E to the set verifying , for all vertices . A rooted distance graph is a pair (G, S), where G is a distance graph and S is a vertex of G. A path of length p, or p-path, of a distance graph is a sequence of vertices. The length of a path gives the number of its edges. Let be a p-path of a distance graph is elementary if, for all j, k such that , if then ; it is a circuit if . The weight function w of G can be extended to paths as follows. The weight of is the sum . A (strictly) negative circuit is a circuit whose weight is strictly negative. We now define the distance graph and the rooted distance graph of an STP. Definition 14 ((rooted) distance graph of an STP). If the TCSP P = (X, C) is an STP, its distance graph is the distance graph constructed as follows: 1. the set of vertices of G is the set X of variables of P 2. The labelling function w is built as follows: (a) for all variables and , with i < j, if P has a constraint , with of the form or (a, b], then the label of edge is (b) for all variables and , with i < j, if P has a constraint , with of the

form or (a, b), then the label of edge is

(c) for all variables and , with i < j, if P has a constraint , with of the form or [a, b), then the label of edge is

(d) for all variables and , with i < j, if P has a constraint , with of the form or (a, b), then the label of edge is

We refer to the rooted distance graph as the rooted distance graph of the STP P.

Theorem 1 ([Pratt, 1977; Shostak, 1981]). Let P be an STP. P is consistent if and only if its distance graph has no negative circuit.

The use of labelled directed graphs to represent a conjunction of linear inequalities, as used in [Dechter et al., 1991], is restricted to large inequalities of the form , where . An idea similar to the one used in this work, which combines large and strict inequalities, can be found in [Kautz and Ladkin, 1991]. Definition 15 (d-graph of an STP). The d-graph of an STP P = (X, C) is the distance graph verifying: is the weight of the shortest path from to in the distance graph of P.

The d-graph of an STP can be built from its distance gragh using Floyd-Warshall’s all-to-all shortest paths algo- rithm [Aho et al., 1976; Papadimitriou and Steiglitz, 1982].

Figure 2: The table M for the transformation of a rooted distance graph to an STP, with

Definition 16 (STP of a rooted distance graph). Let be a rooted distance graph, with and . The STP of is the STP P = (X, C), with , constructed as follows:

1. Initialise C to the empty set: ;

2. for all vertices and of G, with i < j, such that at least one of the two edges and is not labelled with :

(b) add to C the constraint , where is as given by the table M of Figure 2 (of the form or , with ; and of the form or , with ).

For instance, if the edges and are labelled, respectively, with 6 and , the constraint (2, 6] is added to C.

In [Dechter et al., 1991], it has been shown that applying path-consistency to an STP P is equivalent to applying Floyd-Warshall’s all-to-all shortest paths algorithm [Aho et al., 1976; Papadimitriou and Steiglitz, 1982] to the distance graph of P. In other words, if is the STP resulting from applying path consistency to ), then is exactly the STP of the d-graph of P. Furthermore, is minimal and strongly n + 1-consistent, n + 1 being the number of variables.

Theorem 2 ([Dechter et al., 1991]). Let P be an n + 1-variable STP. If path-consistency applied to P does not detect an inconsistency, then the resulting STP is minimal and strongly n + 1-consistent. Furthermore, is the STP of the d-graph of P.

For the detection of an STP’s inconsistency, which is equivalent to the detection of a negative circuit in its distance graph [Pratt, 1977; Shostak, 1981], we will need a lower bound of the weight of a finite-weight elementary path. Furthermore, for the purpose of evaluating the computational behaviour of the binarized-domains Arc-Consistency algorithm to be de-fined, we will additionaly need a upper bound of the same weight. These are defined as follows.

Definition 17 (path-lb, path-ub of an STP). Let P = (X, C) be an n+1-variable STP, its rooted distance graph, and and the following subsets of :

• Edges, Xj and w, X< 0 and w, X< w, X, Xi < j and w, Xand w, X, X,

Definition 18 (path-lb, path-ub of a TCSP). Let P = (X, C) be an n + 1-variable TCSP: path-lb(P) = path-lb(cc(P)) and path-ub(P) = path-ub(cc(P)). Theorem 3. Let P = (X, C) be an n+1-variable STP, G = its distance graph, and an elementary path of G that is not a circuit. If the weight w(u) of u is finite then path-lbpath-ub(P). Proof : Let u be an elementary path of G, of finite weight: 1. The lowest weight possible for u, when n, correponds to the case when the edges of u are exactly those in ; and when , it corresponds to the case when the edges of u are the first n in . In both cases, the weight is equal to path-lb(P). 2. The uppest weight possible for u, when n, correponds to the case when the edges of u are exactly those in ; and when , it corresponds to the case when the edges of u are the first n in . In both cases, the weight is equal to path-ub(P).

The transformation of the unary constraints of a TCSP into binary constraints, after the addition of an ”origin of the world” variable , makes the constraints of the TCSP become exclusively binary. In this work, we look at the constraints between the ”origin of the world” variable and the other variables as representing the (binarized) domains of these other variables. With this in mind, we define a notion of arc-consistency for TCSPs, which we will refer to as binarized-domains arc-consistency, or bdAC for short.

Definition 19 (binarized-domains arc-consistency). Let P be a TCSP. P is said to verify the binarized-domains arc-consistency, or to be bdArc-Consistent for short, if for all all , the following holds: . Said differently, P is bdArc-Consistent if, for all , the following holds: for all such that , there exists such that and the instantiation satisfies the constraints, if any, on variables and . Definition 20. Let P be a TCSP, and and two variables of is reachable from if and only if there exists a finite-weight elementary path from to in the distance graph of cc(P), the convex closure of is disconnected from if none of and is reachable from the other; is connected to otherwise. P is connectd if is connected to each of the other variables. The algorithm of Figure 4 takes as input a TCSP P, and does the following: 1. it makes P bd-ArcConsistent, if at all possible, 2. if P cannot be made bd-ArcConsistent then it is inconsistent, and the algorithm detects the inconsistency. We refer to the algorithm as bdAC-3, for it is mainly an adaptation of Mackworth’s [1977] well-known arc-consistency algorithm AC-3. bdAC-3 initialises a queue Q to all pairs (i, j) such that and P contains a (binary) constraint on and . Then it proceeds by taking in turn the pairs in Q for propagation. When a pair (k, m) is taken (and removed) from Q, bdAC-3 calls the procedure REVISE (Figure 3) which eventually updates , which represents the binarized domain of , if it is not a subset of the composition . The main difference of bdAC-3 with Mackworth’s [1977] AC-3 lies in line 4 of procedure REVISE, which guarantees termination of bdAC-3, and can be explained as follows, where the notations lowerB(A) and upperB(A), for a set , refer, respectively, to the lower bound and upper bound of A: • If P is an STP, and stand for the current values of the weights of the shortest paths from to and from to , respectively, in the rooted distance graph of P. Those of the two that are finite should satisfy the conditions of Theorem 3. In other words, the algorithm should make sure that the evolution of the two weights makes none of them get below the lower bound path-lb(P). Should the condition get violated, this would correspond to the detection of a negative circuit in the rooted distance graph of P, and bdAC-3 would terminate with a negative answer to the consistency problem of P. • If P is a general TCSP, given that path-lb(P) = path-lb(cc(P)) and that P is a refinement of its convex closure cc(P), line 4 of procedure REVISE still applies. If the REVISE procedure successfully updates , without making it become empty, the pairs (i, k) such that {0, k, m} and P has a constraint on and , reenter the queue Q if they are no longer there. The algorithm terminates

2. temp ; 3. if(temp

4. if[temp and (lowerB(temppath-lb(P)

or upperB(temp) < path-lb(P))]temp ; 5. Ptemp;Ptemp;

6. DELETE=true 7. }

8. return DELETE 9. }

Figure 3: The boolean procedure REVISE.

1. Q = {(i, j) : P has a constraint on Xand X, i , i ;

2. Emptydomain = false; 3. while and (not Empty

4. select and delete an arc (k, m) from Q; 5. if REVISE(k, m)

6. if Emptydomain = true 7. else Q i, k) : P has a constraint

10. }%end bdAC3

Figure 4: The binarized-domains Arc-Consistency algorithm bdAC-3.

when a binarized domain becomes empty, or when the queue Q becomes empty. This leads us to the following Theorem.

Theorem 4. Le P be a TCSP. The bdAC-3 algorithm applied to P terminates and, either detects inconsistency of P or computes a bd-Arc Consistent TCSP equivalent to P.

The range of a TCSP will be needed for the determinination of the computational complexity of bdAC-3:

Definition 21 (range of a TCSP). Let P = (X, C) be an n+1-variable TCSP. The range of P, rg(P), is defined as rg(P) = path-ubpath-lb(P).

Theorem 5. Let P = (X, C) be a TCSP, with |X| = n + 1 and |C| = m. bdAC-3 applied to P can be achieved in relaxation steps (calls of the procedure REVISE of Figure 3) and arithmetic operations, where R = rg(P) is the range of P expressed in the coarsest possible time units.

Proof: The worst case scenario of bdAC-3 occurs when, whenever the procedure REVISE updates , the length of the set decreases by one time unit. Furthermore, if has a finite bound, it will be in the set [path-lb(P), path-ub(P)] (Theorem 3). Therefore, can be updated at most path-ubpath-lb(P) = R = O(R) times. The pairs (i, j) that enter initially the queue Q of bdAC-3 are such that there is a constraint of P on and . A pair (k, i) can reenter the queue O(R) times, whenever has been updated. Because there are constraints, the number of relaxation steps is . A relaxation step consists of a call REVISE(i, j) consisting mainly of the computation of a path consistency operation of the form , which needs arithmetic operations since each of the three sets and is a union of at most R convex subsets. The whole algorithm therefore terminates in time.

For an STP, a relaxation step is in O(1) (see Remark 1). This justifies the following corollary to Theorem 5.

Corollary 1. Let P = (X, C) be an STP, with |X| = n + 1 and |C| = m. bdAC-3 applied to P can be achieved in relaxation steps (calls of the procedure REVISE of Figure 3) and arithmetic operations, where R = rg(P) is the range of P expressed in the coarsest possible time units.

Theorem 6. Let P be a connected STP (no variable 0, is disconnected from ). If P is bdArc-Consistent, its (binarized) domains are minimal: for all , for all , there exists a solution such that .

be the rooted distance graph of P, with G = . According to Theorem 2, showing that the binarized domains , with , are minimal, is equivalent to showing that the labels (weights) and are the weights of the shortest paths from to and from to , respectively. Suppose that this is not the case; in other words, that for some , either is not the weight of the shortest path from to , or is not the weight of the shortest path from to :

Summing the left-hand sides and the right-hand sides of the linear inequalities, we get:

. This, in turn, gives , which clearly contredicts our supposition.

2. Case 2: is not the weight of the shortest path from to . This would mean the existence of j in , and of a path < from to through , whose weight is strictly smaller than . But, because the STP is bdArc-Consistent, we have the following:

Summing the left-hand sides and the right-hand sides of the linear inequalities, we get: . This, in turn, gives , which clearly contredicts our supposition.

As an immediate consequence of Theorem 6:

Corollary 2. Let (G, V ) be a rooted distance graph. The bdArc-Consistency algorithm bdAC-3 can be used to compute the weights of the shortest paths from V to all vertices of G, and the weights of the shortest paths from all vertices of G to V .

Proof. Proceed as follows:

1. Linearly transform the input rooted distance graph (G, V ) into its STP P;

2. apply the bdArc-Consistency algorithm bdAC-3 to P;

3. linearly transform the STP resulting from bdAC-3 into its rooted distance graph.

Appendices B and C present two detailled examples. The example of Appendix B applies the bdAC-3 algorithm to an STP, transforming the latter into a bdArc-Consistent STP with no variable disconnected from the ”origin of the world” variable, without making a binarized domain become empty. The example of Appendix C applies bdAC-3 to an STP whose rooted distance graph presents a negative circuit not reachable from , the ”origin of the world” variable, but from which is reachable: bdAC-3 detects the negative circuit, and the inconsistency of the STP. In particular, the example of Appendix C shows that bdAC-3 without line 4 of procedure REVISE, which could be seen as a ”literal” adaptation to TCSPs of Mackworth’s [1977] algorithm AC-3, has no guarantee to always terminate (see Remark 3).

Remark 3. We refer to the procedure REVISE of Figure 3 without its line 4 as REVISE, and to the algorithm bdAC-3 (Figure 4) in which procedure REVISE is replaced with REVISEas bdAC-3. bdAC-3is, somehow, a ”literal”

Input: The matrix representation of a bdArc-Consistent STP P having variables disconnected from .

Output: Extracts a connected bdArc-Consistent STP re-finement of P, and returns true, if P consistent; returns false otherwise.

1. select a variable disconnected from , and a real number a;

2. ; 3. if(bdAC-3(P))

4. if (P has no variable disconnected from )

Figure 5: The polynomial backtrack-free procedure

adaptation of Mackworth’s [1977] AC-3 algorithm to TCSPs. In the light of the example of Appendix C, bdAC-3is not guaranteed to always terminate.

Given a bdArc-Consistent STP P, the backtrack-free procedure connectX0inbdACstp(P) of Figure 5 checks consistency of P: it extracts a connected bdArc-Consistent STP refinement of P, and returns true, if P consistent; it returns false otherwise. Correctness of procedure

Theorem 7. Let P = (X, C) be a bdArc-Consistent STP with a variable , disconnected from , and the STP obtained from P by adding the constraint , with . P is consistent if and only if is consistent.

Proof: Immediate consequence of Theorem 1 and the fact that the rooted distance graphs of P and are such that one has a negative circuit if and only if the other has.

Correctness of the backtrack-free procedure of Figure 6 is a direct consequence of Theorem 6. If the input bdArcConsistent STP P is not a singleton STP (line 1), we select a non-singleton edge and instantiate it with an element of (lines 2 and 3): because P is connected and bdArc-Consistent, the binarized domain is minimal (Theorem 6), which guarantees that the element chosen to instantiate edge participates in a global solution.

Input: The matrix representation of a bdArc-Consistent STP P with no variable disconnected from .

Output: A bdArc-Consistent singleton-domains STP refinement of P.

2. select a non-singleton edge ;

3. Instantiate with an element of : ;

4. P = bdAC-3(P); 5. backtrackfree(P)}%endif

6. else return P 7. }

Figure 6: A polynomial backtrack-free procedure computing a consistent singleton refinement of a connected bdArc-Consistent STP.

bdArc-Consistency is then applied to the refinement resulting from the instantiation (line 4). The process needs to be reiterated at most n times before the binarized domains , , become singleton (line 6).

We define a refinement of a TCSP P to be any TCSP on the same set of variables such that for all constraint of , the corresponding constraint of P verifies . A constraint such that is called sublabel of . A refinement is convex if it is an STP [Dechter et al., 1991]. The solver can now be described as follows (see Figure 7). As the filtering procedure during the search, it uses a weak version of the bdArc-Consistency algorithm bdAC-3, which we refer to as wbdAC-3, and consists of replacing composition by weak composition in the REVISE procedure of Figure 3, the aim being to avoid the “fragmentation problem” [Schwalb and Dechter, 1997]. If P is the input TCSP, the recursive procedure consistent(P) is called, which works as follows. The filtering procedure wbdAC-3 is applied (the very first application of the filtering, at the root of the search space, consists of the preprocessing step). If the wbdAC-3 fil-tering detects an inconsisteny (line 1), by reducing a binarized domain to the empty set, a failure (dead end) is reached and the procedure returns false. Otherwise, if P has no disjunctive edge (line 10) then the result of the wbdAC-3 filtering is a bdArc-Consistent STP, which is not necessarily consistent since it might contain a negative circuit disconnected from ; and, in this case, the procedure does the following:

1. if P has no variable disconnected from then P is consistent (Theorem 6), and the procedure returns true (line 11);

2. if P has variables that are disconnected from (line

2. else 3. if(P has disjunctive edges){%beginif2

4. select a disjunctive edge ;

5. let mPcs, . . . , P;

6. for(k = 1 to 7. ;

8. if()return true}%endfor 9. return false}%endif2

10. else 11. if (P has no variable disconnected from )

12. else return connectX0

inbdACstp(P) 13. }

Figure 7: The recursive procedure consistent(P).

12), these might hide a negative circuit, of which cannot be a vertex. The backtrack-free search procedure connectX0inbdACstp(P) is called, which checks consistency of P: consistent(P) returns the result returned by connectX0inbdACstp(P). If the result of the wbdAC-3 filtering is not an STP then there remain disjunctive edges (line 3). A disjunctive edge is selected (lines 4 and 5) and instantiated with one of its maximal convex sublabels (line 7): is the refinement of P resulting from the instantiation. The recursive call is then made (line 8). If returns true, consistent(P) returns true. If now returns false, the next maximal convex sublabel, if any, of the edge being instantiated is chosen, and the recursive call is made again. If all sublabels have been already chosen (line 9) then consistent(P) returns false. Completeness of the solver is guaranteed by completeness of bdArc-Consistency for connected STPs (Theorem 6). Given an input TCSP P, the solver of Figure 7 can be adapted so that, when P is consistent, it returns a connected bdArc-Consistent STP refinement of P. From , one can then get a solution to P with the use of the polynomial backtrack-free procedure of Figure 6. The next section describes how, from the general TCSP solver, one can extract a TCSP-based job shop scheduler with bdAC-3 as the filtering procedure during the search.

Many approaches to scheduling are known in the literature, among which mathematical programming, timed Petri nets [Carlier et al., 1985] and discrete CSPs [Dincbas et al., 1990; Sadeh et al., 1995]. We focus on job shop scheduling problems.

Input: The matrix representation of a scheduling TCSP P. Output: The optimum z of P.

Method: Initialise the optimum: ; then call the recursive procedure optimum(P) procedure optimum(P){

1. if (not bdAC-3(P) or return

2. else 3. if(P has disjunctive edges){%beginif2

4. select a disjunctive edge ; 5. let ;

6. for(k = 1 to 2){ 7. ;

8. %endfor 9. }%endif2

Figure 8: The TCSP-based job-shop scheduler.

A scheduling TCSP is a TCSP P = (X, C), with X = being the ”origin of the world” variable standing for a global release date, n being the number of (non-preemptive) tasks:

(b) the duration of task i is , with (the tasks are durative, in the sense that their durations are not null; furthermore, they have fixed durations, known in advance); and

(c) the release and due dates of task i, if any, are and .

2. A conjunctive (or precedence) constraint between tasks i and j has the form .

3. A disjunctive constraint between tasks i and j has the form .

4. A release (respectively, due) date constraint has the form (respectively, ).

5. Finally, standing for a global release date, we add the n constraints .

We define the duration dur(s) of a solution of P as ; the latency lat(s) of s as the amount of time separating stimulus and response, the stimulus being given at time , and the response obtained at the effective beginning of the very first task: . The optimum of P, , is defined as , with sol(P) being the set of solutions of P. The scheduler we propose (Figure 8), with bdAC-3 as the filtering procedure during the search, minimises the makespan and initialises the optimum z to ; it is an adaptation of the TCSP solver of Figure 7. The lower bound of the optimum of P, OLB(P), is defined as , where is the lower bound of the binarized domain . Note that , which is used by the scheduler to backtrack whenever (line 1). Furthermore, whenever the bdAC-3 filtering leads to a (bdArc-Consistent) STP (line 10), the optimum is updated in a way one can justify as follows. Given the nature of a scheduling TCSP (is a global release date), is disconnected from none of the other variables. Because the binarized domains of a connected bdArc-Consistent STP P are minimal (Theorem 6), a direct consequence of results in [Dechter et al., 1991] (Corollaries 3.2 and 3.4, Pages 69 and 70) is that the solution realising the optimum of P is given by the lower bounds of these binarized domains, and the optimum itself is OLB(P). See Figure 8 for details.

The relaxation step of the bdAC-3 algorithm, consisting of a call of the REVISE(i, j) procedure of Figure 3, and reducing mainly to the path-consistency operation , may result in a fragmentation of the binarized domain , as illustrated by Example 1. To avoid such a fragmentation, we used in the general TCSP solver of Section 6, a weak version of the bdAC-3 algorithm, wbdAC-3, as the filtering procedure.

The restriction to scheduling TCSPs, however, makes it possible to use bdAC-3 as the filtering procedure, with no risk of fragmenting a binarized domain. Given such a TCSP P = (X, C), with , the binarized domains , with , are of either of the two forms [a, b] (form A1) or (form A2), with . Furthermore, the entries of the matrix representation of P, with and such that there is a constraint on tasks i and j, are of either of the three forms with a < 0 (form B1), with a > 0 (form B2), or with a < 0 < b (form B3). Therefore, the composition of the REVISE(i, j) procedure of Figure 3 results in a convex set with no open finite bound; this implies that, the relaxation operation of the same procedure, replacing the binarized domain with its intersection with the composition , results in a binarized domain of either of the two forms A1 or A2. This leads to the following theorem:

Theorem 8. The class of scheduling TCSPs is closed under bdArc-Consistency: applying a bdArc-Consistency algorithm, such as bdAC-3, to a schedulig TCSP P either detects inconsistency of P, or computes an (equivalent, bdArc-Consistent) scheduling TCSP.

Theorem 8 justifies our use of bdAC-3 as the filtering procedure of our TCSP-based scheduler, instead of its weak version wbdAC-3: bdAC-3 applied to a scheduling TCSP does not fragment the binarized domains. Furthermore, given that the instantiation of a disjunctive edge transforms a constraint of the form B3 into a constraint of either of the two forms B1 and B2, the resulting refinement is a scheduling TCSP. This brings us to this nice behavior of the class of scheduling TCSPs: at each node of the scheduler’s search tree, the bdAC-3 filtering either detects inconsistency of the corresponding refinement, indicating a failure (deadend), or computes an (equivalent, bdArc-Consistent) scheduling TCSP.

Related work on arc-consistency for TCSPs include [Cervoni et al., 1994; Cesta and Oddi, 1996; Kong et al., 2018; Planken et al., 2008], but the focus has always been restricted to STPs. The most related remains [Kong et al., 2018], which defines an arc-consistency algorithm for STPs, which can be seen as an adaptation of Bellman-Ford-Moore one-to-all shortest paths algorithm [Bellman, 1958; Ford and Fulkerson, 1962; Moore, 1959]; this can also be seen as an adaptation of Mackworth’s [1977] arc-consistency algorithm AC-1 restricted to one pass. Beyond the fact that the algorithm is defined only for STPs, the other criticism is that for applications needing incrementality such as planning, which seems to have been the authors’ targetted application, it is clear that the use of an adaptation of Mackworth’s [1977] AC-3 instead of AC-1, in case of arc-consistency, and an adaptation of Mackworth’s [1977] PC-2 instead of PC-1, in case of path-consistency, is much better, mainly because these use a queue allowing them, when new knowledge comes in, to continue on what had been done before, and not to redo it. Allen’s well-known Interval Algebra [Allen, 1983] in general, and its convex part in particular, whose most targetted application is planning, uses an adaptation of PC-2. The most related work, worth comparing, is Decther et al.’s [1991], where, in particular, the authors show the equivalence between, on one hand, applying path-consistency to an STP and, on the other, applying an all-to-all shortest paths algorithm, such as Floyd-Warshall’s [Aho et al., 1976; Papadimitriou and Steiglitz, 1982], to the corresponding distance graph. Dechter et al. [1991], as explained in the introduction, didn’t focus on node- and arc-consistencies, because the adding of an ”origin of the world” variable led them to the conclusion that a TCSP was already node- and arc-consistent. In the present work, we have looked at the constraints between the ”origin of the world” variable and the other variables, as the binarized domains of these other variables. This led us to the definition of the notion of binarized-domains Arc-Consistency, which is computationally one factor less expensive. We showed, in particular, that applying bdArcConsistency to an STP was equivalent to applying a one-to-all all-to-one shortest paths algorithm to the corresponding rooted distance graph. The bdArc-Consistency algorithm we have defined, bdAC-3, detects negative circuits reachable from , or from which is reachable. Another related work is Schwalb and Dechter’s [1997], where, in particular, the authors propose the use of weak versions of path-consistency as filtering procedures of general TCSP solvers. One of these weaker versions is ULT (Upper-Lower Tightning), in which composition is replaced with weak composition. We have discussed the use of a similar idea in a general TCSP solver with the filtering procedure consisting of a weak version of the binarized-domains ArcConsistency algorithm bdAC-3 proposed in this work. The rest of the section presents an adaptation to TCSPs of

the other local-consistency algorithms in [Mackworth, 1977], namely, the arc-consistency algorithm AC-1, and the path consistency algorithms PC-1 and PC-2; it also looks at the termination of these adaptations; and shows, in particular, that an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997] is not guaranteed to always terminate.

8.1 Adaptation to TCSPs of AC-1, PC-1 and PC-2

In addition to the bdAC-3 algorithm, we provide in Figures 9 and 10 adaptations to TCSPs of the other three local-consistency algorithms in [Mackworth, 1977]: the arc-consistency algorithm AC-1 and the two path-consistency algorithms PC-1 and PC-2. The adaptations are named, respectively, bdAC-1, PC-1 and PC-2. Like bdAC-3, when applied to an STP, bdAC-1 detects, if any, negative circuits reachable from , or from which is reachable, in the corresponding rooted distance graph; it makes the STP bdArc-Consistent otherwise. PC-1 and PC-2, when applied to an STP, both detect, if any, negative circuits in the corresponding distance graph; they make the STP path-consistent otherwise. Both of bdAC-1 and PC-2 use the condition on negative circuits one can extract from Theorem 3 (line 4 of the REVISE procedure of Figure 3, for bdAC-1; line 4 of the REVISEPC-2 procedure of Figure 10, for PC-2).

As already stated in Remark 3, we refer to the procedure REVISE of Figure 3 without its line 4 as REVISE, and to the algorithm bdAC-3 (Figure 4) in which procedure REVISE is replaced with REVISEas bdAC-3. In addition to that, we refer to the procedure REVISEPC-2 of Figure 10 without its line 4 as REVISEPC-2, to the algorithm bdAC-1 (Figure 9) in which procedure REVISE is replaced with REVISEas bdAC-1, and to the algorithm PC-2 (Figure 10) in which procedure REVISEPC-2 is replaced with REVISEPC-2as PC-2.

8.2 Termination of the adaptations

PC-1 proceeds by passes, and each pass considers all possible triples of variables. It is a ”literal” adaptation from [Mackworth, 1977], and is guaranteed to terminate and to detect, when applied to an STP, the presence of negative circuits in the corresponding distance graph. This is not the case for bdAC-1and PC-2, which, deprived of line 4 of Procedure REVISE for the former, and of line 4 of Procedure REVISEPC-2 for the latter, have no guarantee to terminate even when the input is an STP. Example 2 shows that bdAC-1and PC-2, which are ”literal” adaptations of Mackworth’s [1977] AC-1 and PC-2, respectively, are not guarateend to terminate.

Example 2 (non termination of bdAC-1and PC-2). We consider the STP P = (X, C) with:

1. X , X, X, Xand

2. : ([30: ([10]: (4]: ([40, 50]}.

The rooted distance graph of P (see Figure 11) does have a negative ciruit that is not reachable from , but from which

Input: The matrix representation of a TCSP P. Output: True, indicating that the TCSP has been made bdArc-consistent; or false, indicating that inconsistency of P has been detected. procedure bdAC-1(P){

3. CHANGE=false; 4. for each

5. if REVISE(i, j){%begin if1 6. if()return false;

7. CHANGE=true 8. }%end if1

9. until CHANGE 10. return true

11. }%end bdAC1

Input: The matrix representation of a TCSP P. Output: True, indicating that the TCSP has been made path-consistent; or false, indicating that inconsistency of P has been detected. procedure PC-1(P){

1. repeat 2. CHANGE=false;

3. for (k = 0 to n)

4. for (i, j = 0 to n){ 5. temp ;

6. if()return false; 7. if(;CHANGE=true}

8. } 9. until CHANGE

Figure 9: The binarized-domains Arc-Consistency algorithm bdAC-1 and the Path-Consistency algorithm PC-1.

1. DELETE=false; 2. ;

3. if(temp 4. if[temp and (lowerB(temppath-lb(P)

or upperB(temp) < path-lb(P))]temp ; 5. Ptemp;Ptemp;

6. DELETE=true 7. }

8. return DELETE 9. }

Output: True, indicating that the TCSP has been made path-consistent; or false, indicating that inconsistency of P has been detected.

and ; 2. Emptydomain = false;

3. while and (not Empty

4. select and delete a triple (i, k, j) from Q; 5. if REVISEPC-2(i, k, j)

6. if Emptydomain = true 7. else Q

{(i, j, m) : (i < m) and and P{(m, i, j) : (m < j) and and P

10. } %end PC2

Figure 10: The path-consistency algorithm PC-2 and the boolean procedure REVISEPC-2 it makes use of.

Figure 11: The distance graph of the STP of Example 2.

is reachable. bdAC-1 and bdAC-1proceed by passes, each of which is guaranteed to terminate since it considers at most once each ordered pair such that there is a constraint on and . Each of the two versions of bdArcConsistency terminates when, either a binarized domain becomes empty, or a whole pass makes no change in the binarized domains. But for the version bdAC-1, the order in which the pairs in its queue are propagated might make it impossible for the two terminating conditions to occur. Initially, the binarized domains are as follows: , and . For each of the two versions, we suppose that each of its passes propagates the pairs on which there is a constraint in the order , . For both versions, the evolution of the binarized domains for the first three passes are as follows:

1. after Pass 1: = [30), = [10) and = [50)

2. after Pass 2: = [46), = [26) and = [66)

3. after Pass 3: = [62), = [42) and = [82)

This means that each pass increases the (finite) lower bound of each binarized domain by 16, which corresponds to the absolute value of the weight of the negative circuit . Given that path-lb, bdAC-1 will detect the negative circuit after the third pass. However, bdAC-1will fail to do so, and will not terminate.

Let’s now look at how the two adaptations PC-2 and PC-2of Mackworth’s [1977] PC-2 will behave on the STP. Keep in mind that their unique difference lies in line 4 of Procedure REVISEPC-2, which is absent in PC-2. Both versions will initialise their queue as follows: Q = . We take the triple for propagation. The resulting modifi-cations are as follows:

1. = [10), = (10],

2. Q , X, X, X, X, X, X,

We then take the triple for propagation. The modifications are as follows:

1. = [50), = (50],

2. Q , X, X, X, X, X, X,

The situation of the binarized domains is now the same as that after Pass 1 of bdAC-1. We now repeat the following sequence: propagate triple , then triple , finally triple . Each pass of this repeat loop will increase by 16 the lower bound of each of the binarized domains. After the second pass, the binarized domain becomes , and PC-2 will then detect the presence of a negative circuit, and terminate. PC-2, however, will keep repeating the loop indefinitely, and will not terminate. The details of the first two passes of the repeat loop are as follows:

We now summarise the discussion: Theorem 9. bdAC-1, PC-1 and PC-2 (Figures 9 and 10) always terminate.

Theorem 10. bdAC-1, bdAC-3and PC-2are not guaranteed to terminate.

Finally, TCSP solution search algorithms using a binarized-domains arc consistency algorithm, such as bdAC-3, as the filtering procedure, are expected to drastically overcome general TCSP solvers [Dechter et al., 1991; Schwalb and Dechter, 1997] and TCSP-based schedulers [Belhadji and Isli, 1998] using path-consistency or a weak version of it as the filtering procedure. As a plausible explanation to this expected future for our newborn notion of binarized-domains arc-consistency, in the case of classical binary CSPs, arc-consistency algorithms and path-consistency algorithms, the first of which has a lower filtering power but is computationally cheaper, are both known since the seventies [Montanari, 1974; Mackworth, 1977], and the place of arc-consistency is known to be more advantageous than that of path-consistency as the filtering procedure of solution search algorithms.

We provided, and analysed the computational complexity of, an adaptation to TCSPs [Dechter et al., 1991] of Mackworth’s [1977] arc-consistency algorithm AC-3. A TCSP is closed under classical node- and arc-consistencies [Montanari, 1974; Mackworth, 1977], and we argued that this was certainly what made [Dechter et al., 1991] jump directly to the next local consistency algorithm, namely path- consistency. What made the adaptation possible was the look at the constraints of a TCSP between the ”origin of the world” variable and the other variables, as the binarized domains of these other variables.

For the convex part of TCSPs, namely STPs, we showed the equivalence between applying bdAC-3 to an STP, on one hand, and applying a one-to-all all-to-one shortest paths algorithm to its distance graph, on the other. We showed that the binarized domains of a connected bdArc-Consistent STP are minimal, and provided a polynomial backtrack-free procedure computing a solution to such an STP. Another polynomial backtrack-free procedure has been provided for the task of extracting, from a bdArc-Consistent STP, a connected bdArc-Consistent STP refinement, if the STP is consistent, or showing its inconsistency, otherwise.

We showed how to use bdAC-3 as the filtering procedure of a general TCSP solver, and of a TCSP-based job shop scheduler.

We also discussed how to adapt to TCSPs the other local-consistency algorithms in [Mackworth, 1977], namely, the arc-consistency algorithm AC-1, and the path consistency algorithms PC-1 and PC-2. In particular, this led us to the conclusion that an existing adaptation to TCSPs of PC-2 [Dechter et al., 1991; Schwalb and Dechter, 1997], contray to the adaptation we provided, is not guaranteed to always terminate.

To the best of our knowledge, the binarized-domains arc-consistency algorithm bdAC-3 we have investigated for general TCSPs is the very first of its kind, and we do hope and expect that it will have a positive impact on the near-future developments of the field. Points needing further investigation include improvement of the lower and upper bounds path-lb(P) and path-ub(P), as defined in this work for a TCSP P, as they are crucial for the bdAC-3 algorithm’s computational behaviour, and for that of search algorithms using bdAC-3 as the filtering procedure during the search.

An important future work that has always retained our attention, whose importance grows with the presented work, is to contribute to the addition of tools to Prolog libraries such as CLP(QI, IR); tools such as a TCSP solver and a TCSP-based job shop scheduler using bdArc-Consistency, or its weak version wbdArc-Consistency, as the filtering procedure during the search.

[Aho et al., 1976] A V Aho, J E Hopcroft, and J D Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley Publishing Co., 1976.

[Allen, 1983] James Allen. Maintaining knowledge about temporal intervals. Communications of the Association for Computing Machinery, 26(11):832–843, 1983.

[Belhadji and Isli, 1998] S Belhadji and A Isli. Temporal constraint satisfaction techniques in job shop scheduling problem solving. Constraints, 3(2-3):203–211, 1998.

[Bellman, 1958] R Bellman. On a routing problem. Quarterly of Applied Mathematics, 16(1):87–90, 1958.

[Bessi`ere et al., 1996] C Bessi`ere, A Isli, and G Ligozat. Global consistency in interval algebra networks: tractable subclasses. In W Wahlster, editor, Proceedings of the 12th European Conference on Artificial Intelligence (ECAI), pages 3–7, Budapest, 1996. John Wiley.

[Bessi`ere, 1996] C Bessi`ere. A simple way to improve path consistency processing in interval algebra networks. In William J. Clancey and Daniel S. Weld, editors, Proceedings of the 13th American Conference on Artificial Intelligence (AAAI), pages 375–380. AAAI Press / The MIT Press, 1996.

[Broxvall et al., 2002] Mathias Broxvall, Peter Jonsson, and Jochen Renz. Disjunctions, independence, refinements. Artif. Intell., 140(1/2):153–173, 2002.

[Carlier et al., 1985] J Carlier, P Chr´etienne, and C Girault. Modelling scheduling problems with timed petri nets. In G Rozenberg, H J Genrich, and G Roucairol, editors, Advances in Petri nets 1984, volume 188 of Lecture Notes in Computer Science, pages 62–84. Springer, 1985.

[Cervoni et al., 1994] R Cervoni, A Cesta, and A Oddi. Managing dynamic temporal constraint networks. In Proceedings of the Second International Conference on Arti-ficial Intelligence Planning Systems (AIPS), pages 13–18. AAAI Press, 1994.

[Cesta and Oddi, 1996] A Cesta and A Oddi. Gaining effi- ciency and flexibility in the simple temporal problem. In Proceedings of the Third International Workshop on Temporal Representation and Reasoning (TIME), pages 45– 50. IEEE Computer Society, 1996.

[Davis, 1989] E Davis. Private communication. 1989.

[Dechter et al., 1991] R Dechter, I Meiri, and J Pearl. Temporal constraint networks. Artificial Intelligence, 49:61– 95, 1991.

[Dechter, 1992] R Dechter. From local to global consistency. Artificial Intelligence, 55:87–107, 1992.

[Dincbas et al., 1990] M Dincbas, H Simonis, and P van Hentenryck. Solving large combinatorial problems in logic programming. Journal of Logic Programming, 8(1):75–93, 1990.

[Ford and Fulkerson, 1962] L R Ford and D R Fulkerson. Flows in Networks. Princeton University Press, New Jersey, 1962.

[Freuder, 1982] E C Freuder. A sufficient condition for backtrack-free search. Journal of the Association for Computing Machinery, 29:24–32, 1982.

[Isli, 2001] A Isli. On deciding Consistency for CSPs of Cyclic Time Intervals. In I Russel and J F Kolen, editors, Proceedings of the Fourteenth International Florida Arti-ficial Intelligence Research Society Conference (FLAIRS), pages 547–551, Key West, Florida, USA, May 21-23 2001. AAAI Press.

[Kautz and Ladkin, 1991] H Kautz and P Ladkin. Integrating metric and qualitative temporal reasoning. In Proceedings of the 9th American Conference on Artificial Intelligence

(AAAI), pages 241–246, Anaheim, CA, 1991. AAAI/MIT Press.

[Kong et al., 2018] S Kong, J H Lee, and S Li. Multiagent simple temporal problem: The arc-consistency approach. In Proceedings of the 32nd American Conference on Arti-ficial Intelligence (AAAI), pages 6219–6226. AAAI Press, 2018.

[Ladkin and Maddux, 1994] P Ladkin and R Maddux. On binary Constraint Problems. Journal of the Association for Computing Machinery, 41(3):435–469, 1994.

[Ladkin and Reinefeld, 1992] P Ladkin and A Reinefeld. Ef- fective solution for qualitative constraint problems. Artifi-cial Intelligence, 57:105–124, 1992.

[Ligozat, 1996] Gerard Ligozat. A new proof of tractability for ord-horn relations. In William J. Clancey and Daniel S. Weld, editors, Proceedings of the 13th American Conference on Artificial Intelligence (AAAI), pages 395–401. AAAI Press / The MIT Press, 1996.

[Mackworth, 1977] A K Mackworth. Consistency in networks of relations. Artificial Intelligence, 8:99–118, 1977.

[Montanari, 1974] U Montanari. Networks of constraints: fundamental properties and applications to picture processing. Information Sciences, 7:95–132, 1974.

[Moore, 1959] E F Moore. The shortest path through a maze. In Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957), page 285–292, Cambridge, 1959. Harvard University Press.

[Nebel and B¨urckert, 1995] Bernhard Nebel and HansJ¨urgen B¨urckert. Reasoning about temporal relations: A maximal tractable subclass of allen’s interval algebra. J. ACM, 42(1):43–66, 1995.

[Nebel, 1997] Bernhard Nebel. Solving hard qualitative tem- poral reasoning problems: Evaluating the efficiency of using the ord-horn class. Constraints An Int. J., 1(3):175– 190, 1997.

[Papadimitriou and Steiglitz, 1982] C H Papadimitriou and K Steiglitz. Combinatorial Optimisation: Algorithms and Complexity. 1982.

[Planken et al., 2008] L Planken, M de Weerdt, and R van der Krogt. P3C: A new algorithm for the simple temporal problem. In Proceedings of the 18th International Conference on Automated Planning and Scheduling ICAPS, pages 256–263. AAAI Press, 2008.

[Pratt, 1977] V R Pratt. Two easy theories whose combina- tion is hard. Technical report, Massachusetts Institute of Technology, 1977.

[Sadeh et al., 1995] N Sadeh, K Sycara, and Y Xiong. Backtracking techniques for the job shop scheduling constraint satisfaction problem. Artificial Intelligence, 76:455–480, 1995.

[Schwalb and Dechter, 1997] E Schwalb and R Dechter. Processing disjunctions in temporal constraint networks. Artificial Intelligence, 193:29–61, 1997.

[Shostak, 1981] R E Shostak. Deciding linear inequalities by computing loop residues. J. ACM, 28(4):769–779, 1981.

[Stergiou and Koubarakis, 2000] K Stergiou and M Koubarakis. Backtracking algorithms for disjunctions of temporal constraints. Artificial Intelligence, 120(1):81–117, 2000.

[van Beek and Manchak, 1996] Peter van Beek and Den- nis W. Manchak. The design and experimental analysis of algorithms for temporal reasoning. J. Artif. Intell. Res., 4:1–18, 1996.

[van Beek, 1992] Peter van Beek. Reasoning about qualitative temporal information. Artificial Intelligence, 58(1-3):297–326, 1992.

The worst-case computational complexity of the three operations of converse, intersection and composition are as follows:

1. If and are convex sets (intervals) then their composition is convex:

(a) the lower (respectively, upper) bound of is the sum of the lower (respectively, upper) bounds of and ;

(b) is left-closed (respectively, right-closed) if both and are left-closed (respectively, right-closed), it is left-open (respectively, rightopen) otherwise.

As an example, 60] = (14, 80]. We need therefore two operations of addition to perfom the composition of two convex sets, whose worst-case computational complexity is thus O(1).

2. If and are convex sets then their intersection is obtained by comparing the bounds of with those of : its worst-case computational complexity is thus O(1).

3. If is a convex set then its converse is obtained by negating the bounds of : its computational complexity is thus also O(1).

4. Therefore:

(a) If and are unions of convex sets with |mPcsand |mPcs, the worst-case computational complexity of their composition is ;

(b) If and are unions of convex sets with |mPcsand |mPcs, the worst-case computational complexity of their intersection is ;

(c) If is a union of convex sets with |mPcsn, the worst-case computational complexity of its converse is O(n).

Figure 12: The distance graphs of the STPs of Appendices B (left) and C (Right). The edges whose weights are infinite and the loops are not shown.

Let P = (X, C) be the following STP, whose distance graph is given by Figure 12(Left):

We apply the bdArc-Consistency algorithm bdAC-3 to P. The initial binarized domains of the variables and the initialisation of the queue Q are as follows:

1.

2.

We take in turn the pairs in Q for propagation. When a pair , with , is taken from Q for propagation, we apply the path-consistency operation on triangle . If is modified, the pairs such that and P has a constraint on and , that are no longer in Q, reenter the queue. bdAC-3 will terminate when a binarized domain becomes empty, indicating inconsistency of the initial STP, or the queue becomes empty, indicating that the STP has been made bdArc-Consistent.

path-consistency operation on triangle :

Step 3: we take the pair :

The queue Q is empty, and no (binarized) domain has become empty. bdAC-3 terminates and the resulting STP is bdArcConsistent. The minimal (binarized) domains of variables are, respectively, [10, 20], [40, 50], [20, 30] and [60, 70]. Therefore, if we consider the distance graph of the original STP, we have the following:

1. the distances of the shortest paths from to are, respectively, 20, 50, 30 and 70

2. the distances of the shortest paths from each of to are, respectively, and .

In the STP of the example in Appendix B, we replace constraint with , remove constraint , and add the constraint . We get the STP P = (X, C), whose distance graph is given by Figure 12(Right):

1. X , X, X, X, Xand

2. : ([10, 20]: ([30: (10]: (4]: ([40, 50]}.

The rooted distance graph of P does have a negative ciruit that is not reachable from , but from which is reachable. The proposed algorithm, contrary to Bellman-Ford-Moore’s, will detect the negative circuit; this amounts to detecting the inconsistency of the STP.

We apply the bdArc-Consistency algorithm bdAC-3 to P. The initial binarized domains of the variables and the initialisation of the queue Q are as follows:

1. Q , X, X, X, X, X, , X, X, X

2.

We take in turn the pairs in Q for propagation. When a pair , with , is taken from Q for propagation, we apply the path-consistency operation on triangle . If is modified, the pairs such that and P has a constraint on and , that were but are no longer in Q, reenter the queue. bdAC-3 will terminate when a binarized domain becomes empty, indicating inconsistency of the initial STP, or the queue becomes empty, indicating that the STP has been made bdArc-Consistent.

Step 1: we take the pair :

1. = IR [10, 20] [30) = [40)

2. There is modification, and the new configuration is:

• Q , X, X, X, X, , X, X, X

Step 2: we take the pair :

1. = [40IR [10, 20] = [40)

2. No modification, and the new configuration is:

• Q , X, X, X, , X, X, X

Step 3: we take the pair :

1. = IR[4010] = [20)

2. There is modification, and the new configuration is:

• Q , X, X, X, X, , X

Step 4: we take the pair :

1. = [40) = [40)

2. No modification, and the new configuration is:

Step 5: we take the pair :

1. = IR[404] = IR

2. No modification, and the new configuration is:

Step 6: we take the pair :

1. = [2040] = [20)

2. No modification, and the new configuration is:

Step 7: we take the pair :

1. = IR [20[40, 50] = [60)

2. There is modification. reenters the queue, and the new configuration is:

Step 8: we take the pair :

1. = [40[60[) = [56)

2. There is modification, and the new configuration is:

• The pair reenters the queue Q, which becomes

Step 9: we take the pair :

1. = [20[56[10] = [36)

2. There is modification, and the new configuration is: • The pair reenters the Q, which becomes Q =

• The pair reenters the Q, which becomes Q =

•

Step 11: we take the pair :

• The pair reenters the queue Q, which becomes

Step 12: we take the pair :

1. = [36[72[10] = [52)

2. There is modification, and the new configuration is: • The pair reenters the queue Q, which becomes

2. There is modification of with strictly smaller than path-lb. The conditions of Theorem 3 get violated, and the situation corresponds to a detection of a negative circuit. The algorithm terminates with a negative answer to the consistency problem of P (line 4 of the REVISE procedure of Figure 3).