This paper presents a general overview of artificial life and an introduction to a few of the first advances in the field. Complexity and its achievement through simple rules is a theme explored throughout. In support of this theme, Boids: Flocks and Schools, a computer program developed by the author (based on the previous work of Craig Reynolds) which models the complex behavior of flocks and schools will be reviewed.
Artificial life is a strongly emerging field contributing to genetics, evolutionary biology, biochemistry, computer graphics, robotics, and the emerging field of complexity. So what is artificial life? According to Chris Langton who coined the term, "Artificial Life is the name given to a new discipline that studies 'natural' life by attempting to recreate biological phenomena from scratch within computers and other 'artificial' media.... rather than studying biological phenomena by taking apart living organisms to see how they work, one attempts to put together systems that behave like living organisms" ("AL-Groups"). Also, a strong comparison between artificial intelligence and artificial life can be made. If one views the fundamental function of artificial intelligence as the mimicking and dissection of cognitive life processes for the advancement of computer learning and decision making, then artificial life can be seen as the understanding, conceptualizing, and modeling of biological mechanisms and ultimately, the creation of life itself.
Theoretical studies of a-life began in the 1950s under the strong, agile mind of John von Neumann. As a strong contender to being the most brilliant mathematician of this century, John von Neumann made full use of his extraordinary mind. Born in Hungary on December 28, 1903, he dazzled everyone with his ability in mathematics and his photographic memory. After receiving his doctorate in mathematics, he was named to a Rockefeller fellowship at the University of Göttingen where he published his first masterpiece, Mathematical Foundations of Quantum Mechanics, at age twenty-three. He went on to be the youngest person to lecture at the University of Berlin where he invented game theory, was later a professor at the Institute for Advanced Study at Princeton, brought the A-bomb at Los Alamos to completion a year earlier than was thought possible, led the work on ICBM missiles, and described the computer architecture used on nearly all modern computers--von Neumann processors (Stonaker 91-102). Additionally, he also laid the theoretical framework for a field that at the time didn't exist--artificial life.
Von Neumann understood that the complexity of biological organisms was more than humans had ever understood, but because he believed life was based on logic, like computers, we were capable of forcing organisms to surrender their secrets (Levy 15). In particular, Von Neumann was interested in self-reproduction, a necessary component of any life form. Rather than trying to accomplish this at the genetic level, he wished to abstract from natural self-reproduction its logical form (Langton 1984, 135). The Hungarian-born mathematician's exploration of very basic a-life formats would latter title--father of artificial life.
These a-life formats would be self-operating machines whose behavior could be defined in mathematical terms, cellular automata (CA). "An automaton is a machine that processes information, proceeding logically, inexorably performing its next action after applying data received from outside itself in light of instructions programmed within itself" (Levy 15). Automata themselves were not new, but von Neumann proposed a variation, self-reproducing automata whose information blueprint controlled its behavior and its reproductive activity.
Automata, then, are essentially algorithms, and if an algorithm can be preformed by any machine at all, then a universal Turing machine can perform the same algorithm. (Here, we're considering a universal Turing machine, an abstract machine capable of mimicking any other machine exactly. Christopher Langton would latter show that universality is a sufficient, but not necessary condition for CA self-reproduction.) So if Von Neumann could demonstrate the existence of a Turing machine which could reproduce itself, then it is plausible to conclude that the reproductive processes of living organisms are algorithmicly describable, because by definition the Turing machine must have been using some method, an algorithm. If this can be proved, then the processes on which life is based are algorithmically describable, and therefore, life itself is achievable by machines (Langton 1984, 135).
Von Neumann's self-reproducing structure consisted of a checkerboard (cellular array) with each square, or cell, in one of n possible states. The number of states is finite and each cell is itself a machine, so in technical gobbledegook each cell is a finite state machine (FSM). At any moment, various cells are in a quiescent, or inactive, state with the other cells in an active state. The precise combination of those cells in their given states defines the creature and tells the creature how to behave. At each instance of simulated time, each cell in the checkerboard uses a set of simple rules to determine its next state as a function of its current state and the state of its immediate neighbor cells. Each cell looks at itself and those around it and then asks, "What do I do next?" (One instance of simulated time, mentioned above, means that every active cell has made its decision and determined its next state.)
Von Neumann's original self-replicating structure consisted of 29-state cells and simulated a computer which read in a 150,000 cell tape, followed its simple rules, and used a protruding constructing arm to from a new organism. The original structure came to be known as the kinematic model, or a universal constructor, and was composed of three components: the factory, the duplicator, and the computer (Reggia 1282-1283 and Levy 42-46). This kinematic self-reproducing automaton would be known as the first cellular automaton. His machine would construct any machine described on its input tape and attach a constructed copy of the input tape to the new machine (Langton 1984, 135).
Von Neumann passed away before completing his work on cellular automata, but many others would take off where he left off. His cellular construction was a complex "machine", along the general lines of an early digital computer, using 29 states as logical building blocks, complete with tape reading arms, clocks, encoders, and decoders. So many of his followers took up a question von Neumann had posed, "What is sufficient organization for an automaton to reproduce itself?" E.F. Codd demonstrated a construction universal configuration which requires just 8-states per cell (Langton 1984, 136). Christopher Langton would show that the "'molecular logic of the living state' can be captured by the interactions of virtual automata and thus that the existence of artificial life within cellular automata is a distinct possibility" (Langton 1986, 120). Excited by how the simple rules of cellular automata could generate dynamic and complex patterns, Steven Wolfram was one of many theorists who began to study complexity using cellular automata (Waldrop 87).
Years before chaos theory and the field of complexity, John von Neumann anticipated the phenomenon and what would become central to the understanding of biology. Steven Levy summed up von Neumann's views best in Artificial Life: "Life, (von Neumann) said, depends on a certain measure of complexity. If a certain critical mass of complexity is reached, objects can self-reproduce in an open-ended fashion, not only creating their equals but also parenting more complicated objects than themselves. (30)" Artificial life was just beginning to show biologists and others that what separated life from non-life was not a mystical force, but something absolutely essential to biological systems: complexity.
The most famous example of John von Neumann's invention and an inspiration to a generation of artificial life researchers was the game of Life. It was created by the mathematician John Horton Conway in the late 1960s at the University of Cambridge. Like von Neumann, Conway also believed that one could produce fantastic results from the most rudimentary elements, but he saw von Neumann's automaton as too complex and set out to construct an extremely elementary CA (Levy 50).
To come up with a few simple rules that yielded unlimited results but also combined to form a certain balance was not easy, especially since Conway aimed to reduce von Neumann's twenty-nine state to two states, filled or empty, alive or dead. These were the complete rules which Conway settled on:
The rules were simplified to account for the three essentials which Conway wanted in his model: survival, birth, and death.
- Life occurs on a virtual checkerboard. The squares are called cells. They are in one of two states: alive or dead. Each cell has eight possible neighbors, the cells which touch its sides or its corners.
- If a cell on the checkerboard is alive, it will survive in the next time step (or generation) if there are either two or three neighbors also alive. It will die of overcrowding if there are move than three live neighbors, and it will die of exposure if there are fewer than two.
- If a cell on the checkerboard is dead, it will remain dead in the next generation unless exactly three of its eight neighbors are alive. In that case, the cell will be "born" in the next generation. (Levy 52)
Conway and his friends began experimenting with the most simple configurations and what happened to them through a few generations. Many settled into stable configurations which they gave names such as beehive, loaf, pond, tub, block, snake, boat, etc. Others were called oscillators due to their alternations between shapes as time steps click by, and some of them were called toads, blinkers, clocks, and traffic lights (See Fig. 1).
Unlike von Neumann's CA's which remained only theoretical, Life could be played with a real checkerboard and real pieces to represent live cells. As their search expanded, Life grew off of the small coffee table, across the room, and out of the room itself. (Conway would soon use a PDP-7 computer to make his discoveries.) More and more simple life-forms were becoming complex. A classic example was the R Pentomino which began with an arrangement of five neighboring cells roughly shaped like the letter R. At each click of time it became something different. Small objects appeared and broke up; symmetry came and dissolved and came back. It was then that a colleague of Conway's, Richard Guy, discovered the first glider. It was walking like a single-celled organism and returning to its original configuration after four time steps, having moved itself one cell diagonally on the checkerboard (Levy 53).
Life's instant popularity began when Martin Gardner's "Mathematical Games" column in Scientific American (Gardner 1970). Conway's games were not new to the column, he was always coming up with some kind of mathematical recreation (an oxymoron to some). But this time he added a bonus, he wanted to find a finite initial configuration of Life that would generate infinite populations. He said it couldn't be done, and offered $50 to anyone who could disprove it. Suggestions were made in the article on patterns that could prove it: a "gun" that repeatedly shoots out gliders or a "puffer train" that moves but leaves behind a trail of "smoke" (Gardner 121-23).
After reading the October 1970 article, William Gosper immediately began work on a program for him and his fellow hackers to run Life configurations on a PDP-6 computer. Gosper was one of the key computer hackers at MIT's Artificial Intelligence Laboratory, and one of the brightest programmers in the world. Within a month his group had found the glider gun, and later, they found a puffer train too (Levy 57).
The glider gun was a major breakthrough. It was the last piece Conway needed to prove that Life could support universal computation. With glider streams to represent bits, a glider gun to serve as a pulse generator, and blinkers and gliders to serve as a clock, the equivalent of and-gates, or-gates, not-gates, and a computer's internal storage could be produced. Thus, Life was capable of emulating any other computation machine, whether electronic or natural. Although he never actually built his virtual computer, the MIT group created a Life-based adding unit. As Conway recalls, "It worked like clockwork. Streams of gliders would come around here, and sort of ticked around--click click click click click--and then the sum came out as another stream. (Levy 57)"
Conway had proved that von Neumann's ideas could be realized in a much simpler context. All the complexity of Life had been created with two CA states and four rules. Scientific papers on Life explorations would be published for years (especially by Gosper, see Gosper 1984), and all future a-lifers inspired by it. Despite that no Life configuration yielded a self-reproducing animal in a reasonably small space, "On a large enough scale your would really see living configurations," Conway says. "Genuinely living, whatever reasonable definition you care to give to it. Evolving, reproducing, squabbling over territory. Getting cleverer and cleverer. Writing learned Ph.D. theses. On a large enough board, there's no doubt in my mind this sort of thing would happen" (qtd. in Levy 58).
For several days in 1986 computer animators at Symbolics Corporation in Los Angeles would bring their lunch to a local cemetery and watch the blackbirds. Among them was Craig Reynolds who, from the time he was in college, had thought he could write computer programs with simple rules to simulate the complex movements of animals (Levy 76). Fascinated by the blackbirds, he was convinced he could recreate their behavior on a computer. In Reynolds's description, "The motion of a flock of birds is . . . simple in concept yet is so visually complex it seems randomly arrayed and yet is magnificently synchronous. Perhaps most puzzling is the strong impression of intentional centralized control. Yet all evidence indicates that flock motion must be merely the aggregate result of the action of individual animals, each acting solely on the basis of it local perception of the world" (qtd in Levy 76).
The trick was finding the few simple rules to produce the global, complex behavior of a flock. Each "boid" (an abbreviation of "birdoid" which applied to schooling fish as well as simulated flocking) would be autonomous and act only on those simple rules, which Reynolds finally boiled down to three:
As they flew, the boids would notice what their neighbors were doing--as though they were cells in a cellular automaton--and apply that information to their own actions in the next time step. Each boid, for instance, would detect the center of gravity within the radius it was aware of and move toward that point. If other boids were to the left, for instance, the boid would move left. It would try to match its speed to the velocity of the nearby boids, unless slowing down or speeding up was required to stay near the flock. And if a boid looked as though it was inching too close to a neighbor, it would move away from that potential collision. (77)
Reynolds also added obstacles, thick cylinders, to the program. The flock would diverge around a cylinder and reunite on the other side (See Fig. 2). This behavior and other responses which were not programmed into them led Reynolds to believe his theory had been enhanced by being successfully implemented (Levy 78).
He presented his results in 1987 at the very first artificial life workshop which was organized by Chris Langton and held at Los Alamos. The question on many attendee's minds was whether or not the responses were truly emergent. Among them were John Holland, founder of genetic algorithms and inventor of classifier systems, and Brian Arthur, non-equilabrium complexity economist, who debated the subject late one Tuesday evening while driving from Los Alamos back to the Santa Fe Institute. Holland was very skeptical. "Maybe everything that's happening in there...is so obvious from the rules that you aren't learning anything new. At least, I'd want to have the ability to put other sorts of objects in, change the environment, and see if it still behaved in a reasonable way" (qtd in Waldrop 242). Arthur wouldn't disagree and questioned what emergence really is. Isn't everything that happens in the universe already built into the rules that govern the behavior of quarks, including life? "I couldn't see how you could define 'truly' emergent behavior," says Arthur. "That goes to the heart of the problem in artificial life" (qtd in Waldrop 242).
What is emergence? When do you have it and when do you not? For any given system, how much of it is emergent and how much is not? When do you have emergent behavior that was unexpected? These questions are still yet unknown.
Boids: Flocks and Schools is a computer program created to reenact Craig Reynolds's results using his three rules described above. A user may simply run the program from any DOS-based PC using the preset values for program's variables, or he may experiment by populating the world himself and then running the simulation.
It's important to note two important differences between this and Reynolds's program. First, the boids of Boids: Flocks and Schools operate in a two-dimensional world, whereas Reynolds's boids existed in 3-D with pillars as obstacles instead of circles. This discrepancy is largely due to the fact that Reynolds had access to graphics animation development software at his company and lesser so due to the fact that Reynolds's program was designed for a graphics workstation, not any old slow PC. But both programs use filled triangles to represent the boids. Secondly, at the start of the program Reynolds's boids are spread out all over the screen and come together to form a flock; however, the boids in Boids: Flocks and Schools are initially randomly positioned at the top-left corner of the screen and usually immediately begin moving a safe distance away from each other. What effect this second difference has on the "emergence" issues of the program is left to the reader; however, the amazing lifelike results of implementing just three simple rules is significant nevertheless.
At the start of the program all the boids have the same values for their parameters which then vary as each boid makes its own decisions. A discussion of these follows. The number of boids can be set between 1 and 30. Each boid has an awareness radius within which it sees other boids and obstacles. It matches its velocity and direction based on those within this radius. Each boid also has a safety radius within which it judges whether it is too close or nearing to close to other boids and obstacles. Realistically, it should be less than the awareness radius, but the user may set it greater than if he or she chooses. The velocity is the number of pixels traveled in each time step. The acceleration value also acts as the amount of deceleration. It is a tricky value to set since it will usually take several time steps to catch up with the other boids or slow down to avoid a collision. An appropriate balance between velocity and acceleration is essential for a realistic simulation.
Initially, all boids start out moving in the same direction, but since they are randomly position in the top-left corner of the screen, they immediately begin moving away from each other and adjusting their directions. The center of the world space is (0,0) at the top-left corner with down and right being positive, up and left negative. Each boid's initial direction vector is normalized from a right-left (x) and an up-down(y) directional weight. So for the boids to initially move down and across the screen at a 45 degree angle, a 1 would be entered for both the right-left and up-down directional weights. Circles act as obstacles and are optional with any number possible. Each is simply composed of its X and Y coordinates and its radius.
Boids: Flocks and Schools is not an extremely provocative program and normally last only several seconds for each simulation. But in those seconds it's very important to observe the behavior of the individual boids and the boids as a whole, to notice the patterns that emerge such as V-shapes, and to realize that the behavior of the group is the result of simple rules.
Like Reynolds's program, Boids: Flocks and Schools is based on local, boid-to-boid interaction. This locality allows the flock to adapt to changing conditions like an adapting flock. There is no "boss boid". Each boid reacts to what the other boids are doing in its immediate neighborhood, allowing the flock to branch around obstacles as each boid does its own thing. Trying to do that with top-down specifications would be, as the author of Complexity explains, "impossibly cumbersome and complicated, with the rules telling each boid precisely what to do in every conceivable situation" (Waldrop 279). And it's impossible to cover every conceivable situation; however, bottom-up systems seldom encounter combinations of events they don't know how to handle.
Does this and Reynolds's program accomplish its goal? It certainly exceeded Reynolds's expectations. With the incorporation of advanced graphics hardware and software, it is easily to imagine this method being used to produce three-dimensional, flapping blackbirds or geese that could appear in a computer game or in a Steven Spielberg movie. And among artificial lifers it certainly raised more than a few eyebrows, even more questions, and inspired quite a few more programs into birth.
John Von Neumann's kinematic self-reproduing cellular automata, John Conway's extension of these ideas into the Game of Life, and Craig Reynolds's trio-ruled boids were only a few of the first advances made in what would later be known as the field of artificial life. Since their foundation, the field has seen genetic algorithms, gene switching modeling networks, autocatalytic networks explaining the origin of life, Lindenmayer's computer-generated plants, Thomas Ray's artificial ecologies, Chris Langton's life at the edge of chaos model, Stuart Kauffman's order and self-organization theories, and ALIFE robots by the dozens, just to name a few.
The field has proved to many sceptics that computers can be used to model the basic biological mechanisms of evolution and life itself, and like many fields, it raises questions faster than people can answer them. It had always been von Neumann's intuition that the computer would become the staging ground for scientific experimentation, even in biology. Indeed, the pioneers of ALIFE have discovered that "lifelike" behavior seems to lie in such principles as bottom-up rules, no central controller, and emergent phenomena. And as Chris Langton has said, "The most surprising lesson we have learned from simulating complex physical systems on computers is that complex behavior need not have complex roots" (Waldrop 279).
The following text should bear the name "readme.txt" and appear in the
same directory as the program Boids: Flocks and Schools, "boids.exe":
Boids: Flocks and Schools
Version 1.0 1995
by Terry Smith
Boids: Flocks and Schools uses simple rules to simulate the complex
movements of animals, creating simulations which can be viewed as either
flocks or schools.
ABOUT THE PROGRAM
The program is based on the work of Craig Reynolds who speculated on
how difficult it would be to get computer creatures to flock in the same way
blackbirds do. Reynolds's theory was that flocking could be modeled by
allowing each individual in the simulation to apply a few simple rules.
Reynolds's settled on three rules:
1. A clumping force that kept the flock together.
2. An ability to match velocity so that the birds
in the flock would move at the same speed.
3. A separation force that prevented birds from
getting too close to each other.
The simulated flocking applied not only to birds but also to schooling
fish. Reynolds's abbreviated "birdoid" and called them "boids". Take a look at
Steven Levy's description from his book Artificial Life:
Their observations and actions were entirely local. As they flew,
the boids would notice what their neighbors were doing--as though they
were cells in a cellular automaton--and apply that information to their
own actions in the next time step. Each boid, for instance, would
detect the center of gravity within the radius it was aware of and move
toward that point. If other boids were to the left, for instance, the
boid would move left. it would try to match its speed to the velocity
of the nearby boids, unless slowing down or speeding up was required to
stay near the flock. And if a boid looked as though it was inching too
close to a neighbor, it would move away from that potential collision.
USING THE PROGRAM
Main Menu options:
Run Simulation - If chosen before Populate, the simulation is built
from the preset conditions described below. The user
may set up his or her own simulation by choosing
Populate and then, when returned to the main menu,
choose Run Simulation. Any keypress exits the
simulation.
Populate - The user can set the number of boids and their
variables, as well as the number and location of
obstacles, from the Populate screen. If the number of
boids is set to 0, the preset conditions are restored
to the world and the user exits the Populate screen.
Help - Displays this help screen. This help file, contained
in readme.txt, should be in the current working
directory. If it is not, the program will ask for
the drive followed by the directory in which readme.txt
is contained. This help file can be printed on a
dot matrix printer by typing from the directory in
which it is contained:> type readme.txt > prn
This file can be shown to the screen in the same
manner by typing:> type readme.txt | more
Quit - Quits and exits the program. Any Populate setup by the
user is not saved.
Populate options:
Hint: If at any time you wish the preset values restored to the world,
simply choose Populate from the Main Menu and type 0 as the number
of boids wanted.
Number of boids: 0 means quit and use preset values.
30 is the maximum number.
Awareness radius: Radius around each boid within which it sees other
boids and obstacles. It matches its velocity and
direction based on those within this radius.
Integer value.
Safety radius: Radius around each boid within which it judges
whether it is too close or nearing to close to other
boids and obstacles. Realistically, it should be
less than the awareness radius. Integer value.
Velocity: The initial velocity of all boids. Enter 0 to use
the preset velocity shown below in the preset
conditions. Represents number of pixels traveled in
each time step. Floating point value.
Acceleration The acceleration and deceleration in one time step
of boids as they speed up to others and slow down to
avoid collisions. Realistically, significantly lower
than the velocity, usually less than one. Floating
point value.
Right-left direction: The right to left directional weight. Positive
is to the right, negative to the left. For users
familiar with vectors, this is the x component of
each boids direction vector. Note that since all
boids start in the top left corner, any negative
value will cause most boids to immediately leave
the positive world space sector that the user views
on the screen. Integer value.
Up-down direction: The up to down directional weight. Positive is
down, negative up. This is the y component of each
boids' direction vector. Again, the value should
normally be greater than or equal to zero. This
value and the right-left direction value are
normalized together to create the initial direction
vector for each individual boid. Integer value.
Number of obstacles: Number of obstacles to be added to the world.
0 means quit, use no obstacles, and use boids only
based on the above preset conditions. All obstacles
circles (or trees?).
X and Y coordinates: The positive coordinates of an obstacle
separated by a space. For example: 100 200
Coordinates separated by a comma may cause immediate
return to the main menu and irregular results when
running the simulation. Negative values will be
converted to positive. Integer values.
Obstacle radius: The radius of an obstacle. A negative value will
be converted to positive. After completing this
entry, the user will return to the X and Y coordinates
above and repeat the loop for each additional
obstacle to the entered. Integer value.
Preset Populate Conditions:
Number of boids: 20
Awareness radius: 40
Safety radius: 20
Velocity: 6.0
Acceleration: 0.5
Right-left: 1
Up-down: 1
Number of obstacles: 3
X and Y coordinates: 100 120
Obstacle radius: 20
X and Y coordinates: 220 200
Obstacle radius: 30
X and Y coordinates: 340 300
Obstacle radius: 25
REFERENCES
Levy, Steven. 1992. Artificial Life: A Report from the Frontier Where
Computers Meet Biology. New York: Vintage Books.
Waldrop, Mitchell M. 1992. Complexity: The Emerging Science at the Edge
of Order and Chaos. New York: Simon & Schuster.
Copyright 1995 Terry Smith
END OF HELP FILE
//====================================================================// // Programmer: Terry Smith // // Prog. name: BOIDS: Flocks and Schools Boids.cpp Version 1.0 // // August 9, 1995 // // Turbo C++ 3.0 (IDE) // // Boids: Flocks and Schools uses simple rules to simulate the // // complex movements of animals, creating simulations which can be // // viewed as either flocks or schools. The program's companion // // readme.txt file, which must be in the same directory as this // // program, contains more information. This sourcecode version is // // not dynamically linkable. It was compiled under the small memory // // model with egavgaf.obj, sansf.obj, littf.obj, and tripf.obj in the // // current directory. // // Copyright 1995 Terry Smith // //====================================================================//
"AL-Groups." Usenet news. comp.ai.alife. 1995.
Elwyn R. Berlekamp, John Horton Conway, and Richard Guy. Winning Ways for Your Mathematical Plays. New York: Academic Press, 1982.
Gardner, Martin. "Mathematical Games: The Fantastic Combinations of John Conway's New Solitaire Game 'Life'". Scientific American, Oct. 1970 Vol 223 Num 4: 120-123.
Gosper, R. William. "Exploiting Regularities in Large Cellular Spaces." Physica D: Nonlinear Phenomena. 10D (Jan 1984): 75-80.
Langton, Christopher G. "Self-Reproduction in Cellular Automata." Physica D: Nonlinear Phenomena. 10D (Jan 1984): 134-144.
________. "Studying Artificial Life with Cellular Automata." Physica D: Nonlinear Phenomena. 22D (1986): 120-149.
Levy, Steven. Artificial Life: A Report from the Frontier Where Computers Meet Biology. New York: Vintage Books, 1992.
Stonaker, Frances Benson. Famous Mathematicians. New York: J.B. Lippincott Company, 1966.
Waldrop, Mitchell M. Complexity: The Emerging Science at the Edge of Order and Chaos. New York: Simon & Schuster, 1992.