Reasoning of Geometric Concepts based on Algebraic Constraint-directed Method

1 Introduction

This paper presents a new approach for learning or reasoning of geometric concepts based on algebraic constraint-directed methods.

Geometric reasoning is available for many applica­ tions, such as robotics, CAD and computer vision. How­ ever, most previous reasoning systems, which are based on predicate logic, have difficulties in handling geomet­ ric notions. This is because the usual symbolic approach fails to grasp the essential characteristics of geometry, and cannot solve complicated problems, such as those which require auxiliary lines.

As a result, handling geometric concepts causes great trouble in many applications of reasoning. For in­ stance, consider the heuristics called skewed symme­ try in computer vision [Kanade81]. This is a fa­ mous geometric constraint which claims that a two­ dimensional skewed symmetry is a projected image of a genuine three-dimensional symmetry (Fig.1). Because of transformation-invariant characteristics such as shear transformation, it is very difficult to represent this con­ straint by usual predicate logic, still more to establish the reasoning system. In order to solve these difficul­ ties, we select Wu's method as algebraic approach, and

·1 wish to thank members in FAI-WG (Foundation of Arti­ ficial Intelligence) and CLP-WG (Constraint Logic Program­ ming) of !COT for useful comments and discussion on earlier drafts of this work.

Hirochika INOUE

Dept. of Mechanical Eng., Faculty of Eng., Univ. of Tokyo 7-3-1 Hongou, Bunkyou-ward, Tokyo, 113, Japan

construct a geometric reasoning system (GREW: Geo­ metric REasoning based on Wu's method). This system is based on the integrated scheme of symbolic reasoning and algebraic method. We show its validity by experi­ ments, such as learning computer-vision heuristics and solutions to locus problems.

2 Geometric reasoning based on algebraic method

2.1 Wu's Method

In general, the hypotheses of a geometrical theorem can be represented in triangular forms of algebraic expres­ sions. That is,

Where u1 , · · ·ud are independent variables and x1 , · · ·Xr-l, Xr dependent. Under these hypotheses, the con­ clusion is represented as follows.

Conc(u1, · · ·ud, XI,·· ·Xr-b Xr) = 0 (2) With these preparations, the geometric proof is equiva­ lent to deciding whether the expression (2) is equal to zero under the equality system of the condition (1). Wu's theorem gives a deterministic procedure for this decision [Wu78]. That is,

(2) is equal to zero under (1) ;

i.e. the conclusion of the theorem is valid ¢:::::} Remr = 0

Remr (called (final) remainder term) is calculated as follows.

Rem;+l =( the remainder of Rem;

divided by tri;+l under Xr-i)

The above procedure is called Wu's method [Chou84]. We have constructed an algebraic theorem proving sys­ tem based on Wu's method. This system uses strategies for the efficient triangulation, such as decomposition of reducible cases, simplification of expressions, and con­ flict resolution of auxiliary or degenerate conditions. We have experimented in many examples to confirm that the efficient process is achieved [Iba90].

and retry Wu's method under this new hypotheses, then the new remainder generally equals to zero. Thus each fi is regarded as new algebraic constraints for validating the conclusion under the old hypotheses. These fi 's are derived heuristics or candidates of geometrical descrip­ tions. Therefore we apply Wu's method to geometric reasoning with the following fundamental principle;

2.2 Algebraic constraint-directed method for geometric reasoning

We realized geometric reasoning based on the algebraic. method. In this section, we explain the constraint­ directed principle with Wu's method.

Consider the case that the final remainder of Wu's method is not zero;

This expression is factorized into irreducibles as follows,

CASE 1: Conclusion is given beforehand.

In this case, each derived /j works like a candidate of newly-found heuristics that validates the original conclusion under the hypotheses trij.

CASE II: Conclusion is not given.

In this case we apply Wu 's method by choosing one trii as Conc.The independent variables u; regulate the resultant remainder description. That is, the final remainder Remr is represented on the basis of independent variables. Therefore it is necessary to choose appropriate independent variables for final expressions, and /j is regarded as the geometric representation on the basis of ui.

