# «Using Shape Grammar to Derive Cellular Automata Rule Patterns Thomas H. Speller, Jr.a, Daniel Whitneya Edward Crawleyb a Engineering Systems ...»

Using Shape Grammar to Derive Cellular

Automata Rule Patterns

Thomas H. Speller, Jr.a,

Daniel Whitneya

Edward Crawleyb

a

Engineering Systems Division,

Massachusetts Institute of Technology,

Cambridge, MA 02139-4307

b

Department of Aeronautics and Astronautics,

Engineering Systems Division,

Massachusetts Institute of Technology,

Cambridge, MA 02139-4307

This paper shows how shape grammar can be used to derive cellular au-

tomata (CA) rules. Searching the potentially astronomical space of CA rules for relevance to a particular context has frustrated the wider ap- plication of CA as powerful computing systems. An approach is offered using shape grammar to visually depict the desired conditional rules of a behavior or system architecture (a form-function) under investigation, followed by a transcription of these rules as patterns into CA. The com- bination of shape grammar for managing the input and CA for managing the output brings together the human intuitive approach (visualization of the abstract) with a computational system that can generate large design solution spaces in a tractable manner.

1. Introduction Cellular automata (CA) offer a large potential for simulating complex system dynamics using parallel computational processes. Challenges exist, however, in the practical utilization of CA. To date, researchers and practitioners continue to express uncertainty as to how to apply CA to modeling and simulation because of the immense difﬁculty in ﬁnding a set of rules from an astronomically large rule space [1] that might generate legitimate system architectures. Others have attempted to address ﬁnding CA rules by trial and error, genetic algorithms [2, 3], and genetic programming [4]. If the rule space can be managed, with proper representation of the underlying physics as demonstrated in the lattice gas research [5, 6], then CA may prove their applica- bility for generative systems. A CA methodology in complex system Corresponding author. Electronic mail address: tspeller@mit.edu.

Complex Systems, 17 (2007) 79–102; 2007 Complex Systems Publications, Inc.

T. H. Speller, Jr., D. Whitney, and E. Crawley 80 modeling would be attractive because CA provide the advantages of parallel processing for large data sets with minimal overhead [3] and local neighborhood interactions comparable to nature’s processes. Ad- ditionally, the CA approach is algebraic and logical, in that it permits using symbolic variables and functional operations according to speci- ﬁed rules. This allows the opportunity of mapping a visually depicted form-function (system architecture) directly into the CA and to present the output in a visual-spatial format as a designer would do.

A shape grammar is a formal set of rules applied to shapes to generate a language of design that allows the visualization of the desired form and function of the rules. The research objective herein is to exploit the potential of CA by presenting an approach for using shape grammar [7] to derive CA rules. The essential scope of this investigation falls within the domain of self-generative system architecture, with speciﬁc methodology entailing the use of a shape grammar for establishing the rules of the design process (at both the elemental and organizational levels). This is followed by a CA approach for actually generating the creative design space. The shape grammar thus expresses the material form relationships and the physics of the form-function and becomes transcribed into CA rules and their conditional neighborhoods, with the CA rules generating the design space.

Using shape grammars offers the system architect the capability of assuring that design proceeds by rules that embody the relevant principles of physics. The architect can then select for design candidates that meet stability, robustness, aesthetics, cost, and other requirements, thereby managing an otherwise possibly explosive design space. At the same time, shape grammars allow the system architect to explore a diverse variety of design styles, providing opportunities for the emergence of unexpected or unpredictable higher-order components and modular structures with potential usefulness. The system architect’s role is thus to create a design space of conceptualizations and select good system architectures for a given speciﬁcation, to determine the design physics and selection rules to be implemented, to develop the shape grammars to reﬂect these rules at the modular and hierarchical levels, and to program the CA to capture these rules and output a design catalog of the best candidates that meet the speciﬁcation.

** 1.1 Cellular automata**

CA comprise rules for evolving the state of a discrete dynamical system.

