Evolutionary Shape Grammars for Product Design

H. C. Lee, M. X. Tang

Design Technology Research Centre, School of Design,

The Hong Kong Polytechnic University, Hong Kong

e-mail: sdhc.lee@polyu.edu.hk

Abstract

This paper describes the development of a product design support system based on a framework of shape grammars enhanced by evolutionary computing. In this research, the forms of a product are analysed to derive shape features in the form of shape grammar rules. The rules are then encoded as the code scripts of a genetic algorithm in order to generate new shape grammar rules. The results generated by the genetic algorithm define a new combination of shape features for alternative designs. In this way, traditional shape grammar is extended to an interactive context in which generative and evolutionary computing methods are combined. Both product component design as well as product configuration are supported in this framework.

While the research is still on going, in this paper, we describe how this framework is formulated and discuss its potentials in supporting product design, with initial examples showing how the system is intended to work.

1. Introduction

Research in shape grammars is concerned with the efficient use of generic shape grammars to support the exploration of innovative and stylistic forms of a product. For example, Cagan developed the coffeemaker grammar, motorcycle grammar and hood panel grammar [1,2,3] in which the coffeemaker grammar uses function labels to maintain the proper function-to-form sequence, to generate novel designs. The motorcycle grammar is used to capture brand identity. The hood panel grammar can generate the novel designs with shape emergence properties. Other examples include the semantic and shape grammar based approach to product design developed by Hsiao and Chen (1997) [4]. All these approaches established a basic framework for using shape grammars to support product design.

However, the issue of systematically exploring alternative shape grammar rules with interactive user involvement in a grammar based product design system has not been fully addressed. Most of the current grammar based systems can only provide a fixed set of grammar rules which must be developed in advance based on an analysis of the existing products. In this way, the users cannot participate in the process of developing and evaluating the shape grammar rules. The exploration of new shape grammar rules is difficult for designers who do not necessarily have the sufficient knowledge about the coding of grammar rules or other reasoning systems. As a result, the generative capability of a shape grammar based design system is still limited.

In order to utilise shape grammar in design and increase its generative capability, we propose the formulation of an evolutionary shape grammar. In our approach, Genetic Algorithms (GA) is used to evolve the shape grammar for a particular product. The GA requires that shape grammar rules to be encoded as ‘code scripts’. The code scripts are analogous to the code scripts of life encoded in DNA [5]. A generative and evolutionary design paradigm is adopted as our system architecture for evolving new shape grammars with the involvement of users interacting with the system.

2. Grammar based design approach

2.1 Shape grammars

The widespread use of grammatical approaches to design began with the introduction of shape grammars in Stiny’s seminal work [6]. A shape grammar consists of a vocabulary of shape elements, a set of production rules and an initial shape. The production rules transform the initial shape into new shapes. The new shapes evolve by recursively applying the transformation rules to their sub-shapes. A final shape emerges from the new shapes if it satisfies the design requirements.

The grammatical approaches to product design involve the analysis of form features of the existing products. The form features of products are collected and categorised according to their usages prior to deducing a set of valid grammar rules.

After the analysis and categorisation, the shapes of the form features are abstracted into grammar rules. The grammar rules are arranged in an order so that they can easily be referenced for manipulation. The users can intuitively select the rules to generate the designs during the design process.

2.2 Evolutionary shape grammars

Generative and evolutionary design techniques are developed based on the inspiration from natural evolution. Centred at the techniques are the generative methods and the testing of the designs generated by these methods [7]. Four main types of evolutionary algorithms were developed: evolutionary strategies [8], evolutionary programming [9], genetic algorithms (GAs) [10] and genetic programming [11]. In all these approaches of GAs are widely used.

In our research, a classical GA is used as the core of the evolutionary architecture for evolving new shape grammar rules. The evolved grammar rules are then used to generate different designs. Figure 1 outlines such an approach to design support with two key elements, shape grammar as the knowledge for design, and evolutionary computing as the generative mechanism.

Fig. 1 Interactive design process utilising evolutionary shape grammars

