Path Consistency in a Network of Non-Convex Intervals

1 Introduction

Common sense knowledge about the occurrence of events is often incomplete. The kinds of incompleteness of in­ terest here is expressed in the following sentences:

1. John sometimes drives to Orlando.
2. John's ten trips to Orlando this month twice pre­ ceded his phoning Phyllis.
3. Some of John's ten trips to Orlando preceded her phoning Phyllis.

The first example exhibits number incompleteness: it is not clear how many driving events there are, hence how many periods of time are involved, but that at least one occurs. The second example illustrates distribution un­ certainty; we don't know which phonin~ intervals over­ lapped with which meetings. The thn~ example ex­ hibits, in addition to distribution uncertamty, what can be called participation uncertainty; it is not known how often the relation between the trips and the phonings occurred.

Uncertainty of this kind is removed by adding quan­ titative information. Compare (1)-(3) with "John's ten trips to Orlando this month twice preceded his phoning Phyllis: the first time and the third time" . Adding the first quantity eliminates number uncertainty; the second quantity ("twice") eliminates participation uncertainty; the last two quantities together eliminate distribution uncertainty.

Temporal knowledge incompleteness makes it difficult to build a reasoner that adequately deals with time. In this paper, the concern is to formalize a representation which addresses the problem of reasoning with number, distribution, and participation uncertainty. To accom­ plish this aim the remaining sections

1. Define a class of binary temporal relations between pairs of n-intervals;
2. Construct an algebra for formalizing reasoning problems involving n-interval relations; and
3. Demonstrate how path consistency can be applied to a knowledge base of assertions about n-interval relations, recast as a relation network, in the sense of [Van Beek, 1990].

2 Underlying Model of Time

