Generative Representations for Design Automation

Gregory S. Hornby
hornby@email.arc.nasa.gov

Introduction

Computer automated design systems have been used to design a variety of different types of artifacts such as antennas, flywheels, load cells, trusses, and robots. While they have been successful at producing simple, albeit novel artifacts, a concern with these systems is how well their search ability will scale to the larger design spaces associated with more complex artifacts. Here we claim that for automatic design systems to scale in complexity the designs they produce must have a hierarchical reuse of building blocks. Our approach is based on the use of a generative representation as the method to encode individuals in the population. In the following two sections we first define generative representations and then present some results with GENRE, an evolutionary design system which uses generative representations to encode designs.

Types of Design Representations

While the optimization algorithm can affect the degree of reuse in a design, the ability to create structures which reuse building blocks is limited by the ability of the representation to encode them. The different types of representations for computer-automated design systems can be classified by how they encode designs. First, designs can be split into parameterizations or open-ended representations:

• Parameterizations consist of a set of values for the dimensions of a pre-defined blueprint.
• Open-ended representations are those in which the topology of a design is changeable.

A fundamental distinction between open-ended representations is whether they are non-generative or generative:

• Non-generative representations use each element in the encoded design for at most one element in a blueprint. The two subcategories of non-generative representations are direct and indirect representations:
  • Direct representations encode a design as a blueprint in which elements can be added/removed in addition to changing parameter values.
  • Indirect representations require a translation or construction process to go from the encoding to the blueprint.
  Non-generative representations are limited in their ability to scale to complex structures because of the exponential growth in the size of the design space and the increasing number of dependencies in a design.
• Generative representations are those in which an encoded design can reuse elements of its encoding in the translation to an actual design. The two subcategories of generative representations are implicit and explicit.
  • Implicit, generative representations consist of a set of rules that implicitly specify a shape, such as through an iterative construction process similar to a cellular automata (CA).
  • Explicit, generative representations are a procedural approach in which a design is explicitly represented by an algorithm for constructing it.
  A generative representation's ability to discover and reuse useful building blocks improves scalability by increasing the unit of variation and capturing design dependencies.

GENRE

GENRE is a computer automated design system that uses generative representations to evolve designs. It consists of the design constructor and simulator, the compiler for the generative representation and the evolutionary algorithm. Each design is constructed by compiling the generative representation of a design into an assembly procedure for creating the design's blueprint. Once a design has been constructed it is evaluated in simulation. Using the results from simulation, the evolutionary algorithm acts on the generative representations to evolve good designs.

A graphical example of the explicit, generative representation used by GENRE is shown below, along with the assembly procedure it compiles to:

Generative representation.		Assembly procedure.		Constructed object.

In these images the cubes are a reference to a compound object, gray spheres are conditionals and multi-colored spheres are construction commands. Once compiled into an assembly procedure, this sequence of commands is used by the design constructor to build the actual object. The reason an explicit, generative representation is used is that GENRE can be applied to different types of designs (eg solid objects, robots, neural networks, computer programs, ...) by changing only the set of construction commands and the design constructor.

Evolved Objects

Genobots

gbot_kayak.avi (8.8M)

gbot_quatro1.mov (600k)

gbot_quatro1.mov (600k)

Tables

In this design domain the objective is to evolve tables of three-dimensional cubes. The fitness function rewarded structures for maximizing: height; surface area; stability/volume; and minimizing the number of cubes. Evolved tables use anywhere from several hundred to several thousand cubes.

Table 1	Table 1 - built
Table 2	Table 2 - built

Selected Publications on Generative Representations