Naive Kinematics: One Aspect of Shape

1. Introduction

Different sorts of reasoning make different use of the "shape" of objects. The notations devised so far have typically been "autonomous" in nature: the shape of each object is described independently, and the problem of reasoning about the interaction between several objects is relegated to the user of the shape representation. In these notes my primary concern is exactly the interaction between several physical objects. would like to be able to reason about questions like

• If I place a smooth plate on a smooth table - will it move if pushed sideways!
• If I bang a nail into the wall - will it move if pushed sideways at its base!
• Why can you stack spoons economically {in term of "wasted space") but not knives!
• What is the magic quality of M.C.Escher's Fish'n'Bird drawings!
• What geometric features makes a piston work!

The two central notions in reasoning about such issues seem to me to be goodne88 of fit and amount of freedom . The goodness of fit between two shapes says something about how much one shape needs to be mutilated in order to be made identical to the other. The amount of freedom of one shape with respect to another is a statement about the physical world

• if you had objects of the two shapes, how would the movement of the first be constrained by the second.

Naive Kinematics: one aspect of shape

Yoav Shoham Computer Science Department Yale University 10 Hillhouse Avenue New Haven CT 06520

To illustrate the probably obvious distinction between the two notions, consider the configuration of two objects A and B shown in Figure 1-1. 1

The fit between the two shapes is lousy, but placing the cross inside the square {in the only possible position) gives it zero amount of freedom.

A notion similar (and at some places identical in name) to "freedom" appears in the literature on the kinematics of machinery 2 . Interestingly, the earlier literature from the 19th century is very close in spirit to my formulation while the later literature is farther apart. We will see that my formulations are actually a generalization and formalization of some principles expressed by Reuleaux in the 1870s. Reuleaux uses the word Kinematics in a restricted sense to denote the science of constrained motion, without reference to ideas such as time or force {A.B.W.Kennedy, his translator, suggests the term Metastatics). It is in this sense of the word that one can view my formulation as naive kinematics. I will discuss the kinematics literature in a later section.

This work was done as part of the "commonsense summer" project at the AI center at SRI International. The purpose of that project was to begin the creation of a large database of knowledge about the real world, and in order that the formulations of different people be integrable it was decided that all theories be expressed in first order predicate calculus {or at least be readily translatable into it). In [Hobbs 84] a fuller version of these notes appears which makes an attempt to make the theory of naive kinematics formal, but in these notes I will be largely informal. In that report I also analyze the concept of {\it fit}, which will not be mentioned any more in these notes. I have another reason for referring the reader to [Hobbs 84) beside as a more detailed description of Naive Kinematics; there are other papers there that fit in nicely with my formulations. Particularly relevant are the reports by Greg Hager and Henry Kautz, attempting to axiomatize materials and space respectively.

11'11 be restrictins the discussion in these notes to 2-spaee. I don't know how well thinss scale up to 3-space.

ZJ·m indebted to Ken Forbus for direetins me to that literature and in particular to the work of F. Reule aux.

Organization of the sections:

Section 2 is concerned with translational freedom and Section 3 with rotational freedom. These formulations have an unintuitive property that is brieny discussed in Section 4. Section 5 discusses the literature on kinematics, and section 6 summarizes these notes and points out where more research is needed.

2. Translational freedom

The freedom of an object in a spatial configuration characterizes its possible motions assuming the rest of the configuration is static. The freedom of an object with respect to another (in a configuration 3 ) is its freedom assuming that it and the other object are the only objects in the configuration.

The two basic motions of an object are translation and rotation. In this section I consider translational freedom, and in the next section rotational freedom. There are two fundamental axioms of translational freedom.

2.1. The first axiom of translational freedom

At any point on a curve the tangent curve may or may not be well defined. Ir it's not then (in our domain) that curve forms an angle at that point. In fact, the case where a tangent exists can be viewed as a special case where the angle is rr.

