|
Intro
This section aims to break the
project down into its nitty gritty. It is written in
documentary style, occaisionally going in and out of
technical aspects. I've tried to write it as accessible
and readable as possible, avoiding extremely detailed
technical jargon when possible.
The work here is known as "computer
based model building", and the analogy here is
multicellular biology. It's just like making a map on
the ground, letting twigs and rocks represent landmarks,
paths, and places of interests. Here I'm allowing equally
crude forms and behaviors represent highly complex things,
such as the laws of physics, chemistry, and systems
of biology.
Concept
Background on "Cellular
Morphogenesis"
The idea came to me reading while
The
Emergence of Everything by Harold J. Morowitz
on a chapter about the emergence of multicellularity
and its implications. The interest for me here is the
emergence of this phenomenon, that individual
and autonomous cells could group together to cooperate
and even specialize, eventually forming functional living
animals. Specifically, the move up from a lower level
of complexity (cell structure, organelles, cell walls,
etc) to a higher level of complexity (cells specializing
into skin cells, nerve cells, bone, tissue, etc). I
want to be able to not only express this idea in a programmed
and algorithmic environment on the computer, but also
have people understand and learn about this concept,
and at the same create visually appealing work with
both stills and animation. In other words, there needs
to be pretty pictures by the end of all this. :þ
 A
Quote from The Emergence of Everything on Multicellularity
"Among single celled organisms,
it often happens that cells divide and do not split
apart, but show a stickiness that leads to colonies.
When this is followed by variable differentiation of
the cells of a cluster into different forms, we refer
to the phenomenon as morphogenesis"
Multicellular life forms come three
particular kingdoms: animals, plants, and fungus. This
project focuses on the animal kingdom because of my
interest in animation, movement, and locomotion. However
this does that mean that the other kingdoms less interesting
in their own right.
Inspiration also came from Karl Sims' Evolved
Virtual Creatures. This work heavily references
his SIGGRAPH 1994 paper documenting his exploration
of techniques to successfully evolve virtual creatures.
No doubt there are many other research projects since
Karl Sims, however I chose to reference him the most
for familiarity.
Another inspiration is SodaPlay and
SodaRace, and its implications of designed virtual creatures.
Emergence
highlights from Wikipedia
Emergence is the process of deriving some
new and coherent structures, patterns and properties
in a complex system. Emergent
phenomena occur due to the pattern of interactions between
the elements of a system over time. Emergent phenomena
are often unexpected, nontrivial results of relatively
simple interactions of relatively simple components.
What distinguishes a complex system from a merely complicated
one is that in a complex system, some behaviours and
patterns emerge as a result of the patterns of relationship
between the elements.
An emergent behaviour
or emergent property is shown when a
number of simple entities (agents) operate in an environment,
forming more complex behaviours as a collective.
The complex behaviour or properties
are not a property of
any single such entity, nor can they easily be predicted
or deduced from behaviour in the lower-level entities.
Emergent structures are
patterns not created
by a single event or rule.
There is nothing that
commands the system to form a pattern,
but instead the interactions of each part to its immediate
surroundings causes a complex process which leads to
order. One might conclude that emergent structures are
more than the sum of their parts because
the emergent order will not arise if the various parts
are simply coexisting; the
interaction of these parts is central.
Emergent processes or behaviours
can be seen in many places, from any multicellular
biological organism to traffic patterns or organizational
phenomena to computer simulations and cellular automata.
Summary from this Wikipedia
article
Important things pertaining
to this project about emergence:
agents operating in an environment and forming complex
behavior or structures, of which could accomplish what
the agents themselves could not have before. It is important
to show how this system could create new and unexpected
results, not predicted by the lower-order forms (the
agents themselves). Another important thing is to have
these agents "form order despite the lack of command".
back to top
Design Q&A
These questions were posed during
the research phase and were answered as the design phase
was executed.
1. What determines success of a creature?
Meaning, what quality are the creatures being selected
for? Survival? Competition for speed? Competition
to accomplish a task? (this assumes creatures automatically
evolve motility).
Any competition involving
animation is interesting. Swimming will be first priority.
2. What are the ways in which breeding
and offspring of successful designs processed? Random
mutations? Mix gene pools?
Mixing gene pools of successors
seems to be ideal, though initially there will be
only evolution through random mutation.
3. What do individual cells do, on
their own? What's the level of interactivity between
cells, and should this be represented? If so, how?
Little. The cells interact with
each other through connections, but as an individual
they will only react to physics (forces, friction,
kinetic energy, etc).
4. What will the environment be?
Will there be immediate competition against other
creatures in a live environment? Will there be physical
terrain to traverse? How important is this to the
study of emergence and evolution?
No initial environment, especially
selecting for creatures with the fastest motion through
a fluid.
back to top
Form
My "agents" in this
case are individual cells. The emergent properties will
come from the interactions between these cells. The
first interaction is form, or how the cells arrange
themselves in two dimensional space in relation to each
other. In addition, all cells are acted upon by my particular
flavor of the laws of physics.
 Springs