Time is considered here to be a linear order on a do­ main consisting of points identified with the real num­ bers under the ordering <. The collection of inter­ vals over this domain is the set of finite sequences of the form I = (T!, It, I:;, It", ... , I;;, I;t), representing a gapped interval with n convex components, or subin­ tervals, starting at T! and ending at I;t. We call such a sequence an n-interva/ 1 , with the ordering I1 < It < I:; < ... < I;t . I; = (I;-, It) represents the ith convex component of I.

In addition to the ordering constraints on n-intervals, there is structure imposed by the fact that n-intervals are the temporal component of the representation of knowl­ edge about recurring events. This complexity is repre­ sented by introducing binary relations between convex parts of n-intervals.

1 This term is used differently by Ligozat [Ligozat, 1990], viz., to denote an interval consisting of n points.

First, time is viewed as being partitioned into seg­ ments, or blocks, each representing a set of occurrences of recurring intervals. Blocks come in various sizes; com­ mon examples include days , weeks, months, years, etc. Formally, a temporal partition can be viewed as a func­ tion from a convex interval R , which we will call a ref­ erence frame, to a set of convex intervals. Being a parti­ tion, no two items in this set overlap, and each segment of R is in one of the members of the set. For example, let W eeks(R) = the set of convex intervals in R with a duration of (at most) one week, starting at R! 2 . From this notion, where r is a partition, we define an equiva­ lence relation ASS OCr (I;, lj ), which is true of pairs of intervals I; and lj if and only if I; and lj are in the same member of r(R) . For example, if ASSOCw eeb(/;, lj) , then I; and lj occur in the same week.

In addition to associated intervals within a block, the model views periods of time to be correlated. Corre­ lation is an equivalence relation between pairs of con­ vex parts of recurring events that holds as a result of binary relations holding between them. For example, consider the sentence "Meetings precede lunches twice a week". There are two distinct groupings here: the first is indicated by the term "weeks", which partitions the reference frame into weekly blocks of associated in­ tervals. The second grouping pairs convex parts of the recurring events "meetings" and "lunches". This pairing phenomenon is represented in the model by the relation of correlation. Further examples of correlation are pro­ vided below.

James Allen [Allen, 1983] defined a set of primitive binary relations on convex intervals by enumerating all ways in which two ordered pairs of real numbers can be related. There are 13 such primitives, which we col­ lect together in the set ACR: before (b), meets (m), during (d), overlaps ( o), starts ( s), finishes (!), their inverses (after ( bi), met by ( mi), et~, and equals ( =). From these, he defined a class of 2 1 interval relations by considering all possible disjunctions of primitives; we call this set CR. Members of CR can be depicted as finite disjunctions of the form "R1 V R2 V ... Rn", where R; E A CR. As constraints in a relation network (de­ fined below) the same relation is depicted as the set {R1, R2, ... , Rn}. 3

Since temporal relations in such a knowledge base are binary, it is possible to represent the knowledge as a network, where each arc represents one of the temporal relations. More precisely (from [Van Beek, 1990]):

Definition 1. A Network of Binary Relations is a set X of m variables {X 1 , ... Xm}, a domain D; of possible values for each variable, and binary relations R;,j between variables . An instantiation of the variables in X is an m-tuple representing an assignment of elements of D; to each X; . A consistent instantiation of a network is an instantiation that satisfies all the relations between the variables. A network is consistent if such an instan­ tiation exists; otherwise, it is inconsistent. A relation R; ,j is f easible with respect to a network if there exists a consistent instantiation of the network where R; i is satisfied. For each edge in a network, the set of fe~ible relations is the set consisting of all and only the relations that are feasible .

2 If it is not possible to divide R into equal segments of one week duration, there will be a segment at the end of R of duration less than one week.

3 A word on notation used throughout: following conven­ tion, R, S etc. stand for members of CR. Lower case letters from i, j, ... are used to specify arbitrary convex intervals; as noted, upper case letters from I, J, ... specify n-intervals. Single subscripts (e.g. Rk) distinguish members of ACR. Double subscripts are used (e.g. R;,i) to emphasize that R is a relation between i and j; these are often omitted.

Definition 2 A {Convex) Interval Binary Relation Net­ work (IRN) is a binary relation network whose variables represent intervals, and whose binary relations are mem­ bers of CR. An atomic IRN is an IRN each of whose edges are labeled with a single member of ACR. A so­ lution network (scenario) is a consistent atomic IRN.

A cheap, useful inference technique used in examining systems of interval relations is that of path consistency [VanBeek, 1990] 4 :

Definition 3 A network is path consistent if and only iffor every triple of variables (i , j,k) , Yx,Yz ,xR; ,kz => 3y E Dj xR;,jy 1\ yRj ,kZ .

A path consistency algorithm such as the one found in [Allen, 1983], is an approximate technique for determin­ ing the set of feasible relations in an IRN. It performs intersection and composition of relations, and assumes that a inverse operation on relations is defined. Intersec­ tion of relations is just intersection of sets. In the tem­ poral domain, a Composition Table ([Allen, 1983], not reprinted here) defines composition between elements of ACR. In the general case, the results of composing two elements of CR is just the union of the result of the pairwise composition of its atomic elements. Finally, for each relation R; ,j , its inverse (R~j) , is defined as the relation Rj,i that satisfies IR;,jJ ¢:::> J Rj,;I. The path consistency algorithm repeatly performs composi­ tion over triangles of edges in a relation network, until no more changes to any edges are performed. Changes occur when a composition of relations on a pair of edges results in a change (a "refinement") of the relation in the third edge.

To summarize, the underlying model for reasoning with recurring events has the following components:

1. A set of n-intervals I, J, K . . . , each consisting of an ordered set of convex parts called subintervals;
2. A function for retrieving the xth convex part of any n-interval I, the result of which is denoted by Iz:.
3. A binary equivalence relation correlation, (COR), defined between convex intervals; in addition to being an equivalence relation, if COR(Iz:, ly) and COR(Iz:, lz) then y = z.
4. A binary equivalence relation association, abbrevi-

4 Freuder [Freuder, 1978] generalizes path consistency to k-consistency: a network is k-consistent if, given any instan­ tiation of any k -l variables satisfying all the relations among the variables, there exists an instantiation of the k-th vari­ able such that the k values together satisfy all the relations. Path consistency corresponds to 3-consistency.

ated as AS SOC; 5 .

1. The set CR, based on the set of Allen primitives ACR.

In what follows, we extend the IRN framework for the representation of n-intervals and their relations. It is demonstrated how the method of path consistency can be applied to the problem of determining the set of fea­ sible relations in a n-interval relation network.

3 A Class of N-Interval Relations

In this section, a language is constructed for specifying a collection of binary temporal relations between pairs of n-intervals, where a specification is a set of assertions describing n-interval relations.

This language regiments fragments of natural lan­ guage discourse (in this case, English) involving the ap­ plication of temporal adverbs "sometimes" "only", "al­ ways", "always and only", and their negations, "never", "not always", etc. These adverbs can be viewed as oper­ ators on elements of CR to make assertions about recur­ ring or repeating events. For example, applying "always" to the convex interval relation "before or meets" results in the n-interval relation "always before or meets".

An adequate semantics for temporal specifications re­ quires sensitivity to what we will call co-designation. For illustration, contrast the following three fragments:

1. John sometimes goes to work before calling his dad. Then, he misses (i.e. the call overlaps) the meeting.
2. Joan sometimes goes to work before calling her dad. Otherwise, she calls her dad first.
3. Faculty meetings sometimes precede seminars. Those meetings overlap with lunch.

In the first passage, the adverb "then" serves to establish a connection with the previously introduced occurrence of going to work. In the second, "otherwise", serves to introduce a temporal relationship between a different oc­ currence of going to work and that of calling. Informally, co-designation can be viewed as a relation between two assertions, in which, informally, each succeeds in "pick­ ing out" a common object (in this case, the same period of time). Thus, there is co-designation between the sen­ tences in fragments 1 and 3, but not in 2.

The case of "sometimes" thus illustrates the need for a mechanism for representing co-designation. This is also the case with contexts involving "always", "only" and "always and only", but these cases are more complicated. To say that cocktails always follow faculty meetings im­ plies a cocktail event after every faculty meeting event. Dually, to say that cocktails only follow faculty meetings is to say that for every cocktail event, there is a faculty meeting preceding it. Finally, to assert that cocktails always and only follow faculty meetings is to express a one-to-one correlation between the two events.

5 The association relation is not discussed extensively in this paper, and does not figure explicitly in the interpretation of the formal language defined in this paper. It is intended to serve within more general systems for reasoning about recur­ ring events, and is introduced here for the reader to become acquainted with this broader framework.

Assertions involving any of these operators will also be se~sitive to co-designation relationships. However, in certam of these contexts, co-designation is being implic­ itly established with any subinterval of ann-interval. An ~xample will motivate this idea. If I say "Faculty meet­ mgs only meet cocktails", and also "Sometimes voodoo chanting begins faculty meetings", one can inf;r a tem­ poral relation between voodoo chanting and cocktails (viz., the former are sometimes before the latter), in­ dependently of the distribution of the chanting among the faculty meetings. To draw this inference, there needs to be a mechanism for expressing the added degree of uncertainty expressed by the italicized phrase.

With this complexity in mind, a language for express­ ing n-interval relations is now defined.

Definition 4. The language NRL consists of the follow­ ing: A set of terms for designating n-intervals I, J . . . ; a set of basic operators: "II" ("always"), "fl" ("only"), "8" ("always and only"), and "E" ("some~imes"); . a symbol for negation of basic operators (e.g., E), the re­ s~lt is a set of operators for "n9t always" (II), "not only" (e), "not always and only" (fl), and "not ever" (f:); fi­ nally, a set of i-terms (index terms), consisting of either: a variable (taken from x, y, .. . ), a constant (taken from a, b, ... ) or a functional expression with one argument of the form Ci ( t), ("the ith correlate of t") where i is an integer and t is an index term.

This language can be used to specify temporal knowl­ edge in the form of a conjunction of assertions about n-interval relations expressed in the form IOPt,t'~,jJ, where I and J designate n-intervals, t and t' are i-terms and OP E {E, t, II, fi:, n, 0, e, €>}. This set will be called OPS. The set of all n-interval relations which are the extensions of relational predicates of the form OPt,t'~.i will be included in a set called NCR. Finally, in the sentence of the form "I OPt,t' R J", we call t the "I i-term", and t' the "J i-term".

The interpretation of single sentences in NRL con­ taining the basic operators are provided by the following translations into first order logic. It is assumed that I is an X-interval and J is an ¥-interval and 1 < x <X and 1 ~ y ~ Y, and that ~ E ACR. J1. and v ;tand for variables, c(JJ.) is a functional expression whose meaning can be expressed as "The correlate of Jl." , and J1. 1 is a constant index term. "COR(JJ., v)" is true of correlated intervals.

• IIIc(v),v{Rl, ... ,Rk}J iff Vv3J1., COR(JJ., v) 1\ I~'{R1, ... , Rk}Jv. (always)

Restricting extensions of relational predicates in NRL to correlated intervals represents the tendency in discourse to restrict attention to correlated events. For example, if one says "faculty meetings sometimes precede cock­ tails", one usually intends to express a relation between a faculty meeting and the single happy hour in closest proximity following the meeting. The close proximity between the two occurrences is typically necessary and sufficient to establish their correlation.

I-terms are used to express both correlation and co­ designation. The latter is depicted by co-indexing, i.e., subscripting with the same term. For example, let GoingToWork, Calling, Meetings, Seminars, and Lunches each denote n-intervals associated with the re­ curring events going to work, calling one's dad, meetings, seminars, and lunches, respectively. Then 1-3 above can be regimented as follows:

1. GoingToWork sometimesa,b before Calling. Calling sometimesb,c overlaps Meeting.
2. GoingToWork sometimesa,b before Calling. Calling sometimesc,d before GoingTo Work.
3. Meetings sometimesa,b precede Seminars. Meet­ ings sometimesa,c overlap Lunches.

In specifying relations involving "always", as in "I al­ ways before J" , the I i-term needs to be indexed, since it may be necessary to refer later to either "the same I" or "some other I" (i.e., other than the ones related to J). On the other hand, the J i-term can be a variable, since every J is after I, and therefore there won't be a need to speak of "other Js". To make this distinction, we introduced the functional expression "c;(t)", indicat­ ing a functional relationship to the variable i-term; e.g. Ilc,(x) ,x . The case of "only" is the dual of "always"; here, the J variable needs to be indexed. Finally, the case of "always and only" can be handled with only variables. 6

Finally, the meaning of assertions involving the nega­ tion of a basic operator is captured using the notion of the complement of a relation. The complement of an el­ ement of CR, R (R'), is ACR -R. Thus, "never-R" is "always-R', and "not-always-R" is "sometimes-R"', etc. For example, to say that "Dinners never precede, meet, or overlap cocktails" is to say "Dinners always do any­ thing but precede meet, or overlap cocktails".

4 An N-interval Algebra

In this section, a set of operations for manipulating a specification written in NRL is defined. First, a set of operations for an n-interval relation algebra is defined, specifically, the operations of inverse, intersection and composition. Secondly, rules governing substitution of i-terms are briefly discussed.

An algebra is a set together with one or more oper­ ations on that set, where the set is closed under those operations. The operations to be defined on NCR are inverse, composition, and intersection. These operations allow for the formalization of the reasoning tasks m­ volved in evaluating specifications.

First, the proper definition of intersection on n­ interval relations requires the introduction of a form of conjunction of relations. To see this, consider contexts involving "always-R" and "sometimes-S''. For exam­ ple, compare "Dinners sometimes end or overlap with speeches", with "Dinners always end with speeches; the latter is a refinement of the former. On the other hand, the case involving the pair "Dinners always end or over­ lap with speeches" and "Dinners sometimes end with or are met by speeches" is more complicated: there is added information in the latter assertion that can't be completely refined. The Ef) operator is introduced to ex­ press what in English is expressed by "and furthermore"; the result of intersection in this example is "Dinners al­ ways end or overlap with speeches and furthermore they sometimes end with speeches" .

6 The reader will have noticed the similarity between the functional index and conventions for eliminating existential quantification in the process of producing clausal forms for first-order sentences, when the existential quantifier is in the scope of a universal quantifier.

Definition 5. (N-Interval Algebra) NCR is the under­ lying set for an N -interval algebra. It consists, first, of 4 x 2 13 basic relations that result from applying one of four operators E, II, 0, e to one element in CR. Secondly, if OPE {II,O,e}, R,S1, ... SJ: E CR and S; C R, and S; n Si = 0 for all i,j = 1 .. . k, then NCR contains the relation 0 P( R) Ef) E( Sl) Ef) ·· · Ef) E( SJ:).

