Functional Representation of Designs and Redesign Problem Solving

1 Design: Proposal, Verification, and Redesign

The design problem can be abstractly characterized as a constrained function-to-structure mapping. The de­ sign task takes as input the specifications of the desired functions of a device and the constraints on the design, and produces as output a specification of a structure that realizes the desired functions and satisfies the con­ straints. One way to analyze a complex task such as design is to identify the methods that can be applied to the task, the knowledge and control that these methods require, and the subtasks generated by them. This anal­ !sis produces a task structure [Chandrasekaran, 1989], 1.~., a task-s_ubta~k decomposition of the problem, along w1th a speCificatiOn of the knowledge required for each of the subtasks. For a given task in this task structure the choice of the method can depend on the knowleda~ available to the problem solver and the computation:! efficiency of finding the solution by various methods ap­ plicable to the task.

One method for solving design problems is propose, verify, and redesign [Chandrasekaran, 1988]. This method identifies and orders three su btasks each of which in turn can be performed in different' domains by different methods. For instance, case-based methods have recently become a subject of research for the pro­ pose subtask, and the verify subtask can be performed by a variety of methods, including actual testing of the device, analytic methods such as finite element analysis and various simulation techniques. One goal of this pa~ per is to perform an analysis of the task of redesign in terms of the subtasks into which it can be decomposed, and the methods applicable to them. The second goal of this paper is to explore the use of function-structure model~ .for the redesign task, specifically, to investigate the utd1ty of the functional representation scheme fSem­ bugamoorthy and Chandrasekaran, 1986] which ~odels the relationship between the structure of a device , the behaviors that arise from it, and the teleology of the device as a whole. This research builds on our earlier work [Goel and Chandrasekaran, 1988] in which we pro­ posed the use of functional representation of desians in · 0 · 0 cntlqumg a proposed design, i.e., in localizina the failure to deliver a function to a part of the struct u~e .

·This research has been supported by the Defense Advanced Research Projects Agency, RADC contract F30602-85-C-0010 the National Science Foundation, grant CBT-87-03745, and th~ McDonnell Douglas Corporation, research contract WS-MDRL2931. Computer facilit ies were enhanced by gifts from the Xerox Corporation.

1.1 Redesign: Corrective and Compensatory

Redesign is triggered as a task whenever the verify sub­ task shows that the proposed design falls short of the desired, either because some of the desired functions are not realized or because some of the behaviors are unde­ sirable. Once the proposed design has been modified the verify-redesign cycle is repeated if the design is ge;ting ~loser to the desired one, or a different candidate design IS sought from the propose subtask. In this paper, we are particularly concerned with redesign problem solv­ ing when the verify subtask finds an undesirable device behavior. The redesign of a ball bearing assembly which generates excess heat due to large rotational loads, where the generation of excess heat is an unintended and un­ desirable dev.ice behavior, is an example of this generic class of redes1gn problems.

Solutions to this redesign problem can be corrective, or compensatory, or some combination of the two. The re­ designer may diagnose and repair the structural fault re­ sponsible for an undesirable behavior, or it may propose additional structures that can compensate for the unde­ sirable behavior. If, for instance , isolating the structural fault responsible for an undesirable behavior or full v cor­ recting it is not feasible, or is computationally t;o ex­ pensive, then the redesigner may devise a compensatory solution to the problem. In the ball bearing example, the proposal for the use of a cooler to remove the excess heat generated is a compensatory redesign solution . In this paper , we are especially interested in corrective redesign problem solving.

The method of correcting an undesirable behavior fur­ ther decomposes the redesign task into two subtasks: diagnosis and repair. The diagnosis subtask takes the proposed structure and its undesirable behaviors as in­ put, and gives the structural causes for the undesirable behaviors as the output. The repair subtask of redesign takes the desired functions, the proposed structure, the undesirable behaviors and their structural causes as in­ put, and produces as output a modified structure that realizes the desired functions without the undesirable behavior . The diagnosis subtask can be performed by a variety of methods ranging from associative mapping of behavior to structure to techniques based on simu­ lation of behavior from structure. Below we present a method for diagnosis and repair that makes use of func­ tional representations of designs in the form of stored structure-to-function maps.

2 Reaction Wheel Assembly

In order to make the present discussion more concrete , let us consider the specific problem of redesigning the reaction wheel assembly (RWA) aboard the Hubble space telescope, a slice of which is shown in Figure 1. The desired function of RWA is to make the telescope point at a chosen area of the sky. The given structure of the RWA consists of a rapidly spinning rotor mounted on a shaft . The rotating shaft is connected to a stator at both ends via assemblies of anti-friction ball bearings. The power that drives the rotor comes from a motor that is remotely controlled from earth. The stator itself is mounted on the walls of the telescope bay. The constraint on the design of RWA is to keep its mass as small as possible.

The functioning of RWA is based on the law of conser­ vation of angular momentum. When the telescope is to be oriented in a specific direction, a signal from earth is sent to the motor that results in a change in the power supplied to the rotor. This causes a change in the angu­ lar velocity of the rotor and a corresponding change in its angular momentum. Due to the conservation of angu­ lar momentum, the angular momentum of the telescope as a whole changes in the opposite direction. When the telescope nears its desired orientation, a change in the angular momentum of the telescope in the opposite di­ rection is achieved in a similar manner, and the telescope angular velocity is reduced to zero.

A common problem in the operation of RWA arises due to friction in the bearing assemblies. The load on the bearings due to the rapid spin of the rotor causes de­ formation of the bearing balls which results in increased frictional forces in the bearing assembly. This causes generation of heat in the bearing assembly. The result­ ing increase in temperature is detected by temperature sensors located near the bearing assemblies . Since the in­ crease in temperature depends on the load on the bear­ ings, a typical redesign solution to this problem is to increase the load capacity of the bearings by increasing the size of the balls.

The increased temperature in the bearing assembly is· an example of an unintended and undesirable behavior.

~-----'

Figure 1: Reac r:on Wheel Assembly

The designer of RWA anticipated the potential for this undesirable behavior and included sensors in the design specifically to detect its presence. Note that because of the constraint of keeping the mass as small as possible, increasing the size of the bearing balls by an arbitrar­ ily large amount is not an acceptable redesign solution. Also, since the effects of rotational loads on bearing as­ semblies are not known analytically, it is not possible to exactly compute the smallest size ball bearings that can support a given rotational load.

In using the redesign of RWA as an illustration of our analysis of redesign problem solving, we assume that the angular momentum of the telescope as a whole is initially zero, and that the angular momentum of the rotor is in the anticlockwise direction. We also assume that the command from earth is to increase the angular velocity of the rotor so that the telescope acquires an angular momentum in the opposite direction, and that the de­ sired change in the magnitude of angular momentum is proportional to the magnitude of the command signal. While these assumptions reduce the size of the problem, they do not entail any loss of generality.

3 Functional Organization of Design Knowledge

3.1 Knowledge for Redesign Problem Solving

Efficient and effective redesign problem solving requires knowledge specific to the proposed design for a device .

Design-specific knowledge can be of several kinds, in­ cluding knowledge of the structure of the device, its com­ ponents and the relations between them; knowledge of the desired functions of the device, and the functional abstractions of the structural components; knowledge of the composition of the device function from the functions of its structural components; knowledge of the justifica­ tions for the choice of various structural components; knowledge of the device states, the state variables char­ acterizing them, and the causal dependencies between them; and knowledge of the anticipated side effects of the functioning of the device.

