Computer-Aided Creative Mechanism Design

1 Introduction

A clock escapement (Figure 1) is the central mechanism of a mechanical clock. It is used to regulate the motion of a 6cape wheel to advance one tooth per oscillation of a pendulum. Since the pendulum has a fixed period of os­ cillation, this ineans the wheel moves at constant speed and can drive the hands of a clock. The ·regulating func­ tion of the escapement requires blocking the rotation of the scape wheel in certain positions of the pendulum, while letting it advance in others. In the device of Fig­ ure 1, this is accomplished by the shapes of the two sides of a piece attached to the pendulum, called the pallet.

A ratchet (Figure 2 a) is a device intended to block rotation of a wheel in one direction, but not in the other. Another property of the device in Figure 2), rather unde­ sirable for the function of the ratchet, is that this blocking only occurs when the lever is in a certain range of positions, but not in others (Figure 2 b). This property can be used to create an escapement device such as the one in Figure 1.

Noticing this "spurious" property of a ratchet to create an escapement is an example of a creative design. It involves three processes:

• ducovery of the fact that the ratchet device has a function which is required in an escapement, and
• analy6i6 to define a shape feature which is respon­ sible for the desired function, thus creating new de­ sign knowledge, and
• adaptation of the shape feature in a new design con-

Discovery of interesting behaviors seems to require hu­ man intuition which is little understood and probably too complex to automate. The more tedious activity of analyzing a behavior and adaptating it into new design contexts, however, can be supported by knowledge-based systems, as we will show in this paper.

Creative design defines new functions, devices and mappings between them. A computer tool which sup­ ports it must provide:

• a language for expressing the functions of a device.
• a language for defining the new design features es­ sential to the creative idea and their mapping to functions.

Current knowledge-based design systems are based on fixed vocabularies of functional and design features. For example, prototype! ([Gero, 1990]) or intelligent object! functions, and use these to define a library of standard solutions which the designer can use to compose de­ signs automatically. Other researchers have attempted to generate designs from symbolic domain knowledge using model-based abductive reasoning (for example [Williams, 1990; Williams, 1990]). They allow function to be specified by a generative language, but generate 6pecification6 for artifacts without consideration of how they could be physically realized.

The essence of creative design is to create new fea­ tures and adapt them to new problems. Knowledge­ based design systems rely on primitive features to pro­ vide support for generating designs. However, analy6i6 does not need to be based on a fixed feature system: for example, finite element analysis can be applied to any representable structure. In this paper, we introduce a technique similar to explanation-based learning where an analysis of a new device is generalized to make it applicable to other contexts. This makes it possible to support creative design by extending domain knowledge as required.

An ideal domain for exploring this idea is shape de­ sign in mechanisms: designers routinely create shapes which involve new design features. At the same time, the kinematic behavior of any new device can be de­ termined and explained using first principles. More specifically, we have developed our technique for the de­ sign of kinematic pair1, also called elementary mech­ anum/1. A kinematic pair consists of two parts with one degree of freedom each, and achieves its function through the kinematic interactions of . the parts. An example of a kinematic pair is a clock escapement, as shown in Figure 1. The qualitative behavior of a kinematic pair can be computed and represented us­ ing the theory of qualitative kinematics ([Faltings, 1990; Forbus et al., 1991]). Furthermore, it is possible to in­ vert the computation to determine the limits up to which it is valid ([Faltings, 1992]) and thus define the new de­ sign knowledge required to represent the new idea. Our techniques concentrate on the conceptual design stage where most creativity takes place. Subsequent detail de­ lign can further optimize the dimensions to accomodate non-qualitative specifications.

