2. RELATED WORK

Representation and generation in the design process are done through the use of a fully implemented shape grammar (Stiny, 1980). In recent years, engineering researchers have discovered that shape grammars (originally a product of architectural research) provide a flexible yet ideally structured approach to engineering design methods (Cagan, 2001). The concept of a grammar is that an experienced designer can construct a set of rules to capture a designer's knowledge about a certain type of artifact. The grammar can be constructed such that any execution of the rules creates a feasible solution (see example in Longenecker & Fitzhorn, 1991) or captures the style of a specific period (see example of traditional Turkish houses; Cagdas, 1996) or a specific designer (Frank Lloyd Wright's prairie houses; Koning & Eizenberg, 1981). Because grammar research can occur at various levels of computational implementations, Chase (1998) developed a model to characterize different grammars. Figure 2 presents six scenarios that are ordered by the amount of human interaction versus computer interaction. At the current stage of this research, the sheet metal grammar falls under scenario 4, where the computer is responsible for the recognition and application of the rules and the updating of the candidate. The user interacts with the system to choose the rules to apply in order to build a complete design. In the future, we will explore this rule choice as an operation of a computational agent, thus classifying the system as a scenario 5 grammar under Chase's (1998) model.

The current sheet metal grammar is at scenario 4, where the computer determines the object and the matching conditions (recognition and application of rules).

An important offshoot of shape grammar research is the function grammar or graph grammar synthesis work (see Pinilla et al., 1989; Fu et al., 1993; Li et al., 2001). 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. The combination of manufacturing constraints and grammars was seen once before in the lathe grammar of Brown and Cagan (1997). In this work, the grammar that is developed operates on the nodes and arcs of a graph but generates a complete shape. The position of nodes within the graph directly represents elements of the sheet metal.

In formulating the sheet metal grammar, it was paramount to reference the numerous handbooks that describe the sheet metal design process and design limits in order to understand how to make the grammar function properly. The most useful of these have been Lascoe (1988) and Boothroyd et al. (1994), who address how manufacturing constraints directly impact the design decisions. Other research in sheet metal forming is often concerned with modeling the sheet as it undergoes various manufacturing operations (see Chappuis et al., 1993; Hardt et al., 1993; Hishida & Wagoner, 1993; Katayama et al., 1993). The Robotics Institute at Carnegie Mellon University has done some significant research in automated bending of sheet metal components. Their algorithms based on A* choose an optimized sequence of operations from different available options (for least cost) and also provide the necessary control signals for the tools to complete part production (see Bourne & Fussel, 1982; Cheng-Hua & Bourne, 1995; Gupta et al., 1998). The engineering design and drawing software PRO/E has a module called PRO/SHEETMETAL that is dedicated specifically to designing sheet metal components. This module helps users create features such as walls, bends, punches, notches, forms, and reliefs and also allows them to create complex geometry, convert solid parts to sheet metal, and automatically generate bend order tables.

Recently, sheet metal research has focused on a computational model that can be used during the design process. Computer-aided design tools have been developed to address specific needs in sheet metal design such as BendCAD (Wang & Sturges, 1996; Lin & Hong, 1998). Furthermore, Shpitalni and Lipson (2000; see also Lipson & Shpitalni, 1997) have set out to develop a systematic approach to representing sheet metal using Euler operators. Their work presents a similar approach to ours; however, it has not provided the set of legal operations to transform an initial sheet as is done here.

3. SHEET METAL GRAMMAR FUNDAMENTALS

The aim of this research is to develop a grammar for sheet metal components in order to capture the set of designs and manufacturing process paths that are intrinsic to sheet metal component design.

