Generative Representations for Design Automation

DEMO Home Gregory S. Hornby
hornby@cs.brandeis.edu
Dynamic & Evolutionary Machine Organization Lab

Contents

Introduction
Method
Results
Downloads / Source
Publications
Links

Note: for more recent work in this area please see my new web page for work with generative representations.

Introduction

Recent research has demonstrated the ability for the automatic design of basic shapes and the morphology and control of real physical robots using techniques inspired by biological evolution. The main criticism of the evolutionary design approach, however, is that it is doubtful whether it will reach the high complexities necessary for practical engineering.

Here we claim that for automatic design systems to scale in complexity the designs they produce must be made of re-used modules. Our approach is based on the use of a generative representation as the method to encode individuals in the population. Unlike a direct representation of a design, a generative representation is an algorithm for creating a design. That is, the data being optimized by the search algorithm is itself a kind of program containing rules and program-like instructions for generating a design, with the ability to re-use parts of the program in a modular way allowing it to create more complex parts from simpler parts and re-use a component multiple times in a design.

We describe a system for creating generative specifications capable of hierarchical regularity by using Lindenmayer systems (L-systems) as the generative representation for an evolutionary algorithms. Using this system we demonstrate a system that evolves hierarchically modular tables and locomoting robots (called genobots).



Method

The evolutionary system used to evolve designs consists of the design constructor and simulator, the parsar for the generative representation and the evolutionary algorithm. Each design is constructed from a sequence of construction commands, similar to an assembly procedure, which specify how to construct the design. This string of construction commands is produced by parsing the generative encoding, for which we use Lindenmayer systems (L-systems). The evolutionary algorithm evolves a population of L-systems, using the fitness returned by a user defined fitness function.

A graphical example of an evolved L-system is shown below, along with the sequence of command strings it produces:

An example L-system.

The sequence of assembly procedures it generates.

In these images production rules are represented by cubes with lines connecting them to their condition-successor pairs. The black sphere represents a condition and the following symbols are the contents of the production body. Triangles are used to represent the repeat operator, and spheres represent construction commands. The final string is then used to construct the design.

Results

This system has been used in the following substrates:






Static Structures
2D Genobots
3D Genobots


Download

The software used for this research is called GENRE, which stands for GENerative REpresentations. The source code for GENRE is available under the GNU GPL: genre.1.1b.tar.gz (248k).
Note that this source code is for Linux and I have compiled and run it on RedHat 8.0.


Publications on Generative Representations

  • Hornby, Gregory S., Lipson, Hod, and Pollack, Jordan B. Generative Representations for the Automated Design of Modular Physical Robots. IEEE Transactions on Robotics and Automation. (conditionally accepted).

  • Pollack, Jordan B., Hornby, Gregory S., Lipson, Hod, and Funes, Pablo. Computer Creativity in the Automatic Design of Robots. Leonardo, Journal for the International Society for Arts Sciences and Technology. 36:2, 2003.

  • Hornby, Gregory S. and Pollack, Jordan B. Creating High-level Components with a Generative Representation for Body-Brain Evolution. Artificial Life, 2002, 8:3.

  • Hornby, Gregory S. and Pollack, Jordan B. Evolving L-Systems to Generate Virtual Creatures.
    Computers and Graphics, 2001, 25:6, pp 1041-1048.

  • Pollack, Jordan B., Lipson, Hod, Hornby, Gregory S., and Funes, Pablo. Three Generations of Automatically Designed Robots. Artificial Life, 7:3, pg 215-223. 2001.

  • Hornby, Gregory S. and Pollack, Jordan B. Body-Brain Coevolution Using L-systems as a Generative Encoding.
    Genetic and Evolutionary Computation Conference (GECCO) 2001.

  • Hornby, Gregory S., Lipson, Hod, and Pollack, Jordan B. (2001). Evolution of Generative Design Systems for Modular Physical Robots.
    IEEE International Conference on Robotics and Automation (ICRA).

  • Hornby, Gregory S. and Pollack, Jordan B. The Advantages of Generative Grammatical Encodings for Physical Design.
    Congress on Evolutionary Computation (CEC) 2001.

    Related Lab Projects

    I have continued work in generative representations and my
    new web page is here.
    Pablo Fune's: Computer Evolution of Buildable Objects
    Hod Lipson's: Evolution of Machines: The Golem Project

    Homepage. Research Projects. All publications.

    hornby@cs.brandeis.edu - Last modified: Feb 22, 2005
    Copyright © Gregory Hornby