Reasoning about Kinematic Topology

1 Kinematic Topology

Reasoning about kinematic behavior IS an important problem in commonsense physics. A large proportion of physical systems involve some form of kinematic in­ teraction, and few methodologies are known for first­ principles modeling of kinematics. In earlier work, we have developed the place vocabulary theory for the spe­ cial case of mechanism kinematics. It provides a gen-

Departement d 'Informatique MA-Ecublens 1015 Lausanne Switzerland

era! first-principles formalism capable of describing the behavior of complex device such as a mechanical clock [Faltings, 1987b, Faltings, 1987a, Nielsen, 1988).

A place vocabulary describes the kinematic behavior of a device as a state graph of different contact relation­ ships. Each possible contact of different pairs of object parts forms a distinct state. There are aspects of human reasoning where this representation is overly detailed. Consider the example of a pair of gearwheels, shown in Figure 1. A mechanism made precisely to the dimen­ sions shown in the drawing on the top will actually work. Its behavior can be analyzed by precise computation on the given data, resulting in an unambiguous place vo­ cabulary. However, the sketch on the bottom is far from a functional gear, and its precise analysis will certainly not reveal a gear function. Yet people are capable of predicting that the gear function is possible, given that the dimensions are adjusted properly.

The metric diagram computation model developed for the place vocabulary theory [Faltings, 1988a, Faltings, 1988b] provides one solution to this problem. It allows us to make complete lists of all possible place vocabularies, and thus all possible behaviors, which may be achieved by variation of the dimensions of the parts. However, this list will be unecessarily big, distinguishing all the different ways that the teeth could mesh or not mesh. A much more appropriate level of analysis would distin­ guish only five different cases, each of which corresponds to a different topology of the set of legal configurations 1 :

1. The device is impossible to contruct, because the parts overlap each other in all possible configura­ tions: the set of legal configurations is empty.
2. The gears block each other, and both wheels can only turn a small amount: several simply connected sets.
3. The teeth mesh properly: one or more doubly con­ nected sets.
4. The teeth do not mesh, and the wheels can turn independently of each other: a multiply (> 2) con­ nected set.
5. No contact between the parts is possible: a simply connected set containing all imaginable configura­ tions.

We call such a description the device's kinematic topol­ ogy. Kinematic topology expresses the connectedness of configuration space and the form of its regions. For example, when the gears mesh properly, the doubly con­ nected regions extend n1 times across the motion param­ eter of the first gear, and n2 times across the motion pa­ rameter of the second gear, where the ratio nl/n2 is the ratio of the number of teeth. A description at this level is sufficient for many applications of reasoning about kine­ matics.

Extracting the kinematic topology from place vocabu­ laries or configuration space is not very promising, how­ ever, as it presupposes that these stronger descriptions have already been computed. The main point of this pa­ per is that the possible kinematic topologies can be de­ termined directly based on only a symbolic description of the objects, and qualitative information about their rel­ ative dimensions. Note the qualification: without metric information, only the possibilities can be listed. Deter­ mining the actual kinematic topology in general is not significantly easier than computing the device's complete place vocabulary. To see why this is the case, consider how intricately the meshing of the teeth depends on their precise shape! The existance of such ambiguities is a necessary consequence of the qualitative nature of the representation.

The fact that kinematic topologies can be computed in a purely qualitative manner is a contradiction to the poverty conjecture made earlier ( [Forbus et al , 1987]), which states that no purely qualitative kinematics is pos­ sible. Note, however, that kinematic topology is not strong enough to compute an envisionment of the de­ vice's behavior.

1 Assuming that the periodicity of the parts is given

Kinematic topologies are of interest not only as a qual­ itative description, but they can also form the basis for a much more efficient computation of place vocabular­ ies. Preliminary tests indicate that the resulting algo­ rithm, called the bubble algorithm, is about 100 times faster than the earlier implementation which was based on configuration space computation. More importantly, kinematic topology can be determined not only for prob­ lems with few degrees offreedom, but also for much more complicated ones where the computational cost of com­ puting with a very high dimensional configuration space is prohibitive. It can provide the basis on which effi­ cient generalizations of the place vocabulary theory can be built.

The qualitative nature of kinematic topology also al­ lows it to be computed for arbitrary object shapes, elim­ inating restrictions on the type of boundary curves al­ lowed. For lack of space, we describe first its derivation for the case of polygonal objects with rotational freedom, and then indicate how it is generalized.

2 Computing Kinematic Topology

