FREE ELECTRONIC LIBRARY - Dissertations, online materials

Pages:   || 2 | 3 | 4 |

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

-- [ Page 1 ] --

Using Shape Grammar to Derive Cellular

Automata Rule Patterns

Thomas H. Speller, Jr.a,

Daniel Whitneya

Edward Crawleyb


Engineering Systems Division,

Massachusetts Institute of Technology,

Cambridge, MA 02139-4307


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 difficulty in finding a set of rules from an astronomically large rule space [1] that might generate legitimate system architectures. Others have attempted to address finding 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- fied 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 specific 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 specification, to determine the design physics and selection rules to be implemented, to develop the shape grammars to reflect 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 specification.

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 defined 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 defined 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 difficulties in the application of CA is finding 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 filled 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-fluid 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 finding 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 fitness to converge on a two-dimensional rule for finding the minimum energy of both a simple cantilever beam with a load applied at the end, and of a flat plate with a hole in its center and a pull force applied in all directions. Their paper goes on to cite two main difficulties 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 field 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 artificial 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 defined 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 specifies the sequence of shape rules used to transform an initial shape to a final 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 first 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 defined operations that specify how the components of grammars are modified to form new grammars. Transformations change the rules through the operators of translation, rotation, reflection, 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 fitness function.

2. Direct “fitness” 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 fitness function.

5. Selection based on survival of the fittest.

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 fittest 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 fits by not exploring the full combinatoric space, and are computationally bounded arbitrarily—halting is user defined [35].

Pages:   || 2 | 3 | 4 |

Similar works:

«LOS PATIOS ESCOLARES: ESPACIOS DE OPORTUNIDADES EDUCATIVAS Imma Marín Resumen: Este artículo presenta los resultados de una investigación1 realizada en 30 centros de educación primaria de Cataluña. El objetivo de la indagación fue reflexionar sobre el concepto y praxis que en las escuelas tienen sobre los usos, espacios, actividades y tiempos de los patios escolares, así mismo promover el debate sobre la adecuación de estos espacios para que cumplan con su función educativa. La...»

«Los dos caminos y los dos destinos Veintidós entregas de un curso de autoestudio acerca del camino de la salvación David Rodgers W., Casilla 624, Rancagua, Chile rodgersdv@123.cl Junio 2005. Edición formateada en Venezuela, 2005 1 CONTENIDO 1 Presentación 2 ¿Por qué hay un camino ancho? 3 Cómo llegó a morar el pecado en uno hoy día 4 Características de los que andan por el camino espacioso y cómo Dios les salva 5 La Puerta y la seguridad que brinda 6 El camino angosto 7 La muerte 8...»

«Measuring the Atmospheric Influence on Differential Astrometry: a Simple Method Applied to Wide Field CCD Frames N. Zacharias1 U.S. Naval Observatory, 3450 Mass. Ave. N.W., Washington D.C. 20392, Electronic mail: nz@pyxis.usno.navy.mil Received ; accepted PASP revised manuscript, 12 Aug 96, proofs to NZ 1 with Universities Space Research Association (USRA), Division of Astronomy and Space Physics, Washington D.C., based on observations made at KPNO and CTIO –2– ABSTRACT Sets of short...»

«El recreo igualitario Guía de recursos sobre coeducación y espacio Ayto. de Hernani (Gipuzkoa) Introducción Esta guía se enmarca dentro de un programa coeducativo auspiciado por el Consejo de Igualdad y el Área de Igualdad del Ayuntamiento de Hernani (Gipuzkoa) desde octubre de 2003. Comenzamos con unas sesiones de sensibilización para el profesorado y las familias. En una segunda fase, realizamos una pequeña investigación antropológica sobre el uso del espacio en dos centros escolares...»

«L-AP “Exploring Creation With Astronomy” Lessons 1-14 Lapbook Package PLEASE NOTE: This product includes BOTH lapbooks for this book. One lapbook covers lessons 1-6, and the other covers lessons 7-14. This lapbook has been specifically designed for use with the book, “Exploring Creation with Astronomy” by Jeannie Fulbright and Apologia Science. Templates are printed with colors that best improve information retention according to scientific research. Designed by Cyndi Kinney of...»