We call the above principle as the constraint-directed reasoning, which is justified alge-geometrically as fol­ lows. The final remainder (3) forms a subset of alge­ braic variety of hypotheses and the conclusion. Thus the ~esired geometric information is represented, though partially, as algebraic constraints of remainder terms.

To illustrate this algebraic constraint-directed ap­ proach, we show its application to learning-by-example of geometric heuristics in computer vision. We alge­ geometrically represent heuristics or relations in com­ puter vision as follows.

IF

condition1 (constraints on variables) THEN conclusion f(x1 ,· · ·,xr) = 0 UNLESS condition2

Conclusion f corresponds to the part of expressions that may occur in the final remainder term of Wu's method. Condition1 describes constraints on variables in f. Learning of heuristics is realized by deriving condition! and conclusion part from common terms in the final remainder of Wu's method. This strategy is based on the above claim in CASE I.

Fig.2 shows the learning process of Kanade's heuris­ tics, in which the skewed-symmetry heuristic (Fig.l) is learned from exemplar bricks and wedges. In this case, hypotheses and the conclusion consist of six expressions with bricks, and five with wedges. These expressions are after (Swain86]. For instance, ht, · · ·h6 represent a brick as a whole (Fig.3). Here, ht, · · ·h3 correspond to Mack­ worth constraints or parallel-line heuristics (Kanade81]. More precisely, h1 shows that the vector (GB- GA) is vertical with the vector ab, and this is equivalent to the fact that upper and lower lines of face B (projected to parallel segments in two-dimensions) are also parallel in three-dimensions. And h4 , · · ·h6 mean that faces A,B,C are vertical with each other in three-dimensions because the normal vector of face A is (ga1 , ga2 , 1) and so on (Fig.l). The whole system of ht, · · ·h6 together gives a complete description of two-dimensional visibility and three-dimensional model of bricks and their relations.

The remainder resulting from Wu's method is shown as Rem in Fig.2. Though omitted in the figure, learning examples are actually taken from six types of bricks and five types of wedges. The reasoning process is executed such as ~attern-matching, eliminating trivial cases (aa2 ), and stonng analogous patterns of terms ( ab2 ac2gb22 + · · ·) an? (aazabzgazz+··). The matching of (ac1gb2 -ac2gbt) and (ab1acz - abzact) failed because the dimensions of gb, ab, ac are different (gb is gradient, and ab, ac are metric). After necessary generalizations, the following representation is obtained as a heuristic.

UNLESS auxiliary conditions of a,b,G

Where G is a x,y coordinate of three-dimensional gradi­ ent of the parallelogram formed by vector a and b. (a,b) means an inner product of vectors. UNLESS part rep­ resents a subsidiary premise which makes this heuristic applicable (Swain86]. Through the use of this UNLESS

knowledge, we have established the appropriate mainte­ nance and modification of constraint-directed models for robotics (Iba88].

The above representation is equivalent to the one in (Kanade81], which shows the validity of our approach. In the same way, other kinds of geometric heuristics in computer vision can be learned from examples; for exam­ ple, parallel-line heuristics and Mackworth constraints (Iba90].

3 Geometric reasoning system: GREW

Algebraic method elaborately solves reasoning problems with auxiliary lines or ad-hoc heuristics. However, at the same time, this approach is accompanied by compu­ tational problems such as the selection of independent variable~ or the derivation of geometric information from algebraic expressions. These kinds of prob~ems are dif­ ficult to solve only within algebraic domains of polyno­ mials (called syntax of expressions). Rather, reasoning with symbolic descriptions (called semantics of expres­ sions) is required.

. In o~der to realize an effective handling of geomet­ nc notwns, we have constructed an integrated reason­ ing scheme; integration both of symbolic reasoning and algebraic reasoning of Wu's method (Fig.4). The ba­ sic principle of this scheme is to describe mathematical knowledge-in terms of symbolic logic and to execute sub­ sidiary reasoning for Wu 's method. Thus, our system establishes appropriate handling of geometric semantics.

Our system GREW consists of four fundamental phases as follows.

Phase I: Translation of symbolic representations into al­ gebraic representations

