In this paper, we present a way of how to handle incomplete knowledge concerning moving objects. Our approach is based on the basic Qualitative Trajectory Calculus (QTCBB), which is a calculus for handling interactions between moving point objects (MPO's). Without elaborating on the domain of linguistics, we show that QTCBB is well-fitted to represent spatiotemporal natural language. Illustrative examples on how to deal with incomplete knowledge are presented.
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
After an explanation of incomplete knowledge and how it is related to qualitative reasoning, a brief overview of QTCBB is presented. Section 4 presents illustrative examples on how to handle incomplete knowledge within the different types of QTCBB. 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
Not always everything has to be known about a situation to make inferences which
are important for the specific study
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
In this section, an informal account of the Qualitative Trajectory Calculus – Basic (QTCBB) is presented. For a formal axiomatisation, we refer to (Van de Weghe, N., 2004). Continuous time for QTCBB is assumed. In general, QTCBB 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+. QTCB1D 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 QTCB1D: x|t denotes the position of an object x at time t, d(u,v) denotes the distance between two positions u and v, vx|t denotes the speed of x at time t, t1 < t2 denotes that t1 is temporally before t2.
A movement is presented in QTCB1D using the following four conditions (C): C1. Movement of k with respect to the position of l at t (distance constraint): −: k is moving towards l: ∃t1 (t1 < t ∧ ∀ t − (t1 < t − < t → d(k|t −, l|t) > d(k|t, l|t))) ∧ ∃t2 (t < t2 ∧ ∀ t + (t < t + < t2 → d(k|t, l|t) > d(k|t+, l|t))) +: k is moving away from l: ∃t1 (t1 < t ∧ ∀ t − (t1 < t − < t → d(k|t −, l|t) < d(k|t, l|t))) ∧ ∃t2 (t < t2 ∧ ∀ t + (t < t + < t2 → d(k|t, l|t) < d(k|t+, l|t))) 0: k is stable with respect to l (all other cases):
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): −: vk|t < vl|t +: vk|t > vl|t 0: vk|t = vl|t Accordingly, a qualitative trajectory pair can be represented by a label consisting of two or three characters, for respectively QTCBL1 (QTCBB of level one) only handling the changing distance between two objects and QTCBL2 (QTCBB 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 vk < vl 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 QTCB2D. The definitions for the 2D movement are the same as the definitions for the 1D movement. In contrast with QTCB12, 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 QTCB1D, 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. In common with qualitative spatial and temporal calculi, we need to consider that we do not always have complete knowledge about which relation holds between a pair of moving objects. In this section, illustrative examples on how to handle incomplete knowledge within QTCBB are presented. Expressions in natural language (Ex), about the movement of two objects (k and l) with respect to each other, are considered. We determine which QTCBB relations hold for each particular expression. We use the standard notation for implication and equivalence: a → b: if a, then b a ↔ b: if and only if a, then b as well as the standard notations for the following set operations: a \ b : a minus b a ∩ b : intersection of a and b
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 QTCB11 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, QTCB2D and QTCB1D 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.
Ex2 ↔ (– +)B11 and Ex2 ↔ (– + A2)B12 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 QTCB11. The difference between Ex1 and Ex2 has perhaps more implications for QTCB12, since (– + A)B12 consists of a disjunction of solutions:
The following statement is false: Ex2 → a (with a ∈ (– + A)B12) The following statement is true: a → Ex2 (with a ∈ (– + A)B12)
Ex2 → (– +)B21 and Ex2 → (– + A)B22 2 A qualitative variable A (B, C, …) stands for the set {–, 0, +} Ex2 represented in QTCB22 gives no extra information compared to Ex2 represented in QTCB21 since the third character of QTCB22, differentiating QTCB22 from QTCB21, 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 ↔ (– 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 QTCB11 from QTCB12. However, note in QTCB12 that when l is not moving, only (– 0 +)B12 holds, because (– 0 –)B12 and (– 0 0)B12 are impossible in 1D.
Ex4a ↔ (– A)B21and Ex4a ↔ (– A B)B22 As could be expected, there is no difference between for QTCB11 and QTCB21.
Now, let us start from four expressions (Ex4a, Ex4b, Ex4c, and Ex4d), which together form the fine compound expression Ex1:
Ex4a ↔ (– A)B11 Ex4a ↔ (– A B)B12 Ex4a ↔ (– A)B21 Ex4b: l is moving away from k. Ex4b ↔ (A +)B11 Ex4b ↔ (A + B)B12 Ex4b ↔ (A +)B21 Ex4b ↔ (A + B)B22 Ex4c ↔ (A*3 B*)B11 Ex4c ↔ (A* B* C)B12 Ex4c → (A* B*)B21
Ex4c → (A* B* C)B22 Again, there is no difference between the representations of QTCB11 and QTCB21, and those of QTCB12 and QTCB22.
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.
Ex4d → (A B)B21 and Ex4d ↔ (A B 0)B22 In contrast to QTCB11, every relation is possible in QTCB21, 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. 3 A qualitative variable A* (B*, C*, ...) stands for the set {−, +} The intersection of the four solution sets for QTCB2D of each expression is respectively (– +)B21 and (– + 0)B22. Again (cf. QTCB1D), the intersection of the solution sets of the components of a compound expression is the same as the solution set of the compound expression.
(– A)B21 ∩ (A +)B21 ∩ (A* B*)B21 ∩ (A B)B21 = (– +)B21 (– A B)B22 ∩ (A + B)B22 ∩ (A* B* C)B22 ∩ (A B 0)B22 = (– + 0)B22
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 QTCBB.
Ex5:
Ex5 ↔ (A B) \ (0 0)B11 Ex5 ↔ (A B C) \ (0 0 0)B12 Ex5 → (A B)B21
Ex5 → (A B C)B22 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 QTCB21 and QTCB22, 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:
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 QTCB1D and QTCB2D. In QTCB1D, an object can only move when a character is different from 0. In QTCB2D, 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 QTCBB is studied. In further research, the possibilities of QTC-Double Cross (QTCC) to handle incomplete knowledge will be discussed. Since QTCC 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 QTCC2D, it is not possible in QTCB2D 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.