In our grammar, a design state is comprised of a “node” or a graph of nodes. A node is the smallest element of the sheet. As seen in Figure 3, this node can be viewed as a rectangular patch of sheet metal having certain properties such as length, width, and thickness. Each node can be bordered by four nodes in the east, south, west, and north directions. Within the C++ implementation, the node class has four pointers in the four neighboring directions mentioned above. A NULL in any direction means that the node is not connected to any other node in that particular direction and hence represents the physical edge of the sheet. For example, in Figure 3, node C is connected to node B in the westerly direction but has a NULL in the north, east, and south, because these are edges of the sheet. A collection of these nodes or patches, having a certain relative orientation with respect to each other, form the current state of the design. These orientations may change as a result of transformations applied to the current design state. The design changes are identical to the types of manufacturing operations that happen to the initial sheet as it is processed. Application of a typical sheet metal grammar rule consists of recognizing a node or graph of nodes with a particular structure as the “left-hand side” of the rule and then transforming it to give it a new structure and properties, as specified by the “right-hand side” of the rule. A presentation of the rules is provided in Appendix A.

An example sheet metal component represented by three nodes.

The grammar development process was a gradual one that included numerous problem-solving sessions and example problems to test the robustness of the representation. Any sheet metal component is manufactured by performing a certain set of operations. These sets of operations are traditionally constrained by the order in which the operations can be performed. Certain operations on the shop floor must be performed on the component before other operations can be performed on it. The rules that were to be developed had to take that intrinsic order into consideration. This is illustrated in Figure 4, where arrows in the direction of an operation indicate the different operations that can be performed on the component.

The four basic sheet metal operations: notch, shear, stamp, and bend. The arrows represent the ideal flow of operations. For example, bending should follow notching but not vice versa.

It is evident from Figure 4 that each operation can be performed on a sheet metal blank. It is interesting to note, as suggested by the figure, that the bend operation is and should be the last operation in the process for manufacture of the component. Similarly, notching can precede any other operation but cannot be performed after bending or stamping. Shearing can be performed after stamping, for example, trimming the edges of a stamped component. In addition to grammar rule order, the operations are also subject to parametric constraints, such as minimum length of cut, maximum length of cut, minimum and maximum angle of the bend, and so on.

The basic representation scheme for sheet metal components is the critical element in the development of the rules. Various approaches were considered. One possible approach is to represent a patch of sheet metal as four nodes (knots) connected to each other, signifying the vertices of the patch, where each node is associated with a relative position in space. A bend would signify a change in the knot structure and a subdivision of the patch. Similarly, shearing would cause a reduction of nodes. This boundary representation method is popular in computational geometry but is not used here because rules are dependent on the nature of neighboring patches and not simply on the location of the edges. Parametric information stored within each patch (i.e., node) such as the length, width, and thickness simplifies rule recognition and eliminates the need to store the absolute positions of these patches in space.

Currently, 17 rules have been developed for four basic sheet metal operations: slitting, notching, shearing, and bending. In addition to choosing the rules to be applied, the user must also select dimensions that are appropriate for the particular rule. As mentioned above, each rule is associated with a set of parameters that characterize the node. The grammar rules contain various parameters that require the user to choose rules and then choose values for the variables of the rule.

Grammar rules can be constrained so that no matter how the rules are applied, one can develop a large set of designs, which are guaranteed to be within a feasible design space. Thus, certain assumptions and constraints have been imposed on the rule selection algorithm to constrain the design space. These assumptions and constraints have been carefully determined so that they do not excessively narrow the design space, yet they prevent the designer from searching a space of infeasible designs. The assumptions and constraints made at this stage of the research are the following:

• The original shape of the sheet metal blank is a rectangle.
• All cutting and bending operations are orthogonal to the sides of the rectangle. (This does not mean that the bend angle is constrained to be a multiple of 90°.)
• No cutting can take place after a bend has been made; that is, all cutting operations on a part must be completed before bending is performed.
• No rebending can be done.
• Nodes already bent along a particular axis cannot be bent about the orthogonal axis.
• There are constraints for the minimum and maximum lengths of cuts, angles of bend, and widths of notches.

3.1. An example

To elucidate the idea of a node and the application of a rule on a node, a step by step approach to the representation of the process path to manufacture a bracket is explained below, with the help of illustrations (Fig. 5). This small bracket or stilt, shown in Figure 5a and b, is used to separate and support mailboxes on a desk. This example includes various sheet metal operations such as notching, slitting, and bending and will be used throughout Section 4 to explain the steps involved in node application.

