Category Archives: Simulations
Avida
Self-replicating programs have been around for a while. The idea was first conceived by John Von Neumann in 1948 as a thought experiment. The first real instance was a game called Core War developed in the early 80s where programmers would write code to compete for sections of the computer’s memory. The best strategies were those that copied themselves, but these programs were fragile – change one piece of code and they would would cease to function.
Tom Ray’s Tierra in 1991 added some stability to the concept of mutation in a digital environment and showed that evolutionary processes previously only seen in nature can take place in the digital world. This eventually led to the “killer app” of self-replicating program research environments, “Avida”, developed by Charles Ofria at Michigan State University’s Digital Evolution Lab in 2000. Below is an animation showing successive generations of Avida organisms (Avidians) taking over the population as a sample evolution progresses:
At the 2010 Artificial Life XII conference in Odense, Denmark, the MSU team presented a paper describing some of their most recent work, including digital creatures that evolved the ability to follow paths along a grid. The environment was strewn with clues, signposts indicating which way the path would go. After tens of thousands of generations of evolution, the Avidians evolved reflex actions which successfully interpreted the signs as either “turn left” or “turn right”, giving them a survival advantage.
A program with just reflex actions can do quite a lot in a complex environment. What about using “volatile memory”, not just knee-jerk responses to the environment, but ones that depend on context? To encourage the evolution of volatile memory, the researchers put sign posts on the grid that symbolized “repeat last action”. The MSU team showed the Avidians were indeed able to take advantage of this information by evolving the ability to remember their last action.
The ability to remember and recall a single variable in the environment appears trivial, especially for a computer program, but the significance of this research is that no one programmed this behavior. The code which navigates the path and uses volatile memory to its advantage bubbled up from the raw evolutionary stew acting against a carefully crafted artificial environment that allowed such evolutionary pressure to exist.
There are many interesting questions here: Under what circumstances does evolutionary pressure tend to favor the development of micro brain structures? How can we configure artificial environments to evolve more complex bottom-up brains? How does the evolution of such structures manifest in nature?
Avida is a robust open-ended research tool and it is likely we will see many more groundbreaking projects coming from this platform for some time.
More:
Flock of Boids
Large flocks of birds appear to display a collective intelligence as they fly in an organized fashion with an apparently singular motive. Starlings in particular have been observed in flocks reaching hundreds of thousands of individuals generating amazing patterns in their group movement as shown in the video below.
Artificial Life researchers get very excited when complexity can be shown to emerge from very simple rules. One of the early examples of this was developed by Craig Reynolds as part of the 1987 SIGGRAPH conference with a program he called BOIDS. With BOIDS he demonstrated that flocking behavior can emerge naturally if every individual BOID followed three simple rules:
- separation: steer to avoid collisions
- alignment: head in the same direction as your neighbors
- cohesion: head towards the center
BOIDS is an excellent example of emergent behavior, and since been adapted for use in computer graphics and special effects, its first use being the 1992 film “Batman Returns” to render bat swarms and penguin flocks.
More:
Tierra
Tom Ray was a tropical biologist who conducted research in the Costa Rican rain forest from 1974 to 1989. His research focused on the ecologies and evolution of various species living there. Eventually he realized he there was a problem with studying evolution in the wild: it occurs far too slowly to actually observe it. He decided therefore to study evolution in a much faster medium, the digital computer. In 1991, he joined forces with the Santa Fe Institute in New Mexico to develop an evolutionary software platform called Tierra.
Genetic Algorithms, programs that simulate evolution to solve a specific problem, had already been well established, but Tierra was different. It wasn’t optimizing anything in particular. Small chunks of machine code were simply left on their own to replicate and compete for access to the CPU, and that was all. Occasional mutations in the copying process allowed evolution to take place. But, this wasn’t a simulation of evolution, these entities were actually evolving. What emerged from Tierra surprised Tom and most of the Santa Fe research team.
The first thing Tom noticed was that these replicating programs became smaller and smaller. A smaller program could replicate faster and so had an advantage over others. Some became so small that they evolved into parasites, tricking other programs into doing the copying for them. The hosts then evolved mechanisms to resist parasites. Some of the host programs were even able to trick the parasites into helping them. Eventually, a form of cooperation emerged where programs helped each other replicate. Then, free-riders emerged who took advantage of this group trust. All of this robust behavior, previously only observed in nature, emerged from Tierra automatically.
Tierra was groundbreaking for the field of Artificial Life, and inspired many systems like it afterwards, including the very robust evolutionary platform, Avida. Most importantly, it gave a demonstration of real evolution occuring in a medium other than nature.
More:
Baby Steps
Passive dynamics is an approach to robotics which uses the momentum of swinging limbs for greater efficiency. A purely passive dynamic robot requires no power at all. It will able down a plank all by itself if it’s configured just right. Of course, in the real world robots can’t be expected to always walk downhill. Ideally, one could combine the efficiency of passive dynamics with some kind of power so it can walk efficiently on a flat surface.
In 2003 at the University of Sussex, Eric Vaughan used artificial evolution to create powered bipedal walkers in simulation. Evolving both the passive dynamic body and the neural control system all at once didn’t work, so the evolution was given some assistance. First, the robot was evolved to walk down an incline passively. As the evolution progressed, the plank was gradually lowered until it was completely horizontal, gradually bringing the neural control system into play. The final result was a robot design that could walk on a flat surface using very little energy, much like a human.
More:
Resilient Robots
Using artificial evolution to design robots is a powerful technique. The difficult part is writing a simulation of the robot and its physical environment. A simulation is required so tens of thousands of design variations can be automatically tested as the evolution progresses.
What if you didn’t need to write a simulation? Imagine the robot could figure out how to simulate itself. Not only have you saved yourself a lot of programming, but the robot is now very resilient. You could snap off one of its legs, for example, and it would be able to re-simulate itself, and re-evolve a walking strategy.
Hod Lipson from Cornell University’s Computational Synthesis Lab has built such a robotic system. His robot first squirms around on the floor, testing theories about how its own motors work and what its own shape is. This simulation of itself is then used to evolve a walking strategy.
Such a system would be very useful for planetary exploration, where robot engineers may not be readily available to fix problems. If the machine breaks a leg, no problem. Re-simulate, re-evolve, and move on.
More:
Evolution: Creativity Engine
Evolution is an inherently creative process. Left to its own devices, it will automatically generate complex and beautiful forms.
Only three ingredients are required for a runaway evolutionary process to take hold: replication, variation, and selection. In nature, DNA is the replicator. It is able to make high-fidelity copies of itself under the right conditions. Variation comes from occasional errors during the copying process, and selection comes from the environment as some life is better suited to live and reproduce under the extant conditions of the planet than others.
Interestingly, these three ingredients are relatively easy to program into a computer. Replication is something computers do inherently. Copying data from one place to another is their most basic function. Variation is achieved by artificially adding some randomness to the copying process, again trivial for a computer. Selection requires a little more work. The programmer must decide what makes some entities more “fit” than others which usually requires a simulation of some kind. The fitter entities are then given more of a chance to copy themselves.
My masters thesis at the University of Sussex in 2005 was to design running, springy robots in simulation (called Metapets). The design task itself was too difficult to solve on my own due to the complex interaction of the springs and coordination of the limbs although I tried. Eventually, I appealed to evolution to work out the details. The fitness of each robot was determined by how far it moved forward, thus selecting robots for speed.
At the start of the evolutionary process, most robots would just fall down and go into convulsions. Others walked backwards, went in circles, or just stood still. But, after letting evolution run for several weeks, more functional designs gradually emerged, and the longer I ran the simulation, the better the designs became.
Many of the designs that evolved were quirky looking, while others dragged their legs, walked on their elbows, or moved in ways that one would not consider intuitive. Therein lies artificial evolution’s primary caveat: it may provide a means of automatically solving a specific problem in a creative way, but not necessarily the way you intended or expected. When this happens, the evolutionary pressure can be refined by adjusting the “fitness function” which determines each model’s fitness score in the selection step.
More:
Walking Tall
The field of Robotics constantly looks to Biology for inspiration, but it’s rare when the reverse happens. Such was the case with the fossil named “Lucy”, an ancestor of homo sapiens who lived over 3.2 million years ago and was discovered in 1974 in Ethiopia. Lucy was somewhere between ape and human, but with a large protruding jaw and a brain capacity 1/4th that of humans, she seemed more ape-like. Thus, some scientists concluded that she didn’t walk upright, and could probably only walk on two legs for brief distances, shuffling awkwardly like a chimpanzee. Others believed she walked like modern day humans. From the bone proportions alone it was difficult to tell. When footprints from the same species were uncovered in 1980, more evidence was brought to the debate. But how can one determine walking posture from just bone proportions and footprint patterns?
Robotics came to the rescue much later in 2005. The field of Evolutionary Robotics uses simulated evolution to automate the design of efficient robot bodies. Using this technique, scientists plugged in the constraints of the bone proportions and the footprint patterns, and let the simulation find the most efficient gait. Behold! Lucy walked upright, much like modern day human beings. Still, much is not known about Lucy and her kind. Their social characteristics and whether they were able to make tools remain a mystery.
More:
Evolved Virtual Creatures
The Connection Machine was a supercomputer designed by Daniel Hillis who came out of the MIT Artificial Intelligence lab in the early 80′s and started Thinking Machines Corp in Cambridge, Massachusetts. The Connection Machine used a unique parallel computer design with over 64,000 small processors all linked together, following a more brain-like architecture (plus it had lots of cool blinking red lights on the front). The ingenuity of the computer design attracted the attention of DARPA from which Thinking Machines received significant funding.
Karl Sims was an artistic consultant whose job was to come up with ways to show off the Connection Machine. One of his projects was a simulation of Darwinian evolution that produced designs of “virtual creatures” in a 3D environment. The simulation required a massive amount of computational power, and the lifelike forms that emerged made for a compelling demonstration of Thinking Machine’s latest model, the CM-5.
Despite the inherent awesomeness of the CM-5, no market could be found for the computers and with increasing competition from more established manufacturers, Thinking Machines filed for Chapter 11 bankruptcy in August 1994. Later, Sun Microsystems and Oracle bought up the remains. And, while the Connection Machine has since been relegated to the dark recesses of the National Cryptologic Museum, Karl Sims’ experiment still represents one of the best examples of the creative power of artificial evolution to date.
More:
