2. RELATED WORK

Function structure research has found its way into a number of educational texts (Ulrich & Eppinger, 1995; Otto & Wood, 2001) because of the presentation provided by Pahl and Beitz (1984). Furthermore, research building upon the concept of function structures has flourished in the past 15 years. Numerous publications have extended the application of function structures (Collins et al., 1976; IEEE, 1998; Chen et al., 2002) and formalized the use of such structures (Hubka et al., 1988; Kirschman & Fadel, 1998; Szykman et al., 2000). Computational approaches have also been explored that further expand the value of function structures (Gietka et al., 2002; Wang & Yan, 2002). In a way, this detailed research into how to represent function is a subset in a larger design process where solutions to function precede those of an artifact's structure. The function–behavior–structure approach presented in Gero and Kannengiesser (2003) has provided a theoretical approach to managing design knowledge as it is created by a team of engineering designers. Although the function structure approach discussed here has often been developed “top-down” from how engineers divide a larger design problem into manageable elements, continuing efforts (including those discussed here) are closing the gap with the related work of functional representation in artificial intelligence research (Chandrasekaran et al., 1993).

In recent years, engineering researchers have discovered that shape grammars, originally used in architectural research (Stiny, 1980), provide a flexible yet ideally structured approach for various aspects of engineering design (Cagan, 2001). A shape grammar is a set of shape rules that are applied in a step by step way to generate a set, or language, of designs. Grammar-based design systems offer the option of exploring design alternatives as well as automating the design generation process. An experienced designer can construct a set of rules to capture his/her knowledge about a certain type of artifact. The grammar can then be constructed such that any execution of the rules creates a feasible solution (Longenecker & Fitzhorn, 1991) or captures the style of a specific period (Cagdas, 1996) or of a specific designer (Koning & Eizenberg, 1981).

An important offshoot of the shape grammar research is graph grammar research. Similar to production systems in cognitive psychology (Klahr et al., 1987), graph grammars are comprised of rules for transforming nodes and arcs within a graph. These techniques create a formal language for generating and updating complex designs from a simple initial specification or seed. Graph grammars are an emerging concept in design synthesis (Pinilla et al., 1989; Fu et al., 1993; Schmidt, 1995; Li et al., 2001). The development of these rules encapsulate a set a valid operations that can occur in the development of a design. Such representations can produce a wider variety of candidates because solutions need not have common characteristics, but merely a common starting point.

According to Kurfman et al. (2001), “the problem with many of these function-based design methodologies is their inability to produce repeatable functional models of a particular product. Two engineers can be given the same product, customer needs, and the process choices, but the likelihood of them producing similar function structures is low.” This is a major issue in using function structures. To develop a formalism for function structures, there needs to be a common language in which the formalism can be developed. The basis that was developed by Stone and Wood (2000) is used for this purpose. The development of the functional basis helps to foster our understanding of function structures and aids in developing repeatable function structures. Hirtz et al. (2001) developed the reconciled functional basis, which covers most of the functions being used in engineering artifacts. This basis consists of eight primary function classes and three flow classes that are further subdivided into secondary and tertiary functions and flows, respectively. This basis has been adapted to suit our formalism and requirements.

3. APPROACH

The typical functional structure methodology starts with a black-box model representation of a product where the identified inputs and outputs to the system are shown on the left and right side of the boxes, respectively, and the primary function of the product is shown within the box as a verb–object pair. Our approach begins by developing a chain of subfunctions that operate on each of the input flows. Consider the example of an Electric Staple/Nail Gun. On observing the product, we notice that the staples and nails are guided into the product and are secured using a spring. We see that the primary function of the gun is to shoot the staples or nails, which have been previously inputted and secured. To shoot, we need to impart some form of energy in the device. It is seen that the energy that is used here is mechanical energy, which is obtained by converting the incoming electrical energy. Hence, we need to import electrical energy and convert it into mechanical energy. In addition, we need human energy to direct when to actuate the electrical energy. Human energy enters the system and gets converted to mechanical energy due to the movement of the hand and this energy actuates the system. We also need to model the staples and the electrical energy as these interact with each other. Following this systematic dissection, we can create all the functional chains for all of the flows entering and leaving the black-box model. This analysis reduces the final product to its original functional specifications. Our goal, however, is to be able to aid the engineer before the design is complete; therefore, we seek a method to automatically generate multiple function structures given the black box as a seed or starting point.

