Conceptual Design and Artificial Intelligence

1 Introduction

The broad goal of our research is to derive computa­ tional theories of conceptual or pre-parametric design. As manufacturing technologies change, as new materials are developed, as new design constraints emerge (designs with recyclable parts, and designs that assemble and dis­ assemble easily) , as products become more complex, as the need to build in continuous improvement into design processes emerges, basic conceptual design procedures for electro-mechanical systems require broadening with effective use of computer tools in the early stages of de­ sign. Our specific aim is to use methods from artificial intelligence, especially qualitative physics and constraint programming, with techniques from computational ge­ ometry and symbolic mathematics to build new compu­ tational prototyping tools for conceptual design.

2 A Case Study

While the talk will present several case studies of effec­ tive tools for conceptual design in a variety of domains, the rest of this paper is devoted to an illustration in the context of mechanism synthesis 1 . Mechanisms are an im­ portant part of most electro-mechanical systems. They transmit motion from one rigid body to another. Our design system takes as input constraints on the motion of a mechanism in qualitative, mathematical form. As output, it produces a systematic enumeration of mech­ anism topologies and geometries that satisfy the given constraints. It also performs high-level simulation to demonstrate the feasibility of the design. The concep­ tual designs produced by our system can be refined and optimized by constraint-solving systems that select can­ didate designs based on cost, material, manufacturing and assembly constraints.

·This work is supported by NSF-IRI-8902721, the Xerox Design Research Institute, and the Moore Fund.

1 This is joint work with my student Cheuk-san (Edward) Wang.

The running example used in this paper is the syn­ thesis of a windshield wiper whose input power is pro­ vided by a motor rapidly rotating around the z axis and whose output is an oscillation in the yz plane with low frequency. Note that this a partial description of the input and output motions of this device.

The first design enumerated by our system is shown in Figure 1. It employs a worm spur which converts the uniform input rotation around the z axis to one about the x axis. The output of the spur gear drives a crank rocker . The overall output is tapped from the rocker. Dimensions, positions and orientations of the gears and the crank rocker are calculated by the system. Another design generated by our system satisfies the same mo­ tion specifications using a rack and gear pair, where the rack is driven by a slider crank with the crank being ro­ tated uniformly by a worm spur pair. The worm itself is connected, in both cases, to a motor shaft.

There are several unique aspects of our method. We have a uniform representation for constraints, and can take them into account during the synthesis process. In this example, motion constraints as well as dimensional constraints are handled simultaneously. The synthesis process is very efficient. The example synthesis above was generated in about half a second on a Spare station. Relevant constraints are enforced as soon as they become applicable. This is what makes the generation process efficient: we elaborate this point in Section 7.

The synthesis process is grounded in a mathematical theory of motion composition that is based on configura­ tion spaces. We compile the algebraic theory of motion synthesis into a qualitative form that preserves essential distinctions for the specification and solution of a large class of kinematic synthesis problems. We introduce a property called join preservation which is a constraint on a qualitative motion language that is needed to guar­ antee the generation of correct designs. Our synthesis algorithms are actually implemented and are currently being field tested at the Xerox Webster Design Research Center. ·Our program has produced innovative designs for a number of common devices described in [19]. An interesting set of egg-beater designs in shown in Figure 4.

2.1 The Problem: Motion Synthesis

We now describe the synthesis problem addressed in this paper in detail. Kinematic synthesis is the problem of determining a three dimensional structure of rigid parts that implements a given motion specification. Kinemat­ ics only considers motions and not the forces that cause the motions. Conceptual kinematic synthesis is generally acknowledged to be a very difficult problem. A modern textbook in the area [18] states that

The designer generally relies on intuition and experience as a guide to type and number syn­ thesis. Very little supporting theory is available in these areas.

Conceptual synthesis of mechanisms is difficult because designs are typically specified in incomplete terms and by their intended use (e.g., a fruit-picker or a fuel-hose con­ nector). There is no general theory that relates function and structure in mechanical devices. That is, the space of mechan,isms that achieves a given functional specifica­ tion is not exhaustively and systematically enumerable. Compendia such as Artobolevsky's catalog [1] provide a library of known mechanisms indexed by type (lever mechanisms, e.g.) and function (e.g., indexing) . They are a useful starting point for a designer who can then use systematic adaptation of these designs to create devices which meet the specified functionality. The derivation of the motions that accomplish a given function is an open problem that is not addressed in this paper. Given the motions, we call the problem of designing a struc­ ture that generates them, the motion synthesis problem.