In order to achieve fluid, organic-like animation, I
had to learn all about springs. A spring connects two
masses together. A rest-state length is defined. When
the two masses are pulled from each other, the spring
forces the two masses closer toegether. When the two
masses are pushed too close, the spring pulls them apart.
In essence, a spring is always trying to maintain that
length of its rest-state. Springs are used in SodaPlay's
creatures. See
Applet.
I performed several tests with springs
until I achieved the results that I wanted.
On a technical note, I've used a hacky version of fourth
order Runge-Kutta. I'm not even sure if I've implemented
it properly, but it does seem to help creatures from
exploding in most cases.
Masses
Each cell is considered one point mass. Each cell has
inertia, so that when thrown, a cell will keep going
until something has stopped it (hitting a wall, or hitting
another cell, or pulled back by a spring). The primary
force that slows down a cell is the friction of the
fluid that it's floating in. In this work, my virtual
cells are sitting in an imaginary pitri dish. The fluid
is invisible, but the effects of the fluid are visible
through these cells. back
to top See
Applet.
Structure
The next step is to provide some kind of "blueprint"
that allows these cells to be placed and connected by
springs in a predictable and consistent manner.
Genome
This blueprint is simply a set of numbers, interpreted
as instructions on how to build a cell. The philosophy
behind this project is to see how emergent behavior
and form could arise from morphology alone, therefore
I minimized the amount of information is given by the
genome. Let me stress that the genome does not hold
information for "each and every cell".
The genome contains a list of "genes".
Each gene holds information like angles, distances,
the type of cell (more on this later), how many times
to replicate, and its following child gene. The embryo
cell (or "root" cell) is placed at a predefined
location. All consecutive cells are grown from this
initial cell. The embryo cell always uses the first
gene in the strand. See
Applet.
example of a genotype graph
Phenome
The blueprint is then read through as data instructions,
specifications on how to build a creature. All construction
starts from the embryo cell and uses information contained
in the genome. So for example, the embryo cell contains
the first gene in the strain, and is told to make a
new cell at 30° absolute angle, 25 pixels away from
itself. It is also told how many times to do this, and
in our example the cell is told to divide three times.
Now we have a form that looks like a column of cells
lined up at 30 degrees. The cell is also told what the
consecutive "child" cell each of these new
cells will make. So if the embryo's child is told to
use gene 13 (which contains information like angle,
distance, which child gene, etc etc), the new cells
that it makes will divide again with those specifications.
This process continues until all cells divide to a cell
that contains a gene telling it to stop. These termination
genes are important because it prevents infinite loops
of cell growth.
To cut corners and save time, I assumed
that creatures are to be built bisymmetrically down
a center axis as are most animals. Thus, the genome
defines exactly one half of a creature and every cell
division is mirrored across its center axis.
The springs that connect these cells
together are not defined directly in the genome. Rather,
a routine runs through all cells checking their distances.
If a cell is within a certain distance threshold (say,
20 pixels), connect the two cells with a spring. This
distance is called "cohesion distance", and
it plays an important part in creature evolution. One
tiny angle shift would greatly change the behavior and
mechanics of a creature.
This is why there isn't a one-to-one
relationship between genes and cells, and that in general
a string of 10 genes can produce a complex pattern of
over 300 cells. This is the relationship between genotypes
and phenotypes. The advantage is to have relatively
little information produce large quantities of patterns
and to have evolution recycle these useful patterns.
See
Applet.
Finally, the genome also instructs
what that particular type of cell is to be grown. The
following three sections describe the nerve cell, the
muscle cell, and the sensor cell in detail. back
to top
Nervous
System While this work
goes in depth with simulating neural networks, the depth
did not serve to be an advantage to the final result.
Nonetheless, I referenced John Holland's description
of artificial neural networks for this project (John
Holland, Emergence from Chaos to Order, chapter 5 on
Neural Nets). As a side note, even though this simulation
of neurons is very detailed, it is but an extremely
crude simplification of true neural networks running
within your skull. I'm also ignoring Hebb's Rule,
which I now think is a grave mistake. See
Applet.
Neuron
Each cell in this work is a simulated neuron, and the
creature as a whole can be thought of as a neural network
in itself. Every neuron cell contains a charge that
is accumulated. This accumulation is the sum of charges
from other neurons firing to it (except sensor cells).
When the accumulated charge surpasses a certain threshold,
the neuron itself will fire to all cells it's connected
to.
Variable Threshold
The threshold at which a neuron
fires is variable. When a neuron hasn't fired for a
very long time, the neuron is more sensitive to firing
(the threshold is low). When a neuron has just fired,
the threshold is high. It will take a much higher accumulation
of charge in order to make the neuron fire again.
Synapse Neural
cells are connected to one another through a synapse
connection. In proper biological terms, these are your
dendrites and axons. The genome does not give information
on which cell is connected to which cell, and therefore
springs are used as bridges of synaptic action.
Fatigue After
a neuron has fired, there is a certain amount of time
where it simply cannot fire anymore. A neuron recovers
over a certain number of time-steps and then is ready
to fire again once the fatigue is gone. This allows
special behaviors like lock-step firing when neural
loops are involved.
Weights In
addition to a signal strength, a signal also contains
a special "signal weight". This value is specified
by the genome, so that each cell has a predetermined
weight that it will fire. The value can be positive
or negative, depending on specifications of the genome.
When a neuron cell is ready to fire, it will sum up
all the weights recieved from other neuron cells that
fired to it. If the combined weight is "not zero",
the cell will fire. If the combined weight is zero (the
event that a cell fired to it with -1, and another cell
fired to it with +1), the cell will refuse to fire.
This property allows for highly complex neural networks
to emerge, explained below.
XOR A
network with two inputs, one with a positive weight
and the other negative, both fire to a recieving neuron
cell. This network is able to accomplish a simple
computational task called XOR. The recieving cell
will only fire if one of the inputs are triggered,
but not both at the same time. See
Applet.
Indefinite Memory
A XOR network with a loop from
the recieving cell firing to one of the inputs causes
the network to have what John Holland calls "indefinite
memory". That is, the network "remembers"
that its free input has been triggered. It can also
actively delete that memory by triggering the same
input at the same time, canceling out signal travelling
in the loop. See
Applet.
example of an XOR network
The goal for simulating these processes
is to have intelligent "feed-forward" neural
networks emerge. A feed-forward is best understood when
compared to a feed-back network. A feed-back network
is a network that makes a direction connection between
the inputs (sensors) and the effectors (muscles). Think
of a venus fly-trap: once its sensors are triggered,
it automatically causes a chemical reaction to make
its jaws close. On the other hand, a feed-forward network
hooks up the inputs to a hidden layer, and the hidden
layer is then connected to the effectors. The hidden
layer is a neural network that will not only behave
reactively, but proactively. A hunter in the
ocean will actively seek out prey, as opposed to acting
only when prey comes its way.
back to top
Muscles
The nervous system of a creature
will pass information onto muscle cells. These specialized
cells are also nerve cells that can recieve charge and
have variable threshold and fatigue like described in
the previous section. I experimented with turning on
and off the muscle cell's capability of transmiting
its own charge with varying results.
In reality, muscles are fibers made
from hundreds of thousands of cells. Sir Charles Dawrin
called it one of nature's most amazing inventions, noting
how a soft piece of jelly could turn stiff and tough
in a fraction of a second on command (electric pulse).
Since I am simulating on the level of individual cells,
I had to take the shortcut of modeling "muscle"
cells. When it recieves a charge and fires, the muscle
cell will temporarily decrease the spring length to
all of its neighbors. The produced effect is a contraction.
Unlike SodaPlay, these muscles do not act constantly
on a Sine wave. They act only when their own internal
neuron fires. Also, Soda's muscles are allowed to extend,
whereas muscles in this work are only allowed to contract,
reflecting real muscles a little closer (though you
can argue that relaxing a muscle is the act of extension...
but let's not go there...).
After a muscle has reached maximum
contraction, the muscle will begin to relax. It cannot
contract again until after it has been relaxed. The
idea of controllable relax rates had been toyed around
with during my evolution tests, but the evolved creatures
were never smart enough to take advantage of such a
mechanism.
Creatures that have efficient muscle
systems can propell themselves through fluid. This is
caused by springs losing energy to fluid friction. The
physics here is more messy than I'm willing to expulge,
and the implementation is equally as messy. back
to top See
Applet.
Sensors
Some cells are tagged as sensor
cells. In biology, specialized cells can pick up a variety
of information about their environment, such as pressure,
magnetic and electrical forces, sounds, chemicals, light
from the visible spectrum, etc. In modeling these creatures,
I wanted to evolve creatures that could not only swim
quickly, but adapt to a changing environment such as
a moving light-source. Pressure sensors were planned
but due to time constraints were cut out of implementation.
Light Sensors All
cells tagged as sensors are light sensors. These cells
recieve charge if it is exposed to a light source. A
ray-trace is performed and if the cell's line-of-sight
is blocked by other cells, it will not recieve charge.
Light sensors have a limited capability of telling distance
to light. Future designs of this implementation should
allow global comparisons of all light sensors, therefore
giving the creature a sense of direction to light. This
is not the case right now. A sensor is either exposed
to light, or hidden.
This is done to encourage eyes to grow
on the outside of the body, as opposed to the inside...
However light sensors can "see" through other
light sensors (other light sensor cells do not block
line of sight), giving the possibility of compound eyes
to emerge. back to
top
Putting
it All Together A complete
creature is now constructed of springs, nerves, muscles,
and sensors. The morphology is built from instructions
contained in the genotype. The cells are color coded
in the following format:
Stucture
Cells that have no specialization.
These cells are referred to structure because they only
serve to anchor other cells together with springs. These
cells are colored in gray.
Nerves
The neuron cells that are allowed
to pass information to other cells are colored in blue.
Muscle
Cells that can pull other cells
behaving like muscles are colored in red.
Sensors
The light sensors of a creature.
They are colore green.
Example of creature anatomy.
Several render views were
written as well. Two important ones are noted here:
The first viewing mode renders all the springs as they
are located in space. The second mode shows the creature
anatomy and all synaptic connections as well as cell
types, neural activity, and so on. See
Applet.
Evolution
The process for evolution to occur
are as follows:
Completely random genotypes are generated.
They are built into phenotypes and dropped in a population.
This population is usually around 150-200 randomized
creatures.
The program then goes through and tests
each creature for performance. Before that occurs, some
simple logistical tests are done to prevent wasting
simulation time. Creatures who explode due to physics
bugs (spring integration errors) are immediately removed.
Creatures who don't have all requisite parts (say, missing
sensors or muscles completely) are also removed. Creatures
who fail to respond in the first 50 frames are removed.
Once a creature is found to be capable
of motion, that creature is placed in the Best Creature
slot and given a fitness value. The fitness value is
determined by what type of test is being done (more
on this next).
After the program has exhausted testing
the population, the best creature is picked for duplication.
Its offspring will take up about 30% of the population
and the rest will again be seeded by randomized creatures.
The offspring of the last successful creature are all
mutated slighly in some particular way (change in cell
spacing, angle, cell type, children, neuron weight,
etc). The program once again tests this population,
finding a creature that has a higher fitness to replace
the last creature.
As an aside, evoltuion could have
benefitted from cross-breeding the genotypes to make
mutant creatures however this feature had been cut
out due to time restrictions.
This is a crude way of evolving virtual
creatures but it was all I had time left for. Two types
of tests were made to test creatures for fitness. They
are:
Fast Swimmers
Creatures from this test are selected for absolute speed
only. A light is placed north of the creature, however
the creature is allowed to swim in any direction so
long as it goes fast. Speed is measured in pixels
per frame (px/frm). See
Applet.
Creatures that emerged come in a variety
of shapes and sizes. Extremely fast creatures were capable
swimming at about 5 pixels per frame. Some creatures
use the entire forward contraction of their bodies to
move forward like a slug. Others wag appendages to move
themselves. There are also creatures that would curl
themselves into an arc and use their entire bodies to
move. A few creatures travel by mysteriously vibrating
extremely short muscles back and forth and generate
motion.
  
