A Spatial Odyssey of the Interval Algebra: 1. Directed Intervals

1 Introduction

Qualitative spatial representation and reasoning has become more and more important in recent years. The best-known approach in this field is the Region Connection Calculus CABVBVBK [Randell et al., 1992] which describes topological relationships between D2-dimensional spatial regions of arbitrary shape. For some applications, however, it is sufficient to use spatial regions with more restricted properties. The block algebra [Balbiani et al., 1999], for instance, considers only spatial regions which are D2-dimensional blocks whose sides are parallel to the defining axes. The most restricted spatial regions are (one-dimensional) intervals. A prototypical spatial application of intervals are traffic scenarios. Vehicles usually move only along given ways (also sea-/airways). Therefore, when looking at vehicles on one particular way, vehicles and their regions of influence (such as safety margin, braking distance, or reaction distance) could be represented as intervals on a line which represents the possibly winded way. Similar to the well-known Interval Algebra [Allen, 1983] developed for temporal intervals, it seems useful to develop a spatial interval algebra for spatial intervals.

A3 This research was carried out while the author was visiting the Department of Computer and Information Science at the University of Link¨oping, Sweden. Supported by the Wallenberg foundation as part of the WITAS project. Thanks to Patrick Doherty, Guy Even, Alfonso Gerevini, and Erik Sandewall for their comments.

There are several differences between spatial and temporal intervals which have to be considered when extending the Interval Algebra towards dealing with spatial applications. (1) spatial intervals can have different directions, either the same or the opposite direction as the underlying line. (2) ways usually have more than one lane where vehicles can move, i.e., it should be possible to represent that intervals are on different lanes and that one interval is, e.g., left of, right of, or beside another interval. (3) it is interesting to represent intervals on way networks instead of considering just isolated ways. (4) intervals such as those corresponding to regions of influence often depend on the speed of vehicles, i.e., it should be possible to represent dynamic information. This is also necessary for predicting future positions of vehicles which is an important task in traffic control. As for temporal intervals it is also important to represent qualitative or metric information on the length of intervals and on the distance between intervals.

We start this spatial odyssey of the Interval Algebra by analyzing the first important difference between spatial and temporal intervals, namely, direction of intervals. We define the directed intervals algebra which consists of 26 jointly exhaustive and pairwise disjoint base relations, identify tractable subsets, and show that path-consistency decides consistency for a particular subset which contains all base relations.

2 Directed Intervals

The Interval Algebra (
BT) describes the possible relationships between convex intervals on a directed line. The default application of the Interval Algebra is temporal, so the directed line is usually considered to be the timeline. The 13
BT base relations (before AU, after AV, meets D1, met-by D1CX, overlaps D3, overlapped-by D3CX, equals AH, during CS, includes CSCX, starts D7, started-by D7CX, finishes CU, and finished-by AC) describe a combination of topological relations (disconnected, externally connected, partial overlap, equal, non-tangential proper part, tangential proper part, and the converse of the latter two) and order relations (BO,BQ). The topological distinctions are exactly those which are made by CABVBVBK. Therefore, CABVBVBK is often considered as the spatial counterpart of the Interval Algebra. Or, from another point of view, what distinguishes the Interval Algebra from CABVBVBK and what makes it its key feature is the given direction of the (one-dimensional) line. This given direction naturally imposes a direction also on the intervals: an interval can have the same or the opposite direction as the underlying line. However, because of its original temporal interpretation (no event can end before it starts), direction of intervals has never been considered in AI. Actually, directed intervals have been studied in the large field of Interval Arithmetics, but work in this field is completely different from the qualitative and constraint-based approaches studied in AI. When using the Interval Algebra for spatial applications, direction of intervals has to be taken into account. This leads to the obvious question: can the large body of work and the large number of results obtained on the Interval Algebra such as algorithms and complexity results also be applied to a spatial interpretation of the Interval Algebra, or is it necessary to completely start from scratch again?

Before answering this question, consider the example of Figure 1 which illustrates the differences of having directed intervals from having only intervals of the same direction. Since all four combinations of the directions of the two intervals are possible, there are four structurally different instantiations of every relation instead of just one. Therefore, it is possible that inconsistent instances of the Interval Algebra become consistent when allowing directed intervals.