In addition, redesign problem solving requires knowl­ edge of the design domain that goes beyond any specific design or particular device. This includes knowledge of primitive components and primitive relations available in the design domain; knowledge of primitive substances in the domain including abstract substances such as heat ; knowledge of primitive processes in the domain such as friction and their effects on components and substances; knowledge of generic engineering mechanisms such as rolling fr iction and generic engineering devices such as bearing assemblies, and knowledge of general domain principles such as the law of conservation of angular mo­ mentum and general domain relations such as the mo­ mentum of a rotating object is proportional to its angu­ lar velocity.

3.2 Representation of Structure-to-Function Maps

\Ve now describe the functional representation scheme for representing and organizing knowledge of the struc­ ture , function, and structure-to-function maps of a de­ sign. The structure-to-function maps, called causal behaviors, explicitly represent design-specific knowl­ edge, and contain pointers to more general domain knowledge 1 .

Let us begin with representation of function . The functions of the device and its components are repre­ sented as schemas; the schema for the function of RWA is shown in Figure 2. 2 The underlined expressions in the figure are the primitives of the functional representation language. The schema specifies the device state the func­ tion takes as input and the device state that the func­ tion gives as output. It also specifies the causal behav­ ior BehaviorChangelvlomentum that results in trans­ forming the given input state into the desired output state, and the conditions under which the transforma­ tion is possible. Finally, the schema specifies the antic­ ipated side-effects of achieving the function in the form of BehaviorGenerateH eat.

1 :'1/ote that the term behavior is being used in two different contexts: to refer to the device outputs as in undesirable behavi or: and to refer to the sequences of devices states as in causal behavior.

2 The arrow on top of a variable, such as Ltdt:.·cupc · indicates that the variable is a vector quantity, i.e. it has both a magnitude and a direction associated with it. The vertical bars on the sides of a vector variable indicate that only the magnitude of the variable is being used. The symbol ~ denotes a change in the value of the variable. The symbol f denotes proportionality, while the p ositive sign indicates direct proportionality.

Knowledge of structure in the functional representa­ tion scheme is organized in a structure-substructure hi­ erarchy. Each substructure in this hierarchy is repre­ sented as a schema. A part of the schema for the ball bearing assembly is shown in Figure 3; not all the prim­ itives shown are used in redesign problem solving below. The schema specifies the . functional abstraction of the device, the domain principles and relations underlying its operation along with the operating range, its struc­ tural relations with other components, and the justifi­ cation for its choice. The schema also contains pointers to the state transitions in causal behaviors in which the component plays some role, specifically to the transitions state2 -+ state3, state3 -+ state4, and state4 -+ state5 in BehaviorGenerateH eat.

Causal behaviors compose the functions of the structural components into the device functions, and are represented as acyclic directed graphs. A node in such a causal graph represents a causal state of the device characterized by its state vari­ ables. An edge between two nodes in the causal graph represents a causal state transition. The causal graphs for BehaviorChangeM omentum and BehaviorGenerateH eat are shown in Figures 4 and 5, respectively. Note the causal dependencies between the state variables characterizing the causal states in the two figures. 3 A state transition in a causal graph can be one of several types. For instance, a transition could be due to the function of some component, e.g., the transition state2 -+ state3 in BehaviorC hang eM omentum shown in Figure 4, or it could be based on some domain princi­ ple , e.g., the transition state5 -+ state6 also in Figure 4. Often, domain principles are applicable only in the con­ text of some structural component or relation, e.g., the transitions state2 -+ state3 in Figure 5 and state3 -+ state4 in Figure 4; sometimes they may require addi­ tional assumptions, e.g., the transition state6 -+ state? in Figure 4. Also, a state transition may point to a more detailed sequence of state transitions, e.g., the transition state3 -+ state4 in BehaviorC hang eM omentum points to BehaviorGenerateH eat .

3 The circular arrows adjacent to some of the vector variables in Figures 4 and 5 indicate the direction of rotational motion about

the rotor axis, clockwise or anticlockwise.