The kinematic behavior of a pair of objects is determined by the condition that they may not overlap each other. This condition defines a set of illegal configurations, the blocked space. Kinematic behavior, on the other hand, refers to the set of legal configurations, the free space , which, by its definition as the absence of overlaps, can only be determined as the complement of blocked space. Both spaces can be represented as regions in the space of possible configurations of the objects, the configuration space (as in [Faltings, 1987b, Faltings, 1987a]).

A configuration is part of blocked space if there ex­ ists a pair of object parts which would overlap in the configuration. Pairs of object parts are therefore the el­ ementary building blocks for computing a description of blocked space.

2.1 Object Description

In the following discussion, we refer to the pairwise inter­ action of two polygonal objects A and B, each of which has freedom of rotation only. We assume that the bound­ ary of each of the objects is described as a sequence of pieces and cavities. A piece is centered around a convex vertex and consists of the vertex and the two boundary segments which are joined there (extending to infinity). A cavity is the complement of a piece, centered either around a concave vertex or a minimum of the radius to the center of rotation, and the two boundaries adjoining it 2 · A sample decomposition is shown in Figure 2.

2.2 Formulating the non-overlap condition

Since the two objects A and B are rotating around a fixed center, the configuration space of such a pair is two-dimensional, spanned by the orientations t/J and 7/J of A and B. The fact that two pieces PA and P8 on ob­ jects A and B can not overlap yields the condition that none of the line segments bounding PA and PB can in­ tersect each other, and none of the two can be entirely inside the other. For each pair of object pieces, this de­ fines an obstacle, the set of configurations which violate the condition. The boundary of the obstacle is given as the envelope of four constraint curves, which consist of the configurations where a vertex of one piece touches one of the two boundary segments belonging to the other piece. An example of such an obstacle is shown in Figure 3. An obstacle contains two touchpoints where all four bounding constraints intersect each other. They are con­ figurations where the vertices of the two objects touch each other.

2 In the case of a radius minimum, the two halves of the boundary segment.

Because object pieces are assumed to extend to infin­ ity, the obstacles often also contain many configurations where no overlap exists, and we call these parts of the ob­ stacle invalid. The importance of the obstacles lies in the fact that any boundary between free and blocked space is part of the boundary of some obstacle (see [Faltings, 1987a, Brooks and Lozano-Perez, 1983]) . Our algorithm composes the correct boundary between free and blocked space by composing only the boundary elements of the valid parts of the obstacles. The obstacles serve as tokens which permit an efficient organization of these elements.

In the case of several adjacent pieces, the obstacles they generated have to be intersected to form the true region of blocked space. For kinematic topology, this means that these obstacles can be combined into a single token of a blocked space area.

2.3 The initial topology graph

Between the obstacles thus centered in configuration space lie regions of potential free space, described by bub­ bles. Intuitively, a bubble describes the potentially legal configurations where a piece on one object falls within a cavity on the other. It is a token which stands for the interaction of either a piece and a cavity or two cavities, and takes its shape from the surrounding obstacles and bubbles .

When two cavities follow each other on an object boundary, they enclose between them a boundary seg­ ment which does not belong to any piece. This segment can also generate a boundary between free and blocked space, which is represented by a token called an infi­ nite obstacle. An infinite obstacle can not exist inde­ pendently, but only modify or link together obstacles to which it becomes adjacent, as shown in Figure 4.

The first approximation of the kinematic topology computed by the algorithm is an array of alternating bubbles and obstacles, where the sequence of bubbles and obstacles in each dimension reflects the sequence of pieces and cavities along the object boundary. An ex­ ample of such a graph is shown in Figure 5.

2.4 The weak topology graph

The initial topology graph can be computed without any metric tests whatsoever, but does not yet say very much about kinematic topology. A much more expres­ sive version, the weak topology graph, can be obtained by a modifications based on the tests involving informa­ tion only about the distance of the centers of cavities and pieces from the center of object rotation, and the distance between the centers of rotation of the objects.

2.4 The weak topology graph

The initial topology graph can be computed without any metric tests whatsoever, but does not yet say very much about kinematic topology. A much more expressive ver­ sion, the weak topology graph, can be obtained by a se­ quence of modifications based on tests involving infor­ mation only about the distance of the centers of cavities and pieces from the center of object rotation, and the distance between the centers of rotation of the objects .

First, if a pair of object parts PA and PB are too far apart or too close together to touch each other, there is no configuration that falls within the corresponding ob­ stacle, and it is marked inactive and ignored in further processing. If we let rrpin and rrpax denote the mini­ mum and maximum radius (distance from the center of rotation) for any point on piece P, and d be the distance between the two centers of rotation, this condition can be expressed as:

These distance comparisons can in general be carried out with only very rough information about object di­ mensions. In the case where not enough information is available, a case split results.

Obstacles separated by a single bubble often intersect each other and destroy or divide the bubble which sepa­ rates them. Consider a bubble generated by a cavity CA and a piece PB. If the configuration where the vertex of PB touches the point of minimum radius of CA is achiev­ able, this point is an intersection between the obstacles generated by PB and each of the pieces adjacent to CA. The obstacles are marked as directly adjacent, dividing the bubble between them in half. This condition is tested by similar radius comparisons as those described above.

The shape of infinite obstacles is determined by the same criterion. As shown in Figure 4, they can either be connected to a finite obstacle on one side only, forming a "bulge", or be connected to adjacent obstacles on both sides, thus forming a link between finite obstacles.

Note that all the tests necessary to compute the weak topology graph are linear distance comparisons, and can be handled by quantity spaces ( [Forbus, 1984]) or even order-of-magnitude reasoning ( [Raiman, 1986]). We will discuss the use of the weak topology graph after finishing the description of the algorithms to compute kinematic topology.

2.5 The full topology graph

In the weak topology graph, we have incorporated those aspects of the metric dimensions which can be easily cap­ tured by qualitative representations. However, this can not be enough for a complete description of kinematic topology. For example, deciding whether the teeth of a pair of gearwheels mesh requires evaluation of non­ linear expressions for which we have not even found a closed-form solution. The reason why computing the full topology is hard is that is must take into account the oc­ curence of free subsumptions, intersections between ob­ stacles which are not directly related in the topology graph. Configurations corresponding to such intersec­ tions are characterized by the fact that the objects are in contact at two distinct points .

Devices in which free subsumptions are important are difficult to understand for people also, and we can do so only in very limited cases, such as that of successive teeth touching each other in gearwheels.

However, the situation is not hopeless, because the set of possible subsumptions can often be bounded. The most powerful criterion for bounding the set of possible subsumptions is the extent of an obstacle in configura­ tion space. The valid portions of an obstacle can be en­ closed within two possibly overlapping bounding rectan­ gles, which enclose all valid portions of obstacle bound­ aries. Only pairs of obstacles whose bounding rectangles intersect are candidates for free subsumptions.

In general, testing whether the subsumption actually occurs requires a detailed (and expensive) analysis of the precise dimensions of the objects' shapes. In many practical cases, however, it can be determined that a subsumption must occur, by finding a valid point on an obstacle which falls within the valid region of another. For this purpose, we test whether the configurations corresponding to the touchpoints enclosed by the intersect­ ing bounding rectangles violate the non-intersection con­ straints of the other obstacle. In practical cases, such as gearwheels, this test has proven very powerful and reli­ able.

Both the computation of bounding rectangles and the tests of non-intersection involve the nonlinear function relating radius to angle of touch. They can either be approximated, or computed by manipulating an analog­ ical representation, using fixed parallel structures similar those in vision systems.

A free subsumption is installed in the topology graph by establishing a direct connection between the obsta­ cles involved in the subsumption, dividing in half all intervening bubbles. As the individual bubbles do not have precise boundaries in configuration space, the exact shape of the path is of no importance - in our implemen­ tation, we chose the shortest one (the one that requires modifying the fewest bubbles) .

The resulting structure now correctly describes the kinematic topology of the device. Every free subsump­ tion candidate whose validity could not be determined means that the existance of the corresponding adjacency in the topology graph could not be decided, and the so­ lution is ambiguous. The bubbles and their connectivity represent the topology of the free space. Additionally, each bubble can be associated with the interaction (or rather closeness) of particular object features. The con­ ditions which have resulted in the transformation of the initial topology graph to the full topology graph are a causal explanation for those aspects of the final result. In the topology graph, we mark adjacencies where the actual positions correspond to zero-crossings of the re­ spective orientation parameter. The shape of each region in configuration space - for example, the number of ro­ tations of each gear required to traverse the doubly con­ nected regions for a pair of gearwheels- is determined by counting the traversals of marked links on a path around the region boundary.

3 Applications and Extensions

Kinematic topology by itself is often a sufficient descrip­ tion for reasoning about kinematics. For example, the kinematic topology of gearwheels describes succinctly their behavior as two objects which can turn in coordi­ nated motion. Note, however, that kinematic topology is not a substitute for place vocabularies: the behavior of a clock escapement, for example, is only described as a doubly connected free-space region, which doesn't capture its function.

