Statement of current research interests
introduction
The common theme of my research is evolution. But, I find myself dissatisfied
with the prevailing computational model of evolution. Evolutionary computation
traditionally adopts a framework that resembles function optimization.
Though there are some exceptions to this view of closed-ended adaptation
within a fixed-environment, evolution is almost invariably modeled as a
convergent process. It is as though there is an underlying assumption of
teleological progress toward a single goal. In contrast, natural evolution
is a creative process not a problem-solving process. The diversity of living
systems, (even if it is now in stasis - which is debatable), has undeniably
increased since the inception of life on Earth. The main drive behind my
research is to roust the closed-ended, convergent view of evolution epitomized
by "survival of the fittest"; and to pursue the broader view of evolution
as Creation - an open-ended, autocatalytic, dynamical system.
Informal questions, such as the following, illustrate the motives of
my work:
-
What is the minimal substrate for evolution, and how does natural evolution
change the representation in which variation takes place?
-
What is the relationship between microscopic and macroscopic scales of
evolution; how does the evolution of entities within an ecosystem affect
the environment in which other entities evolve, and is this feedback fundamental
to evolution?
-
Under what conditions will the complexity of an evolutionary system become
autocatalytic; producing increased complexity in response to extant complexity?
My concrete attempts to approach these questions are necessarily more humble,
and for the most part, have taken my work into two established fields:
Evolutionary Robotics and Genetic Algorithms. I give some detail on my
work in these areas below, and then return to the big picture in 'work
in progress' subsequently.
evolutionary robotics
My work in this area (together with Sevan Ficici) has developed an evolutionary
robotics methodology we call Embodied Evolution (EE). The motives for creating
the EE methodology pertain to three different research areas. We view EE
as an artificial life experiment, as an evolutionary robotics tool, and,
in particular, as a substrate for the evolution of collective robotics
behaviors. The following extract from our recent CEC'99 submission (enclosed)
details the EE idea:
"Our work is inspired by the following vision. A large number
of robots freely interact with each other in a shared environment, attempting
to perform some taskÑsay the collection of objects representing food or
energy. The robots mate with each other, i.e., exchange genetic material,
producing (offspring) control programs that become resident in other members
of the robot population. Naturally, the likelihood of a robot producing
offspring is regulated by its ability to perform the task or collect Ôenergy.Õ
Further, there is no need for human intervention either to evaluate, breed,
or reposition the robots for new trialsÑthe population of robots evolve
hands-free. Many substantial technological demands are made by this vision,
and considerable algorithmic detail must be added before it is workable.
We have developed this vision (to our knowledge first articulated
by Harvey [Harvey 1995]) into a methodology we call embodied evolution
(EE). We define embodied evolution as evolution that takes place in a population
of real robots, and we stipulate that the evolutionary algorithm is to
execute in a distributed and asynchronous manner within that population.
Thus, we exclude methods that serially evaluate candidate controllers on
a single robot as well as algorithms that maintain and manipulate the specifications
of individual agents in a centralized manner. We wish to create a population
of physical robots that both perform their tasks and evolve autonomouslyÑwithout
human intervention of any kind. This paper introduces our implementation
of embodied evolution and reports results of initial experiments that provide
the first proof-of-concept for embodied evolution." [Watson et al,
1999]
Our embodied evolution experiments to date have used a population of eight
robots, that receive power through an electrified floor. Reproduction is
performed autonomously by the robots in a way which is seamlessly integrated
with their task behaviors (see 'Probabilistic Gene Transfer Algorithm'
in [Watson et al, 1999]). No centralized or globally coordinated control
is involved in the evolutionary process - the adaptive mechanism is entirely
distributed in the robot population. This integration of reproduction with
other autonomous behaviors has previously been limited to simulated agents
in ALife experiments. By using a population of robots, evolving and interacting
in a shared environment, EE also enables future research on the evolution
of collective behaviors.
genetic algorithms
There are many different varieties of evolutionary algorithms. However,
it is very difficult to ascertain the merits of one method with respect
to another since there is little agreement in identifying the class of
problem for which they are well-suited. My research in this area has pursued
the fundamental role of recombination as described by the building-block
hypothesis. To this end I have formalized the class of problems for which
recombination is advantageous. Specifically, I have defined a simple but
rigorous hierarchically decomposable problem - its canonical form is Hierarchical-If-and-only-if
(H-IFF). [Watson et al 1998].
H-IFF is motivated by the inadequacy of previous test problems in respect
of epistasis. In particular, previous building-block functions such as
the Royal Roads and the concatenated trap functions have no interdependency
between blocks, and, at the other extreme, problems like the NK landscapes
have no modular decomposable structure. Indeed, it may seem impossible
for a problem to be decomposable yet have significant interdependency between
components. However, this is not so. H-IFF has a hierarchically decomposable
structure yet the component-problems have strong non-linear interactions.
The key conceptual shift is that problem decomposition enables dimensional
reduction but does not require separability. H-IFF is easily solved by
a GA but impossible for non-population based methods.
One interesting proviso to the success of the GA on H-IFF is that diversity
in the population must be maintained. If the GA is allowed to converge
then it as useless as a hill-climber on this problem. This observation
is in keeping with our intuitions of population-based search methods. [Watson
et al 1998]
work in progress
The questions mentioned earlier pertain to three fundamental issues: substrate,
micro/macro interaction, and dynamics. My work on evolutionary robotics
and genetic algorithms fits together with other work in progress, described
below.
substrates
The one substrate that we know for sure is sufficient for life is natural
physics. Maybe there are some essential subtleties of the way that physical
things interact in our universe that is missing from other dynamical systems.
Accordingly, one approach to artificial life is to utilize natural physics
as much as possible - hence Embodied Evolution. However, it seems likely,
(and perhaps it is necessary for our own understanding), that it is possible
to extract the essential properties extant in nature. The result will be
some form of abstract massively parallel dynamical system. An important
emphasis in the EE research is that the individual robots will be simple
and that interesting phenomena will emerge from their collective interaction
- not from the actions of any one individual. In the limit, we might imagine
that an individual robot can hardly even compute by itself. Perhaps we
could reduce it to something approaching a single neuron and allow interaction
between individuals to form a computational network. And perhaps we can
reduce its action set nothing but movement. Then, the flow of excitation
into a node (formerly a robot) will control its movement, and its position
will influence the strength of its connections to other nodes and hence
the computation of the network. Thus the movement and computation of the
network is inextricably linked. This (imaginary) system, which I call moovons
(for 'neurons that move'), essentially reduces physics to geometry. I would
like to find out whether it is a sufficient substrate for evolving complexity.
But, moovons still have a lot of artifactual properties. Suppose we reduce
them further to simply a system of real values. Let their values (formerly
positions) be a function of other values in the system regulated by similarity
(formerly proximity). In so doing we arrive at a continuous-valued cellular
automaton. I have implemented several versions of systems of this type
with variously interesting results.
micro/macro interaction
My Masters research lead me to develop a model of the interaction between
symbiosis and the evolution of the individuals concerned. This turned into
an algorithm: Symbiogenic Evolutionary Adaptation Model (SEAM). SEAM is
a GA variant with some similarity to Messy GAs. It uses the formation of
symbiotic relationships to prime the population with species that are complementary
in their abilities. The subsequent joining (SEAMing) of individuals into
composite individuals enables encapsulation of the group. This process
continues forming groups of successively sophisticated individuals. The
recursive nature of this process is fundamental to my interpretation of
the larger view of natural evolution. In this model the diversity of the
ecosystem and the mutually beneficial interaction of the species therein
is an integral part of the process which enables increased complexity.
H-IFF, as an EA test problem, has a recursive structure and a requirement
for diverse populations which is integral to this aspect of my research.
To date, I have applied a simple variant of the Messy GA to H-IFF [see
'Incremental Commitment GA' in GECCO'99 submission] and am currently working
on an adaptation of Hinton and Nowlan's 1987 work "How Learning Can Guide
Evolution" to demonstrate how symbiosis can do the same.
dynamics
Evolving ecosystems are complex dynamical systems. It's not easy to determine
the attractors of such systems. And worse, as we know, life tends to approach
the edge of chaos. Coevolution is a popular evolutionary computation method
where the fitness of individuals is measured relative to other adapting
entities rather than an absolute performance metric. One of the difficulties
in using coevolution is that the dynamics of the system can breakdown.
For example, stagnation where the competition between evolving individuals
reaches a stable state which is sub-optimal, (e.g. alternating wins, or
repeated drawing), and even when the relative selection pressure promotes
continued adaptation in the system there may be no progress in the absolute
metric that we really care about (e.g. circular patterns of specialization
rather than generalization). To investigate some of these concepts I have
conducted evolutionary trials where individuals are represented as partially
ordered tuples. These have one of the more interesting properties found
in coevolutionary systems - the potential for circular dominance (e.g.
A beats B, B beats C, C beats A). Experiments in this substrate enable
easy analysis, assist in gaining an intuition for the relationship between
relative and absolute metrics, and the difficulties that this can present.
In natural evolution there is no teleological goal, and the probability
of survival is a function which is almost entirely relative to other evolving
entities.