This is also difficult to solve as it involves deriving ge­ ometry from motion. Most of the current work on con­ ceptual design of mechanisms focuses on this problem [6, 11, 14, 15, 16, 26].

Previous work in this area falls under three major cat­ egories: structural, behavioural and functional theories of synthesis. Structural theories[6] generate mechanism topologies systematically, usually from specification of the number of links and the total number of degrees­ of-freedom of the mechanism. Pure structural theo­ ries of synthesis result in a generate-and-test method for producing mechanisms given input-output motion specifications. This procedure is usually quite expen­ sive, and it is generally difficult to exploit information about the desired motion to control the enumeration phase. Behavioural theories derive the structure of a mechanism from specifications of its output and input motions. They fall into two categories: compositional and non-compositional. Compositional theories of mo­ tion synthesis [16, 24, 9, 5], assume the presence of primitive or atomic building blocks which implement simple input-output motion specifications. They pro­ vide methods for systematically breaking down a com­ plex input-output specification in terms of the primitive ones. Compositional theories typically address the syn­ thesis of large scale electro-mechanical systems. Non­ compositional theories [11, 14] build structures "from scratch" that satisfy given motion specifications. They are typically used for small-scale electro-mechanical sys­ tems or the synthesis of specific parts. Functional theo­ ries are theories that work from intended function of a device and derive a structure that performs that func­ tion. Functional theories of synthesis posit intermedi­ ate behavioural specifications and then design structures that generate those behaviours. Few functional theories exist in the literature: [7] and [10] take kinematic func­ tion into account in the design of mechanism topologies.

This paper is organized as follows . In Section 3, we formally define motion specifications in terms of configu­ ration spaces and introduce abstract and concrete mech­ anisms . The operators which compose abstract mecha­ nisms and their concrete counterparts are presented in Section 4. The composition operators form the basis for a rigorous specification and solution of the motion synthesis problem in Section 5. In Section 6, we discuss tractable qualitative representations of the configuration space descriptions manipulated by our algebraic synthe­ sis method. We then present efficient constraint solv­ ing algorithms that use the qualitative representations. These algorithms have been implemented in CLP(n) [27] and we present examples of interesting syntheses in Sec­ tion 7. We conclude by reiterating the main contribu­ tions of our paper and provide a discussion of future work on the problem of automating motion synthesis, and more generally on the problem of conceptual design.

3 Configuration Spaces, Motions, and Mechanisms

We briefly review the concept of a configuration space before formally defining the motion of an object . Let FA be a Cartesian frame embedded in the object A , and let Fw be the fixed frame. The origin OA of FA is the reference point on A.

Definition 1 A configuration of A is a specification of the position and orientation of FA with respect to Fw. The configuration space of A is the space C of all possible configurations of A.

The motion M of an object is a description of how its configuration changes with time. The configuration of a planar rigid body undergoing pure rotation at timet, is (xA, YA , O(t)) where XA and YA are fixed. (xA , YA) , the center of rotation, is also the origin of FA , and O(t) is the angular orientation of FA with respect to Fw, at timet .

Definition 2 The motion of an object is a continuous function from time to its configuration space.

Now we are ready to formally define a mechanism. Reuleaux [23] defines a mechanism as "a combination of rigid bodies so formed and connected that they move upon each other with definite relative motion." We dis­ tinguish between an abstract mechanism which is a rela­ tion on the configuration spaces of the input and output links, from a concrete mechanism which is a 3D arrange­ ment of rigid bodies that implements this relation. The difference between an abstract and concrete mechanism is that while an abstract mechanism describes what a mechanism does, the concrete mechanism is a specifica­ tion of how it does it.

Definition 3 An abstract mechanism is a relation n which is a subset of I x 0 where I and 0 are config­ uration spaces of its input and output links respectively.

Consider a meshed gear pair A and B on the xy plane with fixed centers at (xA , YA) and (xB, YB) · a > 0 is the gear ratio, and ¢ is the initial difference in angular position between the local reference frames attached to the centers of the two gears. It implements the relation 9 ~I x 0, I= {(xA ,YA,O) I 0 E [0, 27r)} and 0 {(xB, YB , tf;) I tf; E [0, 27r)} ,

This description 2 has abstracted structure and could well be implemented by any mechanism that transforms uniform unconstrained rotation around the z axis at (xA, YA) to uniform unconstrained rotation of the op­ posite sense with angular velocity scaled by a around the z axis at ( x B, YB). Note that 9 has only one de­ gree offreedom, namely 0. All other components of this relation are either constants or can be calculated from 0.

Definition 4 The degree of freedom (DOF) of the ab­ stract mechanism n is the dimension of n.