Synthesis of kinematic pairs has been studied by Joskowicz and Addanki [Joskowicz and Addanki, 1988j. The techniques we present improve on their work in the following ways: (i) we use a realistic qualitative langu­ gage for specifying function, and (ii) our techniques can deal with contact subsumptions and intermittent mo­ tion, required for devices of practical interest.

We first discuss the formal representation of kinematic behavior and show how languages for expressing qualita­ tive function can be defined on its basis. We then show how the analysis of a particular device can be general­ ized to define the shape features which are responsible for the its function, and how the new features can be used to derive new designs. Finally, we give an exam­ ple of a design in which a ratchet is transformed into an escapement.

2 A language for qualitative function

Function is a mapping from external influences to the behavior they cause. We define a set of behavior predi­ cate/1 and a formalism for expressing external influences on mechanisms. Functions are then defined by logical expressions connecting external influences and behavior predicates.

Representing qualitative kinematic behavior Textbooks on the subject explain kinematic behavior qualitatively by sequences of kinematic 6tate/l. Exam­ ples of kinematic states of a ratchet device are shown in Figure 3. In qualitative physics terminology, a graph of kinematic states and transitions is called an envi.!ion­ ment. It can be computed based on a place vocabulary [Faltings, 1990], a graph where each node represents a different combination of contact relationships, and each arc represents a potential transition between them. The envisionment is obtained by combining each node of the place vocabulary with assumed motions and keeping only the states and transitions consistent with external forces and motions. We have developed and implemented com­ plete algorithms to compute place vocabularies for arbi­ trary two-dimensional higher kinematic pairs in fixedaxis mechanisms [Faltings, 1990]. These have been used to compute envisionments for a number of mechanisms, such as a mechanical clock [Forbus et al., 1991].

We represent place vocabularies using a set of behavior predicate· which characterize places, their features and their connectivity. For a kinematic pair, the place vocab­ ulary defines a graph containing three types of kinematic states, corresponding to two, one and no contacts, and identified by the following behavior predicates:

• point-place(x): the contacts in x hold only in a single configuration.
• edge-place(x): the contacts in x hold in a one­ dimensional set of configurations.
• face-place(x): x is a place without any contacts and two-degrees of freedom.

For each place, the place vocabulary defines the allowed qualitative directions of motion:

• qualitative-motion(d): d is a qualitative vector (do, d1) whose components indicate the direction of motion of each object: ~ E { -, 0, + }.
• allowed-motion(x,d): motion d is possible every­ where in place x.

For each link between states, the place vocabulary de­ fines the directions which can cause a transition:

• transition(x,y,d): motion d can cause a transition from place x to y.

The kinematic states of a mechanism are obtained by combining each place :z: with its maximal set of possible qualitative motions:

In an actual behavior, only those motions M ( :z:) which in fact cau&ed by an external influence actually occur. The set of transitions between states is the set:

Tm = { (:z:,y) I (3d E M(:z:)) transition(:z:,y,d) }.

More details on envisioning mechanisms using place vo­ cabularies can be found in (Nielsen, 1988].

Representing external influence In kinematic pairs, external influences can be either force·, repre­ sented by a set :F,., of qualitative vectors ([Faltings, 1990]), or motion&, represented by a set M,., also con­ sisting of qualitative vectors. Since a qualitative force vector causes a qualitative motion in the direction of the same vector, the set of possible motions M 1 caused by external forces is then given as:

The actual set of motions M ( :z:) to be considered in state z is then: ·

Formulating functions Functions are properties of behavior under certain assumed forces and motions. Therefore, qualitative functions can be defined as con­ dition& on place vocabularies without first constructing the qualitative behavior. Using the behavior predicates which represent the place vocabulary, a set of functions can be defined as required for the application, and ex­ tended whenever required to express a new specification.

For example, some functions our current prototype sys­ tem uses are:

• transmitting-place(:~:, dir1, dir2): (Vd = (d1, d2)){d1 = dir1 => d2 = dir2} 1\ {d2 = -dir2 => d1 = -dir1}
• blocking-place( :z: ):
• -,(3d E M(:z:))allowed-motion(:z:, d) (a place blocks motions if it does not allow any of the assumed motions).
• partial-blocking-place( :z:, dir s): ..,(3d E dir&)allowed-motion(z, d) (a partial blocking place blocks the specified mo­ tions)
• possible-path(:z:o, :z: .. ):
• (:z:o = :Z:n) V 3 S = (:z:o,:z:l,:z:2,····:z:n) (Vi< n)(3d E M(:z:,))transition(:z:,, :Z:i+l· d) (There is a path from place :z:o to place :Z:n when­ ever there is a sequence of places with transitions between them under at least one assumed motion)
• cycle(:z:o, C): C = (:z:o, :z:1, :z:2, ... , :z: .. , :z:o) (V:z:, E C)(3d E M(:z:,)) transition(:z:i, :Z:mod{i+l,n+l)· d) (there is a cycle of states C such that transitions between subsequent states are consistent with as­ sumed and allowed directions of motion.)

A place vocabulary can only fulfill the required func­ tions if the number of states and their connectedness is sufficient. Reasoning about such topological features is difficult in the place vocabulary itself, since it is based only on individual boundarie1 of shapes which cannot be modified individually. We use an explicit represen­ tation of the kinematic topology ([Faltings et al., 1989]) of the mechanism to detect cases where the topology of particular object shapes would not permit the specified function. An example of a function defined on the basis of kinematic topology is:

• cycle-topology( c, d1, d2): if the first or second ob­ ject have rotational freedom, the cycle involves d1 rotations of the first or d2 rotations of the second object. This predicate is defined directly on the kinematic topology of the mechanism.

which can be defined formally using similar behavior predicates as those which define place vocabularies.

The function of a ratchet can now be defined qualita­ tively as follows:

For all starting states a in which the orientation of the lever is in the interval (0.:1r] (pointing to the left such that the moment gravity exerts on it is positive):

• forM,.,={(+,*)} 1\ :F,.,= {( *· +)}(the '*'stands for either +, 0 or -):

-cycle( a, C) 1\ cycle-topology(c, 1, 0)

• -,(3:z: )blocking-place(:z:) 1\ possible-path( a, :z:) (assuming that the wheel turns counterclockwise and the lever is forced onto it, there is a cycle of states where the wheel can rotate, and no reachable blocking state from any starting state a.)
• for M(:z:)={(-,*)} 1\ :F,. ·· = {(*,+)}: (Vy)possible-path(a, y) => { -,cycle(y) 1\

(3z)(blocking-state(z} 1\ possible-path(y, z})} (assuming that the wheel turns clockwise, no reach­ able state leads to a cycle and all states can even­ tually lead to a blocking state).

Note that due to the ambiguities inherent in qualita­ tive envisionments, the formalism always overgenerates behaviors. It is therefore only possible to define nece66ary, but never 1ujjicient specifications of behavior and, consequently, function. For example, we can express the specification that clockwise motion leads to a blocking state only in an indirect manner: if there is no possibil­ ity to cycle, and there is at least one reachable blocking state, the device must eventually reach this state.

3 Extending the feature vocabulary and domain knowledge

Shapes are represented using a metric diagram ([Falt­ ings, 1991; Faltings, 1992]). The metric diagram con­ sists of a symbolic structure which defines vertices, edges and metric parameter1 for the positions of the vertices. In our current implementation, we restrict ourselves to polygons, but see [Faltings, 1990] for ways to extend it to include circular arcs.

While qualitative functions can be formulated in a symbolic language, nobody has so far found a similar language for defining features of individual shapes which is descriptive enough to infer kinematic behavior. Be­ cause of the strong dependence of shape features on the counterparts they interact with, it seems unlikely that such a language could be defined at all ([Faltings, 1991]}. We now show how it is possible to define a language for features of pair1 of shapes which predicts kinematic fea­ tures of their interaction.

Using the metric diagram, a shape feature (which may involve several objects) is defined by:

• a set of vertices and edges,
• the metric parameters associated with them,
• a set of constraints which must hold simultaneously for the shape feature to be present.

For every behavior predicate of the place vocabulary for a novel device, our program constructs an elementary 1hape feature which implies the presence of that fea­ ture in the absence of subsumptions (see below). The computation of this definition is illustrated in Figure 4. For each behavior predicate in the place vocabulary, the trace of the computation shows a conjunction of tests on metric parameters which have been satisfied and led to asserting the predicate. Each test queries the sign of an algebraic expression in a set of metric parameters, and can be understood as a conltraint on those parameters. These constraints, and the parameters they involve, de­ fine the new shape feature.

Subsumptions are interactions between unrelated parts of the shapes which make certain contacts phys­ ically impossible. In principle, every behavior predicate is valid only under the assumption that no subsumptions inhibit it. For efficiency reasons, our system generates tests for subsumptions only when they have been discov­ ered to be important by leading to unexpected results.

More details on the mapping between functions and met­ ric dimensions can be found in [Faltings, 1992].

A creative idea defines a new combination of shape features which satisfies a function. The combination is defined in the example which implements the idea and can be formulated as a rule:

feature1 1\ feature2 1\ · · · => function

Note that it would in principle be possible to gener­ ate designs from first principles by using the transla­ tion from elementary functional predicates to elementary shape features to transform functional specifications into shape specifications. However, in pratice this is a bad idea, since the resulting dynamic constraint network is only a specification for a solution and there are no known general methods for solving such specifications.

Designing with new knowledge The formulation of metric predicates turns shape design into a constraint satisfaction problem: find a structure and associated di­ mensions which satisfy the constraints for the functions required by the specification. The constraint network is dynamic, since modifications of the shapes can change the constraint set, and it involves unbounded value sets. Another difficulty is that many constraints depend on a large number of variables, so that representations by binary constraint networks are not appropriate.

As a tractable, but incomplete, way of solving such constraint systems, we use incremental refinement of an initial solution using means-ends analysis. Each refine­ ment is carried out by identifying a discrepancy between specifications and current function and applying a modi. fication operator which is likely to eliminate this discrep­ ancy. More efficient strategies are possible by analyzing the dependencies between functions, similar to the tech­ niques investigated by Williams [Williams, 1990]. Our system generates two types of modification operators:

• dimen6ional modifications, where the dimensions of parts are adjusted to fit the functional requirements, and
• topological modifications, where vertices are added to part shapes. A topological modification is always coupled with a dimensional modification to fix the dimensions of the new features.

Dimensional modification operators are indexed by their effect on the place vocabulary: changing the appearance of a state in the place vocabulary, or making a state appear or di6appear. Based on matches between possi­ bilities and active goals, the system computes a finite set of potentially applicable modification operators for proceeding with the design.

All modification operators are subject to the addi­ tional constraint that a polygon shape may not overlap itself, a configuration which would be physically impos­ sible to achieve. We have developed an algorithm for in­ crementally generating and maintaining the constraints which express this condition.

Topological modifications are proposed when the con­ straints formulated by metric predicates are contradic­ tory: adding an additional vertex gives two additional degrees of freedom to resolve the contradiction. More precisely, a contradiction occurs when there is no fea­ sible region to place the vertex whose modification the system is considering 1 . The system then proposes two modification operators which add vertices in the centers of the two edges which meet at this vertex. Removal of vertices to simplify shapes is considered only when the final result is reached. A vertex can be removed if plac­ ing it on the straight line between its two neighbours is consistent with all metric constraints.

Dimensional modifications are based on the con­ straints defined by metric predicates. These divide up the space of shape parameters into regions in which the qualitative behavior does not change. Since any choice of value is equivalent, new dimensions are obtained by picking an arbitrary value combination within a region that exhibits the desired behavior [Faltings, 1992].

In practice, the computational complexity makes ex­ plicit computation of the region intractable or even in­ computable, since most of the constraints are nonlinear and some are not even algebraic. A tractable, but neces­ sarily incomplete solution is to select only a single land­ mark parameter for modification, and project the con­ straints onto la.ndmark valu.e6 of this parameter. The landmark values can be computed by numerical approx­ imation, thus avoiding expensive computation with non­ linear curves.

As an example, consider the possibility of touch be­ tween v3 and v4 (Figure 4 as a function. The constraints required for proving the existence of the feature is:

1 Note that this does not imply that there is no solution at all, only that it cannot be found by changing a single vertex.

Figure 5: Metric predicate6 define the region6 in the 6pace of metric parameter6 where certain fu.nction6 are 6ati6fied.

Assuming that d, 3 has been chosen for modification, pro­ jection (using d, 4 = 26 and d = 30) gives landmark val­ ues of d,a > 4 d,a > -4 and d,a < 56. A modification operator which makes the touch appear would set d,a to a value within the interval, for example at d,3 = 6. An operator which would make a touch di6appear would set it to d,3 = 2, for example. This solution is incomplete, as it can only extend v3 straight outwards from the cen­ ter of rotation, but not change its angle seen from that point.

For designing two-dimensional shapes, the most seri­ ous incompleteness problems can be avoided by consid­ ering the pair6 of parameters which define the positions of individual shape features. Our system uses an ap­ proximation method to generate solutions for pairs of parameters :c and y, illustrated in Figure 5. First, we arbitrarily pick one of the two parameters, say y, and define a number of equally spaced sample points {our im­ plementation uses 40), shown as y0 through y6 in Figure 5. For each value y,, we project the constraints to find the interval of :c within the legal region: only intervals / 1 through / 3 {for y11 y2 and y3 ) exist in the example. Finally, a new value combination is picked as the center of one of the intervals for :c and the corresponding Yi. for y.

Designing with modification operators The gen­ eration and application of modification operators must be controlled using domain knowledge to avoid excessive search. Since it is very difficult to formulate such domain knowledge, our current system asks the user to choose

• the discrepancy to modify based on suggestions pre­ sented by the system,

• the modification operator to apply from a list of possibilities (this implies selction of the variable to be changed),
• topological changes to create additional degrees of freedom, when required.

Automating the choice using explicit control knowledge is beyond the focus of this project, but we are investi­ gating the use of case-based reasoning for this purpose.

4 Turning a ratchet into an escapement

As an example of using modification operators for design, we show how the escapement shown earlier in Figure 1 can be obtained from the ratchet of Figure 2.

Using the functions defined earlier, an escapement can be specified in the following way:

1. (3cycleX = {:z:o,:z:1,:z::l,····:Z:n-1}) ofstates: V:z:i, partial-blocking-place(:z:i, ( +, *)) and cycle-topology( X ,1,0)
2. (3cycleY = {yo, Y1 1 Y:l, ... , Yn-1}) of states: Vyi, partial-blocking-place(yi, ( +, * )) and cycle-topology(Y,1,0)
3. for M(:z:)={(*,O),(*, -)} 1\ :Fau = {(+,*)}: (V:z:i E X)possible-path(:z:i, Yi), Yi E Y (when the pendulum swings from right to left or is stationary, there exists a path from place :Z:i to Yi)
4. for M(:z:)={(*,O),(*,+)} 1\ :Fa..,={(+,*)}: (Vyi E Y)possible-path(yi, Zmod(i+1,n)) 1 :Z:i EX (when the pendulum swings from left to right or is stationary, there exists a path from place Yi to the place following :Z:i in the cycle X.)
5. for M(:z: )={( +, 0)}: (V:z: )·(3C)cycle(:z:, C) (the wheel is prevented from rotating a full cycle whenever the pendulum does not move)

One possible trace of an incremental modification which achieves these specifications is illustrated in Fig­ ure 6.

The ratchet (device A) already provides a cycle of blocking states which can be used to satisfy either the functional specification (1) or (2) of the escapement. However, it does not satisfy specification (5), and speci­ fications (3) and ( 4) cannot be evaluated.

The system matches the cycle of blocking states of the ratchet to specification (1), and we assume that the user chooses to first satisfy specification (2). The first subgoal is then to create the cycle of places it requires, in a way that they satisfy the partial-blocking-place property. The user chooses to change the position of vertex v3 (see Figure 4) among the variables which the system determines suitable for modification operators. New contacts and thus new states will exist whenever vertex v3 is able to touch v4, which results in the con­ dition 4 < t.4a < 42.43 on the position of v3 for (po­ tentially) removing discrepancy (2). Further constraints are added to ensure that the shape of the lever remains a legal polygon, and values are found by constructing the feasible regions in the space of :z:.,a and Yv3· Choosing :Z:va = -1.9, Yv3 = 5.69, the system simulates the new de­ vice and finds that specifications ( 3) and ( 4) are not sat­ isfied: there is no transition between the blocking states where the pendulum does not move. The user chooses to correct this by modifying v3, thus creating another constraint and the new values :z:.,a = -2.53, y11 3 = 7.59, resulting in the device shown in Figure 6 B. The total number of possible modifications proposed by the sys­ tem to address discrepancies existing in state A is 112, and computing and applying the modification operator took 1309 seconds on a Symbolics 3650 LISP machine. User interaction is therefore quite important to avoid excessive computation time. ·

Simulating version B shows that due to a subsump­ tion, the required transitions between blocking states are still impossible. Again, the user chooses to satisfy this property by modifying v3, but this time the constraint for avoiding the subsumption is contradictory with the earlier ones and no modification can be found. The con­ straints on v3 are thus declared contradictory, and a new vertex v6 is introduced between v2 and v3 to create a new degree of freedom in version B. The user can now choose to modify v6 to solve the discrepancies; the sys­ tem proposes :z:.,6 = 0. 78 and Yv6 = 0.63, shown in Figure 6 C. Simulation shows that there are no subsumptions which produce unexpected behavior, and furthermore specification (5) also turns out to be satisfied. This time, there were 180 alternative ways of satisfying the specifi­ cation, but computation of the actual modification took only 111 seconds. We note that user interaction is in­ dispensible for controlling the modification process: had the system started by attempting to satisfy specifica­ tion (5), for example, a long and not very fruitful search would have resulted. The intuitions behind such choices appear very complex and we doubt that they could be formulated in a sufficiently concise way.

5 Conclusions and Future Work

We have shown how first-principles knowledge about kinematics can be used to support creative design of shapes in elementary mechanisms by providing:

• a language for formulating qualitative kinematic function, and
• a method for automatically extending the vocab­ ulary of shape features and domain knowledge to accomodate creative design ideas.

An intelligent CAD system using the technique would allow the user to introduce creative ideas and have the system use them in automatically generated designs. By making the system search for novel ideas itself, one could also construct an autonomous creative system, but this would probably not be widely applicable due to the ex­ cessive computational complexity.

Our technique is similar to explanation-based learn­ ing. Its application to a continuous domain en­ ables the explanation-based technique to actually ac­ quire new knowledge, contradicting common belief that explanation-based techniques are not capable of extend­ ing the deductive closure of existing knowledge.

The system we have developed for adapting creative solutions with modification operators is computationally tractable and shows the feasibility of the concept. It in­ completeness - solutions are only found by modifications of single vertices at a time - did not seem to be significant in practice. It is in fact surprisingly easy to create truly novel designs using the program. For example, start­ ing from the observation that the pawl of an escapement can be used to drive the scape wheel, the program has invented the reversing mechanism shown in Figure 7, a much simpler and more reliable design than that found in a mechanism book which involves 4 parts and reliance on friction for function 2 ·

The incremental refinement method can only adapt a single solution, and requires guidance from the user to do so. However, by proposing itself the useful modifica­ tions, the system does automate the most difficult and tedious aspect of creative design, that of formulating the constraints and possible solutions. Our current research focusses on methods for combining two devices and their functions. This should make it possible, for example, to design an escapement by combining two ratchet de­ vices. The combinatorial explosion of modification op­ erators would then be significantly reduced and might make automatic adaptation tractable. In conjunction with a suitable mechanism library and indexing device such as [Williams, 1990], truly creative design systems might be possible.

2 However, our 'program only takes kinematics into ac­ count. Constraints on materials or manufacturing may make another mechanism better.

Acknowledgements

This research has been supported by the Swiss National Science Foundation (Fonds National de Recherche Sci­ entifique ).