«CURRICULUM VITAE Ralf S. Klessen Ruprecht-Karls-Universität Heidelberg Zentrum für Astronomie (ZAH) Universitätsprofessor Institut für Theoretische Astrophysik (ITA) Dr. rer. nat. Albert-Ueberle-Str. 2, 69120 Heidelberg Germany Tel: +49-6221/54-8978 Fax: +49-6221/54-4221 E-Mail: klessen@uni-heidelberg.de Homepage: http://www.ita.uni-heidelberg.de/∼ralf German, born 18th February 1968, married, four children Personal Data: Wilhelm-Blum-Straße 12–14, 69120 Heidelberg Education and...»

«The BMB Weekly Vol. 41, No. 40, September 29-October 3, 2008 nd Please send submissions to: Katie Gallagher at galla134@msu.edu or 105B Biochemistry (mailbox on 2 floor) Calendar Monday, September 29 Department of Physiology Cancer Faculty Candidate Seminar: Explore novel epigenetic targets for breast cancer therapy. Yi Huang, Johns Hopkins University, 9:00 a.m., 1425 Biomedical and Physical Sciences. Chemistry Seminar: Presentation by Kapil Lokare, Michigan State University, 11:20 a.m., 136...»

«DOI: 10.5433/1984-3356.2015v8n15p313 Una forma territorial alternativa: la tribu de Coliqueo en la pampa bonaerense An alternative territorial form: indigenous tribe of Coliqueo in the Buenos Aires pampas Melina Yuln Graciela Silvestri RESUMEN Durante gran parte del siglo XIX la pampa de Buenos Aires fue dominio de los indígenas, propiciando así el retrato de un espacio salvaje. Luego de ser controlado por el Estado este territorio sufrió un proceso de transformación en el cual se...»

«The Shapes of Dense Cores and Bok Globules Barbara S. Ryden 1 Department of Astronomy, The Ohio State University, 174 W. 18th Ave., Columbus, OH 43210 ABSTRACT The shapes of isolated Bok globules and embedded dense cores of molecular clouds are analyzed using a nonparametric kernel method, using the alternate hypotheses that they are randomly oriented prolate objects or that they are randomly oriented oblate objects. In all cases, the prolate hypothesis gives a better fit to the data. If Bok...»

«John Redden Copyright 2008 © Cosmos Heaven Awakening I have no beginning or. and. Click. The grains of dirt on my plain don't live. A plain I know for all conscious existence spreads before me. The colors change slightly to make up time periods. This awakening period is unusual. There was a clear impression Ideea had on the borderlands of her consciousness. She had visions of a brown haired woman in a cool and comfortable place very different from the omnipresent Waste. Then the words that...»

«Uncloaking globular clusters in the inner Galaxy1 Javier Alonso-Garc´ ıa Departamento de Astronom´ y Astrof´ ıa ısica, Pontificia Universidad Cat´lica de Chile, o 782-0436 Macul, Santiago, Chile Department of Astronomy, University of Michigan, Ann Arbor, MI 48109-1090 jalonso@astro.puc.cl Mario Mateo Department of Astronomy, University of Michigan, Ann Arbor, MI 48109-1090 mmateo@umich.edu Bodhisattva Sen Department of Statistics, Columbia University, New York, NY 10027...»

«Spectroscopy of Globular Clusters out to Large Radius in the Sombrero Galaxy Terry J. Bridges Department of Physics, Queen’s University, Kingston, ON K7L 3N6, Canada; tjb@astro.queensu.ca Katherine L. Rhode1 Astronomy Department, Wesleyan University, Middletown, CT 06459; kathy@astro.wesleyan.edu and Department of Astronomy, Yale University, New Haven, CT 06520 Stephen E. Zepf Department of Physics & Astronomy, Michigan State University, East Lansing, MI 48824; zepf@pa.msu.edu Ken C. Freeman...»

<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.