Note the reference to the law of conservation of angular mo~entum in transition s~ate6 -+ state7 in BehaviorChangeMomentum. Knowledge of such Physics laws can be represented as behavioral templates. Knowledge of the law of conservation of angular mo­ mentum, for example, can be represented as a small set of behavioral templates corresponding to the prototyp­ ical situations governed by the law. In one prototyp­ ical situation, for instance, if one object is contained in another, and the angular momentum of the first ob­ ject changes then, on account of the conservation law, the angular momentum of the second will also change with an equal magnitude but in the opposite direction. In fact, the functioning of RWA is based on this use of the law. Thus, the behavioral template represent­ ing this prototypical application of the law of conser­ vat ion of angular momentum (not shown here) is in­ stantiated in BehaviorChangeM omentum that results in the achievement of the function of RWA (transition state6 -+ state7 in Figure 4) .

The ball bearing assembly, which has been treated as a generic device in functional representation of RWA, can be similarly represented in terms of its structura; components and their functional abstractions , making available finer grained design knowledge. At a larger grain size , the telescope as a whole can be represented . Thus the design knowledge is organized in two hierar­ chies: the classical structure-substructure hierarchy, and the function-behavior hierarchy. Since the causal state transitions in a behavior contain pointers to the sub­ structures, and the schemas representing substructures contain back-pointers to the causal state transitions in which they play some role , knowledge in one hierarchy is accessible from the other. This function-structure model of the design is generated by the propose subtask of de­ sign.

4 Corrective Redesign: Diagnosis and Repair

4.1 Diagnosis of Undesirable Behavior

Let us now consider how the functional representation of des ians helps in solving redesign problems in which an und;sirable behavior is to be corrected. As mentioned above, the method for corrective redesign decomposes the redesign task into the subtasks of diagnosis of the structural faults(s) responsible for the undesirable be­ havior and repair of the structural faults . The method of functional reasoning further decomposes the diagnos­ tic task into three subtasks: identification of the causal behavior(s) in which the sensor that detects the unde­ sirable behavior plays a functional role; identification of the malfunction responsible for the undesirable behav­ ior; and identification of the structural fault responsible for the undesirable behavior 4 .

4 w~ ass urn~ that th~ s~nsor itself is functioning prop~rly. s~n­ sor validation is a relat~d but diff~r~nt probl~m which r~quir~s functional r~pr~s~ntation of th~ s~nsor .

Let us begin by analyzing the task of identifying the causal behavior in which the sensor that detects the un­ desirable behavior plays a functional role . Since the un­ desirable behavior does not realize any explicit function of the design, searching the function-behavior hierarchy for the causal state transition in which the sensor plays a role is likely to be computationally very expensive. How­ ever, because of the specification of the structural rela­ tions in the schema for each substructure, the structure­ substructure hierarchy can be searched more efficiently to locate the schema for the sensor. The schema for the sensor specifies the causal behavior(s) in which the it plays a functional role. In the RWA problem, for exam­ ple, the schema for the temperature sensor (not shown here) specifies that the transition state5 -+ state6 in BehaviorGenerateH eat is based on the function of the sensor (see Figure 5) .

The second subtask of diagnosis is to identify the malfunction responsible for the undesirable behavior. This is accomplished by backward tracing of the causal behavior(s) determined in the first subtask, starting from the causal state transition in which the sensor plays a functional role. The values of the state vari­ ables characterizing the preceding causal states are computed and checked against the operating ranges of the structural components specified in the state tran­ sitions. In the RWA problem, this backward tracing of BehaviorGenerateH eat leads to state2 characterized by the variable Ldhw ring (Figure 5). On comparing the value of Ldbearing with the operating range specified in the schema for the bearing assembly (see Figure 3) , it is determined that the load on the bearing is beyond what the bearing assembly can support. This identifies the malfunctioning of the bearing assembly as the cause of the given undesirable behavior .