By generalizing the Ef) operator in this way, n-interval relations can be defined which are sucessive refinements of other n-interval relations. For example, "Always be­ fore or meets or after and (furthermore) sometimes meets and (furthermore) sometimes before" is more specific than "Always before or meets or after and (furthermore) sometimes meets".

The operators defined on this set are inverse, intersec­ tion and composition. Due to space limitations, atten­ tion is restricted to defining these operations on basic relations. Extending the definitions to fit the case of re­ lations defined using the Ef) operator is straight forward, but somewhat tedious.

First, generalizing the notion of inverse to n-interval relations is straight forward. When R is in CR we have:

For example, if cocktails always follow or meet faculty meetings, then faculty meetings only precede or are met by cocktails.

Intersection is defined among members of NCR of the form OPt,t'R and OP;,t,S; Table 1 contains rules govern­ ing intersection. We use n to distinguish n-interval rela­ tion intersection from convex relation intersection (n).

1. II(R)ne(S) 2. O(R) n e(S) 3. O(R) n II(S) 4. II(R) n II(S) 5. O(R) n O(S) 6. E(R) n E(S) 7. e(R) n e(s) 8. e(R) n E(S) e(Rn S); e(R n S); e(Rn S); II(R n S); O(RnS); E(RnS); e(R n S); { e(R) ~(R) EB E(R n S) if R c;;_ S; if Rn s = 0; otherwise

Table 1. Intersection of N -interval relations

The rules collectively expresses the fact that "always and only" is as specific or more specific than "only" , "some­ times" or "always". For example, to say that dinners always follow cocktails is more specific than to say that they sometimes do. Similarly, to say that they always and only follow cocktails is more specific than to say that they always do.

Table 2 defines composition between non-convex inter­ val relations of the form OPt,t'R and OP;,,t,S, where R and S are in CR, and OPE OPS. For example, if I is always and only (e) before J and J always (IT) starts I<, then using composition one infers that I is always and only before (before-convex-composed-with-starts) ](.

As noted above, negation operates on each of the four basic non-convex relation operators to form new oper­ ators. Because negation can be defined in terms of re­ lation complement, contexts involving them can be re­ duced to contexts without them. Hence, the operations defined in this section can be applied to all members of OPS .

Finally, in order for a reasoner to effectively apply these operations on relations in NRL, it is necessary to define rules for i-term substitution. We do this infor­ mally. In general, i-term substitution is applied to two pairs of i-terms T and T', and occurs prior to perform­ ing either intersection or composition. First, any i-term can be substituted (uniformly within a pair) for a vari­ able i-term. In the case of intersection, if one i-term in T is the result of a substitution with another i-term in T', then restrictions on correlation relationships con­ strain the value of the other i-term in T to be identical to value of the other i-term in T'. For example, intersection can be performed on relations llc,(x),xb and Ea,cb, m, by making the appropriate substitutions; the result of the intersection is the refinement Ilc,(x),xb. In the case of composition between OPt ,t'R and OP;",t"'· for the re­ sult to be defined it is necessary either that t' and t" be the same term, or that one of them is a variable. The examples in the next section provide other illustrations of the substitution process.

5 Consistency In N-interval Networks

A knowledge ba,se of assertions about n-intervals can be represented as a network of binary relations defined as follows:

Definition 6. A N -interval relation network (NRN) is a network of binary relations whose variables (nodes) represent n-intervals and whose arcs link pairs of nodes. The arcs are labeled with a single element of NCR. Example 1. I always Overlaps J. J sometimes occurs before K. K always meets L. L is sometimes before I. The NRN representation is found in Figure 1 7 . The figure shows the edges added as the result of composition involving nodes I, J, and ]( and K, L and J . The

knowledge base is consistent.

Example 2. I is sometimes during J. Some (other) times, I meets J. The same J sometimes occurs before ](. ]( is never after I. The network representation is found in Figure 2. The knowledge base is inconsistent. Composition will establish that I is sometimes before ](; but taking the inverse of the arc between ]( and I will establish that I should never be before ](.

Determining path consistency for NRN networks in­ volves:

7 Not all the information has been represented; for exam­ ple, the inverse relation between J and I (only overlapped by) has not been represented. In addition, pairs of n-intervals for which no initial relation has been specified (e.g. between I and K) can be joined by an arc indicating this fact . Let ACR be the set of all atomic Allen relations; then complete lack of information in an n-interval network can be depicted by the relation l;'E,.,yACR;,jlj. (In English: some part of!; has some temporal relation to some part of J 1 ).

1. Possible additions to the number of apparent edges in the network as the result of composition; hence
2. Dealing with possibly multiple arcs between the same two vertices; (i.e., an NRN is a multigraph); and
3. Two kinds of relation composition (0 and o), inter­ section, inverse, complement, and i-term substitu­ tion.

For an n-interval relation network, the worst-case behav­ ior of a path consistency algorithm is determined by both the number of nodes and the number of edges, both the edges initially specified, and those added as the result of composition. The latter can be estimated by consider­ ing the number of distinct values of x and y among the xy-relations, as the following proof sketch demonstrates. Theorem. Path consistency for NRN networks can be determined in O(k 3 m 3 ) time, where k is the number of distinct values of initial xy-indices, and m is the number of nodes in the network.

Proof (sketch) : In an m-node NRN there are m(m-1)/2 pairs of nodes. For each pair (I, J) there are up to O(k 2 ) distinct xy-indexed temporal relations (arcs) from I to J . Given a node pair (I, J) and an arc A from I to J there are m-2 intermediate nodes K where composition can be used to form an alternate path of length 2 from I to J . For this node K there are up to a maximum of k edges from I to K that could qualify for composition. Since the composition operation itself has constant time complexity, the time complexity of the path consistency algorithm on an NRN is O(k 3 m 3 ).

Contrasting this result with the complexity of path consistency for convex interval networks ( 0( m 3 ) [Van Beek, 1990]) , it should be noted that because cluster­ ing of convex intervals is involved, there will in general be fewer variables in an NRN than in a convex interval network. In addition, k will tend to be small in practice.

6 Related Work

The research presented here extends current efforts in developing interval-based systems for reasoning about time by allowing for an explicit representation of inter­ vals with gaps. The purpose of this extension is to ex­ pand the set of properties and relations that can be at­ tributed to periods of time for applications such as static scheduling, natural language processing, and temporal database querying.

The impetus for this work was provided by Peter Lad­ kin's initial discussion [Ladkin, 1986], and by advances made by Ligozat [Ligozat, 1990]. Our work, as noted, has been also inspired by the success of constraint-based approaches to time [Mehri, 1991]. Finally, we were moti­ vated in part by issues raised and discussed in [Koomen, 1989] which led to similar ideas of clustering intervals and their relations as a heuristic to aid in the reasoning process. The results here should also be compared to ear­ lier work by two of the authors [Morris and Al-Khatib, 1991].

7 Summary

The problem of reasoning about certain kinds of incom­ plete knowledge about time was discussed. The mecha­ nism chosen for the solution uses a non-convex interval representation, and a class of non-convex relations con­ structed by considering only groups of correlated convex intervals within a single temporal block. It was demon­ strated that path consistency techniques can be applied to problem solving involving networks of n-interval rela­ tions.