3 The Directed Intervals Algebra

A straightforward way for dealing with directed intervals would be to add additional constraints on the direction of intervals to constraints over the Interval Algebra and treat the two types of constraints separately while propagating information from one type to the other (similar to what has been done in [Gerevini and Renz, 1998].) We say that an interval has positive direction if it has the same direction as the underlying line and negative direction otherwise. So possible direction constraints could be unary constraints like "DC has positive/negative direction" or binary constraints like "DC and DD have the same/opposite direction". This approach, however, is not possible since the Interval Algebra loses its property of being a relation algebra when permitting directed intervals. This can be easily seen when considering the "behind" relation of Figure 1. The converse of "DC behind DD" is "DD is behind or in front of DC", whose converse is "DC is behind or in front of DD", i.e., applying the converse operation (A1 CM ) twice leads to a different relation than the original relation. This is a contradiction to one of the requirements of relation algebras (CA CMCM BP CA) [Ladkin and Maddux, 1994]. This contradiction does not occur when we refine the "behind" relation into two disjoint sub-relations "behind BP " and "behind BIBP " where the subscript indicates that both intervals have the same (BP) or opposite (BIBP) direction. The converse of both relations is "in-front-of BP " and "behind BIBP ", respectively. Applying the Since a relation algebra must be closed under composition, intersection, and converse, we have to make the same distinction also for all other
BT relations. This leads us to the definition of the directed intervals algebra (DIA). It consists of the 26 base relations given in Table 1, which result from refining each
BT relation into two sub-relations specifying either same or opposite direction of the involved intervals, and of all possible unions of the base relations. This gives a total number of BE BEBI BW
BT relations. Converse relations are given in the same table entry. If a converse relation is not explicitly given, the corresponding relation is its own converse. We denote the set of 26 BW
BT base relations as BU. Then BW
BT BP BE BU . Complex relations which are the union of more than one base relation CA BD BN BM BM BM BN CA CZ are written as CUCA BD BN BM BM BM BN CA CZ CV. The union of all base relations, the universal relation, is denoted CUA3CV.

A BW
BT base relation CA BP
CS consist of two parts, the interval part
which is a spatial interpretation of the Interval Algebra and the direction part CS which gives the mutual direction of both intervals, either BP or BIBP. If a complex relation CA consist of base relations with the same direction part CS, we can combine the interval parts and write CA BP CU
BD BN BM BM BM BN
CZ CV CS instead of CA BP CU
BD CS BN BM BM BM BN
CZ CS CV. We write CA CT (resp. CA D2 ) in order to refer to the union of the interval parts of every subrelation of a complex relation CA where the direction part is CUBPCV (resp. CUBIBPCV.) In this way, every BW
BT relation CA can be written as CA BP CUCA CT CV BP CJCUCA D2 CV BIBP . BW
BT
denotes the set of BE BDBF possible interval parts of BW
BT relations.

It is important to note that the spatial interpretation of the Interval Algebra was chosen in a way that the interval part of a relation DC
CS DD only depends on the direction of DD and not on the direction of DC. Therefore, if the direction of DC is reversed, written as DC, then only the direction part changes, i.e., DC
CS DD BP DC
BMCS DD. This would not be the case in a straightforward spatial interpretation of the original temporal relations. For instance,
BT relations like "DC started-by DD" or "DC finished-by DD" depend on the direction of DC. Instead, we interpret these relations spatially as "DC extends-the-front/back-of DD" and "DC contained-in-the-front/back-of DD". This interpretation is independent of the direction of DC. When all intervals have the same direction, both interpretations are equivalent. In order to transform the spatial and the temporal interval relations (independent of the direction of the intervals) into each other, we introduce two mutually inverse functions CSCXCP BM
BT BJAX BW
BT
and CXCP BM BW
BT
BJAX
BT, i.e., CSCXCPB4CXCPB4CAB5B5 BP CA and CXCPB4CSCXCPB4CAB5B5 BP CA. The mapping is given in Table 2.

