On Finding a Solution in Temporal Constraint Satisfaction Problems
Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence. Temporal Reasoning. Pages 1460-1464.
© 1997 International Joint Conferences on Artificial Intelligence
Abstract
Computing a consiste nt int erpretatio n of th e variables involved in a set of temporal constraints is an important task for many areas of AI requiring temporal reasoning. We focus on the important classes of the qualit at ive relations in Nebel and Biirckert's ORD-Horn algebra, and of the metric constraints forming a STP , possibly augmented with in equat ions. For these tractable classes we prese nt three new algorithms for solving the problem of finding a solution, and an efficie nt algorithm for determining the consistency of a STP augmented with inequations.
- [Allen, 1983] J. Allen. Maintaining knowledge about tem-poral intervals. Communication of the ACM, 26(1):832-843, 1983.
- [Cormen et al., 1990] T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.
- [Dechter et al., 1991] R. Dechter, I. Meiri, and J . Pearl. Temporal constraint networks. ATtificial Intelligence, 49:61 -95, 1991.
- [Gerevini and Cristani, 1995] A. Gerevini and M. Grist- ani. Reasoning with inequations in temporal con- straint networks. In Proc. of IJCAI-95 Workshop on Spatial and Temporal Reasoning, pp. 13-23, 1995.
- [Gerevini and Schubert , 1995] A. Gerevini and L. Schu- bert. Efficient Algorithms for Qualitative Reasoning about Time. Artificial Intelligence 1 74:207-248, 1995.
- [Henschen and Wos, 1974] L. Henschen and L. Wos. Unit refutations and Horn sets. Journal of ACM, 21 :590-605, 1974.
- [Kautz and Ladkin, 1991] H.A. Kautz and P.B. Ladkin. Integrating metric and qualitative temporal reasoning. In Proc. of AAAI-91. The MIT press, 1991.
- [Koubarakis, 1992] M. Koubarakis. Dense time and temporal constraints with =f.. In Proc. of KRf3R'92, pp. 24-35, Cambridge, MA, 1992.
- [Koubarakis, 1995] M. Koubarakis. From local to global consistency in temporal constraint networks. In Proc. of the 1st Int. Conf. on Principle and Practice of Con- straint Programming, 1995. Springer Verlag.
- [Ladkin and Maddux, 1988] P.B. Ladkin and R. Mad- dux. On binary constraint networks. Technical Report KES.U.88.8 Kestrel Institute, Palo Alto, CA, 1988.
- Ligozat, 1996J G. Ligozat. A new proof of the tractabil- ity of ORD-Horn Relations. Proc. of AAAI-96, pp. 395-401. 1996. AAAI Press/The MIT Press
- [Montanari, 1974] U. Montanari. Networks of constrain- ts: Fundamental properties and applications to pictu- re processing. InfoTmation Science, 7(3):95-132, 1974.
- [Nebel and Biirckert, 1995] B. Nebel and H. J. Biirckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Jour- nal of the ACM 42(1):43-66, 1995.
- [van Beek, 1990] P. van Beek. Reasoning about qualita- tive temporal information. In Pmc. of AAAI-90, pp. 728-734, Boston, MA 1990.
- Vilain and Kautz, 1986J M. Vilain and H.A. Kautz. Constraint propagation algorithms for temporal rea- soning. In Proc. of AAAI-86, pp. 377-382. 1996.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
Reasoning about temporal constraints is an important task in many areas of AI. Allen's Interval Algebra (IA) [1983] and Vilain and Kautz's Point Algebra (PA) [1986] are two fundamental models for qualitative temporal rea soning, while Dechter, Meiri and Pearl's TCSP [1991] is a prominent approach for met ric temporal reasoning.
Given a set S of temporal constraints, two important related reasoning problems are determining the consis tency of S, and finding a consistent scenario or solution for the variables involved inS. A consistent scenario is an ordering of the variables (either points or interval end points) inS, which is consistent with the constraints inS. A solution for Sis an interpretation of the point-variables (interval-endpoint variables) inS which satisfies' the con straints in S.
Consistency checking and finding a solution (a consis tent scenario), are NP-Hard problems for lA [Vilain and Kautz, 1986] and TCSP [Dechter et al., 1991], while they are polynomial for PA [van Beek, 1990] and for some important restrictions of lA and TCSP. These include the qualitative interval relations of the ORD-Horn class [Nebel and Biirckert, 1995], and the metric constraints of a "simple temporal constraint satisfaction problem" (STP) [Dechter et al., 1991]. The ORD-Horn class forms a subalgebra of lA, which is the maximal tractable sub class of relations in lA containing all the thirteen basic relations. The constraints of a STP are inequalities of Matteo Cristani Istituto Policattedra Universita degli studi di Verona Strada le Grazie, I-37134 Verona, Italy cristani@romeo.sci.univr . it the form p2- p1 ::; d, where p1,p2 are point-variables, and d is any value in a dense time domain. 1
STP"' is another interesting tractable class, which subsumes PA and STP. STP1"' is an extension of STP to include inequations, i.e. constraints of the form p2 - p1 =f. d [Koubarakis, 1995; Gerevini and Cristani, 1995] . Koubarakis [1992] proposed a method for check ing the consistency of a STP augmented with disjunc tions of inequations, whose time complexity reduces to 0( n 3 + kn 2 ) when the input is a STP1"', where n is the number of variables and k the number of inequations.
In this paper we are mainly concerned with the prob lem of finding a solution for these tractable classes. While Nebel and Biirckert [1995] proved several interest ing strong results about their ORD-Horn algebra, they left open the problem of efficiently finding a consistent scenario or solution.
Dechter et al. [1991] proposed a simple algorithm for finding a solution of a given STP which only contains non strict inequalities, leaving open the important case in which inequalities can be strict (e.g., p2 - p1 < d).
Concerning STP1"', we are not aware of any specialized algorithm for the problem of finding a solution.
We propose three new algorithms for solving these problems. Also, we investigate the problem of deter mining the consistency of a given STP1"', presenting an efficient algorithm which improves the complexity bound of Koubarakis' method. Specifically, we will present:
- a simple algorithm for finding a solution for a set of ORD-Horn relations. The algorithm requires O(n 2 ) time, if the input set of relations is known to be path-consistent, and O(n 3 ) time in the general case, where n is the number of interval-variables.
- An O(n 3 ) time algorithm for finding a solution for a given STP including strict inequalities.
- An O(n 3 + k) time algorithm for determining the consistency of a given STP1"'. 2
1 Equality constraints such as p2-pl = d can be expressed as a pair of inequalities.
2 Note that when the number of input inequations (k) is limited to those required to express the qualitative point re lations of PA or of the interval relations in the "Pointizable
- An O(n 3 + k) time algorithm for finding a solution for a given STP"'.
2 Finding a solution for ORD-Horn interval relations
In this section we provide an algorithm for finding a so lution of a set of relations over the ORD-Horn interval algebra (7-l). The time complexity of our algorithm is O(n 2 ), if the input set of relations is known to be path consistent, and O(n 3 ) in the general case, where n is the number of interval variables.
The proofs of our claims are based on the following definitions and facts:
- Disjunctions of PA-relations of the form a = b, a :::; b, a -=f:. b are called ORD clauses. ORD clauses containing at most one literal (PA-relation) of the form a = b or a :::; b and an:y· number of literals of the form a =I- bare called ORD-Horn clauses [Nebel and Burckert, 1995].
- The theory ORD that axiomatizes "=" as an equiv alence relation and "S" as a partial ordering over the equivalence classes is a Horn theory [Nebel and Burckert, 1995].
- Let e be a path-consistent set over 7-l. Then 1r(e) U ORD1r(8) does not allow the derivation of new unit clauses by positive unit resolution, where 1r(e) denotes the set of ORD-Horn clauses translat ing the relations in e, and ORD1r(e) denotes the ax ioms of ORD instantiated to all the point-variables mentioned in 1r(e) [Nebel and Burckert, 1995].
- ( 4) Let e be a set of relations over 7-l. Each clause of 1r(e) is either unary or binary [Nebel and Burckert, 1995].
- A temporally labeled graph ( TL-graph) is a graph with at least one vertex and a set of labeled edges, where each edge ( v, l, w) connects a pair of distinct vertices v, w. The edges are either directed and la beled :::; or <, or undirected and labeled =I- [ Gerevini and Schubert, 1995].
- A set S of the PA-relations can be represented by a TL-graph T such that S is consistent iff T does not contain any <-cycle, or any ::;-cycle that has two vertices connected by an edge with label# [Gerevini and Schubert, 1995; van Beek, 1990]. 3
- A set S of PA-relations can be translated into a logically equivalent set of unary ORD-Horn clauses [Nebel and Burckert, 1995], which we will call the ORD-Horn translation of S.
Before introducing our algorithm, we need to prove the following lemma:
subclass of IA" [Ladkin and Maddux, 1988], our algorithm takes O(n 3 ) time, while Koubarakis's method requires O(n 4 ) time. If k is larger than O(n 2 ), then the improvement is even more significant.
3 A =-relation such as X = y is represented as the pair of edges (x, :S, y) and (y, :S, x).
Lemma 1 Let I: be the ORD-Horn translation of a con sistent set S of FA-relations, and x and y two point variables involved in S. If S entails x = y then x = y is derivable from I: U ORDer:.) by positive unit resolution.
Proof. Suppose that S entails x = y, but x = y cannot be derived from I: U ORD(E) by positive unit resolution. Then, the set I:' = I: U { x -=f:. y} is inconsistent, but from L:'UORDcr:.') we cannot derive the empty clause by pos itive unit resolution (because the only positive unit reso lution possible against x =I- y is with positive unit clause x = y). Since I:' U ORD(E') is a set of propositional Horn clauses, this contradicts the fact that positive unit resolution is refutation-complete for propositional Horn theories [Henschen and Wos, 1974].
Therefore, if S entails x = y, then x = y must be derivable from I:UORD(E) by positive unit resolution. 0
Theorem 1 There exists an O(n 2 ) time algorithm for finding a consistent scenario of a path-consistent set e of relations over 7-l, where n is the number of interval variables involved in e.
Proof (sketch). By Property (4) we have that 1r(e) = I: 1 U I:2, where I:1 is a set of unary Horn clauses and I: 2 is a (possibly empty) set of binary Horn clauses, each of which has at least one #-disjunct (=f:.-relation). 4
Let T be the TL-graph representing I:1 , and P the set of the positive unit clauses entailed by I:1 . By properties (3- 4) and Lemma 1, we have that if x -=f:. y is a disjunct of a clause in I:2, then (x = y) $. P.
Consider now choosing a #-disjunct for each of the clauses in I:2. Let I be the set of inequations selected, and T' the TL-graph obtained by extending T with the edges representing the relations in I. Since T is consis tent, by Property (6) and construction ofT', T' does not contain any <-cycle. Furthermore, by construction of I:1 , I:2 and T, if x =I- y is a disjunct in I:2 then T does not contain a ::;-cycle crossing x and y (otherwise we would have that (x = y) E P). Hence, by Property (6) I: 1U I is consistent.
It is easy to see that the endpoints of all the inter val variables involved in e have a corresponding point variable in I:1 U I, and that if we find a solution for I:1 U I, then we will also have a solution for e. In fact, if s is a solution for I: 1 U I, then, by construction of I:1 U I, the interpretation of the interval endpoints defined by s do satisfy 7r(e) and e.
A consistent scenario s for a set of PA-relations in volving m point-variables can be found in O(m 2 ) time [van Beek, 1990]. From s we can derive a solution in O(m) time (e.g., we assign an integer ito the variables in the first position of s, i + 1 to the variables in the sec ond position, etc.). Since I:1 U I is a set of PA-relations involving 2n variables (those corresponding to the end points of the n interval variables of e), we can find a solution for I:1U ~(and for e) in O(n 2 ) time. 0
4 1r(8) can be computed in 0(181) time using a table of 868 elements containing the translation of each ORD-Horn relation.
Let 1r1 (8) be the set of unary clauses in 1r(8), and 1r2(8) the set of binary clauses in 1r(8). Given a set n of relations in 'H., from the proof of Theorem 1, and the fact that the consistency of n can be decided in O(n 3 ) time by enforcing path-consistency to it [Nebel and Biirckert, 1995], it is easy to see that the following algorithm com putes a solution for n (if it exists) in O(n 3 ) time:
Algorithm 1: ORD-HORN-SOLVTION
Input: a set D of relations in 'H..
Output: a solution for n, if one exists; nil otherwise.
- Determine the consistency of D by enforcing path consistency to it. If n is not consistent, then return nil , otherwise let e be the path-consistent set uf relations equivalent to n.
- Run Beek's algorithm [1990] for determining a con sistent scenario of a set of PA-relations on 1r1 (8)UD, where D is a set of #-relations consisting of a # disjunct for each clause in 1r2 ( 8). Let s be the sce nario computed. 5
- Derive from s a solution for 8 (D) by assigning to each interval endpoint of 8 a number consistent with s. (This can be done in O(n) time, as discussed in the proof of Theorem 1.)
Therefore, we have proved the following theorem:
Theorem 2 Given a set D of relations in 'H., ORD HoRN-SOLUTION computes a solution for n {if it exists) in O(n 3 ) time, where n is the number of variables in D.
Remark. If the input set of relations is known to be path-consistent, then step 1 can be omitted and the time complexity of ORD-HORN-SOLUTION reduces to O(n 2 ) .
3 Preliminaries on STP and STPf
Most of the terminology introduced in this section is based on the concept of a Temporal Constraint Network given in [Dechter et al., 1991].
A Temporal Constraint Network (TN) is a directed la beled graph where the vertices represent point variables over a dense time domain T (e.g., the real numbers), and the edges connect distinct vertices and are labeled by a fi nite set of convex intervals overT. An edge ( v, l, w) from v to w with label {!1 , 12 , ... , In} represents the binary constraint: Cvw = w- v E IVW> where lvw = u~=l Ii .
The constraints of a given STP can be represented by a Simple Temporal Network (STN), which is a TN where each edge is labeled by exactly one (convex) in terval [Dechter et al., 1991].
Given a set C of constraints represented by a TN (TN constraints) involving the set of variables x1 , x2, .. , Xn, the set of values i 1 , i 2 , .. , in is a solution of C iff the as signment x1 = i1, i2 = i2, .. , Xn = in satisfies all the constraints in C. A TN is consistent iff the correspond ing set of constraints has at least one solution. Two TNs are equivalent if they have the same set of solutions.
5 Note that since 1r(8) U D is known to be consistent, we could actually consider only the PA-relations of 1r1 (8) . This is because any consistent scenario computed by applying van Beek's algorithm to 1r1 (8) is also a consistent scenario for 1!'1(8) u D.
Given two TN-constraints Cxy and c~Y' involving the same pair of variables, Cxy is tighter than C~Y (Cxy ~ C~y) when lxy ~ I~y [Dechter et al., 1991]. Given two TNs S and T, S is tighter than T (S ~ T) if every constraint represented by S is tighter than the corresponding constraint represented by T. If S is tighter than T then the solutions of S are also solu tions of T. The minimal network of a TN T is the tightest network equivalent to T [Dechter et al. , 1991; Montanari, 1974] .
A TNT is decomposable [Dechter et al., 1991; Monta nari, 1974] if every locally consistent assignment to any subset of variables (vertices) ofT can be extended to a solution. 6
To prove our results we will also use the following def initions and properties from [Dechter et al., 1991] :
- Given a STN S the distance graph of Sis a directed labeled graph with the same vertices asS, and with an edge from v tow, labeled by the upper bound of the interval of the label on the edge from v to w in Sand an edge from w to v, labeled by -1 times the lower bound of the interval of the label on the edge from v to w in S .
- A STN is consistent iff its distance graph does not contain "negative cycles", i.e., cycles where the sum of the labels on the edges is negative.
- Given a STN S the d-graph of S is a directed labeled graph that has the same vertices as S, and an edge for each pair of (not necessarily distinct) vertices in S labeled by the shortest path between those ver tices in the distance graph. S is consistent iff its d-graph does not contain any negative edge from a vertex to itself (a circular edge).
Note that Property (9) assumes that the intervals of the labels of the STN are all closed, except the intervals where the lower bound is -oo, or the upper bound is +oo (i.e., in the STP represented by the STN there are no strict inequalities of the form y- x < d). Such an as sumption is made for simplicity in [Dechter et al., 1991, p. 64]. When the intervals can be (semi)open (i.e., in the STP there are strict inequalities), in order to ensure the consistency of the STN (STP), the absence of neg ative cycles in the distance graph corresponding to the STP can still be a sufficient condition, provided that the notion of negative cycle is slightly extended to take into account the presence of the strict inequalities. This can easily be done by using a method similar to the method used by Kautz and Ladkin [1991].
The constraints of a STP# can be represented by a STN augmented with inequations, defined as follow:
6 An assignment of values to a set S of variables is locally consistent if it satisfies the constraints involving only vari ables in S [Dechter et al., 1991].
Definition 1 A STN augmented with inequations (ST Ni-) is a directed labeled graph where the label on each edge is a pair (T, E), T is a convex interval that can be either closed, semi-open or open with the open bound equal to +oo or -oo, and E is a finite (possibly empty) set of points ofT called excluded points ofT.
The label (Tvw, Evw) on an edge ( V, (Tvw, Evw), W) from v to w of a STNi- represents the constraint w- v E {Tvw- Evw}·
A STNi- T entails w - v -=1- d ( w - v = d) iff v and w are vertices ofT, and there is no solution for the set of constraints represented by T such that w - v = d ( w - v -=1- d) is satisfied.
Definition 2 Given a STNI' T, the STN obtained from T by substituting [a, b] for any label ([a, b], E) ofT is called the relaxed network ofT, written as yr .
Definition 3 Given a STNI' T and two vertices v,w of T such that I = [I-, I+] is the label of the edge from v to w in the minimal network of the relaxed network of T , an inequation w- v -=1- d ofT is:
- convex iff d = I- or d = I+;
- non-convex iff I- < d < I+ .
4 Finding a solution for STP
In this section we address the problem of finding a so lution for a given STP. The consistency of a STP S can be determined in O(n 3 ) time, where n is the number of variables in S [Dechter et al., 1991] . If S is not consis tent, then there are no solutions for it. If S is consistent, then we distinguish two cases: S does not contain strict inequalities, and S does contain strict inequalities.
In the first case, the following is a solution that can be computed in O(n 3 ) time [Dechter et al., 1991]:
where xi (i = l..n) are the variables of the given STP, x0 is a special additional variable indicating the absolute starting time and preceding all the other variables (0 ~ xi - x0 < +oo), and li is the lower bound of the interval labeling the edge from x0 to xi in the minimal network of the given STP. 7
If S is consistent and contains strict inequalities, then we prove that the following algorithm computes a solu tion in O(n 3 ) time:
Algorithm 2: STP-SOLUTION
Input: a STP S
Output: a solution for S, if it exists; nil, otherwise
- Check the consistency of S. If S is not consistent then return nil and stop.
- Compute the minimal network M of the STP de rived from the original one by relaxing each strict inequality of the form y- x < d (d finite) to the non-strict inequality y - x ~ d.
7 Note that in' such a minimal network all the left bounds on the distance between xo and Xi are finite.
- For each interval I labeling an edge of M, if it has an open and finite left bound I-, then replace it with the closed bound I- + €, where € is a positive quantity defined as: 8
and 8 is the finite length of the shortest interval labeling the edges of M, if this exists, or any finite number if all the intervals of M have -oo or +oo as one of their bounds. Let us call the resulting relaxed network M'.
- Compute the minimal network M" of M'.
- Return xo = 0, x1 = l1, ... , Xn = ln as a solution for S ( M), where li are the left (closed) bounds of the intervals labeling the edges from x0 to Xi in M" (i = l..n) .
Theorem 3 STP-CONSISTENCY computes a solution for a given STP (STN) in O(n 3 ) time (if it exists), where n is the number of point-variables (vertices).
Proof. It is easy to see that the global time complexity of STP-SOLUTION is O(n 3 ). Concerning its correctness we observe that:
- (i) all the intervals of M' with a finite left bound are closed on the left (by construction of the network). Hence in M" the left bound of the intervals on the edges from x0 to xi (i = l..n) will also be closed.
- (ii) All the solutions of M' are also solutions of M (be cause M' is tighter that M).
- (iii) M' is consistent (provided that the original STP was consistent).
In order to prove (iii) suppose that step 2 adjusts k left-open intervals of M to derive M'. Consider now per forming each of these perturbations incrementally (in stead of all at once), according to the following scheme:
- 1'. N:=M;
- 2'. adjust one of the finite left-open bounds r;; of N by increasing it to r;; + €;
- 3'. M :=Minimal network of N;
- 4'. if M contains a finite open left bound then go to 1' else return M.
Note that after each iteration in this scheme the num ber of intervals in M with a finite open left bound mono tonically decreases. So, a sequence of at most k "tuned" networks is computed at step 2', and at most k minimal networks are computed at step 3'. (The actual number of these networks can be less than k, because the com putation of the minimal network of N can make closed some open left bounds.)
Let N1 , ... , Nh be the sequence of networks computed at step 2' and M 1 , ... , Mh the sequence of minimal net works computed at step 3' (1 ~ h ~ k ~ n 2 ) . We can prove by induction on h that the tuned network Nh is consistent. This is obvious for h = 1, since M is de composable. Suppose now that Nh_1 is consistent (and Mh- 1 is minimal), we show that Nh is consistent as well (Mh is minimal). We have that in Mh- 1 any finite left bound interval (either open or closed) can be increased at most to I'M + (h - 1)E, relevant to its value (I'M) in the original network M (by construction of Mh_I). While the right interval bound of any interval of Mh-1 maintains the same value as in the original M. Since by definition of E we have that
8 The use of appropriate €-quantities is a known technique in Linear Programming.
and by definition of 6 I'M + hE < r}j, we can increase the (finite) left open bound of any interval in Mh-1 of E, deriving a new left bound which is still strictly less than the corresponding right bound in Mh_ 1 . Hence, since Mh- 1 is minimal and decomposable, the tuned network Nh will be consistent.
To conclude, note that the network returned by the "incremental" algorithm (Mh) is the same as the network M" computed at step 3 of the "non-incremental" algo rithm, and that the existence of E is guaranteed by the fact that the temporal variables have dense domains. D
5 Checking consistency and finding a solution for STP'"'
In this section we first prove that checking the consis tency of a STN'~" can be accomplished in O(n 3 + k) time and O(n 2 + k) space, where n is the number of point variables, and k the number of inequations. Then, we give an algorithm for finding a solution of a given STP'~", which has the same complexity as consistency checking.
The following proposition is a direct consequence of property (9) given in Section 3. It will be used in the proof of Lemma 2, which is the base for proving the correctness of our algorithm for checking the consistency.
Proposition 1 A STNI T is consistent iff for each in equation w- v -I- d it is possible to choose one of the two inequalities w - v < d or v - w < -d so that the dis tance graph obtained by extending the distance graph of yr with the resulting inequalities does not contain nega tive cycles.
Lemma 2 A STNI Tis consistent iff yr does not have negative cycles in its distance graph, and it does not en tail w - v = d for any inequation w - v -I- d in T.
Proof. The "only if" direction is trivial. The "if" di rection is proved by induction on the number k of in equations of T. We first consider the case in which for every inequation w - v -I- d, d ~ 0. When k = 0 the ab sence of negative cycles in the distance graph guarantees consistency. Suppose that the property holds for k - 1 inequations and consider a STN'~" N with k- 1 inequa tions, whose relaxed network Nr does not have any neg ative cycles in its distance graph, and does not entail the equation corresponding to any of the k - 1 inequations. Thus, by the induction hypothesis N is consistent, and Algorithm 3: STN'~" -CONSISTENCY
Input: a STN'~" T
Output: true if T is consistent, nil otherwise
- Compute the d-graph D of the relaxed network ofT;
- if D contains negative circular edges then return nil ;
- for each inequation w- v-I-dinT do
- if the label on the edge of D from v to w is d and the label on the edge from w to v is -d
then return nil ;
- return true.
by Proposition 1 we can extend the distance graph of Nr with one inequality for each inequation of N, obtaining a graph D without negative cycles.
Consider adding the inequation w- v-I- d toN. We can do that consistently if we can consistently add w - v < d or v- w < -d to D. Since when there is a path from v to w in D there is also a path from w to v, and since D does not contain negative cycles, only one of the following possibilities can hold:
- (a) all the paths connecting v and ware positive paths;
- (b) there are negative (and possibly positive) paths from w to v and only positive paths from v to w ;
- (c) there are negative (and possibly positive) paths from v tow and only positive paths from w to v.
In cases (a) and (b) we can add w- v < d to D without creating a negative cycle, so that by Proposition 1 N U { w - v -I- d} is consistent. For the remaining case (c) suppose that both the addition of w - v < d and of v - w < -d create a negative cycle. Then there exists a negative path of length l (with l < 0) from v tow and a positive path of length l' (with l' > 0) from w to v such that d + l < 0 and l' - d < 0. From these inequalities we derive l + l' < 0. But this means that D contains a negative cycle, contrary to the construction of D . Hence, also for case (c) at least one of w- v < d and v- w < -d can be consistently added to D. It follows that w- v -I- d can be consistently added to N.
The proof can be extended to include inequations w- v-I- d (d < 0) excluding negative points by an anal ogous argument, using induction on the number of such inequations. In cases (a) and (c) we can consistently add v- w < -d, while we deal with case (b) in the same way as we did for case (c) when d ~ 0. D
The previous lemma guarantees that consistency checking of a STN'~" (STP'~") can be accomplished by using the algorithm given in Figure 1.
Theorem 4 STNI-coNSISTENCY correctly checks the consistency of a STNI Tin O(n 3 +k) time and O(n 2 +k) space, where n is the number of the vertices ofT and k is the number of inequations.
Proof (sketch). Property (10) of STNs (see Section 3) together with Lemma 2 ensure the correctness of STN~ CONSISTENCY. Regarding the complexity, it is sufficient to observe that: the relaxed network ofT can be com puted in time linear over the number of the edges ofT; step 1 can be accomplished in O(n 3 ) time and O(n 2 ) space [Cormen et al., 1990; Dechter et al., 1991], step 2 in O(n) time, and step 3 in O(k) time and space. D
We now show that the problem of finding a solution for a given STP~ can be solved by running an algorithm which has the same complexity as STN~-CONSISTENCY.
Theorem 5 A solution for a given STNI' {STP'i') can be found in O(n 3 + k) time (if it exists), where n is the number of point-variables {vertices), and k is the number of the inequations.
Proof (sketch). We can derive an algorithm for comput ing a solution for a given STN~ (STP~) by modifying STP-SOLUTION in the following way:
Algorithm 4: STP~-SOLUTION
Input: a STP~ T
Output: a solution forT, if it exists; nil, otherwise
- Check the consistency of T. If T is not consistent the return nil and stop.
- Let M be the STN~ computed by the following steps:
- (a) compute the minimal network T' of the relaxed network ofT;
- (b) add toT' the input inequations which are con vex relative T', and compute the minimal net work T" of the resulting network;
- (c) add to T" the input inequations which are non convex relative to T";
- Same as step 2 of STP-CONSISTENCY, except that 8 is defined as:
- Min { 8ij}, if at least one interval has both the bounds finite, or the lower bound is finite and the interval is not convex, i.e, it has at least one (finite) point excluded;
- any finite number otherwise,
where i, j = l..n, i =f. j and 8ij is the length of the jiTst convex subinterval of the (possibly non-convex) intervals of M (e.g., for the interval [2, 10] -{3, 4} the length of such a subinterval is 1; while for the interval (1, 5], the relevant subinterval has length 4).
- Same as step 3 of STP-SOLUTION, except that M" is the minimal network of the STN resulting from M' by omitting all the non-convex inequations.
- Same as step 4 of STP-SOLUTION.
The proof of the correctness of STP-CONSISTENCY is similar to the proof of Theorem 3. Concerning the com plexity, note that by Theorem 4 step 0 can be computed in O(n 3 + k) time, step 1 in O(n 3 + k) time, and steps 2- 4 in O(n 3 ) time. D
6 Conclusions
We have presented three new algorithms for computing a solution (scenario) for a set of ORD-Horn relations, for a given STP, and for a STP~. Also, we have presented an algorithm for checking the consistency of a STP~ , which improves the complexity bound of Koubarakis' method.
Recently Ligozat [1996, personal communication] pro ved the tractability of the ORD-Horn algebra by using a method for deriving a consistent scenario that is based on iteratively (a) refining a path-consistent network and (b) imposing path-consistency to it. However, he does not give a detailed analysis of his method in terms of time complexity, which appears to be at least one order of magnitude worse than the complexity of our method.
@inproceedings{ijcai1997p210,
title = {On Finding a Solution in Temporal Constraint Satisfaction Problems},
author = {Gerevini, Alfonso and Cristani, Matteo},
booktitle = {Proceedings of the Fifteenth International Joint Conference on
Artificial Intelligence, {IJCAI-97}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Martha E. Pollack},
pages = {1460--1464},
year = {1997},
note = {Temporal Reasoning},
url = {https://ijcai.org/proceedings/1997/210},
}
TY - CPAPER TI - On Finding a Solution in Temporal Constraint Satisfaction Problems AU - Gerevini, Alfonso AU - Cristani, Matteo T2 - Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence, IJCAI-97 PB - International Joint Conferences on Artificial Intelligence PY - 1997 SP - 1460 EP - 1464 UR - https://ijcai.org/proceedings/1997/210 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: