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: 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.