All relations of the directed intervals algebra are invariant with respect to the direction of the underlying line, i.e., when reversing the direction of the line, all relations remain the same. This is obviously not the case for the Interval Algebra, e.g., if DC is before DD and one reverses the direction of the timeline, then DC is after DD. In order to transform BW
BT relations into the corresponding
BT relations and vice versa, we introduce a unary reverse operator (A1 D6 ) on relations CA such that CA D6 specifies the relation which results from CA when reversing the direction of the underlying line. For all relations CA BE BW
BT we have that CA D6 BP CA. For
BT relations, the reverse relation is given in Table 2. The reverse of a complex relation is the union of the reverses of the involved base relations. The reverse of the composition (Æ) of two relations is equivalent to the composition of the reverses of the two involved relations, i.e., B4CAÆCBB5 D6 BP CA D6 ÆCB D6 . Applying the reverse operator twice results in the original relation, i.e., CA D6D6 BP CA. Using the reverse operator we can also specify what happens with a relation DC
CS DD if only the direction of DD is changed. Then the topological relation of the intervals stays the same, but the order changes, i.e., "front" becomes "behind"/"back" and vice versa. The mutual direction also changes. This can be expressed in the following way: DC
CS DD BP DC CSCXCPB4CXCPB4
B5 D6 B5 BMCS DD.

We now have all requirements for computing the composition (Æ) of BW
BT relations using composition of
BT relations (denoted here by Æ CXCP ) as specified by Allen [1983].

Theorem 3.1 Let CA D4 BN CB D5 be BW
BT base relations.

1. If D5 BP CUBPCV, then CA D4 Æ CB D5 BP CSCXCPB4CXCPB4CAB5 Æ CXCP CXCPB4CBB5B5 D4
2. If D5 BP CUBIBPCV, then CA D4 Æ CB D5 BP CSCXCPB4CXCPB4CAB5 D6 Æ CXCP CXCPB4CBB5B5 BMD4

Proof. Assume that DCCA D4 DD and DDCB D5 DE holds. If D4 BP D5 BP CUBPCV and DCBN DDBN DE have positive direction, it is clear that the interval part of the composition of the BW
BT relations is the same as the composition of the
BT relations (with respect to the different interpretations.) The result of the composition is the same if DCBN DDBN DE have negative direction, since BW
BT relations are invariant with respect to the direction of the underlying line. CA only depends on the direction of DD and CB only depends on the direction of DE. Therefore, reversing the direction of DC (i.e., D4 BP CUBIBPCVBN D5 BP CUBPCV) does not change the result of the interval part of the composition, only the resulting direction part. This proves the first rule.

Assume that D4 BP D5 BP CUBIBPCV and DCBN DE have positive direction while DD has negative direction. If we reverse the direction of DD, which changes the relations to DCCSCXCPB4CXCPB4CAB5 D6 B5 BP DD and to DDCB BP DE, then we can apply the first composition rule. This results in CA BIBP Æ CB BIBP BP CSCXCPB4CXCPB4CAB5 D6 B5 BP Æ CB BP BP B4BDBMB5 CSCXCPB4CXCPB4CSCXCPB4CXCPB4CAB5 D6 B5B5 Æ CXCP CXCPB4CBB5B5 BP BP CSCXCPB4CXCPB4CAB5 D6 Æ CXCP CXCPB4CBB5B5 BP , the second composition rule. As in the first case, this rule does not change when we reverse the direction of DC (i.e., D4 BP CUBPCVBN D5 BP CUBIBPCV) or the direction of all three intervals. This proves the second rule.

The composition of complex relations is as usual the union of the composition of the contained base relations. It follows from the closedness of the Interval Algebra that BW
BT is closed under composition, intersection, converse, and reverse.

4 Reasoning over Directed Intervals

The main reasoning problem in spatial and temporal reasoning is the consistency problemCSPSAT(CB) where CB is a set of relations over a relation algebra [Renz and Nebel, 1999].

Instance: A set CE of variables over a domain BW and a finite set A2 of binary constraints DCCADD (CA BE CB and DCBN DD BE CE .)

Question: Is there a consistent instantiation of all D2variables in A2 with values from BW which satisfies all constraints?

The consistency problem of the directed intervals algebra, CSPSAT(DIA), is clearly NP-hard since the consistency problem of the Interval Algebra is already NP-hard. On the other hand it is not clear whether the consistency problem is tractable if only the BW
BT base relations are used.

