Introduction
This paper describes a system for animating simple, physically-based
computergraphic figures that can undergo evolution.
The project began as my attempt to create an articulated stick figure which can
move on its own.
In the early stages, it became apparent that it would be difficult, maybe
impossible, to find appropriate parameters of angular motions in the joints
to create walking behaviors. Thus, a genetic algorithm was created as a
method for generating a set of parameters for these motions. In this
project, principles from Artificial Life research are combined with
techniques of physically based modeling. For researchers pursuing more realistic
behavior with character animation, the task of determining parameters for how a
character moves becomes demanding. A solution to this is adaptation. Why not
let the characters evolve within the environment they were placed in? If we want
to create life-like figures in a synthetic world, we should allow their behaviors
to evolve to be fit for that world, rather than trying to force global rules onto them.
Autonomous life-like behavior is generally too complex for global direction,
as in traditional character animation. Complex behavior should be emergent:
evolving to fit the environment.
About the Anatomy
Pun not intended: one must
learn to crawl before one can walk, so I have chosen to start simple, since I am new
to the art of physically based modeling and character animation: so, simultaneous
with the choice to use a genetic algorithm to find good behavioral parameters, I
chose to reduce the anatomy to the simplest figure possible for an object which
walks: two sticks, nothing more (some may argue that there must
be knees before there can be walking - I will discuss this further below).
Part of the incentive for this simple figure was to encourage the emergence of
realism to be more from behavior than from anatomy. This simplification does
not deter from the essence of walking as demonstrated by the animations.
The Need to Control Friction
Without virtual knees, problems have arisen in the way the walker interacts
with the floor, namely, the walker cannot actually lift a foot into the air and
place it down again, as most animals can do by bending knees and ankles. The
walker has to slide the foot along the floor for a moment before the foot can be
free to move in the air. Thus, if a walker were to be used as a model for
manufacturing an actual robot, the robot could only be operated on a hardwood
floor or some other low-friction surface, otherwise it would not be able to pull
its feet out from under itself. In the walker world, some of the virtual physical
properties such as friction between feet and floor had to be tweaked at the setting-up
stage until the environment was of a satisfactory state for this need. After this,
the fine-tuning of feet-floor interaction was left up to the evolving walkers, since
they can, after all, adapt to the conditions of the environment.
About the Physics
In the artificial world of the walker, Newtonian mechanics are approximated to
allow concepts such as inertia, mass, and gravity to be used in describing the dynamics.
The two legs are treated as rigid bodies, and respond to mass, rigidity, internal
forces from the walker's actions, friction between floor and feet, and dampening
of vertical motion upon collision with floor.
In the spirit of Artificial Life research, the world in which the walkers live can
have a degree of arbitrary physics where laws do not necessarily reflect Newtonian
mechanics and classical rigid body dynamics. What makes many Artificial
Life systems robust is the fact that the genotypes can (and must) adapt to
whatever world their subsequent phenotypes exist in. In this project, the
implementation of Newtonian mechanics needs improvement. But the thrust in
this project has been the emergence of meaningful behavior through adaptation
to a synthetic environment: walkers always adapt to the conditions in creative
and amusing ways.
In the Breeding Room
The breeding process is as follows:
A population of walker genes is initialized with each gene set having initial
states set randomly within a prespecified range. This population of genes is
expressed as phenotypes (behaviors for walkers) which are rated, one by one,
for adaptability. Each walker, upon being rated, is placed on a virtual
hardwood floor in an upright position. On the floor is a virtual plate of
food which serves as a source of attraction to the walker's head. Like a
subtle magnet, the food source pulls the walker's head towards it, causing the
walker to tilt.
In the early stages of the breeding process, most
walkers simply fall over at this point, and do some spastic kicking in the process,
due to their initially random genes.
The criterion for rating the phenotypes is based upon how long the walker stays alive.
A walker's life can be terminated in two possible ways: (1) it loses its balance and
its head hits the floor, or, (2) it fails to reach the food source to satisfy its
innate hunger before a prespecified deadline. This criterion is simple, yet it
encourages the two most important ingredients for walking (at least in this system):
remaining upright, and getting somewhere.
Mating, Mutating, and Recycling
After this point, a cycle begins in which walkers mate and have offspring with
chances of genes randomly mutating. At each stage of the cycle, two walkers
are randomly chosen to be mated, with chances of being chosen proportional to
their rating. Their genes are spliced together to form a new genotype which
inherits sections from both. This new gene set is subjected to possible random
mutations to encourage constant variability in the population. At this point
the lowest-rated gene set is disposed of and the new offspring replaces it,
thus keeping the population at a constant count. The process is repeated
indefinately. At any point, the computer program can be halted and one of
the more successful gene sets can be saved in a file and used in one of a
number of animation scenes.
An Ecological Element
This system has one
ecological component: the food source is able to flee from the walker, and so
there is interaction between agents within the system representing a simplified
predator-prey couple. Not only can the plate of food flee from the walker,
but its 'fear-level' increases every time the walker partakes of a bite (enters
the radius of the plate of food). Each time the walker takes a bite, the hunger
deadline is extended, representing a state of being nourished. The walker must
then periodically take bites of the food in order to keep the hunger state in
check. As one may expect, the more successful the walker is at pursuing the
food, the more vigorously the food will flee, since it is being nibbled at more
frequently. This, in turn, causes the survival criterion to be more demanding -
better pursuers of food will encounter more dynamic chase scenes.
Laurie Anderson's Idea of Walking
Performance artist Laurie Anderson once described, in a monologue, the act of
walking as a continual process of catching oneself while almost falling, by
placing one foot out in the direction of the fall, catching oneself, falling
again, and then placing the other foot out. Anderson's description of
walking-as-falling inspired the criterion for walking in this model.
In the breeding process, the phenotype begins in the vertical position with
feet on the floor. Since there is a constant attractive force of the head
towards the food, the walker continually experiences a pull in the direction
of the food, causing it to tilt, and to always be slightly falling.
The definition of walking in this system is, '...the ability for the figure to
move itself in the direction of the pull without its head coming in contact
with the floor (falling down) by way of complimentary angular motions of the
legs.'
Are they Really Walking?
The definition of walking may have different flavors depending upon who is defining it.
A physical therapist would define it differently than a fashion model.
A Zen master would probably have a different definition of walking than
an anatomist. In my program, walking is never clearly defined. Many adaptive
behaviors which evolve in my program can be described as hopping, scurrying,
stumbling, teetering, and shuffling. Without their having knees, it is
difficult to attribute any of these specific actions to the figures in a
clear way, but in general, the overall impression of their behaviors may
be summerized as that of walking. Thus, the use of the term walking is
impressionistic.
About the Kicking Behaviors
The behaviors of the walker are determined by a set of parameters,
encoded in the gene set. Most of the parameters control angular motions of
the legs as they pivot at the head joint. With a number of genes controlling
these kicking motions, a huge variety of kicking dynamics is possible.
The majority of possible behaviors, though, are quickly eliminated at
the beginning of the breeding process, due to evolutionaly selection.
The kicking parameters affect the amplitudes, phases, and frequencies of sine waves
in both spherical coordinates, theta, and phi for each foot.
Another parameter controls the gait rate; another controls the amount which
the gait rate changes in response to the tilting angle of the walker. One
can think of the motions defined by these parameters as causing the feet to trace
trajectories along an implied sphere surrounding the head. The trajectories
can vary widely.
Since gravity is constantly pulling the walker downward,
these kicking motions tend to involve much contact with the floor, and generally
cause less-evolved walkers to fall over in uncontrollable spasms. It is only
when the angular motions of the legs have evolved to a state in which they
interact in a complimentary way that the motions begin to encourage the walker
to remain upright and affect locomotion.
'Walking the Dog' with a Virtual Leash
A feature of the walker system is an interactive animation allowing one to
guide a matured walker around by pulling it with a virtual leash.
The end of the leash may be 'grabbed' with a cursor controlled by the mouse.
Here, the user can more readily 'feel' the behavior of the walker as it
interacts to mouse motions. Behaviors of walkers with different gene sets
can be explored in this way.
Interacting Walkers
Another feature of the Walker system is an animation showing two walkers interacting.
One walker is attracted to the other walker, and the other walker is repelled by
the first. In addition, the fleeing walker is attracted to the center stage,
such that it doesn't wander too far away from the performance area. Finely
tuned combinations of these forces create interesting and unpredictable chase
scenes.
Future Walkers
An obvious need of the walkers at this point is the
inclusion of knees so that they could have more degrees of freedom in lifting
their feet. Along with the inclusion of knees would be extra genes controlling
knee bending parameters. Down the road, I envision the genetic algorithm
evolving more than just dynamics of leg movements but to include anatomy itself.
In this way, walkers may evolve any number of limbs of varying lengths,
with any number of joints, with some limbs possibly inter-connected to
form 'bodies'. In this world, a much larger vocabulary of behaviors would emerge,
due to the varietiy of anatomies possible.
Notes on Production
The Walker project was
developed in the Advanced Graphics Research Lab, a facility of Research
Computing Services at Syracuse University. Hardware used was a Silicon Graphics
IRIS model 3020. Software was written by the author in Pascal, and includes the
SGI graphics library. A videotape about the Walker project is available through
the author at the address below.
See the Video on YouTube
|