In this paradigm, a set of shape grammar rules is developed first and then encoded as the ‘code scripts’ of a genetic algorithm. The grammar rules are used to generate a population of random or predefined solutions at the beginning of evolutionary design session. For each new generation, the GA decodes the ‘code script’ to produce a set of new shape grammar rules. In addition, the system allows the users to participate in the construction of the new rules. Consequently, more rules are generated and the users can use the evolved new rules to explore alternative designs. The design of digital camera is used as an application domain to illustrate the proposed framework and to evaluate the effectiveness of this approach.

3. Shape grammars in product design domain

In our research, the form features of digital cameras are abstracted from several different brands. These form features representing different components are categorised according to their geometric locations in the assembly. The main components considered in our system so far include the main body, lens, flash, viewfinder and Liquid Crystal Display (LCD).

A parametric labelled two-dimensional (2D) shape grammar is constructed first to create a 2D profile for each component. The 2D profile is chosen because it can be further manipulated with different methods such as coiling, extrusion, lofting, revolving and sweeping to create three-dimensional (3D) features. In this application, once a 2D profile is created by the application of grammar rules, it is then extruded with a thickness to form a 3D object.

Two sets of rules are established, one is for the generation of each component and its corresponding location in an assembly. The other set of rules is for the emergent shape generation.

3.1 Shape grammars for component generation

There are over 20 rules for the component grammar and the configuration grammar used in our system. For the sake of clarity, only typical rules are explained here.

The first set of rules generates the profile of digital camera (Figure 2). Rule 1 starts with a rectangular shape labelled ‘I’ with the constraint points ‘a, b, c, d’. Theses constraints points limit the maximum boundary of the main body. The rule changes the label of the shape from ‘I’ to ‘CD’ for the classical design. Rule 2 generates a rectangular shape labelled ‘SD’ with a slot for the swivel lens design. The label ‘SX’ is used to match the swivel device created by rule 6.

Fig. 2 Rules for the profile of a base component

The second set of rules is for the design of lens. For the classical design, rules 3 to 5 produce circular shapes for optical zoom lenses with zoom ranges: 1X (fixed), 2X and 3X respectively.

For the swivel design, a swivel device is attached to the slot of the main body. Rule 6 produces the swivel device in which the lens and flash are flushed on the same surface. This allows the flash always to point to the object whichever the lens focuses. The label ‘SX’ is used for matching the label in rule 2 so that a swivel device can rotate on a swivel path of 300 degrees. Figure 3 shows the rules for a 3X zoom lens and swivel device.

Fig. 3 Rules for the zoom lens and swivel device

The third set of rules is for the generation of flashes and viewfinders. Rules 7 to 9 generate three types of flashes and rules 10 to 12 create three types of viewfinders. Figure 4 shows the rules for one type of flashes and viewfinders.

Fig. 4 Rules for the flash and viewfinder

The fourth set of rules provides two types of LCD screens (Figure 5). Rule 13 generates a rectangular shape for the LCD screen. Some LCD screens are added with swivel features. Rule 14 constructs a LCD screen with swivel features, which allow a screen to be moved independently of the camera body. With the swivel features, the users can view the image on the LCD screen while shooting at the “over-the-head” or “low-angle” positions.

Fig. 5 Rules for the LCD screen

The fifth set of rules for component design generates the form style of the main body (Figure 6). An elegant outlook gives a good impression to the users and attracts the user’s attention. Rule 37 to 41 generate the outlook of the main body based on the rectangular shape generated by rule 1.

Fig. 6 Rules for the form style

3.2 Shape grammars for component configuration

The sixth set of rules specifies the configuration of components. Figure 7 shows the typical arrangement of components located at the main body.

Fig. 7 The front and back view of digital camera

The configuration rule 46 uses the boundaries: ‘a, b, c, d’ as configuration constraints for the allocation of the lens (L) and the “flash and viewfinder” unit (S) in the front view of the main body (Figure 8). The same set of configuration rules are applied to the back view of digital camera. The “LCD screen and viewfinder” unit (S) and the button unit (L) are placed at specified locations in the back view of the main body.

Fig. 8 The configuration rule

3.3 Modification of rules for emergent shape generation

