Orientation and Qualitative Angle for Spatial Reasoning

Introduction

Qualitative reasoning deals with reasoning on the conceptual level. Most approaches in the area of qualitative spatial reasoning define a set of spatial relations and show the connections of these relations in composition tables. Each entry in such a table is verified by informal considerations of some pictures showing the concepts, or by general quantitative considerations. This means there is an implicit qual,}titative semantics underlying the spatial relations. In this sense each qualitative inference is semantically verified in three steps: 1. definition of the qualitative concepts in quantitative terms, 2. quantitative reasoning, and 3. qualitative abstraction. Each of these steps has its inherent problems: The quantitative definition of spatial concepts is often context dependent, quantitative reasoning is a difficult problem in non-trivial domains, and the qualitative abstraction often entails a loss of information. For these reasons the underlying quantitative semantics is kept implicitly in most systems.

Our approach takes two cognitively motivated spatial concepts, arrangement and angles, and offers a context independent well defined mapping of these simplest approach in cognitive science is to adopt arrangement information as described in [Schlieder, 1990]. There, relative positions are described in terms of the orientation of triangles, clockwise or counterclockwise. If, for example, a triangle ABC is oriented counterclockwise, then we know that point C is to the left of the straight line AB (see Figure 2). The distinction of a left and right hand side is clearly a cognitively motivated concept.

Arrangement knowledge has been successfully applied in Artificial Intelligence (see [Levitt and Lawton, 1990; Schlieder, 1990]) and in Computational Geometry (see [Bokowski and Sturmfels, 1989]). Though arrangement knowledge is well suited for qualitative representations of spatial situations, if we only use this kind of knowledge, we cannot do inferences we are interested in, as the following example shows. Given the orientation of two triangles over four points, it is not possible to say anything about the orientation of the other two triangles. In both Figures 3a and 3b, triangle ABC is oriented counterclockwise and BCD is oriented clockwise, but triangle ABO is oriented differently in Figures 3a and 3b. Of course, the same situation can be constructed for triangle ACD.

Now the question is whether one can find another cognitively motivated concept for representing spatial situations without using metric information. There is psychological evidence that people are able to recognize the right angle (especially while treating the angle from the vertex perspective), and so are able to distinguish an acute angle from an obtuse angle.

Therefore, it is straightforward to augment the concept of arrangement information by the qualitative distinction of acute and obtuse angles.

These two concepts of arrangement and qualitative angles fit together quite well, since both describe orientation information.

Notation

When introducing a system integrating arrangement and qualitative angles, for reasons of simplicity and transparency, we will treat neither the concept of collinearity of three points, nor the concept of right angles. This means that we will distinguish situations in which a point C is to the left or to the right of a straight line AB, but we will exclude situations where point C is on the line. In the same manner we will distinguish situations where three points form an acute or an obtuse angle, but we will exclude situations where they form exactly the right angle. The augmentation of the system by these concepts is straightforward.

Similar to the representation of arrangement information, the relative positions of triples of points will be described by triangles in our system. Each triangle will be represented by qualitative information about its three angles and its orientation. Orientation will be denoted by "+" for counterclockwise and "-" for clockwise. Qualitative angles will be abbreviated by "ac" for acute and "ob" for obtuse. For example, the representation of the triangle presented in Figure 4a is shown in Figure 4b. An obvious observation is the fact that if one angle is obtuse, the other two have to be acute.

Since our inference processes are based on qualitative angles, we will introduce a special notation for a single angle. We will denote an angle XYZ by an ordered pair consisting of the orientation of points XYZ and the qualitative angle in Y. For example, angle CAB of the triangle presented in Figure 4 will be described as CAB(+, ac). As it is easy to note, if we know the orientation of one angle, we know the orientation of the whole triangle, so we can infer the orientation of the other angles. This simple fact together with the fact that every triangle can have only one obtuse angle forms some useful inference rules for reasoning about a single triangle.

Reasoning