An interesting aspect is the fact that kinematic topol­ ogy often contains ambiguities. This reflects the ambi­ guity which arises in human reasoning based on rough sketches. For problem solving, it can be an advantage because it points out the possibilities which could be achieved given that the details are chosen in the proper way. In the example of a sketch of gearwheel behavior the interpretation of a functioning set of gears requires very particular shapes and dimensions of the gearteeth, which are far more likely to be violated than satisfied. Yet, the gearwheel interpretation is the only one which exhibits a remarkable and useful function not achieved by most other objects, and is therefore chosen as the desired interpretation.

The algorithm described in this paper has been im­ plemented as part of a research project in automatic mechanism design and has proven robust and efficient . Depending on the example, it is between 500 and 5000 times faster than computing a complete place vocabu­ lary, and can work using less precise object descriptions. However, much more important than the advantages in speed are the generalizations that the method permits.

3.1 Generalizations

An important aspect of kinematic topology is that it is easily generalizable. The topological computation can be extended without great difficulty to devices with more than two degrees offreedom. Because bubbles and obsta­ cles are tokens, their nature does not change in higher­ dimensional configuration spaces. An important differ­ ence, however, lies in the potentially much higher num­ ber of ambiguities which may result in such a device .

Another important generalization is that of object shapes. For reasons of conciseness, we have so far as­ sumed objects to be polygons. The same theory applies, however, to arbitrary boundary shapes, where pieces are defined by convex segments of the boundary, and cav­ ities by concave ones. Imagine the boundary approxi­ mated by a very fine polygon, as shown in Figure 6. Each convex segment is then a sequence of convex ver­ tices (pieces), and each concave segment one of concave vertices (cavities). The obstacles generated by the adja­ cent pieces form one contiguous region of blocked space, and the bubbles generated by the adjacent cavities gen­ erate a contiguous region of free space, possibly broken in half by the succession of the infinite obstacles between them. As the grain size of the approximation becomes infinitely fine, these conjoined regions become the kine­ matic topology of the complex shapes .

Topologically, both the succession of obstacles or bub­ bles can equally well be modelled by a single obstacle and a single bubble, generated by pieces and cavities formed by the convex and concave segments of the boundary curve. The condition for the existance of the combined obstacle is that at least one of its component exists, which is the case if and only if the one at the extremum of the radius exists. If the point of extreme radius is taken as the "vertex" of the combined piece, it will cor­ rectly predict the existence of the combined obstacle. An equivalent result holds for combined cavities.

Note that this generalization requires the same divi­ sion into segments of equal curvature that has already been proposed on independent grounds by vision re­ searchers such as ( [Brady and Asada, 1986]).

3.2 The Bubble Algorithm

The kinematic topology can be used as the basis for an efficient algorithm to compute place vocabularies. The place vocabulary is derived from the kinematic topology by determining the shape of the region boundaries as sequences of different contact relationships, and marking their qualitative directions, which define the inference rules for qualitative analysis (as described in [Faltings, 1987b, Faltings, 1989?]).

When the kinematic topology is given, the place vo­ cabulary computation can ignore most of the actually impossible contact relationships, as the regions of kine­ matic topology contain only legal contacts. The place vocabulary can now be computed in time proportional to its actual size. We also do away with an explicit rep­ resentation of configuration space and all the expensive computation associated with it. Preliminary tests indi­ cate that on typical examples, the bubble algorithm will be about 100 times faster than earlier implementations of the place vocabulary theory. More importantly, the topology-based computation can potentially be general­ ized to more than two simultaneous degrees of freedom, three dimensions, and complex boundary curves.

4 Conclusions

In this paper, we have introduced the concept of kine­ matic topology as a robust model of commonsense rea­ soning about kinematics from very approximate informa­ tion. Kinematic topology is an abstraction of the place vocabulary concept and distinguished by the fact that (i) it is almost always ambiguous, but with a manageable number of possibilities, (ii) requires significantly less in­ formation for its computation, but (iii) is not powerful enough to allow an actual envisionment of the behav­ ior. The prime motivation for the development of the concept was the need for a causal analysis of kinematic topology in an ongoing project to develop a system for automatic mechanism design.

Kinematic topology can be computed in a purely qual­ itative way, and is the first representation of kinematics with this property. It stands in contradiction to the ear­ lier poverty conjecture that no purely qualitative kine­ matics is possible ( [Forbus et a/ , 1987]), and gives an indication of the extent to which we may succeed in the challenge of disproving this negative prediction.

As a practical application, kinematic topology is being used as a basis for place vocabulary computation meth­ ods which are much more efficient and general than was possible before.

Acknowledgements

The authors wish to thank Tom Galloway for help with the implementation, and Suzanne Sellers for comments on earlier drafts on this paper.