Knight (2003) has presented a detail description and the ways on how to compute with emergence [12]. In this section, we present the working principle of how the GA modifies the rules to generate emergent shapes.

The first step is to modify the spatial relation of the rule by modifying the shape on the right hand side of the rule. In order to illustrate the change of rules by the GA, an example is used to simulate the key operations (Figure 9).

Fig. 9 The change of rules

In an ideal situation, all the existing rules in the system may be changed during an evolutionary design process, but in our initial experiment, we do not change all the rules. Instead we only change the rules (Rule 37 to 41) which are for constructing the main body of the camera.

There are seven ways available for the GA to take action (Figure 10a). When the mutation rate set by the users is higher than a predefined value, for example say 0.02, the modification rule is executed.

The choice of action number 1 is to keep the current rule unchanged. Action numbers 2 to 5 specify a shape ‘C’ to be extracted from a library (Figure 10b). A label ‘B’ is first added to the shape on the right hand side of the rule. Then, the shape ‘C’ is added to the shape ‘B’ by different algebra operations.

Number 6 specifies the extracted shape ‘C’ to be randomly generated by the computer. Number 7 specifies the extracted shape ‘C’ to be provided by the users.

Three types of operations change the spatial relation, + (sum), - (difference) and ● (product). Chase S.C. presented the operation of shape algebras and formal logic in design modelling [13]. An example of adding a circular shape ‘C’ to the rectangular shape ‘B’ on the right hand side of the rule 41 is shown in figure 10c.

Fig. 10 Boolean operations of shapes

In our approach, we adopt these operations to see how these operations might be utilised in our system. However, results obtained from the initial experiments are not satisfied for all operations. Therefore, at this stage, we only apply the union operation on the existing shapes to derive new rules in our implementation.

4. System architecture

There are four main steps to apply a GA to solve design problems. First, representations of genotypes and phenotypes for the specific design problem are defined. Second, a suitable GA for the manipulation of the representations is designed. Third, selection criteria for the evaluation of design objects are formulated. Fourth, factors of user interaction that affect the performance of the evolutionary process are considered.

4.1 Representation

The phenotype representation describes all permissible solutions that can be generated by the system. It enumerates the design-space for evolutionary search by a GA. The main aspect to be studied is what elements of a grammar rule can be evolved. Then the second aspect is how to represent these elements for the manipulation by a GA.

For the first issue, a product has a set of components. These components are configured under spatial constraints to form an assembly. Therefore the phenotype consists of two elements: the rules for constructing these components and the corresponding configuration (Table 1).

Rules for components

Configuration

TABLE 1 The phenotype

For the second issues, these two elements are represented by the corresponding rule number and stored in an array for the GA manipulation. Table 2 shows the components and their corresponding rules for a GA to manipulate.

Item	Type	Lens	Flash	View finder	LCD	Form style
Rule No.	Choose 1 to 2	Choose 3 to 6	Choose 7 to 9	Choose 10 to 12	Choose 13 to 14	Choose 37 to 45

TABLE 2 The elements of the phenotype: Rule number of each component

The genotype is represented by a single chromosome. A chromosome is a list of alleles which is the binary encoding of the phenotype.

4.2 Manipulation

The GA performs three main functions: modifying alleles within chromosomes using genetic operators, decoding the genotype to produce the phenotype, and evaluating the phenotype to identify the fittest solutions (Figure 11).

Fig. 11 Operation of the GA

A GA generates an initial population of individuals with random values. The main loop begins at this stage. Each individual is then evaluated and assigned a fitness value by a fitness function. Based on the score obtained from each solution, the solution with higher score will be selectively copied more to a temporary area termed ‘mating pool’.

It is now entered to the second loop. Two of the solutions are randomly selected as parents from this ‘mating pool’. These two parents generate two offspring by random crossover and mutation operators. These two offspring replace the parents of the population. The crossover and mutation processes repeat to generate offspring until every parent of the old population is replaced, a new population with fitter solutions is then established [10].

For each generation, the genotype is converted into the phenotype which represents the solutions. The solutions are a number of individuals, each of which consists of a set of rule numbers and the instructions to change the rules. After execution of the rules in accordance to the generated rule sequence, the components are generated.