Additional to the BW
BT relations, we also give the possibility of explicitly specifying the direction of intervals. We maintain them in a set A1 which contains unary direction constraints of the form B4DCBN CSB5 where DC is a variable over a directed interval and CS AI CUB7BN A0CV gives the direction of DC, either positive CUB7CV, negative CUA0CV, or indefinite CUB7BN A0CV. Unary direction constraints and BW
BT constraints interact in two ways.

Proposition 4.1 Given two intervals DCBN DD, the BW
BT constraint DCCADD with CA BP CUCA BD D1 BD BN BM BM BM BN CA CZ D1 CZ CV, and the unary direction constraints B4DCBN CS BD B5 and B4DDBN CS BE B5. These constraints interact in the following way:

1. If all D1 CX (CX BP BD BM BM BM CZ) are equivalent, then (a) CS BD BP CS BD CK CS BE and CS BE BP CS BD CKCS BE if D1 BD BP CUBPCV and (b) CS BD BP CS BD CKBMCS BE and CS BE BP BMCS BD CK CS BE if D1 BD BP CUBIBPCV.
2. If CS BD and CS BE are both definite, then (a) CA BP CUCA CT CV BP if CS BD BP CS BE and (b) CA BP CUCA D2 CV BIBP if CS BD BIBP CS BE .

If all information is propagated from A2 to A1 and from A1 to A2 we write the resulting sets as A2 A1 and A1 A2 . If the empty constraint occurs during this propagation, then A2 is inconsistent.

There are several ways of deciding consistency of a given set of constraints over a set of relations CB. The most common way is to use backtracking over a tractable subset of CB which contains all base relations and enforce path-consistency as forward-checking (this is done by applying for each triple of constraints DCCADD, DDCBDE, DCCCDE the operation CC BMBP CC CK B4CA Æ CBB5; if the empty relation is not contained, the resulting set is pathconsistent) [Ladkin and Reinefeld, 1997]. Before we can use this method for deciding CSPSAT(DIA), we must prove that the consistency problem is tractable for the BW
BT base relations and preferably that path-consistency decides consistency for these relations. In order to prove this, we need a different method for deciding consistency and we have to show that this method is polynomial for the set of BW
BT base relations.

For the Interval Algebra most tractability proofs were carried out using the endpoint encoding of the
BT relations (e.g. [Nebel and B¨urckert, 1995]) which describes the qualitative relations between the four endpoints of the two involved intervals. For instance, the "before" relation can be encoded as CG CT BO CH D7 plus the default relations CG D7 BO CG CT and CH D7 BO CH CT which hold for all non-directed intervals (CG D7 BN CH D7 denote the start points and CG CT BN CH CT the end points of the intervals CGBN CH .) It is also possible to specify an endpoint encoding of the BW
BT relations. Since spatial intervals can have different directions, the default relations do not hold anymore. Furthermore, we have to take into consideration that BW
BT relations are invariant with respect to the reverse operation. Therefore, it is the most compact way to use the "betweenness" predicate for specifying an endpoint encoding of BW
BT relations. CQCTD8DBCTCTD2B4CG CT BNCG D7 BN CH D7 B5 means that CG D7 is between CG CT and CH D7 , no matter which direction the intervals have. Using this predicate, the relation CQ BIBP , for instance, can be encoded as CQCTD8DBCTCTD2B4CG D7 BN CH D7 BN CH CT B5 CM CQCTD8DBCTCTD2B4CG CT BNCG D7 BN CH D7 B5. Since the BETWEENNESS problem is NP-hard [Garey and Johnson, 1979], this encoding does not seem to be helpful for proving any tractability results. We will therefore refrain from specifying the endpoint formulas of the BW
BT base relations.

Another possibility of deciding the BW
BT consistency problem is to transform a set of BW
BT constraints A2 into an equivalent set of
BT constraints A2 BC and decide consistency of A2 BC . In order to make such a transformation, the direction of every interval must be known. Then it is possible to reverse the direction of certain intervals such that all intervals have the same direction and transform the updated BW
BT constraints into
BT constraints. We call this the normal form of a set of BW
BT constraints A2 and a set of definite unary direction constraints A1 for each interval involved in A2. The normal form (written as D2CUB4A2BNA1B5) is obtained as follows.