This paper presents the preliminary findings toward this goal. The hypothesis of this work is as follows: a formal set of rules can be created that will describe function structures for a range of products, based on a common basis, and which, when executed, will help in the automatic generation of function structures. Derived from this hypothesis are certain objectives that need to be satisfied. It needs to be shown that a set of rules can be developed that can effectively describe function structures. This set of rules then can be programmed as an algorithm that can be used to generate function structures. Thirty consumer products are chosen to provide an empirical basis for creating our rules. These products offer simple technologies, yet the range of technologies that each of these products uses varies enough to present a challenging problem. The products that were examined are shown in the Table 1.

The 30 products used as an empirical basis for the development of the grammar rules

One of the first challenges we faced in comparing the functions structures created for these products is the unpredictability of signal flows. Signal flow depends to a large extent on the environment in which a product is used. We believe that trying to model signal flows is cumbersome and leads to rules that are too vague and general. Hence, signal flows have not been considered at this time.

Another challenge in our study was determining the level of granularity to use in systematically making function structures. In the functional basis (Stone & Wood, 2000) three levels are developed: primary, secondary, and tertiary. Using different levels of granularity leads to different function chains. This poses a problem for formalizing the grammar for function structures. The problem becomes a lot more complex if the developed system of rules must differentiate and understand the three levels. This necessitates the formation of a new reduced basis that incorporates the elements of the previous functional basis. For example, the secondary level of Guide has four different words at the tertiary level: Guide, Translate, Rotate, and Allow DOF. To create a grammar that is consistent, we have to create a rule that would apply to secondary class Guide, that would be applicable to the tertiary class as well. At the same time, because these bases have their own intricate differences, rules have to be created to maintain those differences at the tertiary level. This creates a complexity that becomes magnified when all the primary, secondary, and tertiary classes are taken into account. It is a much better approach to create the rules considering just one level, as this will result in a more robust set of rules. The reduced functional basis is shown in Table 2.

The three levels of granularity in the functional basis and our reduced single level used in our function structures

An empirical study is conducted to extract rules from function structures of different products. This study culminated in the design knowledge that is captured in the developed rules, which are implemented to generate new functional models. We observed similar rules or patterns from the function structures created for products shown in Table 1. By using the reduced basis, we are able to more readily develop generic rules that are valid across all products. Because the same rules were seen in successive products that were examined, the number of newly created rules diminished throughout the process. Figure 4 shows the graph between products examined and the rules obtained from them. The number of rules appears to asymptote toward a finite number. This validates our assumption that a finite set of rules can describe all function structures in our current product domain. We recognize that the rules that have been developed do not fully represent the entire set of engineering artifacts, but the current set provides a basic framework on which future rules can be developed.

A graph of the Number of Products examined versus the Rules obtained from each of them. The products are listed in random order.

Grammar-based design systems offer the options of exploring the design alternatives as well as automating the design generation process. It may be argued that using grammars can hinder the creativity of the user as the generated solutions are based on a predefined set of rules, which makes the generated design repetitive and clichéd. However, the use of a design grammar helps to generate a wide range of solutions by altering the way the rules are applied and changing the rules themselves with little or no input from the user. This can give the designer the potential to evaluate a large number of alternative designs without tedious work. This set of designs generally includes many alternatives that might have been overlooked by a designer who is working without the aid of a grammar, thus paving the way for possible innovative designs. The shape grammar rules can be used to represent the transitions between states in a search tree as shown in Figure 2. Thus, such a representation of a design space requires navigation techniques to enable search for a desired or optimal solution. The issue in implementing the grammar now becomes one of controlled searches through the space of solutions. In our case, we start with the black-box model as the initial seed. Each rule that is recognized as feasible opens up different avenues that can be explored. We have the option of applying any of those rules and then once again evaluating the design to see where, which, and how many rules can be applied. This process is repeated until there are no more rules that can be applied. The logic that is followed for recognizing, applying, and reevaluating the design at each stage is explained in the next section of this paper.