Figure 2-I describes the general case of two objects touching at a point. OBJ and OBST touch at PI and the curves of their boundaries form angles a and 1 respectively (either or both of which could be equal to rr, and in the latter case the two curves would be tangents of one another at PI).

Let assume some global frame of reference, so that the orientation of PI-P2 is, say, I . The first axiom of translational freedom says that in the given configuration the translation of OBJ is restricted by OBST to be (going clockwise) between the rays R1 and R2 (inclusive), where

the orientation of R1 is

l+a-rr, if a+6>=rr

8-6, if a+6=<rr

Note: if a+6=rr then rr+a-=8-6

and the orientation of R2 is

8+rr, if a+fJ>=tr l+a+{J, if a+{J=<rr

Note: if a+{J=tr then 8-=P+a+{J (MOD 2rr))

Figure 2-2 shows one application of the first axiom of translational freedom.

2.2. Special eases of the first axiom of translational freedom

Case !.:.. a=rr or ~tr

In this case either OBST or OBJ have a tangent at PI, and if they both do then they have the same tangent. The freedom allowed by PI is the half plane on the OBJ side of the tangent (again, including the tangent itself).

In this case the freedom allowed by PI is the plane segment whose borders are (going clockwise) l+a-tr and l+tr (inclusive). The situation is shown schematically in Figure 2-3.

This is the similar to the previous case, only here it's the obstacle that has an refiect angle. In this case the translation of OBJ is restricted by Pl to be (going clockwise) between 1-6 and l+a+{J.

Notice that Case 1 is actually the limiting case of both Case 2 and Case 3.

2.3. The second axiom or translational freedom

Let us call a point where an object touches an obstacle (in a configuration) a touchpoint of that object (in the configuration).

The translational freedom of an object is the intersection of translational freedoms allowed by all its touchpoints.

2.4. Examples or the second axiom of translational freedom

Example l OBST2 0 OBJ

Figure 2-4 describes a circle trapped by three circular objects. There are three touchpoints - say Pl, P2 and P3 corresponding to the objects OBSTl, OBST2 and OBST3. They individually restrict the direction of translating OBJ to the following plane segments:

The intersection of these allowable plane segments is empty, and so OBJ has no freedom whatsoever.

Example g_

Figure 2-5 describes a two dimensional piston in a cylinder. Considering the piston as our object and the cylinder as an obstacle we compute the freedom of the piston in the configuration. There are an infinite number of touchpoints - all those between A and B and all those between C and D. However all the points between A and B place an identical restriction on the translation of the piston, as do all the points between C and D. Let Pl be any point on the former segment and P2 any point on the latter one. They restrict the movement of the piston as follows:

Since the boundaries of these restrictions are included in the freedom direction, the intersection or the directions allowed by Pl and P2 (and therefore the intersection of the directions allowed by all touchpoints) is {0,11"}, that is in either direction along the x-axis.

2.6. Theorems on translational freedom

The following are theorems that fall directly out of the two axioms of translational freedom. They are not the only important ones, but will serve to illustrate the power of the axioms.

The Two Point theorem

You need at least two touchpoints to eliminate translational freedom of an object.

The Three Point theorem

You need at least three touchpoints to eliminate translational freedom of a convex object by convex obstacle(s).

The Three Point theorem relies on the following Lemma: The translational freedom of a convex object that is allowed by a single touchpoint spans an arc of at least 11'.

A amooth object is one whose boundaries have no angles different than 11'.

The Two Obstacle theorem

Given an and object and two smooth obstacles or a smooth object and any two obstacles it is possible to arrange them in space so that the translational freedom of the object is limited to the two directions along some single axis 4 ·

The theorem Q{ Maximum Effect

Suppose you're given an object Obj and an obstacle Obst and you are required to arrange them in space so that they touch at a single point and so that the translational freedom of Obj is minimal. The theorem states that your arrangement must have them touch at a point where the boundary or either Obj or Obst forms the largest angle such that the other can be arranged to touch there and only there.

3. Rotational freedom

The treatment of rotational freedom is only slightly more complex than that or translational freedom, and most or the ground work has already been done in the previous section. Any rotation is defined by its center (a point in space) and its direction (clockwise or counter-clockwise). Our axioms will state for each point in space whether it can serve as an center of a clockwise rotation of the object and whether it can serve as an axis of a counter-clockwise rotation of it. As for the translational case, there are two fundamental axioms of rotational freedom.

3.1. The first axiom or rotational freedom

Consider again the general schema of touching in Figure 2-1. The first axiom of rotational freedom states that the clockwise rotation of Obj allowed by P is around all points that lie in the space segment trapped (going clockwise) between the rays Rl and R2, where

the orientation of Rl is

O+o-11'/2, i.f o+6>=1r

4 Can the condition of smoothne8ll be weakened or even dropped! I think that at least the former.

8-6+11'/2, if o+6=<11'

(Note: if o+6=11' then l+o-11'/2=1-6+11'/2)

and the orientation of R2 is O+o+/J+ll'/2, if o+fJ=<ll' 8-11'/2 if o+fJ>=ll'.

(Note: if o+{J=ll' then

O+o+/J+ll'/2=8-11'/2 (MOD 211') )}

The statement on the clockwise rotation is similar:

the counter-clockwise rotation of Obj allowed by P is around all points that lie in the space segment trapped (going clockwise) between the two rays Rl and R2, where

the orientation of Rl is O+o+ll'/2, if o+6>=11' 8-f>-11'/2, if o+6=<11' (Note: if o+6=11' then l+o+~2=8-f>-~~MOD2~) and the orientation of R2 is O+o+fJ-11'/2, if o+fJ=<ll' 8+11'/2, if o+fJ>=ll' (Note: is o+fJ=ll' then O+o+fJ-11'/2=8+11'/2)}

In all cases the rotational freedom includes the rays themselves.

Figure 3-1 shows one application of the first axiom of rotational freedom.

3.2. Special cases or the first axiom or rotational freedom

Case £ o=ll' or 1=11'

In this case the plane is divided into four quadrants, the Y axis being the tangent to Obj or Obst (or their common tangent, if both have one). The clockwise rotational freedom of Obj are the two bottom quadrants and the counter-clockwise rotational freedom of the two objects are the two top quadrants (see Figure 3-2). The points on the X-axis (the normal to Obj or Obst or both) belong to both rotational freedoms.

The clockwise rotational freedom is (going clockwise) between the rays 9+a-~r/2 and 9-~r/2. The counter-clockwise rotational freedom is (going clockwise) between the rays 9+o+~r/2 and H~r/2.

The clockwise rotational freedom is (going clockwise) between the rays 9-6+~r/2 and 9+a+fJ+~r/2. The counter­ clockwise rotational freedom is (going clockwise) between 9-6-~r/2 and Ha+fJ+~r/2.

Notice that here too Case 1 is the limiting case of both Case 2 and Case 3.

3.3. The second axiom of rotational freedom

The clockwise (counter-clockwise) rotational freedom of an object (in a configuration) is the intersection of clockwise (counter-clockwise) rotational freedoms allowed by all its touchpoints (in the configuration).

3.4. Examples of the second axiom of rotational freedom

We can use the two examples from the section on translational freedom to illustrate the second axiom of rotational freedom.

Figure 2-4 described a circle trapped by three circular objects. There were three touchpoints - say Pl, P2 and P3 corresponding to the objects OBSTl, OBST2 and OBST3. They individually restrict the rotation of OBJ to the following plane segments:

Recall that the segment boundaries are included in the freedom. Thus the intersection of the segments of clockwise freedom is the center of the circle as is the intersection of the segments of counter-clockwise freedom. That means that the only rotation possible for the circle is about its center, in either direction.

Figure 2-5 described a two dimensional piston in a cylinder. All the points Pl between A and B allow different rotational freedom as do all the points P2 between C and D (although as we saw that was not the case with translational freedom, where all the points Pl allowed the same freedom as did all the points P2). However it is easy to show that as we move left on AB the clockwise rotational freedom only decreases and as we move right the counter-clockwise rotational freedom only decreases. Since we are interested in the intersection of all such freedoms anyway we can restrict our attention to points A and B. By a similiar argument the· only points on CD that we need consider are C and D. The rotational freedom allowed by each of these points is shown is shown in Figure 3-3.

The intersection of the four plane segments of clockwise rotational freedom is empty, and the same holds for the segments of counter-clockwise rotational freedom. The piston therefore has no rotational freedom at all .

3.6. Theorems on rotational freedom

As for the translational case we give some theorems that illustrate the power of our formulation.

The Two Point theorem

You need at least two touchpoints to completely eliminate rotational freedom of an object in a given direction (clockwise or counter-clockwise).

The Three Point theorem

You need at least three touchpoints to eliminate all rotational freedom of an object.

The reader is urged to read Section 4 before trying to come up with counter-examples to this last theorem.

The Two Obstacle theorem

Given a smooth object and two obstacles of any shape or two smooth obstacles and an object of any shape you can arrange them in space so that the rotational freedom of the object is completely eliminated in one direction - unless the object is a circle. (Here too the smoothness requirement can probably be weakened).

The Incomparability theorem

There exists a configuration where an object has ze;-o translational freedom but some rotational freedom. There also exists a configuration where the converse holds - an object has some translational freedom but no rotational freedom.

(Proof: see Figures 2-4 and 2-5).

Ir the limiting case of zero freedom serves to distinguish between the two kinds of freedom, the opposite limiting case relates them:

The theorem !1f Absolute Freedom

An object has total translational freedom in a configuration if and only if it has total rotational freedom in the same configuration.

·· An observation about the nature of freedom

Our formulations so far have been "local" in flavor, that is we discuss freedom in term of touchpoints. This causes some unintuitive results. For exampl_e, does the object in Figure 4-1 have translational freedom! Does it have rotational freedom!

The answer to both questions is yes in our system, although in both cases it is freedom that is deprived as soon as it is exercised. The translational freedom is along the X-axis and the rotational freedom is in either direction around all points on the Y-axis. Fortunately these controversial cases tend to arise when there are very few touch points, and usually there will be many. Still there's something discomforting about such a result, and the solution seems to me to define something that might be called "continuous freedom" (either translational or rotational). Some theorems will extend from freedom to continuous freedom (like the Three Point theorem for translation) and some will fail to do so (like the Three Point theorem for rotation). I don't pursue this further in these notes.

li. Naive kinematics and real kinematics

When I started this work I intended to make concrete some notions that seemed to me intuitive and fundamental for reasoning about objects. In doing that I found my work, and in hindsight not surprisingly, overlapping with that of researchers in the kinematics of machinery. As early as 1876 F. Reuleaux stated that

... the elementary ... parts of a machine are not 8ingle, but occur always in pair8, so that the machine, from the kinematic point of view, must be divided rather into pair8 of element8 that single elements. ( IReuleaux 761 p.86).

Reuleaux then goes on to state assumptions that are very close to the ones I used - objects are rigid, space is fiXed (i.e. a global frame of reference), only one object can move. He then has two sections - "Restraint against sliding" and "Restraint against turning". As might be expected these deal respectively with what I have termed translational freedom and rotational freedom. It turns out that in both cases Reuleaux considered Case 1 of sections 2.2 and 3.2. This amounts to the assumption that all objects are everywhere "smooth", that is the tangent to their boundaries is defined everywhere. My results for this special case are identical to Reuleaux's. He also gives an informal version of the Three Point theorem for translational freedom, and analyzes cases of rotational freedom where three, four and five points are need to completely eliminate rotational freedom. Like in these notes Reuleaux restricts the discussion to 2-space. In 1897 P. Somov proved that in 3-space at least seven points of contact are needed to completely eliminate freedom ( (Somov 97]).

To avoid giving the wrong impression it must be emphasized that these issues are only a small part of what these learned kinematicians are concerned with. They only introduced them in order to define complicated notions like the crank and the screw-pair, so they could reason about actual machines like the newly-invented train. In fact as far as I could see in most of the more recent texts this introductory analysis doesn't appear -for example in the texts by Hardison (1979), Dijksman (1976), Shigley (1959), Sue & Radcliffe (1978), Hinkle (1953), Barr (1899), Guillet (1940) and Beyer (1963).

The concernes of these texts are typified by a quote from (Hardison 79)

A major aim !of this book isl to provide explanations for ... the more difficult concepts.

Computers of course need explanations for the "easy" concepts too, and it is those I've been concerned with in these notes.

One exception is (Rosenauer & Willis 53) where Reuleaux's results are reproduced in a slightly more rigorous way, and new terms are used which may not sound totally unfamiliar- "field of translational (rotational) freedom", "field or restraint".

Current interest in robotics has produced more recent related work. One example is (Salisbury 82) which analyzes possible designs for a robot hand. Based on this analysis one was in fact built - the Stanford/ JPL three-fingered hand. Involved in the analysis is classification of surface contacts, which unlike my (or Reulaux's) treatment allows friction. His analysis of them is by determining the "degree of freedom" of each contact type, rather than directly in terms of translational and rotational freedom.

What then is the relation between Naive Kinematics and the real thing! The answer seems to me that the naive version is concerned with the basic notions underlying the kinematics of machinery, which were explicated more than one hundred years ago when some folks were attempting to make the kinematics of machinery a science rather than an engineering discipline, and that in the meanwhile have been somewhat neglected. In the process of recreating that information I arrived at a formulation that is more general than the original one. We can now build on top of that basis a richer theory - but it will probably look very different from the one found in the kinematics literature. Gears, cams, linkage chains and screws are unlikely to appear in the formulation, at least not at the early stage they do in in kinematics.

8. Summary

• I have outlined an approach to object representation - instead of describing each object without regard to other objects, center the representation around the relation between objects. In doing that there are two main notions to consider
• freedom, which I analyzed here, and fit, which I did not.

There are several directions in which the analysis offered in these notes should be extended:

• The notion of fit should be analyzed and related to freedom. Some results along those lines are offered in my report in (Hobbs 84), including an application to robot grasping.
• I mentioned the unintuitive "local" fiavor of the formulation, and suggested that it could be avoided by defining "continuous freedom" .
• A ricb library of "shape tuples" should be created, each analyzed in terms of fit and freedom. In doing that one important issue is abstracting away from configurations: we want to know the relation between two shapes regardless or how they are
• embedded in a specific spatial configuration. In terms of our our formal notation in (Hobbs 84), we want to get rid or the "configuration" argument to the FREEDOM and FIT predicates. This can be achieved by essentially quantifying over configurations In a sense this is where things get really interesting - in these notes I have only provided the machinery for creating such a knowledge base.
• Natural language concepts such as touch, contact, pointed, aligned, abut, rap around, encircle, trap, lean against, tangled, fit like a glove, hold, grasp, grip, pinch, clasp, slide along, turn, insert, "guide" , hinge, bottleneck, wedge, hang and others could be analyzed m terms of concepts defined in these notes.

Aclr.nowledgementa

This work was done while I was at the AI Center at SRI International and supported by a gift from the Systems Developement Foundation. Thanks to Jerry Hobbs who organized the project and supervised this research, to Greg Hager and Henry Kautz with whom I had useful discussions, and to the other participants of Commonsense Summer. Pat Hayes and Ernie Davis gave detailed comments on previous versions of this paper. Tomas Lozano-Perez and various members of the Mechanical Engineering Department at Stanford helped fill in the gaps in my knowledge of robotics.