Input expressions Desc; for GREW are represented by symbols. In Phase I, these descriptions are trans­ lated into algebraic representations hyp;. We realized the translation of about 20 geometric notions in two- or three-dimensional Euclidean space into algebraic repre­ sentations. This translation is, in general, reversible. In Phase IV, the inverse translation is used to derive geo­ metric descriptions in the symbolic form.

In Phase I, in addition to the above mechanical trans­ lation, the following important information is derived for the subsequent reasoning. This corresponds to the geo­ metrical semantics in algebraic expressions.

(1) DESCRIPTIVE

The information as to which variables exist in the origi­ nal problem description. This is used in Phase IV.

(2) INDEPENDENT

This maintains important information of dependent vari­ ables used in the triangular derivation (Phase II). In lo­ cus problems (Fig.5,6), variables in the FIND statement are independent because they are designated to lie in the desired locus. On the other hand, added variables are generally candidates for dependents.

(3) DEPENDENTS

This represents a set of dependent variables, which can be derived from problem descriptions by judging whether to lie on the same figure or geometric relations. It is difficult, in general, to determine INDEPENDENT and DEPENDENTS completely. Thus some sorts of heuris­ tics are essential. These two kinds of information are used for the triangular derivation in Phase II.

(4) SYMMETRIC

The information as to the symmetry of descriptions. Symmetries are ubiquitous in geometric problems and enable an effective reasoning, as shown later.

(5) FORALL

The information as to the variable definition range for universally valid equations is maintained. This informa­ tion is used in Phase III.

Fig. 7 shows a part of the reasoning process of GREW for the two-circle problem. This problem is described as follows (Fig.5).

Find the locus of the mid-point P of all seg­ ments QT's, where the end points Q and T lie on 0 1 and 0 2 respectively ( 0 1 and 0 2 are two circles outside each other and the radii are r 1 and r2 , respectively).

Deseg, · · ·Desc15 and hyp1 , · · ·hyp8 are the results of Phase I. NIL means to be undecided slots in the original descriptions. In this case it is unnecessary to describe the center or radius of circles beforehand. These slots are appropriately filled by new symbols in Phase I. The FIND statement means that the point P is on the de­ sired locus.

Phase II: Constraint-derivation based on Wu's method This phase is the core of our reasoning system GREW, which deduces algebraic constraints with Wu's method. Here the triangular form is derived with the following principles of selecting dependents; that is, se­ lecting as many variables that belong to the same set in DEPENDENTS as possible, and avoiding the selection of variables in INDEPENDENT and FORALL. These principles work as heuristics for Phase IV.

Phase III: Algebraic reasoning based on mathematical knowledge

The reasoning is executed on the final remainder terms. Mathematical knowledge is maintained for this execution as follows.

(1) Manipulations of algebraic expressions Simplify the final remainder terms by factorizing or transforming. This is effective when focused variables are given beforehand, such as locus problems. In locus problems those variables are designated by FIND state­ ments (Fig.7,8).

(2) Reasoning as to universally valid equations In order to derive the condition for making the final re­ mainder term zero, the reasoning about universally valid equations is executed with FORALL descriptions.

(3) Reasoning as to trigonometric functions Reasoning about trigonometric functions are essential for describing circles.

( 4) Solving inequalities Try to solve simple inequalities.

(5) Manipulations on vectors or matrices Components of vectors or matrices are manipulated in connection with its geometlic representation.

(6) Reasoning by pattern matching between expres­ sions

Reasoning is executed based on symmetry or analogy of derived algebraic expressions. Geometric semantics are essential for this. We illustrated the learning experiment in this reasoning (Fig.2).

Phase IV: Inverse translation into symbolic representa­ tions

Translate algebraic expressions into symbolic repre­ sentations inversely. The basic strategy is to make pattern-matching with the template of deduced alge­ braic expressions in Phase I. DESCRIPTIVE informa­ tion is used so as to derive symbolic expressions as gen­ eral as possible (the least number of variables newly in­ troduced).

4 Experimental Results

We have confirmed the validity of GREW and our al­ gebraic constraint-directed reasoning scheme by many experiments such as locus problems (Fig.5,6) and con­ struction problems (Iba90]