4. RULE SET

In this section, we shall discuss the rule set that is developed and the methods that we use to generate the rules. A function structure is composed of two basic units: functions and flows. A function can be defined as “a description of an operation to be performed by a device or artifact, expressed as the action verb of a function block.” A flow can be defined as “a change in material, energy or signal with respect to time that is expressed as the object of a function block, a flow is the recipient of the function's operation” (Stone & Wood, 2000). The main types of flows are shown in Table 3.

Common basis of energy and material flows

A major issue in the implementation of these rules is the recognition as to where and when these rules can be applied. To this end, we have borrowed the concept of active centers from the phenomenon of polymerization. In polymerization, chemical agents operate on distinct locations on a polymer chain (Progelhof, 1993). These locations are called active centers because they are potential areas of attachment by incoming molecules. Similarly, during the creation of a function structure, there are many “active centers” where incoming flows and functions can attach themselves. These active centers are the points where grammar rules can be applied and where new functions and/or flows are added if certain criteria are met at a specific open connection. In addition to borrowing the active center concept, the creation of a function structure follows a similar initiation, propagation, and termination process as that of polymerization. Rules are thus divided into three groups based on whether they create, maintain, or consume active centers: initiation rules, propagation rules, and termination rules. The initiation rules are first recognized and applied until no more rules from this group are recognized. This stage of the process includes rules that tend to create more active centers than they consume. The propagation rule set is then used to check for active centers and these rules are similarly applied until no more grammar rules are recognized from this group. As in polymerization, propagation tends to maintain a constant number of active centers. The termination set completes the function structure generation process by invoking rules that eliminate the remaining active centers.

The current development of rules has been modeled after the basic grammar conventions where rules contain both a left-hand side and a right-hand side. The left-hand side contains the state that must be recognized in the current configuration and the right-hand side shows how the design is updated to a new configuration. As long as there are “active” centers, then the function structure is not complete. At any instant there are a number of rules that can be applied, and the implementation of the grammar recognizes all of these possibilities and the associated active centers to which they apply. The rule that is actually applied can be a choice of the user or an automated process. The choices determine which branch of the tree to follow in reaching the final state of the generated function structure.

Some of the basic rules are shown in Figure 5. The gray circles with the black dots inside them that are present in these figures represent active centers, or the potential areas where flows and functions can be added. In Figure 5a, we see an active center being created. This rule recognizes any flow that is coming into the black box. If such a flow is recognized, it adds the function “Import” to the head of the flow and adds another open flow of the same type in front of the function. This is an example of an initiation rule.

Five of the 69 grammar rules developed for creating feasible function structures.

Consider the rule shown in Figure 5b. This is an example of a rule where the active center is on a function rather than on a flow. It recognizes a function named “Remove” and adds a mechanical energy flow as the secondary flow to its back and a reaction force flow to the front of the function. It also replaces the solid coming out of the flow with two solids. This rule captures the principle that whenever we cut or grind a solid, we need to supply some mechanical energy and this results in two or more pieces of that solid. It should also be noted that this rule results in the creation of many active centers. This rule cannot be applied again because the active center necessary for rule recognition has been eliminated. Care must be taken to define rules that prevent the same rule from being applied over and over again.