An example sheet metal component. (a) The component is a small bracket for supporting shelves. (b) A close-up of the end shows how bends and slits are arranged. (c) The grammar works by starting with a single blank upon which rules are applied to create the final shape.

Recall that a shape grammar needs a seed, or initial node, on which transformations occur. In the case of the bracket, the application of rules starts with a rectangular sheet metal plate having certain dimensions, which serves as the seed node. Performing an operation on the sheet metal blank can be simulated by executing rules on the current state of the graph of nodes.

4. STEPS IN THE GRAMMAR EXECUTION

This section describes a C++ implementation for the representation and generation tasks of the design synthesis flowchart shown in Figure 1. A more detailed flowchart of what happens within the generation block is shown in Figure 6. In this section, we describe the four main subtasks of generation: recognition, instantiation, node propagation, and application. Each of these is implemented as a separate function.

Within the context of a computational design synthesis process shown in Figure 1, the grammar presented in Section 4 is an inner loop to the task of generating new designs.

Throughout this section we will use the example shown in Section 3.1 to illustrate how these tasks are accomplished.

4.2. Instantiation

After rule recognition is done, a list of all the applicable rule choices for every node is generated. This rule choice is a valid execution that can be performed on the given design state and includes the rule number, where it is applied, and its orientation. The user is presented with the list of these choices and he/she can choose any rule choice to achieve a new feasible design state. After selecting a rule, it must now be instantiated.

Because the grammar is parametric, dimensions within the rule must be specified. The rules are bound by a framework of constraints that are verified while selecting the values for the parameters of the rule. Parameters for every rule are different, and hence the instantiation code is different, depending upon the degrees of freedom of each rule. In Table 1 each of the 17 grammar rules is indicated by how many degrees of freedom it has. These degrees of freedom are represented by physical dimensions such as the depth of a notch or the angle of a bend.

Grammar rules with respective degrees of freedom (DOF)

To clarify, we take the example of a simple slitting rule (Fig. 7, rule 1). All 16 rules are provided in Appendix A. In the figure, the height (H) and depth (D) are the initial dimensions of the node. A slit of a certain depth is made in the node. This results in the formation of three new nodes. The instantiation of dimensions for the nodes is done in the “instantiate rules” function. In this case, the depth of the slit causes a change in the dimensions of node 1. The height of this node is now changed from H to h and its width is now D − d, where d is the depth of the slit. This change of dimension, as well as the instantiation of the dimensions for the newly created nodes, is carried out in this function. Node 4 will now have height H − h and width d. The value for h represents the position of the slit from the top edge of the target node.

Rule 1 causes a slit that splits a single node into four nodes. This requires some dimensions to be specified (height, notch width).

As mentioned earlier, each rule is associated with parameters that must be provided for the application of that rule. The values for these parameters depend on the size of the node and on the two other constants, defined as follows:

lambda_cutting: the minimum distance from each edge of the node necessary for any cutting rule to be applicable

lambda_bending: the minimum distance from each edge necessary for any bending rule to be applicable

The dimension under consideration for the node has to be at least 2 * lambda_cutting for cutting operations (or 2 * lambda_bending for bending operations) for the corresponding rule to be applicable. The values of lambda_cutting and lambda_bending are based on the experimental data.

In the bracket example (Fig. 5), rule 8 is a 3 degree of freedom rule because one can specify the position of the notch on the edge, its depth, and its width. Rule 12 is a 1 degree of freedom rule that maintains the same notch width as the notch created with rule 8. Rule 12 can be used to make symmetrical notches to rule 8. Rules 2 and 4 introduce the slitting operation. Here, rule 2 is a 1 degree of freedom rule where the user can specify the slitting depth and rule 4 performs a symmetrical slit on the opposite side.

Instantiation is carried out before application of the rule as the instantiation function sets the values of the various dimension variables. These variables are then passed to the function that applies the rules to create nodes with these new dimensions or to update the dimensions of existing nodes.