The last subtask of diagnosis is to identify the struc­ tural cause of the undesirable behavior. This is accom­ plished by using knowledge of the relations underlying the operation of the malfunctioning substr1,1cture iden­ tified in the second subtask. In the RWA problem, for example, the schema for the bearing assembly (Figure 3) shows that the load capacity of the bearing assembly, max.Ldbearing depends on the size of the bearing balls, Rball · This enables the identification of the structural cause of given undesirable behavior, namely, the size of the bearing balls is too small for the load .

4.2 Repair of Faulty Structure

Once the structural cause for the undesirable behavior has been determined, the redesigner has to repair the structure to correct the behavior . The method of func­ tional reasoning decomposes the repair task into three subtasks: selection of a repair strategy for correcting the structural fault; proposal of a repair solution; and testing whether the proposed solution necessitates addi­ tional structural modifications .

The subtask of selecting a repair strategy requires a memory of repair strategies indexed by the type of repair tasks for which they are appropriate. For instance, one common repair strategy is component replacement, i.e., to replace the component responsible for the undesirable behavior with a functionally equivalent component that meets the design requirements . This repair strategy is useful for repair tasks in which the parameter of some component is responsible for the undesirable behavior. The functional representation of design helps in identi­ fying the type of repair task, which can then be used to select the appropriate repair strategy. In the RWA problem, for example, the diagnostic task showed that the small size of the bearing balls is responsible for the abnormally high reading of the temperature sensor. This leads to the selection of the repair strategy of component replacement .

The second subtask of repair is proposal of a repair solution. Functional representation is of limited help in performing this task; the repair solution is produced by the application of the strategy selected in the first sub­ task. In the RWA problem, the repair strategy of com­ ponent replacement uses the relation between Ldb, aring and Rball to propose the solution of replacing the bearing balls with larger cnes.

The third subtask of repair is to check whether the proposed solution necessitates additional structural modifications. This is accomplished by causally propagating the effects of the structural modification. Starting from the state transition where the structural modifica­ tion is proposed, the causal behavior is traced forward. New values of the state variables characterizing the suc­ ceeding causal states are calculated using the causal de­ pendencies between them, and compared against the op­ erating ranges of the structural components specified in state transitions. If the value of some state variable is beyond the range of the corresponding component, then another structural modification is made along the lines indicated above . This process is repeated until the be­ havior is traced fully, and the values of the state variables show that the undesirable behavior has been corrected.

The modified structure produced by the repair task can now be verified, and if needed, redesigned again. Note that the causal propagation of the effects of a struc­ tural modification in the repair task helps to locally verify that the undesirable behavior has been corrected. How­ ever, this does not constitute verification of the design as a whole.

4.3 Limitations of the Method

There is of course no guarantee that the method for cor­ rective redesign described above would succeed in solv­ ing an arbitrary redesign problem. Its success or fail­ ure depends on whether or not the needed knowledge is available to it. For instance, if, in the RWA problem, knowledge of the causal relation between the load ca­ pacity of the bearing assembly and the size of the bear­ ing balls, or the repair strategy of component replace­ ment were not available, the redesigner could not have reached the solution of replacing the bearing balls with larger ones . Instead it would have continued to trace the causal behavior backwards, until, using the knowl­ edge of the causal relation between the angular velocity of the shaft and the load on the bearing assembly, it de­ cided that the angular velocity of the shaft was too high, and proposed reducing the angular velocity of the shaft as the solution to the redesign problem. The designer could have failed altogether if even this knowledge was unavailable. However, the problem solving does termi­ nate, even if in failure, once the causal behavior has been traced fully.

This analysis also provides focus to the issue of spatial and geometrical reasoning in redesign problem solving, since the realization of a redesign solution often involves reasoning about the shapes and contours of structural components. In the RvVA problem, for instance, once the redesign solution of increasing the size of the ball bearings is reached , it still remains to be decided how this solution is going to be realized. The functional rep­ resentation of RWA makes the knowledge of the struc­ tural relations of the bearing assembly available to the redesigner. However, what changes have to be made to the shaft and the stator so that larger sized ball bearings can be used is not clear. This requires the capabilities of spatial and geometrical reasoning about the shapes and contours of ball bearings, the rotor, and the stator.