Proposition 4.2 Given a set of BW
BT constraints A2 and a set A1 of definite unary direction constraints for each interval involved in A2. The normal form D2CUB4A2BN A1B5 is obtained by applying the following procedure.

1. For each constraint DCCA CS DD BE A2 A1 do
2. If DD has negative direction, add DC CXCPB4CAB5 D6 DD to D2CUB4A2BN A1B5
3. If DD has positive direction, add DC CXCPB4CAB5 DD to D2CUB4A2BN A1B5

Lemma 4.3 Given a set of BW
BT constraints A2 and a set A1 of definite unary direction constraints for each interval involved in A2. D2CUB4A2BN A1B5 can be computed in time B4D2 BE B5.

Proof. A2 A1 can be computed in time B4D2 BE B5, since all constraints of A1 are definite and information has to be propagated only from every pair of intervals to the corresponding constraint in A2 using rule 2 of Proposition 4.1. A2 A1 is transformed to D2CUB4A2BNA1B5 in time B4D2 BE B5, since each of the B4D2 BE B5 constraints is transformed separately in constant time.

Lemma 4.4 Given a set of BW
BT constraints A2 and a set A1 of definite unary direction constraints for each interval involved in A2. A2 A1 is consistent if and only if D2CUB4A2BNA1B5 is consistent.

Proof. Suppose that A2 A1 is consistent and that
is an instantiation of A2 A1 . The direction of each interval of
is as specified in A1 and the relation between each pair of intervals DCBN DD is a base relation CA BC CS which is a sub-relation of DCCA CS DD BE A2 A1 . We can now reverse the direction of all intervals of
with negative directions, resulting in
B7 . Since all BW
BT relations DCCADD only depend on the direction of DD, the relations between the intervals of
B7 are now DC CSCXCPB4CXCPB4CA BC B5 D6 B5 BP DD if the direction of DD was negative in
and DCCA BC BP DD if the direction of DD was positive in
. Transforming these relations into
BT relations results for every pair of intervals in sub-relations of D2CUB4A2BN A1B5. Thus,
B7 is a consistent instantiation of D2CUB4A2BN A1B5. The opposite direction can be proved similarly. Suppose that D2CUB4A2BN A1B5 is consistent and that - is an instantiation of it where all intervals are considered to have positive direction. Let A2 B7 be the set of constraints between all intervals of - using BW
BT base relations. Reversing the direction of all intervals which must have negative direction according to A1 results in - A6 and adopting the constraints of A2 B7 results in A2 A6 . Since applying the reverse operator twice gives the original relation, each constraint of A2 A6 is a sub-constraint of a constraint of A2 A1 . Thus, - A6 is a consistent instantiation of A2 A1 .

Using the normal form, we can now decide consistency of a set of BW
BT constraints A2 by computing or guessing a set A1 containing the direction of all intervals, computing D2CUB4A2BN A1B5, and deciding consistency of D2CUB4A2BN A1B5 using the methods developed for the Interval Algebra. Since there are BE D2 different direction combinations of D2 directed intervals, it is in general -hard to find a suitable set A1 for which D2CUB4A2BNA1B5 is consistent or to show that there is no such set. If, however, we can show that for a given set CB of BW
BT relations all possible candidate sets A1 can be identified in polynomial time and if D2CUB4A2BNA1B5 contains only relations of a tractable subset of the Interval Algebra, then CSPSAT(CB) is tractable. Using this method, we identify several tractable subsets of the directed intervals algebra in the following section.

5 Tractable Subsets of BW
BT

The first set we analyze is the set of BW
BT base relations BU.

Lemma 5.1 CSPSAT(BU CJ CUA3CV) is tractable.

Proof. Consistency of a set A2 of constraints over BUCJCUA3CV can be decided in polynomial time by using the following steps.

1. TransformA2 into a graph BZ A2 BP B4CEBNBXB5 where CE is the set of variables involved in A2 and BX contains an (undirected) edge B4DCBN DDB5 if DCCADD BE A2 where CA BE BU.

