Benjamin Loomis Working Paper SGGA 1 A NOTE ON GENERATIVE DESIGN TECHNIQUES: S G G A A USER-DRIVEN GENETIC ALGORITHM FOR EVOLVING NON-DETERMINISTIC SHAPE GRAMMARS Benjamin A Loomis Massachusetts Institute of Technology, Cambridge MA, USA ABSTRACT We propose a model for generative design which synthesizes two separate but well-established forms of computational design. It is argued that shape grammars and genetic algorithms address complementary aspects of the generative design problem, and that injecting the theory and research from each field into the other will promote the development of better generative design machines. We also present a prototypical system which synthesizes these strands of research, sketched out within AutoCAD's programming environment. Note: the included Figures and Tables are mock-ups onlyBenjamin Loomis Working Paper SGGA 2 INTRODUCTION Efforts in computational design can largely be characterized as stemming from one of two positions, which might be referred to as the logical and biological. Broadly speaking, the logical strand of research focuses on systems of production and analysis, such as grammars, syntaxes, and similar rigorously defined languages. The biological strand of research, on the other hand, tends to focus on adaptation and evolution, along with the related processes of complexity, self-organization, and emergence. Among the work in each of these strands of thought about computational design methods, shape grammars and genetic algorithms stand out as two of the most well-established fields of research in their respective domains. Both first made known in the early seventies, shape grammars and genetic algorithms have each established a solid body of knowledge and community of researchers over the past thirty years. Shape grammars have proven capable of producing complex and meaningful design languages, as exemplified by the Palladian, Prairie, and Queen Anne house grammars, and are theoretically capable of producing any design (Stiny, 1975). Similarly, genetic algorithms are recognized as a powerful and robust problem-solving method, with a wide range of theorems and applications which suggest their optimality for many types of problems (Goldberg, 1989; Mitchell, 1996). However, as the two areas of research stand on opposite poles of the computational design spectrum, the few examples of explicitly combining grammars and search algorithms (Shea, 1998; Rosenman and Gero, 1999) have yet to incorporate the established fields of shape grammars and genetic algorithms. In the field of genetic algorithms and other evolutionary computing techniques, for example, it is often thought that shape grammars are too simplistic or restrictive to make use of the full potential inherent in theBenjamin Loomis Working Paper SGGA 3 evolutionary paradigm (Frazer, 1995). Similarly, it might be argued that the structure of genetic algorithms do not lend themselves to the full range of possibilities inherent in visual calculation, or that the evolutionary approach tends to focus on results to the detriment of understanding. Yet, as this paper shows, the two fields are in fact complementary, and could benefit from research which explores the points of convergence between them. The most obvious point of convergence lies in the fields' respective strengths with respect to problem spaces. Genetic algorithms are an advanced search mechanism ideal for exploring large and complex problem spaces, though the research to date leaves the structure of the problem spaces themselves less understood than the searching mechanisms. On the other hand, shape grammars provide a rigorous method for defining and constraining design spaces, though they put aside issues of exploring those spaces. Thus, insofar as computational design methods focus on the construction and exploration of design spaces, these two forms of computation address opposite sides of the same coin. The work we present takes a designer's approach, and is about practical synthesis and gains in understanding rather than strict adherence to theoretical possibilities. Our prototype uses a very simplified and limited shape grammar and genetic algorithm, and makes some naive assumptions about each system in order to test their combination. However, though limited, the theory behind our grammar and genetic algorithm is solid, and the model we outline should be extensible into more practical design contexts. Similarly, the prototype does provide insights into each technique that would not otherwise be obvious, and suggests that each research paradigm could benefit by exploring the gains made so far by the other.Benjamin Loomis Working Paper SGGA 4 SHAPE GRAMMARS A shape grammar consists of shapes, labels, shape rules, and an initial shape. Shapes and their labels are the basis for the definition of shape rules. A shape rule has two parts - a left side shape(s) and a right side shape(s), separated by an arrow. A rule states that the shape(s) on the left side is transformed or replaced by the shape(s) on the right side. Given an initial shape, one transforms it using the rules of the grammar to produce a new shape or shapes. A transformation in this generalized sense could include subtracting part of the shape on the left side, adding a new shape to it, dividing it, or so on. Successive use of the grammar's rules on an initial shape produces designs. Though we will now introduce an example of a two-dimensional shape grammar to illustrate the basic mechanisms, shape grammars can be of any dimension. The grammar we will describe in our prototype is a three-dimensional shape grammar very similar to the one here. Consider Figure 1a, which shows a two-dimensional shape grammar with one rule. The rule adds a rectangle to another in the relationship shown on the right side of the rule. Given the rectangle on the left side as the initial shape, two possible designs generated by the grammar are shown in Figure 1b. Each design is generated by four rule applications. In each step, the rule applies to the rectangle added previously. The difference between the two designs lies in the decision of where to apply the rule, which in turn is predicated by the symmetry of the rectangle (i.e., the number of Euclidean transformations which can be applied to the shape without changing it).Benjamin Loomis Working Paper SGGA 5 (a) (b) Figure 1. A simple shape grammar that creates chains