The GA repeats the main loop of evaluation and reproduction processes for a specified number of generations, or the GA will stop if a satisfactory solution emerges.

4.3 Evaluation

At this stage, the evaluation is done by the users. For each generation, the system generates 20 designs. The users can evaluate the designs generated by the evolved grammar rules in accordance to the user’s preferences. This is achieved by visualising the designs and subjectively selected the best one by the users in each generation. The selected design is graded with the highest scores. Those grammar rules which can generate the designs with higher scores will be of high survival chance in the next generation. In our implementation, the maximum number of generation is set to 1000. The users can halt the generation progress at any time as long as the users satisfy the designs.

5. Implementation

5.1 Application of shape grammar without evolutionary feature

At the beginning, the users can explore designs individually using the grammar based design system without the integration of the evolutionary architecture. The system provides different sets of component rules in sequence for the users to select. The users have to specify the type of each component and then its corresponding parameters. A software prototype has been developed and tested for the system (Figure 12).

Fig. 12 Grammar based design approach

5.2 Application of evolutionary shape grammars

The users can then explore the designs using the grammar based design system with the integration of the evolutionary architecture. The users can input the design criteria such as the number of generations, crossover and mutation rate. After over two hundred generations, the GA has generated the population of the results as shown in figure 13.

These designs are graded by the users intuitively. The system uses the grammar rules which are of higher scores to generate the designs for the next generation. The whole design process repeats until the users satisfy the results.

Fig. 13 Evolutionary grammar based design approach

The two designs with the highest scores are shown in figure 14, the “decorative features” and the “press button” are added manually for illustration purpose only.

Fig. 14 The two designs with higher scores after over 300 generations

These two designs become the major population in the next generations and the solutions are converged (Fig.15).

In addition to the designs generated by evolving a fixed set of grammar rules, the system can modify the rules as explained in section 3.2. Figure 16 shows the designs with emergent shapes which are generated by the modification rule during evolution. In the following text, we illustrate how the emergent shape shown on the top left corner of the figure 16 is generated.

It is supposed that the main body form design is generated by rule 38 and a label ‘B’ is added on the right hand side of the rule 38. A circular shape ‘C’ shown in figure 10b is randomly extracted from the library by the system. Then this shape label ‘C’ is added to the shape label ‘B’, as specified on the right hand side of the original rule 38. The operation: B + C is then carried out to modify the original shape. After this simple algebraic operation, a new rule is formed similar to the process shown in figure 9.

Fig. 15 Solutions are converged after over 300 generations

As mentioned in section 3.2, results obtained from the initial experiments are not satisfied for all operations. Therefore, a dynamic process is being investigated to measure the frequency of a rule being invoked and modified to generate new rules. Every time a rule is involved in a successful modification resulting in a new rule being generated, information is recorded together with the rules. Rules and algebraic operations with higher values are likely to be selected more frequently by the system than others.

This dynamic process addresses the issue of when to change rules and how to change them in the process of an evolutionary design. A control strategy is devised from this dynamic process to control the random modification to the new rules. Our objective is to use the control strategy as well as the quantitative evaluation in an interactive process involving users in order to formulate a good strategy to evaluate the generic aspects of the rules and how much room is there for exploring new rules, and thus new designs.

In our implementation, we only apply the union operation on the existing shapes to derive new rules while the control strategy is being investigated.

Fig. 16 Emergent shape generation

6. Conclusions

This study attempts to construct a framework for product design support system integrating a GA with shape grammars. Currently, the framework only allows visual judgment of a user as the main evaluation criteria. The objective function for an automatic selection has not yet been formulated. This is so because the shape grammar rules we considered so far only represent spatial information. Sun [14, 15] has applied GA to design with the consideration for manufacturability. In the similar way, in the next stage after the full system implementation, we will investigate the issue of how to formulate fitness function when considering aesthetic or functional constraints.

When designing the system, the rules must also be evaluated. If the rules are too specific to a problem, then the system is limited to certain range of designs. If the rules are too general, then the system does not have the specific kind of knowledge for the users to benefit from.

As shown in figure 17, the designs require more specific rules to generate the shapes. This requires additional study for the GA to evolve new rules.