1. Split CE into disjoint subsets CE BP CE BD CJBM BM BMCJCE CZ such that for each pair of variables DCBN DD BE CE CX there is a path from DC to DD in BX and for each pair of variables DC BE CE CX , DD BE CE CY (CX BIBP CY) there is no path from DC to DD in BX.
2. Generate a set of direction constraints A1 by selecting one variable DC CX for each CE CX and adding (DC CX BN CUB7CV) to A1.
3. Compute D2CUB4A2BNA1 A2 B5 and decide its consistency.

It is clear that each of the four steps can be computed in polynomial time. For each pair of variables of different sets CE CX BN CE CY there are only constraints involving the universal relation, i.e., A2B4CE CX B5 and A2B4CE CY B5 which specify subsets of A2 containing all constraints involving only variables of CE CX or CE CY , respectively, are completely independent of each other. There is a path fromeach variable of CE CX to every other variable of CE CX and each path consists of constraints where each constraint involves only BW
BT relations with the same direction part. Therefore, it is sufficient to have the direction of only one variable DC CX BE CE CX given in order to compute the direction of all variables DD BE CE CX . If the path contains an odd number of constraints involving BW
BT relations of the type CA BIBP , the direction of DD is opposite to the direction of DC CX . Otherwise they have the same direction. Thus, A1 A2 contains definite unary direction constraints for all variables of A2. If there are conflicting paths, then A1 A2 is inconsistent. Since BW
BT relations are invariant with respect to changing the direction of the underlying line, it does not matter for consistency purposes if we select the direction of DC as positive or negative. D2CUB4A2BNA1 A2 B5 contains only relations of a tractable subset of
BT. It follows fromLemma 4.4 that its consistency is equivalent to the consistency of A2.

In the above proof it is not important that all non-universal relations are base relations, only that all non-universal relations consist of BW
BT base relations with the same direction part. Therefore, we can easily extend the above result.

Theorem 5.2 Let CB be a tractable subset of the Interval Algebra which is closed under the reverse operator. Then CB A6 BP CUCSCXCPB4CAB5 BP CYCA BE CBCV CJ CUCSCXCPB4CAB5 BIBP CYCA BE CBCV CJ CUA3CV is a tractable subset of the directed intervals algebra.

Proof. We can apply the same proof as given for Lemma 5.1. But only if all
BT relations contained in the normal form are contained in a tractable subset of the Interval Algebra. This is clearly the case if CB is closed under the reverse operator which is used in the transformation into the normal form.

ORD-Horn (also denoted ) is the only maximal tractable subset of the Interval Algebra which contains all
BT base relations (and for which path-consistency decides consistency) [Nebel and B¨urckert, 1995]. Using a machine-assisted comparison of the ORD-Horn relations we found that they are closed under the reverse operator. This is not true for some of the maximal tractable subclasses identified in [Drakengren and Jonsson, 1998] which do not contain all
BT base relations.

All tractability results we have given so far rely on given mutual directions of intervals. For some applications this is a realistic assumption, but what happens if this is not given in all cases, if some constraints involve relations with different direction parts such as DCCUCQ BP BN CR BIBP BND1CQ BIBP CVDD? Assume that we have given a set A2 of constraints over arbitrary BW
BT relations.

One way of obtaining a possible candidate set A1 of definite unary directions for each interval in A2 is to look at each triple of variables B4DCBN DDBN DEB5 of A2 separately and check all BE BF different combinations of directions B4DC CS BN DD CS BN DE CS B5 of B4DCBN DDBN DEB5 (DC CS can be either B7 or A0). If enforcing path-consistency to the normal form gives the empty relation for a particular choice of B4DC CS BN DD CS BN DE CS B5, then this choice makes A2 inconsistent. If we combine all such inconsistent triples D8 CX BP CUB4DCBN DC CS B5BN B4DDBN DD CS B5BN B4DEBN DE CS B5CV, then A2 is inconsistent if A8 BP CF CX B4D0 DC CM D0 DD CM D0 DE B5 is satisfiable (D0 DC is a placeholder for BMDC CS if B4DCBN A0B5 BE D8 CX and for DC CS if B4DCBNB7B5 BE D8 CX , analogously for D0 DD and D0 DE .) A possible candidate set A1 can be obtained by computing a model of the complement of this formula, namely, A9 BP BMA8 BP CE CX B4BMD0 DC CN BMD0 DD CN BMD0 DE B5. This formula is an instance of 3SAT and, thus, -hard to compute. Eventually, since we did not propagate information between different triples, we have to check all possible models of A9.

