Evolving Buildable Arches
Introduction
Previous work in evolved structures has ignored the process of
construction, considering only the stability of the final
structure. My goal is to evolve buildable structures. In
order to be buildable, a structure must be stable at every stage
of its construction. This constraint becomes non-trivial when the
construction process is stochastic
Method
The structures I am trying to evolve are compsed to 2x1 bricks.
The "physics" of my simple world are that:
- Bricks placed vertically have a 50 percent chance of falling
over (in either direction).
- Cantilevered Bricks have a 50 percent chance of falling
over.
- Once a brick has settled, it is considered "glued", and will
remain in place as long as it is at least partially supported
from below.
The genotypes that I am evolving are assembly procedures
that consist of a sequence of commands to an LOGO-like
turtle such as go forward, turn right, place
brick, take brick. I'm using two-point crossover (70
percent), and single-point mutation (2 percent per-locus), where
mutations can add, delete, or change an instruction within the
assembly procedure.
Because of the noisy assembly environment, each assembly procedure
is built and evaluated 100 times. I am using Multi Objective
Optimization over the following objectives:
- length (shorter is better)
- average number of bricks missing from goal structure
- average number of extra bricks in final assembly
- yield - percentage of "perfect" final assemblies
- missing brick yield - percentage of final assemblies with no
missing bricks
Preliminary Results
legend
Black - Vertical Bricks
Grey - Horizontal Bricks
The moving square is the turtle.
The Goal Structure:
A "Naive" Solution
evolved in a noiseless building environmment:
and then built in a noisy one:
The Final Result:
This assembly procedure is 93 instructions long, and capable of
building a perfect structure 59 percent of the time.
This second assembly procedure (below), which arrived a few
generations later, is only 78 instructions long, and yet builds a perfect structure 63 percent of the time:
Below: 81 instructions, 66 percent.
Below: 82 instructions, 69 percent.
Below: 82 instructions, 75 percent.
Here is a more detailed presentation of this work.
Last modified: Fri Sep 6 17:04:23 EDT 2002