The same rule is applied repeatedly to a system state, and new states are generated in parallel as a step function. As Wolfram [8] has emphasized, simple rules and programs can create complex systems. CA are local and parallel processors that can model physics in time and space. A rule, which can consist of a logical computation and/or pattern match Complex Systems, 17 (2007) 79–102 Using Shape Grammar to Derive Cellular Automata Rule Patterns 81 (such as to a list structure), is applied to each cell as based on the values of cells in its deﬁned neighborhood, in order to determine its value at the next step. The origins of CA are attributable to von Neumann [9, 10], Ulam and Zuse [11], and Wiener [12], and its resurgence to Wolfram [13]. A survey of CA in the literature may be found in [1].

The simplest neighborhood is an elementary system consisting of a one-dimensional row of cells, each of which can contain the value 0 or 1 (depicted as two colors), with a local neighborhood of size 3 (range or radius of 1). More complex CA can be deﬁned on two- or higherdimensional arrays with multicolored cells and larger ranges. Each rule is represented as an array of cells. For the case of a local neighborhood of size 3, each triplet determines a single output cell in an array. A triplet with binary values can have eight possible patterns from 111 to 000. A local neighborhood of size 3 thus can generate 256 possible rules. The formula for calculating the rule size space in a one-dimensional system (2r 1) is kk, where k represents the color possibilities for each state and r is the range or radius of the neighborhood. It is interesting to note that merely increasing r from 1 to 2 and maintaining the colors at two increases the rule space from 256 to 4.3 billion.

Moreover, as illustrated in Figure 1, the number of parameter options under the discretionary control of the modeler (the “controllables”) can produce a rule space that is beyond comprehension. Consequently, one of the fundamental difﬁculties in the application of CA is ﬁnding rules from this exploded space that exhibit the desired behavior.

CA can model spatio-temporal systems (e.g., biological, physical, or engineering) in which complex phenomena build up as a result of many simple local interactions. This local neighborhood seems similar to a “bounded rationality,” as described by Herbert Simon [14], wherein

phenomena only act in local areas, do not explore all possibilities, and make a perfectly rational choice. The local neighborhood is a subset of full information, only a portion of perfect information is used for decision-selection at any moment as it is computationally intractable to consider full information in order to make a rational choice. The universe may be ﬁlled with such local neighborhoods which not only follow their own set of rules but also interact with other local neighborhoods in their universe, thereby collectively creating emergent behavior.

Lattice gas-ﬂuid dynamics have been modeled successfully by CA rules using simple patterns of particle behavior adhering to the physical laws of conservation of momenta and conservation of mass [5, 15].

Most noteworthy is the use of a hexagonal neighborhood comprising 64 patterns of particle collision behavior which exactly predicts the Navier–Stokes equation of low Mach velocity gas dynamic behavior.

A different approach to ﬁnding a CA rule was taken by Hajela and Kim [3] in determining solutions to mechanical engineering problems.

They used a genetic algorithm technique with crossover, mutation, and selection after testing for ﬁtness to converge on a two-dimensional rule for ﬁnding the minimum energy of both a simple cantilever beam with a load applied at the end, and of a ﬂat plate with a hole in its center and a pull force applied in all directions. Their paper goes on to cite two main difﬁculties with the current state of parallel processing, stemming from the more typical pattern of linear thinking by humans. First, existing programs are reworked ineffectively for use on different processors.

Second, programs are written with different domains (as they put it) to be processed in parallel. They noted that there is a diminishing rate of return in processor speed as additional processors are added due to the necessary software overhead applied to control the different processors and the algorithm. CA, by nature being parallel, are therefore thought to be possibly a more natural way to conduct parallel processing.

** 1.2 Shape grammar**