Because of its  hardness, this way of generating a candidate set A1 does not seem to be helpful. However, we can show that it leads to a tractability proof for a restricted but interesting set of BW
BT relations, namely, those BW
BT relations BU BT which correspond to the set BT of 13 base relations of the Interval Algebra, i.e., BU BT BP CUCUCSCXCPB4CAB5 BP BN CSCXCPB4CAB5 BIBP CVCYCA BE BTCV.

Theorem 5.3 Let A2 be a set of BW
BT constraints over the variables DC BD BN BM BM BM BN DC D2 which contains a constraint DC CX CADC CY with CA BE BU BT if and only if CX BO CY. Consistency of A2 can be decided in polynomial time.

Proof. For each triple of variables DC CX BN DC CY BN DC CZ of A2 with CX BIBP CY BIBP CZBN CX BO CZ we check for all BE BF possible directions if the normal form of the triple is consistent or not. Depending on whether CX BO CY, either DC CX CADC CY or DC CY CADC CX is given in A2. Equivalently, either DC CY CBDC CZ or DC CZ CBDC CY is given in A2. Since CX BO CZ, DC CX CCDC CZ BE A2. Obviously, it is not possible that DC CY CADC CX and DC CZ CBDC CY are both in A2. Therefore, we compare in the normal form either (1) CA Æ CB, (2) CA CM Æ CB, or (3) CA Æ CB CM with CC in order to check consistency of the triple. In all three cases, the result is invariant with respect to the direction of one of the three variables and depends only on the direction of the other two variables. We can verify this using Table 3. In the first case, the only thing which changes in Table 3 when varying the direction of DC CX (which is DC CS in the table) are the subscripts of CA and CC : CA CT changes to CA D2 , CC CT changes to CC D2 and vice versa. Since all relations used in A2 are of the form CU
BP BN
BIBP CV,
CT and
D2 are always equivalent, i.e., the result of comparing CA Æ CB with CC is invariant with respect to the direction of DC CX . In the second case, the result is invariant with respect to the direction of DC CY (which is DD CS in the table.) When varying DD CS in the table, CB CT changes to CB D2 , CXCPB4CA CM CT B5 changes to CXCPB4CA CM D2 B5 D6 , and CXCPB4CA CM D2 B5 changes to CXCPB4CA CM CT B5 D6 and vice versa. Since CB CT is always equal to CB D2 , the change of CB does not change the result. The change of CA CM is more difficult. Using a case analysis of the 13 different cases, we were able to prove that CXCPB4CA CM CT B5 BP CXCPB4CA CM D2 B5 D6 and that CXCPB4CA CM D2 B5 BP CXCPB4CA CM CT B5 D6 if CA is of type CU
BP BN
BIBP CV. As an example consider the relation CA BP CUCQ BP BN CQ BIBP CV whose converse is CA CM BP CUCU BP BN CQ BIBP CV. CXCPB4CUB5 BP CUAVCV BP CXCPB4CQB5 D6 and CXCPB4CQB5 BP CUAUCV BP CXCPB4CUB5 D6 . In the third case, the result is invariant with respect to the direction of DC CX which can be proved equivalently to the first case.

Because consistency of every triple depends on the direction of only two of the three variables, the resulting formula A9 (see above) is an instance of 2SAT and, thus, solvable in polynomial time. For any model of A9, the resulting set A1 of unary direction constraints leads to a consistent normal form D2CUB4A2BNA1B5. This is because D2CUB4A2BNA1B5 contains only
BT base relations and because all triples are consistent (as it has been checked when A9 was generated.) Therefore, enforcing pathconsistency does not change any relation of D2CUB4A2BN A1B5.

Instead of transforming every set A2 of BW
BT constraints to the normal form in order to decide consistency, it would be nice to know if and for which sets of BW
BT relations pathconsistency is sufficient for deciding consistency when applied directly to A2. We show this for A6 , the set of BW
BT relations which results from ORD-Horn (see Theorem 5.2).

Theorem 5.4 Path-consistency decides CSPSAT( A6 ).

