In the last two decades, qualitative formalisms suited to express qualitative temporal (e.g. : Freksa, C., 1992a) and spatial relationships (e.g. : Randell, D., Cui, Z., and Cohn, A.G., 1992) between entities have gained wide acceptance as a useful way of abstracting from the real world. Only in recent years, attention has been extended to applications that involve spatio-temporal data. Nevertheless, a variety of research communities have been studying movements of objects, e.g.: Wolfson, O., Xu, B., Chamberlain, S., and Jiang, L., 1998;Erwig, M., Güting, R.H., Schneider, M., and Vazirgiannis, M., 1999;Fernyhough, J.H., Cohn, A.G., and Hogg, D.C., 2000;Nabil, M., Ngu A., and Shepherd A.J., 2001;Pfoser, D., 2002. Until now, the spatiotemporal community has paid little attention to the qualitative aspects.
Apart from some limiting cases, such as a car accident and a predator catching a prey, where moving objects meet, mobile objects are represented by the relation disjoint in calculi defining topological relations, such as RCC (Randell, D., Cui, Z., and Cohn, A.G., 1992). This approach ignores some important aspects of reasoning about continuously moving physical objects. For example, given two trains on a railroad, it is of the utmost importance to know their movement with respect to each other, in order to detect whether or not they could crash in the near future. Thus, the inherent property with topological theories is that they put all disjoint relations into one undifferentiated set. Therefore, a challenging question remained largely unaddressed: 'How do we handle changes in movement between moving objects, if there is no change in their topological relationship?' With this in mind, and starting from the idea that the enormous complexity of interacting real world objects can be described by the relations between pairs of interacting point objects being constantly disjoint, the Qualitative Trajectory Calculus (QTC) was introduced by Van de Weghe Van de Weghe, N., 2004). QTC is a theory for representing and reasoning about movements of objects in a qualitative framework, able to differentiate between groups of disconnected objects. Depending on the level of detail and the number of spatial dimensions, different types of QTC were defined all belonging to QTC-Basic (QTC B ) (
) or QTC-Double Cross (QTC B Van de Weghe, N., Cohn, A.G., De Tré, B., and De Maeyer, Ph., 2006 C ) ( ). The reasoning power of QTC has been worked out, applying important reasoning techniques, such as conceptual neighbourhood diagrams (
) and composition tables ( ). In this paper, the focus is on the feasibility of QTC Van de Weghe, N., Cohn, A.G., De Maeyer, Ph., and Witlox, F., 2005 Van de Weghe, N. and De Maeyer, Ph., 2005 Van de Weghe, N., Kuijpers, B., Bogaert, P., and De Maeyer, Ph., 2005 B B to handle incomplete knowledge1 . Without elaborating on the domain of linguistics, we show that QTC B is well-fitted to represent spatio-temporal natural language.
B After an explanation of incomplete knowledge and how it is related to qualitative reasoning, a brief overview of QTC B is presented. Section 4 presents illustrative examples on how to handle incomplete knowledge within the different types of QTC B B B . Section 5 concludes the paper and gives some directions for further research.
Reasoning can be performed on quantitative as well as on qualitative information. According to Goyal (Goyal, R.K., 2000), a predefined unit of a quantity is used, typically when working with quantitative information. In the qualitative approach, continuous information is discretised by landmarks separating neighbouring open intervals, resulting in discrete quantity spaces (Weld, D.S. and de Kleer, J., 1990). The major idea in the qualitative approach is that only relevant distinctions are made (Clementini, E., Di Felice, P., and D. Hernandez, 1997). Thus, qualitative reasoning only studies the essence of information, represented as a small set of symbols such as the quantity space {-, 0, +} consisting of the landmark value 0 and its neighbouring open intervals ]-∞,0[ and ]0,∞[ represented respectively by the symbol -and + (Cohn, A.G. and Hazarika, S.M., 2001).
Not always everything has to be known about a situation to make inferences which are important for the specific study (Frank, A.U., 1996). Obviously in such situations sometimes information lacks for giving complete answers to queries. However, like Freksa (Freksa, C., 1992a, p.203) states, 'a partial answer may be better than no answer at all.' By abstracting away from metrical details, qualitative representations are much more appropriate for handling such incomplete knowledge than quantitative methods (Cristani, M., Cohn, A.G., and Bennett, B., 2000).
The development of the Qualitative Trajectory Calculus (QTC) has been inspired by some important qualitative calculi in temporal and spatial reasoning, especially the temporal Semi-Interval Calculus (Freksa, C., 1992) and the spatial Double-Cross Calculus (Freksa, C., 1992b;Zimmermann, K. and Freksa, C., 1996). Central in these theories is the specific attention to incomplete knowledge, for example produced by natural language expressions. In combination with the inherent capability of the qualitative calculi lying at the basis of QTC, one might expect that QTC ought to be able to handle incomplete knowledge.
In this section, an informal account of the Qualitative Trajectory Calculus -Basic (QTC B ) is presented. For a formal axiomatisation, we refer to (
). Continuous time for QTC B Van de Weghe, N., 2004 B B is assumed. In general, QTC B compares positions of two objects at different moments in time. The movement of the first object (called k) with respect to the second object (called l) is studied by comparing the distance between l at the current time point (denoted t) and k during the period immediately before the current time point (denoted t ), with the distance between l at t and k during the period immediately after the current time point (denoted t ). In addition, the movement of l with respect to k is studied by comparing the distance between k at t and l at t , with the distance between k at t and l at t . QTC
B1D handles the qualitative movement of two constantly disjoint point objects restricted to 1D. Because the movement is restricted to 1D, the velocity vector of an object only has two possible directions, with the intermediate case where the object stands still. Hence, the direction of the movement of each object can be described by one single qualitative variable. Both degrees of freedom can be further subdivided according to the relative speed of the objects. This subdivision results in redundant information because the relative speed of k with respect to l is the inverse of the relative speed of l with respect to k. By reducing the continuum to the qualitative values -, 0 and +, the underlying continuous system can be described discretely. We introduce the following notation for QTC B1D :
x|t denotes the position of an object x at time t, d (u,v) denotes the distance between two positions u and v, v x |t denotes the speed of x at time t, t 1 < t 2 denotes that t 1 is temporally before t 2 .
A movement is presented in QTC B1D using the following four conditions (C):
C1. Movement of k with respect to the position of l at t (distance constraint):
all other cases C2. The movement of l with respect to the position of k at t (distance constraint) can be described as in C1 with k and l interchanged.
C3. Relative speed of k at t with respect to l at t (which dually represents the relative speed of l at t with respect to k at t) (speed constraint):
Accordingly, a qualitative trajectory pair can be represented by a label consisting of two or three characters, for respectively QTC BL1 (QTC B of level one) only handling the changing distance between two objects and QTC B BL2 (QTC B B of level two) also taking into account the third label representing the relative speed of both object with respect to each other. In theory, there should be 27 (3³) B12-relations (QTC relations of level two in 1D). As illustrated in Fig. 1A, 10 relations are impossible (e.g. relation 2b: if object k moves towards object l and object l stands still, then v k < v l is impossible). Therefore, we get only 17 B12-relations. Each icon in Fig. 1A represents one single relation, and therefore is called a relation icon, in this particular case a B12-relation icon. The left and the right dot of the B12-relation icon respectively represent the positions of k and l. The line segments represent whether each object can be moving towards or away from the other. A dot is filled if the object can be stationary, and open if an object cannot be stationary. The representations are no more than icons, in which we assume that k is on the left side of l.
The approach for 1D can be successfully used for higher dimensions by denoting the Euclidean distance between a pair of point objects as being the only dimension. This way 2D and even 3D movements can be reduced to 1D movements. To emphasise that we are working on 2D movements, the theory is called QTC B2D . The definitions for the 2D movement are the same as the definitions for the 1D movement. In contrast with QTC B12 , there are 27 potential B22-relations, represented as 27 B22-relation icons in Fig. 1B. If, for example, the first character of the B22-relation is 0, then the first object stands still or can move tangentially with the second object. The icons contain line segments with the point object in the middle of it. The line segment stands for the opportunity to move to both sides of the point object. A filled dot represents the case when the object can be stationary. An open dot means that the object cannot be stationary. The icons also contain crescents with the point object in the middle of its straight border. If a crescent is used, then the movement starts in the dot and ends somewhere on the curved side of the crescent. It is important that the crescent is an open polygon: the straight boundary of a crescent is an element of another relation. Of major importance is that, in contrast to QTC B1D, all 27 relations are possible. The reason for this is quite straightforward. In 1D, an object can only move along a straight line. On the other hand, in 2D an object can move throughout the complete 2D space, being a higher dimension than the 1D distance. Therefore, there is a higher degree of freedom in B2D-movements compared to B1D-movements, resulting in the different number of possible relations. This example starts from Ex1 forming fine knowledge concerning moving objects, and relaxes the constraints in order to get incomplete knowledge (Ex2, Ex3 and Ex4a).
Thereafter, the inverse approach is discussed. Starting from several incomplete constraints (Ex4a, Ex4b, Ex4c, and Ex4d), fine knowledge will be generated by the intersection of the incomplete solutions. The example is worked out for 1D and 2D.
Ex1: k is moving towards l, which in turn is moving away from k, both objects moving along the same straight line and having the same speed.
Ex1 → (-+) B11 and Ex1 ↔ (-+ 0) B12 QTC B11 does not give full detail, because (-+) B11 also contains situations where k and l have a different speed. Therefore, it is more appropriate to work at level two, which incorporates the speed variable.
Ex1 → (-+) B21 and Ex1 → (-+ 0) B22 At first sight, QTC B2D and QTC B1D give the same result. However, there is only an implication (→) between Ex1 and (-+ 0) B22 , because (-+ 0) B22 does not consider the restriction in Ex1 that both objects are moving along the same straight line, which was an implicit restriction for movements in 1D.
Ex2: k is moving towards l, which in turn is moving away from k, both objects moving along the same straight line.
The only difference between Ex1 and Ex2 is the speed constraint, which is not given in Ex2. In contradiction to Ex1, we have in Ex2: if (-+) B11 is true, then Ex2 must be true. Ex2 is thus totally covered by QTC B11 . The difference between Ex1 and Ex2 has perhaps more implications for QTC B12 , since (-+ A) B12 consists of a disjunction of solutions:
The following statement is false:
The following statement is true:
Ex2 represented in QTC B22 gives no extra information compared to Ex2 represented in QTC B21 since the third character of QTC B22 , differentiating QTC B22 from QTC B21 , can have all qualitative values. Note that there is only an implication (→) between Ex2 and (-+) B21 , because (-+) B21 does not consider the restriction in Ex2 that both objects are moving along the same straight line, which was an implicit restriction for movements in 1D. The same applies to the implication between Ex2 and (-+ A) B22 .
Ex3: k is moving towards l, which in turn is moving away from k.
Ex3 ↔ (-+) B11 and Ex3 ↔ (-+ A) B12
Compared to Ex2, the objects do not need to move along a straight line. However, this constraint is straightforward, since we are working in 1D.
Ex3 ↔ (-+) B21 and Ex3 ↔ (-+ A) B22
In contrast to the 1D movement, the constraint that both objects have to move on the same straight line (or in 1D) is important in 2D. In Ex3, this constraint is deleted, which results in an important extension of the solution set. This extension can be seen in the formulae; on the one hand one gets an implication between Ex2 and the B2D relations, on the other hand one gets an equivalence between Ex3 and the B2D relations. This extension can be easily seen by comparing the relation icons for (-+ A) B21 in Fig. 1A with those for (-+ A) B22 in Fig. 1B.
Ex4a: k is moving towards l.
Ex4a ↔ (-A) B11 and Ex4a ↔ (-A B) B12
This expression does not state whether l is moving. Because this expression is less complete than Ex3, it is obvious that we cannot distinguish QTC B11 from QTC B12 . However, note in QTC B12 that when l is not moving, only (-0 +) B12 holds, because (-0 -) B12 and (-0 0) B12 are impossible in 1D.
Ex4a ↔ (-A) B21 and Ex4a ↔ (-A B) B22
As could be expected, there is no difference between for QTC B11 and QTC B21 .
Now, let us start from four expressions (Ex4a, Ex4b, Ex4c, and Ex4d), which together form the fine compound expression Ex1:
Ex4b: l is moving away from k.
Again, there is no difference between the representations of QTC B11 and QTC B21 , and those of QTC B12 and QTC B22 .
Ex4c: k and l are moving along the same straight line.
Because it is specified that both objects are moving, neither of the two objects may stand still.
Ex4d: k and l have the same speed.
Ex4d → (A* B*, 0 0) B11 Ex4d ↔ (A* B* 0, 0 0 0) B12 It is not specified whether the speed has to be higher than zero. Therefore, (0 0) B11 and (0 0 0) B12 are possibilities. However, since the speed of both objects has to be the same, it is impossible to have a pair of objects where only one object is moving.
In contrast to QTC B11 , every relation is possible in QTC B21 , which is a direct result of specifications concerning the exclusive B22-relations.
The intersection of the four solution sets of the expressions Ex4a, Ex4b, Ex4c, and Ex4d, gives (-+) B11 and (-+ 0) B12 . One can state that the intersection of the solution sets of the components of a compound expression is the same as the solution set of the compound expression.
(
The intersection of the four solution sets for QTC B2D of each expression is respectively (-+) B21 and (-+ 0) B22 . Again (cf. QTC B1D ), the intersection of the solution sets of the components of a compound expression is the same as the solution set of the compound expression.
(
If we say that an object is moving, we can have interpretation problems; do we mean that at least one of the objects is moving, or do we mean that exactly one object is moving? This ambiguity can be overcome by QTC B . B
Ex5: At least one of the objects is moving.
Due to this expression, it is possible that only one object is moving or it could be that both objects are moving. Note that for QTC B21 and QTC B22 , the relations where the first and the second character are zero do not need to be excluded since objects can move tangentially when both the first and the second are 0 in 2D.
Ex6: Exactly one of the objects is moving.
Ex6 ↔ (A* 0,0 B*) B11 Ex6 ↔ (A* 0 B, 0 A* B) B12 Ex6 → (A 0, 0 A) B21 Ex6 → (A 0 B, 0 A B) B22
Note again the subtle difference between QTC B1D and QTC B2D . In QTC B1D , an object can only move when a character is different from 0. In QTC B2D , an object can move if a character is 0. Note that (A*B*) B21 is impossible since here both objects are moving.
Based on several illustrative examples, the ability of handling incomplete knowledge and natural language expressions within QTC B is studied. In further research, the possibilities of QTC-Double Cross (QTC B C ) to handle incomplete knowledge will be discussed. Since QTC C considers additionally the direction in which an object is moving with respect to the line segment between the two objects, this calculus is more expressive and will involve more complex reasoning. Note for example that, in contrast with QTC C2D, it is not possible in QTC B2D to denote whether two objects are moving along the same straight line. This will be possible. In the future, we will continue to explore the bridge between natural language, perception and formal ontologies of moving objects.