Graph Grammars as a Representation for Interactive Evolutionary 3D Design

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


James McDermott: Graph Grammars as a Representation for Interactive Evolutionary 3D Design. In: EvoMUSART 2012, S. 199-210.



A new interactive evolutionary 3D design system is presented. The representation is based on graph grammars, a fascinating and powerful formalism in which sub-graphs, nodes and edges are iteratively rewritten by rules analogous to those of context-free grammars and shape grammars. The nodes of the resulting derived graph are labelled with Euclidean coordinates: therefore the graph fully represents a 3D beam design. Results from user-guided runs are reported, demonstrating the flexibility of the representation. Comparison with results using an alternative graph representation demonstrates that the graph grammar search space is rich in appealing, organised designs. A set of numerical graph features are defined in an attempt to computationally distinguish between good and bad areas of the search space, leading to the definition of a computational fitness function and non-interactive runs.

Extended Abstract


booktitle={Evolutionary and Biologically Inspired Music, Sound, Art and Design},
series={Lecture Notes in Computer Science},
editor={Machado, Penousal and Romero, Juan and Carballal, Adrian},
title={Graph Grammars as a Representation for Interactive Evolutionary 3D Design},
url={ },
publisher={Springer Berlin Heidelberg},
author={McDermott, James},

Used References

Byrne, J., Fenton, M., Hemberg, E., McDermott, J., O’Neill, M., Shotton, E., Nally, C.: Combining Structural Analysis and Multi-Objective Criteria for Evolutionary Architectural Design. In: Di Chio, C., Brabazon, A., Di Caro, G.A., Drechsler, R., Farooq, M., Grahl, J., Greenfield, G., Prins, C., Romero, J., Squillero, G., Tarantino, E., Tettamanzi, A.G.B., Urquhart, N., Uyar, A.Ş. (eds.) EvoApplications 2011, Part II. LNCS, vol. 6625, pp. 204–213. Springer, Heidelberg (2011)

Chomsky, N.: Three models for the description of language. Transactions on Information Theory 2(3), 113–124 (1956)

Clune, J., Lipson, H.: Evolving three-dimensional objects with a generative encoding inspired by developmental biology. In: Proceedings of the European Conference on Artificial Life (2011),

Dawkins, R.: The Blind Watchmaker. Longman Scientific and Technical, Harlow, England (1986)

Ehrig, H., Korff, M., Löwe, M.: Tutorial Introduction to the Algebraic Approach of Graph Grammars Based on Double and Single Pushouts. In: Ehrig, H., Kreowski, H.-J., Rozenberg, G. (eds.) Graph Grammars 1990. LNCS, vol. 532, pp. 24–37. Springer, Heidelberg (1991)

Gilbert, E.N.: Random graphs. The Annals of Mathematical Statistics 30(4), 1141–1144 (1959)

Gips, J.: Computer implementation of shape grammars. In: NSF/MIT Workshop on Shape Computation (1999),

Gu, Z., Xi Tang, M., Frazer, J.H.: Capturing aesthetic intention during interactive evolution. Computer-Aided Design 38(3), 224–237 (2006)

den Heijer, E., Eiben, A.E.: Evolving art with scalable vector graphics. In: Proceedings of the 13th Annual Conference on Genetic and Evolutionary Computation, pp. 427–434. ACM, Dublin (2011)

Hemberg, M., O’Reilly, U.-M., Menges, A., Jonas, K., da Costa Goncalves, M., Fuchs, S.: Genr8: Architect’s experience using an emergent design tool. In: Machado, P., Romero, J. (eds.) The Art of Artificial Evolution. Springer, Berlin (2007)

Keles, H.Y., Özkar, M., Tari, S.: Embedding shapes without predefined parts. Environment and Planning B: Planning and Design 37(4), 664–681 (2010)

Knight, T.: Computing with emergence. Environment and Planning B: Planning and Design 30(2) (2003)

Knight, T.W.: Transformations of De Stijl art: the paintings of Georges Vantongerloo and Fritz Glarner. Environment and Planning B: Planning and Design 16(1), 51–98 (1989)

Koning, H., Eizenberg, J.: The language of the prairie: Frank Lloyd Wright’s prairie houses. Environment and Planning B 8, 295–323 (1981)

Luerssen, M.H., Powers, D.M.W.: Graph design by graph grammar evolution. In: Proceedings of the 2007 IEEE Congress on Evolutionary Computation, pp. 386–393. IEEE (2007)

McCormack, J.P., Cagan, J.: Curve-based shape matching: supporting designers’ hierarchies through parametric shape recognition of arbitrary geometry. Environment And Planning B: Planning And Design 33(4), 523 (2006)

O’Neill, M., Ryan, C., Keijzer, M., Cattolico, M.: Crossover in grammatical evolution. Genetic Programming and Evolvable Machines 4(1), 67–93 (2003)

Piazzalunga, U., Fitzhorn, P.: Note on a three-dimensional shape grammar interpreter. Environment And Planning B 25, 11–30 (1998)

Reddy, J.G., Cagan: An improved shape annealing algorithm for truss topology generation. Journal of Mechanical Design 117, 315 (1995)

Sims, K.: Artificial evolution for computer graphics. In: SIGGRAPH 1991: Proceedings of the 18th Annual Conference on Computer Graphics and Interactive Techniques, pp. 319–328. ACM, New York (1991)

Stiny, G., Gips, J.: Shape grammars and the generative specification of painting and sculpture. In: Petrocelli, O.R. (ed.) The Best Computer Papers of 1971, pp. 125–135. Auerbach (1972); originally published in: C. V. Freiman (ed.), Information Processing 71: Proceedings of the 1971 Congress of the International Federation for Information Processing, Ljubljana, Yugoslavia

Tapia, M.: A visual implementation of a shape grammar system. Environment and Planning B 26, 59–74 (1999)


Full Text

[extern file]

intern file

Sonstige Links