Proof. Consistency of a set A2 of BW
BT constraints over A6 can be decided in polynomial time by deciding consistency of its normal formA2 BC as it is obtained by applying the steps given in the proof of Lemma 5.1. Assume that A2 is path-consistent, i.e., for every triple of variables DCBN DDBN DE with DCCADDBN DDCBDEBN DCCC DE BE A2we have that CC AI CAÆCB. If A2 BC is also path-consistent, then A2 is consistent. In order to show that A2 BC is path-consistent, we have to show that CC AI CAÆCB implies CC BC AI CA BC Æ CXCP CB BC for all triples DCBN DDBN DE (DCCA BC DDBN DDCB BC DEBN DCCC BC DE BE A2 BC .) Since all relations of A6 consist of BW
BT base relations with the same direction part, we can extend the composition rules given in Theorem 3.1 to all A6 relations. According to these rules, CC AI CA Æ CB can be written as either CC BIBP AI CSCXCPB4CXCPB4CA CT B5 D6 Æ CXCP CXCPB4CB D2 B5B5 BIBP , CC BIBP AI CSCXCPB4CXCPB4CA D2 B5 Æ CXCP CXCPB4CB CT B5B5 BIBP , CC BP AI CSCXCPB4CXCPB4CA D2 B5 D6 Æ CXCP CXCPB4CB D2 B5B5 BP , or CC BP AI CSCXCPB4CXCPB4CA CT B5 Æ CXCP CXCPB4CB CT B5B5 BP depending on the directions of DCBN DDBN DE. The corresponding restrictions of CC BC can be derived using Table 3. If DE CS BP CUB7CV, the restrictions of CC BC are equivalent to the results of applying CXCP to the interval parts of the above given restrictions of CC. If DE CS BP CUA0CV, we have to reverse CC and the restrictions of CC . Since B4CDÆ CXCP CE B5 D6 BP CD D6 Æ CXCP CE D6 and CD D6D6 BP CD for all
BT relations CDBN CE , the restrictions of CC BC are also equivalent to the results of applying CXCP to the interval parts of the restrictions of CC (e.g. the first restriction B4CXCPB4CA CT B5 D6 Æ CXCP CXCPB4CB D2 B5B5 D6 BP CXCPB4CA CT B5 Æ CXCP CXCPB4CB D2 B5 D6 is the same as line 2 in Table 3.) Thus, CC AI CAÆ CB implies CC BC AI CA BC Æ CXCP CB BC .

This result enables us to decide consistency of arbitrary sets A2 of BW
BT constraints by backtracking over the A6 relations and by using path-consistency as a forward-checking method and as a decision procedure for sub-instances of A2 which contain only relations of A6 .

6 Discussion &Future Work

We extended the Interval Algebra for dealing with directed intervals which occur when interpreting intervals as spatial instead of temporal entities. Reasoning over the directed intervals algebra BW
BT is more difficult than over the Interval Algebra
BT, but it is possible to transform a set of BW
BT constraints into an equivalent set of
BT constraints if the mutual directions of all intervals are known. This enabled us to transfer some tractability results from
BT to BW
BT. If the mutual directions are not known, a tractable subset of BW
BT can be identified if two potentially exponential nested problems can be shown to be tractable for the subset: (a) compute a set of mutual directions and (b) decide consistency of the resulting set of constraints. We proved this for a small but interesting subset of BW
BT, but the problem is mostly open. Consequently, no maximal tractable subset of BW
BT has been identified so far.

BW
BT can also be used instead of
BT as a basis for defining a block algebra [Balbiani et al., 1999]. Then it is possible to reason about D2-dimensional blocks with intrinsic directions. Remotely related to directed intervals are line segments with arbitrary directions which were analyzed by Moratz [2000].

The spatial odyssey of the Interval Algebra is to be continued as follows: (1) extend BW
BT to deal with intervals on parallel lines and on networks of lines, (2) add qualitative and metric information on the length of intervals and on the distance between intervals, and finally (3) extend the algebra to deal with dynamic instead of just static information, e.g., intervals move on lines with a certain velocity and sometimes switch to accessible lines. These are the desired properties of a calculus for representing and reasoning about traffic scenarios, a prototypical application of spatial intervals. Hopefully, contact with applications will be made before 2010...