Qualitative Kinematics: A Framework

I. Introduction

Recently there has been signficant progress in qualitative physics. However, this progress has focussed on qualitative dynamics, the representation and organization of quali­ tative time-varying differential equations (c. f. :3, 9, 15, 2l i). Qualitative spatial reasoning has mainly been ig­ nored. This paper presents a theoretical framework for qualitative kinematics (or QK), the aspect of spatial rea­ soning concerned with the geometry of motion. Figure l provides an example of a problem involving qualitative kinematics, namely understanding a rachet (from [5)). We exclude problems of navigation, relating function to form, and robotics.

The framework we propose is organized around three ideas:

1. The Poverty Conjecture: There is no purely qualita­ tive general-purpose kinematics.
2. The .W.Dj PV model: Qualitative kinematics requires metric diagrams in addition to qualitative representa­ tions.
3. The Connectivity Hypothesis: The appropriate notion of state for QK concerns connectivity, since changes in connection usually determine when forces change.

We start by explaining these ideas and describing a set of basic inferences for qualitative kineq1atics which can serve as a basis for organizing theories and algorithms. We then illustrate the utility of the MD; PV model two ways. First. we use examples from a working AI program.

FROB [7, 8J. Second, we outline a system being developed which uses this model to reason about mechanisms. such as mechanical clocks. Finally, we analyze other relevant research in terms of this framework and raise questions for further research.

T d

Figure 1: An example of Qualitative Kinematics The parts of a rachet, shown below; are free to rotate. The kinematic problem is, how can they contact each other, and how can they move?

II. A Framework for Qualitative Kinematics

Motion pervades the physical world - things roll, swing, fly, gyrate, spin, and slide. The breadth of the phenom­ ena and wide variation in the kinds of answers we desire argues against a single representation for all of qualitative kinematics. Nevertheless, we believe there are underlying commonalities which, if made explicit, will serve to focus the search for specific solutions. Here we describe what we think these commonalities are.

A. The Poverty Conjecture

The first idea is a conjecture about the limits of quali­ tative representation. Specifically, we claim that there is no purely qualitative, general-purpose kinematics. Unlike qualitative dynamics, where weak representations of time­ varying differential equations suffice for a broad spectrum of inferences. weak qualitative spatial representations ap­ pear virtually useless.

To see this, consider the Rolling problem: Given two objects, can one smoothly roll across the other? For pro­ totypical cases little information is needed: .\ ball can roll across a table, and if two meshing gears are aligned properly then one can roll across the other. But a general­ purpose reasoning system cannot rely solely on prototypes: it must at least have the ability to compose prototypes, and preferably provide the ability to generate new shapes from surface or volume primitives. And here is where purely qualitative representations fail. Without some met­ ric information as to the relative sizes and positions of the parts of a compound surface, the rolling problem cannot be solved. Consider for example two wheels, one with a bump on it and the other with a notch carved out of it. Without more details one cannot say how smoothly they will travel across each other: Both perturbations of the shape could be trivial, or the notch might include sharp corners that cause the bump ·to catch. Stating that the shapes are complementary and their sizes are identical is cheating, of course.

It is difficult to make ."purely qualitative" precise be­ cause there is a spectrum of representations. Clearly a representation which includes elements of !i as constituents is not purely qualitative. Symbolic algebraic expressions, while closer. we still exclude from our conjecture. Repre­ senting a 2D boundary by a list of segments described as concave. convex, or straight , on the other hand. is exactly the kind of tempting representation we are talking about. There are several arguments for the Poverty Conjecture:

1. Negation by failure: Many smart people have tried to find a "pure~ QK for years, without success.
2. Human performance: People resort to diagrams or models for all but the simplest spatial problems [13, 14i.
3. :l. No total order: Quantity spaces don't work in more than one dimension, leaving little hope of concluding much by combining weak information about spatial properties.

The first argument simply makes one think; after all, one could be invented tomorrow. The second argument is more serious. If people can't do it, then we know that it isn't needed to be intelligent . The third argument is the strongest.

What we want from a qualitative representation is the ability to combine weak relationships between its elements to draw interesting conclusions. For numbers inequality information suffices for many inferences. Allen's temporal logic [1] is another example of a system of relationships which individually are weak but together provide enor­ mous constraint . Both Allen's logic and quantity spaces crucially rely on transitivity. And except for special cases, (e. g. equal and inside), transitivity is unusable in higher dimensions. We suspect the space of representations in higher dimensions is sparse; that for spatial reasoning al­ most nothing weaker than numbers will do.

B. The MD /PV model

We believe the best way to overcome these limitations is to combine quantitative and qualitative representations. We call this the MD/ PV model because it has two parts:

• metric diagram: a combination of symbolic and quan­ titative information used as an oracle for simple spa­ tial questions.
• place vocabulary: A purely symbolic description of shape and space, grounded in the metric diagram.

A reasoner starts with a metric diagram, which is in­ tended to serve the same role that diagrams and models play for people. The metric diagram is used to compute the place vocabulary, thus ensuring the qualitative repre­ sentation is relevant to the desired reasoning.

The particular form of these representations varies with the class of problem and architecture, as will be seen below. The quantitative component of the metric dia­ gram could be floating point numbers, algebraic expres­ sions, or bitmaps. The place vocabulary can be regions of free space, configuration space, or something else entirely. The key features are that (a) the place vocabulary exists and (b) it is computed from a metric representation. These features mean that we can still draw some conclusions even when little information is known (by using the place vocab­ 'ulary as a substrate for qualitative spatial reasoning) and that we can assimilate new quantitative information (such as numerical simulations or perception) into the qualitative representation.

C. The Connectivity Hypothesis

We claim that QK state is organized around connectivity. Connectivity is important because contact (of some kind) is required to transmit forces. The kinematic state of a system is primarily the collection of connectivity relation­ , hips that hold between its parts. Changes in connectivity signal changes in QK state. For example, the rachet is clearly in a different state when the pin is against a tooth than when jammed in a corner.

A system's total state is the union of its kinematic and dynamic state. The dynamical component can be repre­ sented in many ways, including qualitative state vectors [7, 8J and Qualitative Process theory [9J. The particular connectivity vocabulary will be domain-dependent .

D. Basic Inferences in Qualitative Kine­ matics

The key to progress In qualitative dynamics was finding appropriate notions of state and state transitions. The use of connectivity for kinematic state suggests a similar set of basic inferences for qualitative kinematics which can be combined for more complex reasoning. These operations are analogous to the basic dynamical inferences of QP the­ ory.

1. Finding potential connectivity relationships: Comput­ ing the place vocabulary from the metric diagram must yield the connectivity relationships that will be the primary constituents of kinematic state. In the rachet this corresponds to finding consistent pairwise contacts . The QP analog is finding potential process and view instances.
2. Finding kinematic states: The constituent connectiv­ ity relationships must be consistently combined to form full kinematic states. Although typically quan­ titative information will still be required (being able to calculate relative positions and sizes is essential), we claim the resulting symbolic description can suffice for the remaining inferences. The result of these first two stages for the rachet is shown in figure 2. The QP analog is finding process and view structures.
3. Finding total states: By imposing dynamical informa­ tion (i.e., forces and motions) complete system states are formed . The key to this inference is identifying qualitative reference frames and the ways in which objects are free to move. The QP analog is resolving influences.
4. Finding state transitions: Motion can eventually lead to change in connectivity, providing kinematic state transitions. Dynamical state transitions are also pos­ sible (pendulums exhausting their kinetic energy. for instance) as well as combinations of kinematic and dy­ namical transitions. Figure 3 shows some transitions for the rachet. The Q P analog is limit analysis.

Figure 2: A Place Vocabulary for the Rachet

Below is a partial representation of the rachet's place vo­ cabulary. The teeth of the rachet are labelled clockwise around the wheel by A, B , . . .. Each node is a configuration space region and each arc indicates a geometrically possible transition between kinematic states. The corresponding physical configuration for several states is shown under­ neath. The arrows in the place graph indicates the path the rachet takes in normal operation. Notice that a transi­ tion to state B12 results in the rachet locking, as expected.

Figure 4: The MD/ PV modeL as instantiated in FROB FROB's representations for a typical motion in its domain are depicted graphically below. By grounding the qual­ itative description of space (the place vocabulary) in a quantitative description (the metric diagram) inference can proceed with weak information, yet allow the re­ sults of more precise data to be assimilated as acquired.

III. Example: FROB

The representational aspects of the :\1D/ PV model were first used in FROB , a program which reasoned about the motion uf point masses (''balls") in a 2D world constrained by surfaces described as line ~egments. FROB's metric di­ agram consisted of symbolic descriptions of points , lines, regions, and other geometric entities containing numeri­ cal parameters. Since only point masses move.d the place vocabulary was a quantization of free space, designed to maximize information available about gravity and energy. Figure 4 illustrates the representations involved.

FROB performed several types of inferences. Given quantitative information it could perform constraint-based numerical simulation. FROB also generated envisionments which were used to predict future motions of the ball, its final state, and whether two balls may or may not collide. The mix of representations allowed FROB to give better an­ swers when given more information. For example, when just told that two balls are in particular (symbolic) places , FROB may not be able to tell whether or not they will col­ lide. But with only a little numerical information, FROB can in some cases ascertain that collisions are impossible by figuring out that the two balls can never be in the same symbolic place. The mix of representations also allowed I>roposed qualitative constraints on behavior to be tested against quantitative simulations.

The inferential structure of the MD ' P V model is new, however, and it is instructive to see how well FROB fits it. Finding potential connectivity relationships in FROB cor­ responds to calculating the place vocabulary. Since point masses have no spatial extent the kinematic states are ex­ actly the connectivity relationships (i.e., where a ball is). FROB's dynamics are organized around qualitative state vectors, so the total state includes the type of activity (e. g., FLY, COLLIDE, etc.), place, and symbolic direction. State transitions are found by determining where the ball might be next, since changes in place are designed to her­ ald changes in activity and direction. In short, FROB is aptly described by the MD /PV model.

IV. The Clock system

Since understanding why FROB worked was a motivation for this framework the conclusion of the previous sec­ tion should not be too surprising. However, we are using this framework to develop a new system (working name: CLOCK) which reasons about mechanisms such as mechan­ ical clocks. While CLOCK is incomplete, it is far enough along to be encouraging.

Methodologically, the MD /PV model suggests split­ ting the system design in half, since the first two inferences require metric diagrams and the last two don't. This ap­ proach has proven successful so far, although of course all the data isn't in. Falting's program starts with a metric diagram and computes a place vocabulary based on config­ uration space [16J. Nielsen's program starts with the place vocabulary, imposes qualitative reference frames, finds po­ tential directions of motion, and computes envisionments. We summarize these programs below.

A. Computing place vocabularies

The input to CLOCK is a collection of shapes described as extended polygons (i. e. segments can be arcs of circles as well as lines). Each part of the mechanism has a defined attachment to a global reference frame, and the union of the parameters implied by these attachments comprises the configuration space (Cspace) for the mechanism.

Each point in Cspace corresponds to a geometric lay-. out of the mechanism's parts. We assume no objects can overlap, hence Cspace is divided into free and blocked parts. The Cspace constraints arising from points of con­ tact between surfaces are the starting point for creating a place vocabulary. The places are quasi-convex and mono­ tone, and it turns out that to satisfy these conditions re­ quires introducing new "free-space divisions" in Cspace (see i6J for details). The computation of places from pairwise object interactions is implemented and has been tested on several examples (including the rachet shown above and an escapement), but the code to combine pair­ wise places into a full place vocabulary is not yet finished.

B. Completing a Qualitative Mechanics

The first step in using the place vocabulary is assigning frames of reference. Reference frames are chosen to max­ imize dynamical information, i.e. along surface normals and surface contact$. Nielsen has developed a qualitative representation for vectors by taking lists of signs with re­ spect to given reference frames. These qualitative vectors are used for representing contact directions, forces, veloc­ ities, and other parameters.

Our dynamics is based on qualitative state vectors, including activities like SLIDE, ROLL, and COLLIDE. The first step ·in determing total state is finding what forces are possible and in which ways objects are free to move. To do this Nielsen has developed a clean theory of "free­ doms", see [17J. Given the freedoms, the possible motions can be ascertained for each kinematic state. Once the mo­ tion for a state is known, the spatial relationships in the place vocabulary can be used to determine state transi­ tions. At this writing the freedom computation has been implemented and tested (see [17]).

V. Other QK systems

Here we examine other QK efforts and relate them to our framework. The earliest are Hayes' Naive Physics papers :u, l2J. His seminal concept of histories was one of the inspirations for this work, and his arguments about the locality of histories (i.e. things don't interact if they don't touch) indirectly suggest the Connectivity Hypoth­ esis. We differ in our view of how rich and varied the spatio-temporal representations underlying histories must be, and see no clues in Hayes' work pointing to the Poverty Conjecture.

Lozano-Perez's work on spatial reasoning for robotics , which led to the configuration-space representation )6! is obviously pivotal to our approach. We expect that progress in robotics will lead to complementary progress in QK.

Gelsey's system for reasoning about mechanisms )01 fits the MD / PV model perfectly. His metric diagram is a constructive solid geometry CAD system, and his place vo­ cabulary is the set of motion envelopes and kinematic pairs computed from this representation. His system only per­ forms kinematic analysis (it does not generate total states or full qualitative simulations), but one can easily imagine adding this capability to make a complete mechanisms rea­ soner. We believe his geometric analysis, being heuristic , is more limited than our configuration-space approach .

Stanfill's system [20] is organized around prototypical objects, with all the advantages and limitations of that approach.

Several attempts to axiomatize QK have been made, notably by Shoham [l8J and Davis i2J. While suitably formal, neither have been very successful. Shoham 's for­ malization of freedoms is far more complex and less useful than Nielsen's. who can handle surface contact and par­ tially constrained objects. Davis has made an excellent case for the addition of non-differential, conservation-like arguments to qualitative physics. However, the generality uf his formalization is not yet convincing.

VI. Discussion

A complete account of qualitative physics must include qualitative dynamics and qualitative kinematics. We have presented a framework for QK in hopes of speeding progress in this area. We believe the framework explains why there has been so little progress; many failures, never reported in the literature, have been attempts to build a purely qualitative kinematics. If the Poverty Conjecture is right much of this effort has been wasted.

Our claims are not all negative; we offer the MD /PV model as a characterization of successful research in QK, both in our group and others cited above. The MD/PV model offers a new set .of research questions and opportu­ nities:

• Form of metric diagram: There is a spectrum of po­ tential representations for metric diagrams. Little is currently known about which are useful for what tasks.
• Form of dynamics: When is a qualitative state vec­ tor description versus a process-centered description appropriate? Are there other reasonable possibilities? Can the distinctions introduced in QK provide a foun­ dation for formalizing spatial derivatives?
• Theory of places: What are the commonalities under­ lying place vocabularies across various domains? It appears convexity, or at least quasi-convexity, is im­ portant . More empirical studies are needed to gain the insight needed for a general theory.
• Links to vision and robotics: We view Ullman's the­ ory of visual routines [22! in part as a theory of human metric diagrams. Understanding these routines better could lead to improvements in QK, and QK theories of place vocabularies may provide theoretical sugges­ tions for what spatial descriptions people might be computing.

VII. Acknow ledgernents

This research was supported by the Office of Naval Re­ search, Contract No. N00014-85-K-0225.