5. MANUFACTURING TIME, WEAR, AND COST PREDICTION

This section deals with the prediction of time, work (or energy), and cost for manufacturing a sheet metal component in accordance with the rule set developed and discussed above. Time, work, and cost are calculated for each individual operation performed. Total time to manufacture a complete component and the total work required are calculated by cumulatively adding the times taken and the work required for each individual rule.

In Figure 8, pseudocode is presented for our heuristic approach to finding these variables. The total process time to manufacture the sheet metal component is represented by the variable T. This time is calculated by cumulatively adding the times for all individual operations as described below. Variable “setup time” (Fig. 8, lines 3, 6, and 9) is used to represent the time to transfer the component from a previous station to the current station. Setup time includes the time to release the component from a previous station (which will be zero for the first operation), move it to the current station, and secure it on that station. In a common large-scale production unit, the setup time can be approximated as 5–7 s for one operation. Variable t_orient (Fig. 8, lines 4, 7, and 10) is used to represent the time spent to prepare the component for operation in a new orientation. For example, in order to make a slit or a notch at a new location on the component, one must rotate it so that it is accessible for the current arrangement of the tooling. The variable orientation time (t_orient) can be approximately taken as 4–6 s for one operation. Finally, the variable operation time (t_operation) (Fig. 8, lines 5, 8, and 11) represents the actual operation time (e.g., slitting, notching, shearing, bending). This time mainly depends upon the material properties of the sheet metal, the feed rate of the machine, and the area to be sheared off in the case of slitting, notching, or shearing or the angle of the bend in the case of bending.

The pseudocode for the algorithm to estimate time and cost for each grammar rule.

Consider the example of applying a notching rule. If the operation just before this operation is not another notching operation, a predetermined setup time is added to T (Fig. 8, line 6). Similarly, a predetermined t_orient is added to T to take into account the time elapsed to perform the operation in some other orientation (Fig. 8, line 7). Finally, the actual t_operation is added to T (Fig. 8, line 8).

Based on the amount that the sheet metal area is cut or bent, an approximation of the energy consumed can be found. This also depends upon the component material properties and the dimensions of the cut or notch. It is therefore important that forces throughout the execution of rules be identified. These forces for each rule are not added like time; rather, it is important to note the highest force for the whole process to determine the operating ranges required of the machines.

Based on the rule number, dimensions instantiated for the rule (length, width, depth, location, angle of bend, etc.), and component material, we can estimate the applied force and the resulting energy provided. The work done by the process is found by integrating the force over the distance traveled.

In shearing, notching, and slitting operations, the maximum force, F_max, required is estimated based on Kalpakjian (1992) as

where UTS is the ultimate strength of the material, t is the thickness of the sheet metal, and L is the total length of the material sheared. Work done in these cutting operations is approximated by the parabolic curve shown in Figure 9a. At the beginning, the tool experiences no force until it contacts the material, then reaches a peak midway through the depth. From that point, less force is required to finish the cut. The energy consumed in this operation is approximately

Work or energy is represented by the area under the force curve for (a) punch-penetration curve in cutting and (b) force variation over die opening in bending.

In bending operations, force increases monotonically from when the tool contacts the sheet to when the sheet is completely bent (Fig. 9b). Again, the maximum force in this operation is estimated from Kalpakjian (1992) as

where k is a correction factor based on the type of die (0.3 is used here, which is standard for wiping dies), Y is the yield strength of the material, L is the length of the bend along the sheet, and d is the distance between the dye contact points. In estimating the work done in this operation, we assume the change in the applied force to be linear, thus:

Work is typically done over half the distance of the contact points, hence the d/2 term.

Cost of the total process is roughly based on the amount of energy required and the amount of time spent on the whole operation. The operating cost of the manufacturing plant (excluding labor and maintenance) depends upon the number of components produced per unit time that is a further function of the time required to produce a single component and the amount of energy spent or work. In the future, we propose to supplement the tool with data look-up tables from which the material properties for a particular class of tools, such as feed rates for standard machines for standard shearing operations, are selected automatically.