5 Concluding Discussion

We have presented an analysis of the redesign problem and shown how function-structure models of designs can be used for solving a generic class of redesign prob­ lems. This work follows a rich literature on redesign problem solving. Stallman and Sussman [1977] intro­ duced dependency-directed backtracking to decide what structural component to modify when a design failed to achieve the desired functions. The causal behaviors of the functional representation scheme serve a similar pur­ pose. These behaviors capture the causal dependencies between the device states which enables the redesigner to trace the structural cause of an undesirable behav­ ior. The REDESIGN system [Steinberg and Mitchell, 1985] makes use of the purposes of structural compo­ nents in a design which is similar to the notion of func­ tional abstractions of structural components in the func­ tional representation scheme. REDESIGN's redesign knowledge, however, is largely associative rather than in the form of function-structure models. The PROMPT system [:\Iurthy and Addanki , 198 7 ~ uses modification operators, and decides on thei r applicability by testing their preconditions. The functional reasoning method for redesign seeks to identify various types of modifica­ tion tasks, and calls for a functionall y organized mem­ ory of modification strategies indexed by the tasks. The CHEF system [Hammond, 1989] makes use of anticipa­ tory knowledge about potential problems with a plan for retrieving the best-matching plan from memory. In our framework , the redesigner uses knowledge of anticipated side effects for correcting undesirable behaviors .

In a different line of research, Rieger [1976] has used functional models of devices for problem solving as well as for natural language understanding. The function­ structure model described in this paper can be similarly viewed as providing both a partial theory of comprehen­ sion of the functioning of devices as well as a language for capturing design knowledge useful in redesign and diag­ nostic problem solving. However, while Rieger's models focus on the identification of various types of causality, the functional representation scheme emphasizes the or­ ganization of causal knowledge.

The main contributions of the present research are two-fold. First, it provides a partial task structure for the redesign problem. That is, it identifies a task-subtask decomposition for the redesign problem, some of the methods applicable to the subtasks, and the knowledge required by these methods. This analysis begins to pro­ vide a framework for capturing the interactions between the tasks, methods, and knowledge for redesign prob­ lems. The second main contribution of this work is to show how the functional representations of designs can be used for solving a class of redesign problems. It also specifies constructs in the language for representing and organizing anticipatory knowledge of undesirable behav­ iors, and for accessing this knowledge from the specifi­ cation of the structural components in the design.

The decomposition of the redesign problem into a task structure and the functional organization of design knowledge provides a method for managing the complexity of the problem. Both the diagnosis and repair subtasks of corrective redesign problem solving can be computationally very complex. In diagnosis, every com­ ponent and every relation between components in the structure can potentially be the cause of an undesirable behavior. In repair , every substructure in the design is modifiable in potentially very large number of ways. Moreover, each structural modification can potentially affect the entire design. The decomposition of the re­ design task into a number of smaller subtasks and the functional organization of design knowledge helps in fo­ cusing the attention of the redesigner and localizing the search at each step in redesign problem solving. Finally, we note that the functional representation of a device also provides a causal explanation of the functioning of the device as well as justification for the design decisions.

Acknowledgments

The problem domain of redesign of the reaction wheel as­ sembly aboard the Hubble space telescope was suggested to us by Professor Edward Feigenbaum. Our description of the reaction wheel assembly has been adapted from [Feigenbaum et al., 1988]. S. Prabhakar has made sig­ nificant contributions to the ongoing implementation of the KRITIK system, which embodies the general frame­ work for adaptive design problem solving presented in this paper. This paper has benefited from helpful com­ ments by the reviewers.