Fig. 7 shows a part of the reasoning process of GREW for the two-circle problem. The constraint-directed reasoning is executed based on inequality relations of trigonometry and quadratic inequalities (type (1)(3)(4) in Phase III). New - Dec5 is finally derived and shows that the point P is in the range which is outside a circle (the center is a mid-point of centers of circle 0 1 and circle 02, and the radius is lrt ;r 2 1 ), and which is inside a circle (the center is the same, and the radius is (rt tr 2 ) ).

As another example, Fig.8 shows the solution to 3D skew-line problem . This problem is described as follows.

Two lines XX' and YY' are given. These lines are not in the same two-dimensional plane, and are vertical with each other. Find a locus of the mid point M of all segments KL's, where the end points K and L are on lines XX' and YY' respectively, and the distance of KL is constant p (Fig.6).

In phase I, new variables are generated for directional vectors of lines, and algebraic expressions are derived with these parameter variables. The reasoning as to uni­ versally valid equations is executed in Phase III, and the algebraic constraints are derived as follows.

(1)a1(x1- yt) + ao(xo- Yo)= 0

(2)y2- X2 = 0

(3)4(a- Y2) 2 + 4(,8- xt) 2 + 4(-y- xo) 2 - p 2 = 0 Because of the symmetrical relation (SYMMETRJC in Phase I), the following equation is added.

(4)4(a- x2) 2 + 4(,8- Yt) 2 + 4(-y- Yo) 2 - p 2 = 0 In Phase III, from (1) and (2), it is deduced that two vectors (ao, a1, a2) and (xo- Yo, XI- YI, x2- Y2) are ver­ tical with each other. It is also deduced that (b0 ,b1,b2) is vertical with ( Xo - Yo, x1 - YI, x2 - Y2 ), because (bo, b1, b2) and (ao, a1, a2) are vertical with each other ( hyp1 ,Fig.8( a)).

(ao, a1, a2) .l (xo -Yo, Xt - Yb x2 - Y2)

(bo,bt,b2) .i (xo- Yo, XI- Yt,X2- Y2) (#)

Thus points of the locus are the intersection of two spheres (each center is ( xo, x1, x2) and (Yo, YI, Y2) respec­ tively, and radius is~. where (xo,Xt,X2) and (yo,yt,Y2) satisfy ( #)). Furthermore, in checking sufficient condi­ tions for the locus, it is also deduced that this intersec­ tion lies on the same plane, which is omitted here. As a result, New - Desc descriptions are derived in Phase IV, where !- means a vector subtraction operator.

5 Future research

Our reasoning scheme has an advantage in handling of geometric notions, and we mean to make applications of this method to more practical domains; such as path­ planning problems or environment model managements of intelligent robots (Iba88] . For this purpose, we now research on further extensions in the algebraic reason­ ing. This is to cope with the failure in Phase IV, that is, the failure to derive appropriate geometrical infor­ mation from algebraic representations. This failure is caused by the lack of primitives to make inverse transla­ tions from algebraic expressions, or by the inappropriate algebraic reasoning in phase III. From the more prac­ tical viewpoint, we think it important to calculate ap­ proximated solutions based on the final remainder terms by using numeric methods or simulations. A program called TLA embodies this kind of methodology for me­ chanical simulations (Kramer90]. On the other hand, mathematical expert systems seem to us promising, in which formal handling of geometric semantics could be realized by the knowledge or meta-knowledge in mathe­ matics. Thus our future research of concern is to further extend our method in this direction to realize the ap­ propriate control of reasoning in algebraic domains, and to formalize its algorithm with both domains; symbolic and algebraic.

6 Conclusion

Reasoning about geometric notions is difficult to exe­ cute only by the usual symbolic method. This paper presents a new scheme for geometric reasoning with al­ gebraic constraint-directed method. Although our alge­ braic approach avoids the complicated problem of rea­ soning in auxiliary lines or handling of heuristics, at the same time it encounters computational difficulty in se­ lecting independent variables. To solve this, we have tried to derive geometric semantics of algebraic expres­ sions from the original problem description, and to es­ tablish the constraint-directed reasoning based on these semantics. Finally, the validity of our system GREW has been shown by experiments.