The rule shown in Figure 5c captures another common principle. Usually, when mechanical energy is being supplied, the energy is amplified using gears and this is represented by the function “Change ME.” This rule looks for a flow of type mechanical energy that is open at the tail and is pointing to the function, “Remove Solid.” If applied, this rule adds the function Change ME to the tail and adds another flow open at its tail to the back of the Change ME function. Figure 5d shows a rule where an electric energy flow that is pointing from Import is recognized and the functions “Transmit EE” and “Actuate EE” are added to it. This rule is observed in many products that use electrical energy, because electrical energy is always transmitted and actuated before being converted to the required form. The above two rules each remove an active center but end up creating a new one. The rules shown in Figure 5b–d are propagation rules as they use and replace active centers.

The final rule shown in Figure 5e is a termination rule where active centers are removed. Whenever two flows are recognized such that we have an open electrical energy flow and energy of any other kind (represented as XE) that needs to be supplied, we convert the electrical energy to the required form and transmit it. Termination rules are vital in obtaining a valid function structure. In the next section, we will illustrate and discuss how these rules are used to create an example function structure.

5. ILLUSTRATIVE EXAMPLE

The Black & Decker electric knife is used to illustrate how rules are recognized and applied to construct a valid function structure. As seen from the black box in Figure 6a, the primary function of this product is “Cut Food.” The black box is then rephrased into the language of the common basis, which in this case is Remove Solid. Traditionally, the black-box model contains a single verb–noun description of the intended function of the product and the input and output energy, material, and signal flows. Figure 6b shows the black box in the common basis language that we use in the grammar.

(a) Electric knife black box and (b) black box in reduced basis.

Figures 7, 8, and 9 present snapshots of the generation process of the three stages of initiation, propagation, and termination. Four snapshots between start to finish of each stage has been provided. The active centers overlaid with colored squares show the active center that has been selected for rule application. The ovals show the result of rules applied at a particular active center. In between the snapshots, we list the grammar rules that are applied (for a complete description of all 69 grammar rules, see www.me.utexas.edu/∼adl/fs_grammar.htm).

A pictorial representation of the generation of the function structure in the initiation stage.

A pictorial representation of the generation of the function structure in the propagation stage.

A pictorial representation of the generation of the function structure in the termination stage.

Consider Figure 7. The algorithm first reads the black box and creates an empty function structure that simply has the inputs, outputs, and the primary function. At this stage, only the initiation rules are active, and hence, the function structure is scanned for possible initiation rules that can be applied. It is seen that at any instant a number of rules can be applied at different active centers. Rule 1 recognizes a flow whose head is “outside” and whose tail is “inside” of the black box and adds a function Import; to that flow. Furthermore, it creates a new flow whose tail is linked to Import and head has the value “NULL” (to indicate it as an active center). Rule 2 also works in a similar way for outputs. Figure 7 shows the application of rules 1 and 2 that transforms the black box into an intermediate state with as many as nine active centers.

These nine active centers then become the input for the propagation stage (Fig. 8). Rule 26 recognizes the function Remove Solid and adds some flows in front of and at the back of that function. The application of rule 26 adds a new flow “ME,” which is open at its tail. This becomes the place where the next rule, rule 29, is applied. Rule 29 adds a function Change ME to the back of the ME flow and creates another open flow at its back. Thus, we see that in the propagation stage, active centers are recognized, rules are applied, and most active centers that are removed are replaced by new ones. In the termination stage shown in Figure 9, rules act on the open and dangling flows and complete the function structure by carefully finding functions that connect between the remaining active centers. The result is the completed function structure shown at the end of Figure 9.

6. IMPLEMENTATION

Function structures can be compared to a typical graph where the vertices are represented by functions and the edges are represented by flows. It is obvious that they are directional graphs as the direction of flows is important in ensuring the validity of function structures. The data structure for a graph needs to store the vertices and edges such that each edge references to the two vertices that it connects to. Typically, graphs store information only in the vertex and the edges are used just to point from one vertex to another. In the case of function structures, we need to store information in both the vertices (functions) and edges (flows) as is discussed in Section 4. The method that we follow stores both the functions and flows in a sequential list. Each function references all edges it is associated with, and each flow stores information about the function that it is pointing from and pointing to.