The definition of an abstract mechanism provided above, is precise, but sometimes unintuitive. It is hard to un­ derstand the behaviour of a mechanism as a general alge­ braic relation on multi-dimensional configuration spaces. This motivates us to define an abstract mechanism as a set of pairs of input and output motions.

2 We have omitted the relation between center distance and pitch diameter of the gears for simplicity.

Definition 5 Let n be an abstract mechanism satisfy­ ing Definition 3, and let M; and M0 be motions of the input and output links respectively. Then this abstract mechanism can be defined alternatively as n'' where

While n is a relation on configuration spaces and relates the instantaneous positions of the input links with those of the output links, n' is a relation between two motions.

The implementation of 'l abstract mechanism-a concrete mechanism, is a g, .. .1etric description of links and joints between links . This description is stored as a kinematic diagram annotated with a set of constraints.

Definition 6 A concrete mechanism is a pair (K, C) where K is the kinematic diagram of the mechanism and C is a set of geometric and dimensional constraints on K. There are two distinguished classes of links in K - input links I, and output links 0. The relation between the configuration spaces of the input and output links of (K, C) is its corresponding abstract mechanism.

Following Freudenstein [8] , we use graph theory to for­ mally specify a kinematic diagram. The kinematic graph K of a concrete mechanism is an undirected graph (V,E) , where V is the set of vertices that denote the links, and the edge set E represents the kinematic pairs. The edges are labeled according to joint type [23] . There are one or more nodes in V standing for the input and output links of the mechanism. An annotated kinematic graph has al­ gebraic constraints on elements of V and E represented as a constraint set C.

4 Composition of Mechanisms

Complex mechanisms are composed out of simpler ones. During composition, we construct the relation (It, 0 2 ) from (It, Ot) and (h 02) by imposing the equality con­ straint Ot = I2. Two configuration spaces are equal if and only if they denote the same set of configurations. To enforce the equality constraint between two configu­ ration spaces, we intersect them to obtain the configu­ rations common to both sets.

Definition 7 The composition l><l of two abstract mech­ anisms Rt ~ It X Ot and n2 ~ I2 X 02 is

An example of composition of two abstract mecha­ nisms is illustrated with the construction of 9T that can be implemented by a gear train, from two relations 9t and 92 that can be implemented by gear pairs. We use the relation in Equation 1 to define 9t and 92.