Fig. 17 The designs which require additional grammars to generate the shapes

Although the evolutionary architecture has demonstrated the flexibility in extending the generative capability of a shape grammar design system, there are much more research issues to be addressed in order to fully utilise the system. These issues include the exploration of evolving different types of shape grammars for product design. There are six types of shape grammars: basic grammars, nondeterministic (ND) basic grammars, sequential grammars, additive grammars, deterministic grammars, and unrestricted grammars [16]. The generative capability and usefulness of different approaches need to be investigated.

In conclusion, we have developed and illustrated a computational framework for the form design of a digital camera using a GA and shape grammars. The generative capability of a traditional grammar based design approach is extended by integrating an evolutionary architecture. This framework can evolve the shape grammar rules to generate new designs with emergent forms.

The framework does not only produce the existing designs but also let the users explore their own ideas. More novel designs can be emerged through user interaction. At this stage, we have developed grammar rules and verified the feasibility of their integration with evolutionary computing in a user-controlled process. Further investigation will address all the above issues, before a design support system prototype can be developed in a real design supporting context.

References

[1] Agarwal, M. and Cagan, J., 1998, "A Blend of Different Tastes: The Language of Coffeemakers," Environment and Planning B: Planning and Design, 25, pp. 205-226.

[2] Pugliese, M.J. and Cagan, J., 2002, "Capturing a Rebel: Modeling the Harley-Davidson Brand through a Motorcycle Shape Grammar,"Research in Engineering Design-Theory Applications and Concurrent Engineering, 13 (3), pp. 139-156.

[3] McCormack, J.P. and Cagan, J., 2002, "Designing Inner Hood Panels through a Shape Grammar Based Framework," AiEdam-Artificial Intelligence for Engineering Design Analysis and Manufacturing, 16(4), pp. 273-290.

[4] Hsiao, S.W. and Chen, C.H., 1997, "A Semantic and Shape Grammar Based Approach for Product Design," Design Studies, 18(3), pp. 275-296.

[5] Goldberg, D.E., 1989, "Genetic Algorithms in Search, Optimization, and Machine Learning," Reading, MA: Addision-Wesley.

[6] Stiny, G., 1980, "Introduction to Shape and Shape Grammars," Environment and Planning B: Planning and Design, 7, pp. 343-351.

[7] Simon, H.A., 1969, "The Sciences of the Artificial," MIT Press.

[8] Rechenberg, I., 1973, "Evolutionstrategie: Optimierung Technisher Systeme Nach Prinzipien Der Biologischen Evolution," FrommannHolzboog Verlag: Stuttgart.

[9] Fogel, L.J., 1963, "Biotechnology: Concepts and Applications," Englewood Cliffs, NJ: Prentice Hall.

[10] Holland, J.H., 1975, "Adaptation in Natural and Artificial Systems," The University of Michigan Press, Ann Arbor.

[11] Koza, J., 1992, "Genetic Programming: On the Programming of Computers by Means of Natural Selection," MIT Press: Cambridge, MA.

[12] Knight, T.W., 2003, "Computing with emergence" Environment and Planning B: Planning and Design, 30, pp. 125-155.

[13] Chase, S.C., 1996, "Design modelling with shape algebras and formal logic," Design computation: Collaboration, Reasoning, Pedagogy, proceedings of ACADIA '96, Tucson, Arizona, October 31- November 3, 1996 Ed F Ozel, P McIntosh,pp. 99-113.

[14] Sun, J., 2002, "A Framework for Supporting Generative Product Design Using Genetic Algorithms," PhD thesis, School of Design, The Hong Kong Polytechnic University.

[15] Sun, J., Frazer, J. and Tang, M. X., 2000, “Shape Optimisation in Design for Manufacturing Using Evolutionary Techniques,” ICME2000-2^nd CIRP International Seminar on Intelligent Computation in Manufacturing Engineering. 21-23 June 2000, Capri (Naples), Italy, pp. 269 – 274.

[16] Knight, T.W., 1999, "Shape Grammars: Six Types," Environment and Planning B: Planning and Design, 26, pp. 15-31.