Flows and functions are represented as data structures. Some of the information that is stored in a flow includes its unique number, its name, the unique numbers of the functions connected to the front and back of the flow, whether the flow is a material or an energy, and the specific type of material or energy. Similarly, functions also store relevant information like unique number, the unique number of flows connected to its front and back, information about the flow that is being processed by the function.

Before explaining how the program works, it is necessary to elucidate the different classes that are a part of the program. There are three main classes that help in modularizing the program so that it is easy to understand.

6.4. Description of process

The sequence of the program is as follows: scan the function structure for active centers, recognize applicable rules, create an active list, if the size of the active list is zero, then move to the next stage; if the size of the list is greater than zero, return the list of applicable rules, choose one rule (done through user interaction), and apply it. The process is repeated for the three stages because the basic framework remains the same, the only thing that differs is the set of rules that are recognized and applied.

The black box is input as a text file that has the inputs, outputs, and the primary function(s). Flows are specified starting with the kind of flow, M or E, for Material or Energy, followed by the domain of the flow (i.e., Human, Electrical, Hydraulic, etc.). A sample black box for a coffee grinder is shown in Figure 10. Currently, the terms in this text file must match the accepted set of terms used thus far. Although any translation to the reduced common basis must be performed as in the example of Figure 6, this is the only preparation needed for the implemented system to begin constructing a function structure.

A black box of a coffee grinder as it is input into the program.

6.5. Computational interface

Snapshots of the user interface at various points during program execution are shown in Figures 11, 12, and 13. Figure 11 shows a screenshot of the user interface as soon as the program is executed. There are four output text boxes in the window that display (from left to right) the applicable rule set, the active centers, the flows, and the functions of the function structure at that instant. There is also a rule set reference window at the bottom that the user can access information about any of the 69 rules. Currently, there is no graphic showing the function structure as it is being created. Although drawing such a structure is a fairly straightforward human activity, the heuristics followed are difficult to implement. In fact, the automatic presentation of graphs is a research area in itself. As a result, the user currently must draft the structure from the information presented in the flow and function text boxes. The user is first presented with an option to choose the kind of generation that he/she wants to pursue. If the “automate” option is chosen, then the computer will repeatedly choose rules and active centers until no more rules are applicable.

A screenshot of the user interface at the onset of the process of building a function structure from a black box.

A screenshot during the running of the program.

A screenshot after the program is complete.

Figure 12 shows the program being executed. The “Applicable Rules” text box displays the list of active centers and the applicable rules at those active centers. The “Active Center” text box displays more information about each active center. The “Flow” and “Function” text boxes display all the flows and functions of the function structure. The user enters the number of the active center and the rule that he wants to apply at that active center. Figure 12 shows an example where there is only one rule applicable at the active centers; however, there may be a case where more than one rule is applicable at one active center. If the user has chosen the “guide” option, he/she can choose the rule that needs to be applied. This way, the user has control over the final function structure.

Figure 13 shows the program once the function structure is generated. Once the program is complete, a text file that has the function structure in a textual easy to follow format is written. The function structure of a coffee grinder is shown in Figure 14.

A completed function structure of a coffee grinder returned at the end of the process.

7. EXPERIMENTS

In this section we discuss two experiments that have been developed to test the effectiveness of the function structure grammar. First, we look at a comparison of function structures created by engineering designers using the grammar rules to function structures created by designers not using the rules (Section 7.1). Next, we look at the resulting function structures created independently by a computational process (Section 7.2).

7.1. Effectiveness of grammar rules applied by hand

To check whether these rules provide a framework to designers that actually helps create better function structures, an experiment is conducted. A set of seven graduate students was divided into two groups of three and four. These students had recently studied in a design methodology course that taught how to create high-quality function structures. Each of the groups of students was given a product for which they had to draw the function structure. The products were then exchanged in the groups and function structures were again created, this time using the grammar rules as a guideline.

These function structures were then graded for quality using a double-blind system. The grader (another graduate student who had been a teaching assistant for a design methodology class) was given a shuffled stack of function structures and was not aware of the experimental details, or the existence of the grammar. The strategy that the grader used to determine a quantitative score for the quality of a function structure was done by averaging separate scores for consistency, level of detail, completeness, and creativity. It is not clear how the grader defined such terms, but when questioned, the grader indicated that he initially determined what he thought the best function structure for a given product should be and then compared each specimen to his ideal. He said he was looking at how well the students understood the basic physics of the product and how thorough they were at identifying all functions that would represent significant and subsequent design efforts.

The results are shown in Figure 15. It is easily observed that the function structures that were created using the rules score better than the ones done without the function structure grammar. As the figures indicate, nearly all of the highest scoring function structures were done with the aid of the grammar. In fact, students who scored poorly when the grammar was not used improved greatly when aided by the grammar (see Fig. 15b). A t test was conducted comparing students' scores when the grammar is used to scores when the grammar is not used. The mean score for structures made with the rules is 8.63, with a standard deviation of 0.85. This is shown to be significantly higher (a t test of seven samples yields a value of 3.41 or a probability of less than 0.05 that the null hypothesis is true) than the mean score for those created without the rules (mean = 5.38, standard deviation = 2.21).

A graph between grades and students. (a) The grades obtained using the rules are the dark bars (average = 8.48) and the grades obtained without rules are the light bars (average = 4.8). (b) A graph showing the performance of the students using rules and not using rules.

After the grading, we questioned the grader for his general thoughts about the function structures. He mentioned that there seemed to be two sets of students: those that put the time into creating quality function structures, and those who did not understand all of the concepts. When we showed the grader the two function structures created by student #2 (one with a score of 3.5 and one with a score of 9.375), the grader was surprised, and conjectured that the student must have run out of time in creating the electric knife example. In fact, student #2 had created the knife function structure first on his own and the air pump structure using the grammar rules. When asked to order the function structures that would most aid in the design of one of these products, the grader ranked three of the function structures created by the grammar as the best. Of the poorest function structures, the grader said that these students did not spend enough time to capture the subtleties of the products and that performing the exercise would not help subsequent design activities. He hoped that such students were using an alternate method (to creating function structures) to properly explore the conceptual design phase.

7.2. Automated development of function structures

As described in Section 6, the user can choose to have the computer automate the search for a complete function structure. Because the grammar rules encapsulate the feasible additions that can be made, the automation is based simply on choosing a series of applicable rules. In this example, we use the black box for the palm sander as shown in Figure 16. Currently, we are not able to systematically search the entire tree. Instead, we simply run through 20 controlled searches through the tree to compare whether the created solutions are valid. Interestingly enough, of the 20 searches only three unique solutions were created (see Fig. 17). Fifteen of the 20 were identical (solution A), and only 2 more were found in the remaining 5 searches (see Table 4). All three solutions appear to follow the rules of creating a logical function structure and provide a clear basis of the functional requirements needed in designing a palm sander.

(a) A black box for a palm sander and (b) the reduced textual representation of the black-box input into the program.

Of the 20 searches through the tree, only three unique function structures were created for the palm sander.

The summary of the three function structures created in the automated search (A, B, and C)

As is described in Table 4, the three solutions are similar in many aspects; however, there are a few small differences. Solution B is the same as A with the exception of one function, “guide air.” In the black box, air is specified as an input and output along with pneumatic energy to charge the air on output. This forces the design to connect the air flow through a series of functions so that it can be expelled to blow away sawdust. In solution B, the air is simply “exported” after it is “transported” (where the transport function requires the participation of an energy flow, such as rotational mechanical energy, i.e., a fan). One can imagine that if embodied designs were created for solutions A and B, they would differ only in the fact that A would have some channel to “guide” the air from the fan to the outlet on the product housing where it is exported, whereas B would lack this channel and simple have the fan placed at the exit of the air on the housing. Solution C is interesting in that it divides the electrical energy into two flows once it is “imported” and uses these flows to drive the sander and transport the air separately. This may be desirable so that the fan can be turned on and off separately from the sander.