{(xA,YA,O,xB , YB,~' ) I tf; = -atO+¢}

The gear ratios a 1 and a 2 are both positive. From QT, we can derive the fact that t~;' = -a2 ( -a18 + ¢>) + ¢>' by algebraic simplification. We can define a corresponding notion of composition using Definition 5 where the con­ straint is that the output motion of one mechanism be made equal to the input motion of the other.

When two concrete mechanisms, (K1, CI) and (K2, C2), that implement relations 'R1 and 'R2 are com­ posed, a rigid connection is formed between the output links of K1 and the input links in K2 . The constraints, cl and c2, are merged.

Definition 8 Let the concrete mechanisms (K1, CI) with K1 = (V1, EI) and (K2, C2) with K2 = (V2, E2) implement 'R1 ~ /1 x 01 and 'R2 ~ /2 x 02 respec­ tively. The new concrete mechanism (K, C) that im­ plements 'R1 l><l 'R2 can be formed from (K1, CI) and (K2, C2) , (denoted (K, C)= (K1, CI)·(K2, C2)} by hav­ ing C = C1 UC2, V = V1 UV2, E = E1 UE2 and by adding edges denoted rigid connections between output links in vl and corresponding input links in v2.

More complex compositions of multi-DOF abstract mechanisms and their concrete counterparts can be per­ famed in our framework.

5 Formal Problem Specification

We now cast the synthesis problem in the formal frame­ work for motions and mechanisms that we have just introduced. Synthesis problems are rarely posed with complete specifications of the desired input and output motions. Typically, constraints on the motions are given which define a class of abstract mechanisms, and not a particular one.

Definition 9 The general synthesis problem is to find a concrete mechanism (K, C), given constraints on an abstract mechanism 'R ~ I x 0.

The construction of K from the partial specification of the relation 'R solves the type and number synthesis prob­ lem. The solution of C solves the dimensional synthesis problem. ·

Like [15], we view mechanisms as motion transform­ ers. Our compositional approach to solving the gen­ eral synthesis problem grounds the syntheses in a set of primitive motion relations (abstract mechanisms) 'Rp and associates with each a set of concrete implementa­ tions (Kp, Cp)· In the first phase of synthesis, we find a composition of abstract mechanisms which satisfies the given constraints on 'R. In the second phase, we choose concrete implementations of the primitive relations. We will show that this method is sound: that is, it produces concrete mechanisms which implement the given motion specifications.

Definition 10 The abstract synthesis problem is to find a sequence of abstract mechanisms, 'R1, 'R2, . . . , 'Rn, with known concrete counterparts, where 'R1 l><l 'R2 l><l ·· · l><l 'Rn satisfies the given constraints on 'R.

A simple incremental, generate-and-test algorithm for solving this problem starts with the identity abstract mechanism I (I = 0) and computes joins of primitive relations 'Rp until the composition satisfies the specifi­ cation. For each primitive abstract mechanism we non­ deterministically pick an implementation. We use Defi­ nition 8 to compose concrete mechanisms. This process involves simultaneously solving dimensional and geomet­ ric constraints from each of the chosen primitive imple­ mentations.

Definition 11 The concrete synthesis problem is to find a set of concrete implementations (K;, C;), 1 ::; i ::; n for each element in the composition 'R1, 'R2, ... , 'Rn, which solves the abstract synthesis problem for the given con­ straints on 'R, such that Uf;:;: 1 C; is satisfiable.

Theorem 1 The synthesis process: solving the abstract synthesis problem followed by concrete synthesis, is sound. That is, if it produces a solution, it will satisfy the specified motion constraints.

To prove completeness, we need to establish that the method will find an implementation of all specifications expressible in the configuration space formalism. The only way to prove this is to show that our primitive rela­ tion set can reconstruct any configuration space relation. Currently, our set of abstract mechanisms is incomplete: work is underway to construct a complete set.

We now discuss the computational complexity of the abstract and concrete synthesis problems. Let the cardi­ nality of the set of primitive abstract mechanisms be n. Suppose we consider only composite mechanisms with at most p primitives. In the abstract synthesis phase, the generation component can explore L:f;:;: 1 ni alternatives. We have to compute compositions during the process, which involves intersection of algebraic sets: the worst case time complexity is doubly exponential in the num­ ber of variables in the constraint set when a closed form solution is possible. In the concrete synthesis phase, the number of possible candidates are dn where dis the max­ imum number of concrete instantiations for a primitive abstract mechanism. Each step in the concrete synthesis phase involves checking that a given non-deterministic choice of primitive implementations yields a consistent constraint set. The complexity of solving these geomet­ ric and dimensional constraints is the same as that of solving constraints generated in the abstract synthesis phase. Algebraic descriptions are extremely general, but suffer from two disadvantages. They require detailed knowledge of the configuration spaces and the computa­ tion of l><l is very expensive in this representation. This motivates a qualitative approach to representing motions and the construction of the qualitative counterpart of the l><l operator on configuration spaces. This is the subject of the next section.

6 Tractable Representations for Compositions

Qualitative descriptions partition the space of possible motions into equivalence classes. They have two chief advantages: they permit partial specification of motions. Second, they allow for potential efficiency gains in per­ forming the join computations by eliminating the need to solve complex non-linear equations.

Our qualitative language is a predicate language that abstracts algebraic motion descriptions. It is similar to other motion languages in the literature [11 , 14, 16, 24) in its use of predicate calculus. However, unlike these approaches, but in common with (13), our aim is to pro­ vide an analysis of tradeoffs between expressive power and computational efficiency for qualitative motion lan­ guages. We develop a soundness criterion called the 1><1preservation property that a qualitative motion language must satisfy to generate correct syntheses.

A qualitative motion language can be characterized by a homomorphic mapping A, from a motion relation to a qualitative description, which picks out specific prop­ erties of a motion. For instance, our symbolic language represents rotations by their centers (xyz location) , their axes (a unit vector), a speed (a constant for a uniform rotation) , an angular range (for constrained rotations) , and a frequency (for rotations that change sense) . Recti­ linear translations are represented by an axis (a unit vec­ tor), a speed, a range (for constrained translations), and a frequency (for reciprocations). How can we determine the representational adequacy of such a language for a given class of design tasks? For our synthesis task, we require the computation of compositions. If we can com­ pute A('R1 1><1 'R2) accurately and efficiently from A('R1) and A('R2), for motion relations 'R1 and 'R2 , we have an adequate language. The formal property is called 1><1-preservation and requires the specification of txl-the composition operation in the abstract language defined by A.

Definition 12 The mapping A preserves joins if

Note that this constraint places restrictions on the defini­ tion oftxl. We illustrate the IXl computation using the gear train example of Section 4. g1 and g2 transform rotary motion to another rotary motion with a different speed and sense. The angular velocity a , can be obtained from the algebraic description of motion: .,P(t) = -aO(t) + ¢ , where t/J(t) is the output configuration at instant t , and O(t) is the configuration of the input link at t. The pred­ icates below reformulate the algebraic descriptions of ro­ tation provided earlier.

To implement 1><1 by IXl, we equate the description of the output motion of g1 with that of the input motion of g2 , where g2 may be rigidly transformed. The composition results in the following constraints.

1. Trigid(XM,YM) = (xB , YB)
2. Trigid(XN, YN) = (xF, YF)

We calculate the rigid transformation Trigid (in this case a pure translation) which moves the rotation about the z axis from ( x M , YM) to ( x B , YB) and we then apply that transformation to the output of g2 .

In general, for the predicate language of rotations and rectilinear translations introduced above, IXl "uni­ fies" motions M; and Mj by calculating the generalized rigid transformation T such that T M; = Mj. There are specific conditions under which two motions can be uni­ fied : they have to be of the same "type". Two rotations can be unified if they have the same axes of rotation, their angular speeds and range are equal, and they have the same frequency (if they are oscillations) . The unifi­ cation process captures the join calculation in C-space, and the abstract description filters exactly the properties of interest .

To demonstrate the computational efficiency gained by the loss of expressive power, consider the slider crank mechanism with the crank at (0, 0, 0) and the slider that moves along the x axis, with crank radius r , and with I being the length of the link connected to the slider. The abstract motion relation implemented by the slider crank is:

Our qualitative description only picks out the motion interval and frequency of the slider. The motion inter­ val is calculated from Equation 2 by using the fact that 0 E [0, 211") . The angular velocity can be derived by ex­ amining the algebraic description of the slider's motion as a function of time. These two aspects of the slider's motion are sufficient characterizations for the 1><1 calcula­ tion. We no longer need to solve the non-linear equation 2.

If the configuration space relations 'R1 and 'R2 are lin­ ear (representable by linear constraints), the IXl operation defined above permits A to be join-preserving. To better understand join preservation, it is useful to consider the example in Figure 3 where it is violated. The output of the crank rocker in Figure 3 is a rectilinear transla­ tion (reciprocation) which is the input to the skotch-yoke mechanism. Our r><J construction unifies the two motions as long as their ranges, speed, and axes coincide. Unfor­ tunately, an analysis of the underlying C-space 3 relations reveals that there is at most one possible position where the two motions would intersect, thus the mechanism would jam (become rigid). Both the crank-rocker and skotch-yoke mechanisms are non-linear.

The specific r><J developed above is inadequate for han­ dling non-linear mechanisms in a general way. To guar­ antee preservation of joins for the specific r><J and A com­ bination introduced here, we ensure that non-uniform motions are not composed. This can be done with the restriction that non-linear mechanisms only take uniform motions as input.

1 Efficient Synthesis Algorithms

We reformulate the algebraic description of the abstract synthesis problem in terms of qualitative motion descrip­ tions.

Given i , a qualitative specification of the input motion; o, a qualitative specification of the output motion, and constraints on i and o.

Find a sequence of abstract mechanisms A1 , .. . , An which when composed will transform any motion described by i to sorrie motion described by o. To be exact, we want

where mi E i means that the motion m; is in the class of motions described by the qualitative speci­ fication i.

To make the process efficient, we transform the naive generate-and-test scheme to a goal-directed procedure in Section 4 that chains backward from the desired out­ put o to i. We distinguish between single-input, single­ output (SISO) mechanism synthesis from single-input, multi-output mechanism (SIMO) synthesis because of the opportunity for optimization by function sharing in the latter case. We begin with the algorithm for the SISO case.

The algorithms below are not committed to any partic­ ular abstraction language. For each language, we require

procedures that test equality of motion descriptions, and regress constraints on motion through a primitive ab­ stract mechanism. We will illustrate these in the con­ text of the simple motion description system introduced in the previous section.

7.1 Synthesizing single input, single output mechanisms

The recursive algorithm for synthesizing single input, single output mechanisms is shown in Table 1. We imple-

SISO_Synthesize(i,o)

1. If i = o, then return the null machine.
2. Else select an abstract mechanism M and find a rigid transformation T such that

Thus q describes the (largest) set of motions that can be transformed by T(M) to motions in o. q is the most general qualitative description in the motion language which meets that the previous re­ quirement. It is the regression or backprojection of o with respect to T(M) .

1. Return [T(M), SISO...Synthesize(i,q)].

Table 1: Algorithm for synthesizing single input, single output mechanisms

ment the synthesis method for our language as a depth­ bounded, goal-directed, depth-first backward chainer in CLP(R). The operational model ofCLP(n) is similar to Prolog (so the reader familiar with Prolog can read the code below quite easily), however unification is replaced by a more general mechanism: solving constraints in the domain of functors over real arithmetic terms.

For a linear primitive mechanism, we store its name, a scaling factor for the input and output motions, and the types of input and output motion. For example, the abstract mechanism corresponding to a gear pair with gears of sizes 3 and 5 is represented as:

mechanism(gear-pair,

linear(-3/5), [rotation( (0,0,0),(0,0, 1) )] , [rotation( ( (3+5)/2,0,0),(0,0, 1) )]).

For a non-linear primitive mechanism, we store its name, its input motion which must be uniform, and its output motion. For instance, the abstract non-linear mechanism corresponding to a crank rocker is repre­ sented as:

mechanism( crank-rocker(L),

non-linear, [rotation((0,0,0) ,(1 ,0,0)), velocity(F)], [rotation((O,L,0),(1,0,0)) , frequency(F) , range(R)]) :- R > 0, R < 1r ·

The top-level invocation of the synthesis function is: synthesize(input motion, output motion, null design, depth bound). The base case of the synthesis occurs when the input motion i is equal to the output motion o: this is established by solving arithmetic constraints that are generated when the motions are unified.

synthesize(ln_motion, Out_motion, Design, Depth) :-

motion_eq(ln_motion, Out_motion) .

motion_eq is a predicate testing whether two motion de­ scriptions are equivalent . Its actual implementation de­ pends on the specific motion language.

The recursive step of synthesis first involves non­ deterministic choice of a primitive mechanism. Suppose a linear primitive mechanism with output motion op is chosen. The output op is made equal to the output of the overall mechanism via a rigid transformation T com­ puted by solving the constraint T( op) = o. Then, the new synthesis problem i , T(ip) is solved, where T(ip) is the input motion of the primitive after rigid transforma­ tion. We can calculate T( ip) very simply from the type of input motion and the scaling factor that relates the input and output motions of the mechanism.

synthesize(In_motion, Out_motion,

[(N,R_transform)IDesign], Depth) :­

Depth> 0,

mechanism(N, linear( F) , P Jn_motion, P _out_motion) , transform(P _out...motion, Out_motion, R_transform), linear_apply(R_transform, F, P Jn...motion, NewGoal), synthesize(ln_motion, New Goal, Design, Depth-1 ).

If, however, the primitive mechanism chosen is not linear, the the input and output motion description, ip and op , have to be provided explicitly. We compute the rigid transformation T by solving the matrix equation Top= o.

synthesize(ln_motion, Out_motion,

[(N,R_transform)IDesign], Depth) :­

Depth> 0, mechanism(N, nl, P _in_motion, P _out...motion), transform(P _out...motion, Out_motion, R_transform) , nLapply(R_transform, P _in_motion, NewGoal), synthesize(ln_motion, NewGoal, Design, Depth-1).

Consider the problem of designing a windshield wiper introduced in Section 1. The input power is provided by a motor rapidly rotating around the z axis. The wiper oscillates in the yz plane with low frequency. We spec­ ify the problem as follows . Capitalized symbols in the descriptions above are variables. The constraints specify ranges on some of the variables .

Input motion i Output motion o

rotation rotation

center: (0,0,0)

center: (O,Y,Z)

axis: (0,0,1)

axis: (1,0,0)

velocity: 20

frequency: F, range: X

Constraints: 0.5 < F < 2, 1r /2 < X < 1r

For the synthesis of the wiper , the first primitive abstract mechanism chosen is a crank rocker.

Input motion Output motion

rotation rotation

center: (0,0,0)

center : (O,L,O)

axis : (0,0,1)

axis: (0,0,1)

angular_velocity: F frequency: F, range: R

Constraints: 0 < R < 1r

To have the output of this primitive mechanism be a rotation at (0, Y, Z) , we will need to move the crank rocker . We have to solve two systems of equations to find the rigid transformation. The first system arises from the requirement that the axes of rotations have to be parallel. We need to find the angles of rotation that allign the axes. We have to solve

where R is a 3x3 rotational matrix. Let t/; , ¢ , (} be rota­ tional angles about the z , x, and y axis respectively.

The second system of equations arises because we re­ quire the centers of rotations to be coincident after the rigid transformation. Let T be the 4x4 transformation matrix.

From these equations, we solve for x , y, z, (} , ¢ , t/; . One solution to this problem produced by our system is

The rigid transformation computed in this case is a ro­ tation of 1r /2 about the y axis and a translation of Y- L along the y axis. We apply the transformation to the input motion of the primitive mechanism. The interme­ diate motion generated is:

Intermediate motion q

rotation

center: (0, Y - L, Z)

axis: (1,0,0)

angular_velocity: F

All that remains is to transform the intermediate mo­ tion generated to the specified input motion i. This is ac­ complished with another abstract mechanism that meets the constraint on F and changes the axis of rotation, in this case, a worm-spur pair.

Input motion

rotation

center: (0,0,0)

axis: (0,0,1)

angular_velocity: F1

Constraints: none

Output motion

rotation

center: (0, W,O)

· axis: (1 ,0,0)

angular _velocity: F1 /a

The unification of the intermediate motion generated above with the output of this primitive abstract mecha­ nism generates the constraints: F = Ftfo:, Y- L = W, Z = 0. The rigid transformation is the identity transfor­ mation. Now the input motion of this primitive mecha­ nism can be matched with the input description i yield­ ing F1 = 20. This generates the derived constraint F = 20/o: . The synthesis and refinement process gener­ ates the constraints on the configuration of both mecha­ nisms, the dependency of X, Y and Z on the dimensions of the links (W, L), as well as the fact that F = 20/o:, where o: is the worm-spur gear ratio. Alternate abstract designs and the corresponding refinements of a wind­ shield wiper found by our system include the compo­ sition of a worm-spur pair, a slider crank, and a rack and pinion mechanism; as well as a worm-spur, scotch­ yoke and a rack-and-pinion mechanism. This example shows how the backward chaining process accumulates simple algebraic constraints which are solved incremen­ tally during the synthesis. The constraint programming language CLP(n) [27] is used to implement the algo­ rithm. CLP(n)Graphical outputs are produced via an interface to Mathematica 4 .

Theorem 2 Algorithm SISO_Synthesize(i, o)) is sound: i.e, it designs concrete mechanisms that satisfy the qualitative motion specifications ( Q;, Q0 ).

This theorem can be proven by induction on the length of the generated solution. The worst case complexity of this algorithm is exponential in the length of the solution produced. The worst case branching factor for the search is around 20, corresponding to the number of primitive motion relations. In practice, the average branching fac­ tor is much smaller (around 2 for the examples in this paper) because the constraint accumulation process is a least-commitment strategy that minimizes backtrack­ ing in the space of compositions of primitive abstract mechanisms . In other words, we incrementally solve for the rigid transformation and dimensions of primitives during synthesis. We do not search for them discretely, which may be very time consuming. Put another way, our constraint-based representation allow us to perform delayed instantiation of parameters. Each search path encodes a whole class of solutions. Pruning or accepting a path involves pruning or accepting a whole class of so­ lutions. The algorithm synthesizes many of the designs for conversion of uniform rotation to reciprocation in [1] in a few seconds. The synthesis of the wiper shown in Figure 1 and its variants was also completed in about two seconds on a Spare 1+.

7.2 Synthesizing single input, multiple output mechanisms

Many useful mechanisms produce multiple outputs from a single source. e.g., eggbeaters , cars. To design these single input multiple output (SIMO) mechanisms, we need to specify a sequence of output motions.

Given i, a qualitative specification of the input ; o 1 , ... , o" , a sequence of output motions, and con­ straints on i and o's.

Find A tree of abstract mechanisms,

Al , ... , Al , Ar, . . . , Ak , which when composed satisfies th~ input-output specification.

The SIMO synthesis problem can be solved by a series of calls to SISO...Synthesize as in (Table 2). Calls to SISO...Synthesize produce a tree with isolated paths from i to each oi . However, this introduces a lot of redundancy in the form of common intermediate mo­ tions along these paths. The optimization algorithm in Table 2 merges common motions in the paths: if

· Mathematica is a trademark of Wolfram Research, Inc.

SIMO_Synthesize(i, o 1 , .. . , o") for j from 1 to n do A{, . .. , A{ . +- SISO ...Synthesize( i, oi) ) I* optimization *I for j from 1 to n do for each A{ in A{ , . . . , M{ . do ) for l from j+1 ton do for each A:n in M~, .. . , AL do . if InMotion(A:n) = InMotion(Ai) then delete (AL ... ,M:n_l) merge the inputs of A:n and M{i

the inputs h and ! 2 to two abstract mechanisms in two different branches of the initial tree are equivalent, we eliminate the path to h and connect !1 in place of !2. This eliminates repeated transformation of i to ! 2 . In the algorithm, we denote primitive A's input motion by InMotion(A) . When we merge the inputs of A:n and A{ in the last step of SIMO_Synthesize, the input links of A:n and A{, as well as the out­ put links of A{_ 1 are rigidly connected together. The optimization step merges identical motions, and there­ fore the final mechanism produced by the synthesis is behaviorally equivalent to the original tree. By the correctness of SISO...Synthesize we can conclude that SIMO_Synthesize is also sound. The optimization re­ duces the number of nodes in the tree and thus produces more compact refinements. Thus we have the following theorem.

Theorem 3 Algorithm SIMO_Synthesize(IJ is sound: i. e, it designs concrete mechanisms that satisfy the motion specifications ( Q;, ( Q~, . . . , Q~) ).

We now present the class of mechanisms that are syn­ thesizable by these algorithms. Clearly the class is de­ termined by the qualitative motion description language used, and the set of primitive abstract mechanisms and their associated implementations. For the specific mo­ tion language used in our current implementation, the class of mechanisms synthesizable are fixed-topology, single-degree of freedom mechanisms with at most one non-linear mechanism on each path from the input to the outputs. The mechanisms we consider thus far are composed of rigid parts. The single-degree-of-freedom restriction applies in our case, because all of our prim­ itive motion relations have only one degree of freedom. The composition of two or more mechanisms with single degree of freedom can only produce mechanisms with at most one degree of freedom. Multi-degree of freedom mechanisms can be synthesized by our algebraic tech­ nique. The restriction on rigid parts obtains because our definitions of motions and mechanisms are grounded in configuration spaces of rigid bodies. By allowing def­ initions based on generalized configuration spaces, we can allow for some limited forms of non-rigidity. The restriction on the number of non-linear mechanisms in a design is needed for the correctness of the abstraction A that generates the qualitative motion language. The fixed-topology restriction can be eliminated by having a richer set of primitive relations as well as a richer mo­ tion specification language which allows for expression of when and how part contacts are made and broken. A limitation of our current approach is the lack of a com­ ponent for shape design. If there is no sequence of prim­ itive relations that satisfies the given specification, our method will fail to produce a design. We can integrate the methods of [11] for synthesizing novel shapes into our design system to automatically extend our library of primitive abstract mechanisms.

8 Conclusions

This paper presented a case study of the integration of methods in qualitative physics and constraint program­ ming with general algebraic reasoning with configura­ tion spaces. The design domain studied is that of kine­ matic synthesis of mechanisms from specifications of in­ put and output motions. Two algorithms were presented that rapidly generate alternate behavioural decomposi­ tions and concrete refinements of a mechanism. We also identified the class of mechanisms which can be correctly synthesized within the qualitative framework . We have implemented our method in CLP('R.) and all examples discussed in this paper are drawn from our implemen­ tation. Our base set of examples are drawn from mech­ anisms in [19] and [1]. We are presently enriching the language of qualitative motion specifications to handle richer classes of non-linear motions. This will allow us to obtain better coverage over the examples in the compen­ dia listed above. Future work involves extending the set of primitive relations, proving completeness properties for these relations, and integrating mechanism synthe~ sis with multi-domain (including dynamics and opt ics) designs.

There are other approaches to mechanism synthesis that can be profitably combined with the first-principles approaches discussed above. Expert system techniques [26] for synthesizing special classes of mechanisms e.g. , cam-follower mechanisms, occupy an interesting middle ground between pre-parametric design schemes which re­ quires high-level qualitative specifications and the nu­ merical optimization packages which require very de­ tailed kinematic specifications. Case-based methods [3, 20] for synthesis of mechanical systems begin with a known library of designs and use the goal specifica­ tion to index relevant designs. The retrieved designs are modified to meet the given specifications. The algorithm developed here can be used to design indices for the li­ brary of designs. This works by running the synthesis algorithm "in reverse" to parse or understand a design in terms of given primitive motion relations.

The class of conceptual design tasks that can profit from the integration we have effected are tasks with a significant geometric component. We have developed fast simulation methods for the class of mechanisms that can be synthesized by the algorithms presented here. Space limitations preclude their inclusion in this docu­ ment; a discussion of simulation methods will be present in the talk. All the physical prototyping of the designs presented in this paper were performed using Technics Lego. Integrating conceptual design systems through detailed design and physical prototyping in a standard medium, will be discussed in the talk . The talk will fo­ cus on mechanical nano-technology designs because low­ dimensional configuration spaces can be used to reason about shapes and motions in that domain. Computa­ tional scale issues and our experience with the field test­ ing of our tools at Xerox will also be presented.