Shape grammar is a formal generative approach that has been applied to creating architectural forms. Its origins are attributable to the work of Stiny and Gips [7], reinforced by Mitchell [16, 17], Knight [18], and Cagan [19] (who has actually generated real product designs using shape grammars with customized output programs). Shape grammar is a precise and at the same time intuitive methodology in the visual medium for generating languages of design. Shape grammars can be used analytically, as in reverse engineering, for characterizing and classifying designs and patterns of designs, referred to as styles in architecture. A shape grammar includes a vocabulary of shapes and a set of spatial relations to control the positioning of shapes in the vocabulary. The shape rules are created and applied recursively starting with the initial Complex Systems, 17 (2007) 79–102 Using Shape Grammar to Derive Cellular Automata Rule Patterns 83 shape, and the generated designs compose a language. Operations and transformations may be applied to the shapes and the rules themselves.

The practice of shape grammar in the ﬁeld of architecture has focused primarily on form. However, functions and properties of shapes can be included in the grammar [20].

Formal grammars are systems of rules for characterizing the structure, or the syntax, of sentences in natural and artiﬁcial languages.

Shape grammars are a geometrical design adaptation of Noam Chomsky’s formal (phrase structure or transformational) grammars [21] and are recursively enumerable, having the capability of producing unrestricted languages [22]. Thus, shape grammars are systems of rules for characterizing the composition of designs in spatial languages. (See Figures 3 through 7 later for a demonstration of shape rules.) As in Chomsky’s formal grammars, which generate a language of onedimensional strings, a shape grammar is also deﬁned by a quadruple SG (VT, VM, R, I) but generates a language of two- or even threedimensional objects that result in an assemblage of terminal shapes, where VT is a set of terminal shapes (i.e., symbols) VM is a set of markers (i.e., variables) R is a set of shape rules (addition/subtraction and euclidean transformations), u v is the shape rule (i.e., productions;

a production set of rules speciﬁes the sequence of shape rules used to transform an initial shape to a ﬁnal state and thus constitutes the heart of the grammar [23]) u is in (VM VT ) and v is in (VM VT ) ; where and refer to excluding or including the empty set I is the initial shape to which the ﬁrst rule is applied (i.e., the start variable) [22].

A shape grammar applies rules to a given shape such as a rectangle by the accompanying operators, which may consist of shape addition, subtraction, and deletion. In addition, transformations are formally deﬁned operations that specify how the components of grammars are modiﬁed to form new grammars. Transformations change the rules through the operators of translation, rotation, reﬂection, and scaling.

** 1.3 Other self-generating computational approaches**

There is a considerable body of research on other approaches to bottom up self-generating design. Evolutionary algorithms arose from attempts to model the processes of nature as the ultimate designer, while tapping computers and programs to manage the time and space problems that confront man as the designer. Various evolutionary computation (EC) approaches have been developed according to darwinian processes of Complex Systems, 17 (2007) 79–102 T. H. Speller, Jr., D. Whitney, and E. Crawley 84 evolution and have been applied in such endeavors as truss bridges [24], a sports car body and boat hull [25], LEGO® bridges [26, 27], tables [28, 29], circuits [4], programs, and others.1 EC consists of at least four subapproaches: genetic algorithms (GAs) [30, 31], evolutionary programming (EP) [32], evolutionary strategies (ES) [33], and genetic programming (GP) [34]. EC approaches are characterized as having the following in common.

1. A given and usually random population of points (potential solutions) in the search for a solution to the ﬁtness function.

2. Direct “ﬁtness” information instead of function derivatives.

3. Evolutionary processes using probabilistic rather than deterministic transition rules (start with an initial population and the operators of selection, crossover, and mutation).

4. Evolution of solutions with parallel search for a solution to the ﬁtness function.

5. Selection based on survival of the ﬁttest.

Thus in the EC process, crossing genomic modular segments generates higher-order modules and greatly expands the design space (diversity).

The principle of survival of the ﬁttest leads to pruning out those designs with low or no probability of survival. However, ECs are a probabilistic set of methods that operate without regard to the laws of physics, discard possibly superior ﬁts by not exploring the full combinatoric space, and are computationally bounded arbitrarily—halting is user deﬁned [35].