Follow the Light In
this test creatures are given fitnes values based on
how well they follow a light source. Three tests are
performed. The first test is with the light directly
north of the creature. Creatures going the wrong way
are eliminated and thus only creatures with sensors
facing the light survive (in nature, escaping a predator
by going toward their jaws is a very bad idea). The
second test is with the light starting directly north,
but slowly moving towards the left. In the third test,
the light moves to the right.
Creatures are scored on how close they
get to the light. Creatures that can only go in a certain
direction (say, they only go straight every single time
and ignore the shift in light direction) are given a
penalty. Creatures that can react to the changing light
direction are thus selected for. See
Applet.
The resulting creatures that emerged
from these tests are surprisingly simple in construction.
For the most part these creatures use the same strategy,
that is, to place their sensors in a concavity or a
convex surface. When the light source has moved, only
one side of its body would respond, thus achieving a
crude "light-following" behavior. None of
the creatures exhibited any usage of complex neural
networks...
Conclusion?
In conclusion, evolving virtual creatures is much harder
than it looks. "Design by brute-force" is
what it really comes down to, and though it's a fantastic
approach, it must be optimized in many ways in order
for hundreds of thousands of generations to be done
feasibly. The dream is to show the process to someone
in real-time, and by recording time-lapse videos of
this project I was able to achieve some of that.
There are many things that didn't work
out, such as the physics engine, the neural network,
evolving by mutation alone, and others. Future versions
of this project should keep things simpler, and allow
complexity to arise as opposed to the other way around.
There are things that I did not foresee, such as physics
problems (fluid dynamics, Runge-Kutta, etc). Other places
that could be greatly improved is the technique in which
evolution is selected. The code is both messy and obsfucated
because of my lack of experience in writing such things.
The neural network was also something I didn't imagine
would be a problem. Future versions would allow neural
networks to evolve seperately, thus evolving creatures
that know how to use their bodies properly. The muscle
system could use a lot of work, as well the sensors
which could benefit from having various other types
of sensors (internal pressure sensors). Finally, new
tests should be performed for other creature designs,
such as with gravity turned on (SodaRace style), and
competition between multiple creatures.
All in all it was a worthwhile learning
experience. From this research I had to delve into many
different disciplines of science, such as biology, physics,
chemistry, neural science, and computer science. Any
future attempts at this project would demand that I
learn a lot more math.
Bibliography
Here are works both cited and
referenced, listed in no particular order.
Emergence
from Chaos to Order by John H. Holland, 1998.
Evolutionary
Wars A Three Billion-Year Arms Race by Charles
Kingsley Levy, 1999
Evolving
Virtual Creatures by Karl Sims, 1994
The
Emergence of Everything by Harold J. Morowitz
SodaPlay
by Soda Creative Ltd.
Blur code by SEB & Modified/Rewritten
by Toxi
Special thanks to Casey Reas, Ben Fry,
Chaim Gingold, Quasimondo, Skloopy, V3ga, marcello,
and Fish-face.
The work on this website
is copyright © Michael Chang 2005
|