The following examples show the profit in the reasoning process we get from combining arrangement and qualitative angle information. We have shown that given the orientation of two triangles over four points, it is not possible to infer anything about the orientation of a third triangle. However, the following example will demonstrate that when arrangement information is augmented with qualitative angles, we can conclude arrangement information about the third triangle. If we get the constellation presented in Figure 5, where ABC as well as CBO form counterclockwise oriented acute angles, then we know that 0 is to the left of line AB (i.e. triangle ABO is oriented counterclockwise), though we do not know whether angle ABO is acute or obtuse, idicated by the dotted line (which will be denoted by ""'").

This inference is valid, because if we add two acute angles with the same orientation, we obtain an angle of less than 1800, which means that 0 stays to the left of line AB.

As another example consider a configuration as depicted in Figure 6. Point C is to the right of line AB and angle ABC is acute.

Figure 6. If ABC is a negatively oriented acute angle and CBD is a positively oriented acute angle, then we can conclude that angle ABD will be acute, though we do not know the orientation of triangle ABD.

Now, if point 0 is to the left of line CB and angle CBO is acute, then we can conclude that angle ABO will be acute too. This is valid, because the difference of two acute angles is an acute angle itself. The dotted line shows that we cannot say anything about the position of 0 with respect to line AB, which will be denoted by""'".

Inference Rule

Now we present a rule that formalizes the above inferences. The general inference schema is to add two adjacent angles ABC and CBO in the vertex B to obtain a third angle ABO, as the following figure illustrates:

ABC

CBO

ABO

Figure 8. The general inference schema is to add two adjacent angles ABC and CBD in the vertex B to obtain a third angle ABD.

In the remainder of this section, we will show how arrangement and qualitative angle information will be passed through this schema. We are looking for a basic concept that underlies the above two concepts.

As we mentioned above, arrangement information splits the plane into two disjoint regions, the left and the right hand side (of line AB in Figure 9a). Another observation is also that angle information splits the plane into two disjoint regions (at line perpendicular to line AB in Figure 9b). For any point C below the perpendicular line, angle ABC is acute, whereas for any point C above that line angle ABC is obtuse. If we combine these two observations, we obtain a division of the unit circle into four quadrants, which for computational reasons we name 0, 1, 2 and 3 as shown in Figure 9c.

Quadrant 0 corresponds to a position of point C forming a negatively oriented acute angle ABC, quadrant 1 to a negatively oriented obtuse angle, quadrant 2 to a positively oriented acute angle and quadrant 3 to a positively oriented obtuse angle.

Now remember the example presented in Figure 6, where ABC was a negatively oriented acute angle and CBO a positively oriented acute angle. Using quadrants, we can express ABC(-, ac) as ABC(O) and CBO(+, ac) as CB0(3). The resulting angle ABO is acute, but without any orientation information, so either ABO(O) or AB0(3) holds, which we will denote ABO(O I 3). This result can also be computed by the following general rule:

If ABC(q1) and BCD(q2), then ABO(q3), where

and q1, q2 and q3 vary over quadrants 0, 1, 2 and 3.

The correctness of this rule can easily be proved by simple angle interval addition, since the quadrants can be described as angle intervals of 900 magnitude. Because the quadrants of the resulting disjunction are always adjacent, the disjunction can be expressed in terms of either arrangement or qualitative angles. Therefore, we have the following correspondence:

ABC(-,,.) ~ ABC(O I 1)

ABC( .. , ob) ~

ABC(+,,.) ~

ABC(l I 2)

ABC(2 I 3)

ABC( .. , ac) ~ ABC(3 I 0)

Figure 10. The correspondence between triangle description and adjacent quadrants.

To demonstrate how to use this rule, we will go back to the example in Figure 5. Using quadrants, the two positively oriented acute angles ABC(+, ac) and CBO(+, ac) will be represented as ABC(3) and CB0(3). By our inference rule, the resulting angle will be AB0(2 I 3), which means that angle ABO is positively oriented and we do not know anything about the qualitative angle: ABO(+, .. ), as expected, due to the above example. The inference is illustrated in the following figure:

Figure 11. Two positively oriented acute angles ABC and CBD result in a positively oriented triangle ABD.

Problem Solution

In this section, we will return to our original problem of finding the qualitative description in terms of arrangement and angles of the remaining triangles when given two triangles over four points in the plane. We will demonstrate that our inference rule provides a solution.

The general problem is depicted in Figure 1. Knowing the orientation of a triangle ABC and the qualitative angles in A, B and C as well as the orientation and angles of a triangle BCD, we ask for the orientation and the angles of triangle ABO (the case for ACO will be treated analogously). The inference is based on the angle addition rule. Obviously, we can apply this rule only at point B, since this is the only point where two angles with one side in common are given, namely 4ABC and 4cBD. As an illustration, let us treat the situation presented in Figure 12.

c

Figure 12. The angle addition is done at point B.

Concerning the angles in point B, the situation is the same as in Figure 5. The resulting angle 4 ABO can therefore be computed as shown in Figure 11. The obtained result ABO(+, ,.) will be interpreted as a counterclockwise orientation of triangle ABO. Let us note once more that knowing only orientation of triangles ABC and CBO, we could not make any inference, since a clockwise orientation of triangle ABO would be consistent with these orientation assumptions as well (cf. Figure 13).

c

Figure 13. We would not know anything about the orientation of triangle ABD in Figure 12 if we only knew the orientation of triangles ABC and CBD.

Another example where qualitative angles can be inferred is depicted in Figure 14: triangle ABC is oriented positively with an obtuse angle in B, whereas triangle CBD is oriented positively with an acute angle in B.

Again we can use our rule for angle addition in the vertex B, which leads to the following inference:

Figure 15. Two positively oriented angles, an acute ABC and an obtuse CBD, result in an obtuse angle ABD.

So, we obtain the qualitative angle information that angle 4 ABD is obtuse. Knowing that one triangle can have at most one obtuse angle, we can additionally infer that the other two angles in triangle ABD are acute. In this situation, we do not obtain any orientation information, as expected, because triangle ABD can be oriented positively (cf. Figure 14) as well as negatively (cf. Figure 16).

Applications

In the problem description we introduced triangles to describe relative positions of points in the plane. Now the question arises as to which relative positions of points can be described with arrangement and qualitative angle knowledge. Figure 17 shows the 8 possible positions of a point C with respect to a pair of points A and B that are distinguishable using our representation.

The vertical line AB divides the plane into two regions which correspond to possible positions of point C with regard to arrangement knowledge (of course, we refer to the line as "vertical" for purposes of illustrations, but it can in fact be oriented arbitrarily). If point C is to the left of AB, then triangle ABC is oriented counterclockwise, whereas if point C is to the right of AB, then triangle ABC is in clockwise orientation. The qualitative angle information provides further subdivision: If triangle ABC has an obtuse angle in B, then point C has to be above the horizontal line in B. In the same way, if the angle in A is obtuse, then C has to be below the horizontal line in A. In the case where both angles in A and B are acute, point C will be in the region between the horizontal lines. This region can be further subdivided into regions inside and outside of the circle, depending on whether the angle in C is obtuse or acute. Note that if point C were on one of the horizontal lines or on the circle, then one of the angles in triangle ABC would be a right angle, but for reasons of simplicity we have not yet extended our representation to those singular cases. For the same reasons, we do not treat collinearity of A, B and C, which corresponds to the vertical line AB.

The obtained subdivision of the plane can be interpreted as a refinement of the system of disjoint orientation relations used by Freksa [1992]. Freksa starts with a left/right and front/back dichotomy in a point B with respect to a reference vector AB. He ends up with 15 disjoint qualitative locations depicted in Figure 18.

In Freksa 's system, the 15 locations have natural language correspondences, for example, straight-front of B (1), left-front of B (2), left-neutral of B (3), left­ back of B, and left-front of A (4), and so on. Spatial inferences are done through the same schema as in our representation (see Figure 8). Each inference step can be encoded in a table showing the composition of the 15 qualitative locations. Freksa uses a neighborhood relation of the qualitative locations to reduce the size of the composition table. Since our inferences are based on an analytic calculus, we do not need any table look-ups.

Freksa and Zimmermann [1992] use these qualitative descriptions for route finding purposes. They illustrate the problems they treat by the following example: "Walk down the road (ab). You will see a church (c) in the front of you on the left. Before you reach the church tum down the path that leads forward to the right (bd)." The question is where the church is with respect to the path (bd):

Figure 19. Route finding scenario used in [Freksa and Zimmermann, 1992].

To answer this question, Freksa and Zimmermann use special operations to transform the input information that (d) is right-front of vector (ab) to an expression based on vector (bd): (a) is right-back of (bd). Knowing this together with the input fact: (c) is left­ front of (ab), we can infer that (c) is to the left of (bd), which answers the question.

Due to the circle, our representation leads to a finer subdivision of the plane. If Freksa's system is augmented by this circle, it turns out that the composition of the operations used to transform the input information is internal, and that these operations form an algebraic group. This is not the case in the original formalism of Freksa and Zimmermann. These algebraic properties simplify the route finding process. The description of these properties and their impact on the reasoning process will be the topic of a forthcoming paper.

Arrangement knowledge is used successfully in [Levitt and Lawton, 1990] for qualitative navigation for mobile robots. Having augmented arrangement knowledge by qualitative angles, which leads to a finer subdivision of the plane, we expect further advantages in qualitative route finding.

As the above example illustrates, our formalism can be used for performing inferences based on qualitative information treated from the observer's perspective. Recently Jungert [1992] presented an extension of symbolic projections of [Chang et al., 1987] which is especially concerned with the observer's point of view. We conjecture that combining these two formalisms would allow us to obtain a powerful system for qualitative spatial reasoning which could be used in motion planning and in building qualitative maps by autonomous systems. A big advantage of such a formalism is that it would not need any global coordinate system.

It is also easy to incorporate arrangement and qualitative angle knowledge into a hybrid system for spatial reasoning which combines propositional and depictorial inferences, as presented in [Latecki and Pribbenow, 1992]. This is due to the propositional inference rule ptesented here and to the fact that using a finite grid as a representation frame for depictorial inferences, we can represent and retrieve arrangement and qualitative angle information in a simple way.

Acknowledgement

We wish to thank Christian Freksa, whose work inspired us, and also Cao Yong, Rolf Sander, and Kai Zimmermann.