Quote of the Day

The secret to understanding complicated things is knowing what not to look at.

- Gerald Jay Sussman

Objectives

I'm thinking seriously about the directions I'd like to pursue in the next six months or so. Some of these are straight-forward and easily testable, some are wild ideas or random shots-in-the-dark.

• Modular vs. centralized controller. Using two instances of the same evolved controller, one for each lateral side, had a dramatic effect on evolvability of biped.
• Does communication between instances help? (eg, a shared connection)
• Will a smaller grain work better? Even unintuitive approaches like an instance for each joint might be interesting.
• More complex neuron models. A recent paper suggests that this is indeed an important factor.
• Beer/Leaky neurons (CTRNNs), 1st-order ODE.
• Taga, 2nd-order ODE.
• Ekeberg, 3rd-order ODE. Reeve's 1999 thesis suggests this model is best for oscillation.
  
• A mix of different neuron models. Gut feeling that this is the most promising.
  
• Different schemes for linkage between networks. People seem fixated with changing weights of semi-static connections, but other approaches, like Gas Nets, are very interesting.
• Development/Embryogeny. Haven't looked into this much, but Bongard's work was pretty compelling, especially when combined with fluid or position-based connections/excitation transfer.
• Related, continuing with the "clump" approach to pattern generation. The echo-state network idea seems wonderfully suited to developmental approaches.
  
• Properties of locomotion space for different neural models. CTRNN-XOR space was looked at in some depth by USussex folks. Clearly need to investigate techniques for characterizing the space, esp interested in relation to neutral networks.
• Related, is cross-over really important? I'm still looking for alternative variatoin operators.
  

Neutral Networks

My very rough idea of Neutral Networks is that they are a special class of problem where you're guaranteed that you can always move "sideways" in at least one-dimension in the fitness space. That is, for any individual, there's always at least one direction to go that doesn't reduce your fitness.

The interesting part is that many systems, such as evolved neural networks, have the hope of being at least a little like ideal neutral networks, and so may be good problems to solve via evolution. Indeed, supposedly, if a problem behaves according to the rigorous definition, a global minima will be found.

All this got started with Motoo Kimura, Eigen and Schuster. Looking at RNA "folding landscapes" (not the proteins generated by the code, but the actual RNA molecule itself, (what's the jargon for it??)) as netural networks.

All this seems to have started with Lionel Barnett's 1997 MSc dissertation "Tangled Webs: Evolutionary Dynamics on Fitness Landscapes with Neutrality" (word) (ps). I find it wonderfully readable and inspiring. Here's some quotes:

Comparatively recent developments in evolutionary theory and molecular biology have all pointed to the importance of selective neutrality as a significant factor in evolutionary dynamics. This work includes Motoo Kimura's Neutral Theory of molecular evolution, Manfred Eigen's analysis of molecular "quasispecies" and recent developments in the understanding of RNA evolution both in vitro, in simulation and analytically. A picture emerges of populations engaged not in hill-climbing but rather drifting along connected networks of neutral genotypes, with sporadic jumps between networks. These neutral networks are of particular significance if they "percolate" the landscape - i.e. they come arbitrarily close to almost every other neutral network - for this raises the possibility that (given enough time) genotypes of almost any possible fitness value can ultimately be attained by the population. The scenario of a population trapped on a local hilltop vanishes.

and he also makes a point that has bugged me since first reading about GA's:

...we limit our "genetic operators" to mutation alone. Our genotypes are all haploid and reproduction is asexual. This merits some comment. In the GA literature dating back to John Holland there has been a perception of recombination (crossover) as the driving force behind evolutionary search, with mutation taking a back seat as an insurance policy against permanent allelic loss. It is not clear why mutation has been thus relegated, nor that recombination is necessarily effective in search. From the biological point of view there are many organisms for which recombination rarely or never occurs during reproduction. Molecular biology, furthermore, offers many scenarios of non-recombinative reproduction.

Finally, Sussex EASy's Bibliography of Neutral Networks (way out of date), and some high-level, but good lecture notes from a class there. (Use IE. Really, Firefox 1.0.4 didn't work)

Locomotion-specific Neuron Models

What neuron model should be used for Locomotion tasks? Is there a big difference? Does the increased parameter space overwhelm the gains of autonomous periodicity? That's the topic of An Analysis of Neural Models for Walking Control and, at least for quadraped locomotion, the answer seems to be that more complex neurons are a gain overall.

Neural models that they consider:

• Threshold.
• Sigmoidal.
• Leaky-integrator/Continuous-time, or first-order ODE. (Beer) (note that self-connections are needed for oscillations). Funahashi and Nakamura. Did Beer use plastic weights? Do R&H? Is it advantageous?
• Taga (10). Second-order ODE, basically an extension of leaky-integrator with an additional, coupled 1st-order ODE.
• Ekeberg (12). Three state version, 3rd-order ODE. Developed for analysis of the lamprey spinal cord networks that controlling swimming.

On a similar note, Center-Crossing Recurrent Neural Networks for the Evolution of Rhythmic Behavior shows that Center-crossing CTRNNs work better for locomotion than randomly aligned CTRNNs.

I'd like to see some comparisons between CC-CTRNNs and Taga's and Ekeberg's models as well.

The details of Reeve's and Hallam's setup are in Reeve's PhD Disseration at Edinburgh, Generating Walking Behaviors in Legged Robots.

Finally, what I keep expecting to find is evolution of a linear combination of sine functions. I mean, if you just want a stable walker, wouldn't this work nicely?

Also worth looking at CiTRuS: The Continuous Time Recurrent System, from Robert Vicker at Sussex.

Multiple Instances of a Single Controller

In ELSE, evolving one controller that handled all the inputs and outputs was pretty much a dead-end. Instead, evolving a single controller network and making two "instances" of it, one for the left side and a mirrored one used by the right side. (need to measure this and the effect of adding a communication connection)

It turns out that insects may do a similar thing. Holk Cruse, according to this the ANWM Seminar notes, "found that insects, which have many legs, do not use a central processor to keep track of all the movements of their multiple legs. Instead local interactions between sensory motor reflexes enable complex walking behaviors to emerge."

Vaughan's using Bilateral-symmetry: BSSNN

http://www.droidlogic.com/sussex/adaptivesystems/Arm.pdf

Where's the Interest in Mapping Fitness Functions of Real Problems?

It seems to be generally assumed that one primary difficulty in applying evolutionary methods is defining a smooth fitness function that avoids local minima as possible. Even the best methods, like NEAT, stagnate as some point. I'm interested in looking at these places in the fitness landscape-- places where evolution isn't able to make further progress. Perhaps even mapping them out. Maybe even generating or co-evolving fitness functions to help find easily understood evolutionary traps. It would probably yield nothing intelligible, but possibly trying to characterize fitness functions by looking at where they trap different representations.

Here's an example looking at CTRNNs and XOR. I find it most striking that there isn't anything familiar-looking in his graphs. Wouldn't you think XOR would be simple? And since it really isn't, what is a simple (but at least slightly non-trival) problem for evolved NN's or CTRNN's?

LT Research Thoughts

Generalize both the code and the approach of ELSE to support the evolution of many behaviors using different approaches (e.g., evolved periodic functions, CTRNNs, echo-state networks, etc.). Possibly fall back to working with something more stable, eg. quadrapeds or maybe even worms/snakes.
- Implement from-scratch version of CTRNN-evolver based on NEAT ideas. Abstract evolver from evolved (how realistic? tricky interface to define and still support things like NEAT)
- upgrade to ODE 0.5 (or possibly look into coding up a Verlet-based PE?)
- add config scripts for generating skeletons, bodies, joints and motors.
- add script interface for fitness and short-circuit evaluation
- add script interface for "supports" as a function of time

Use PF's learned-controller-selection approach to choose which evolved controller to use at any point in time. Probably, just add evolved controllers to DANCE (plus maybe add ODE to DANCE or ?? to ELSE).
Co-evolve controller-selection (dispatcher?) with controllers. How to structure fitness s.t. controllers don't become muddled up?

Developmental Neural Networks

Just stumbled upon this page:

This project models the rules of biological self-organisation that can generate neural circuits. Rules governing development are used to "grow" the inter-connections between the neurons. Currently this development model "grows" 3 D layers of Neural Networks using local chemical gradients emitted by neurons that influence both the growth direction of other neurites (axons and dendrites) and their propensity to split. It has been used to generate a large-scale structure based on a biologically plausible model of a retina that does edge detection and, for individual neurons, to produce the appropriate spiking behaviour when presented with a stimulus. A genetic algorithm is used to search the parameter space to determine the best parameter values for the development rules.

A multi-compartmental neuron simulator (called NEURON), that used partial differential equations, was used when investigating the neuron firing patterns. This model is too slow for networks of neurons and a faster simulation, that uses an adaption of a finite state machine to tree structures, has been partially developed.

The PhD programme will either:

1. Complete the new multi-compartmental neuron simulator and integrate it with the developmental model. The final combined models will be used to look at the effect of dendritic geometry on function, and possibly to define classes of dendritic geometries.
or

2. The model for growing neural networks will be extended to include the concept of genetic regulatory networks. A genetic regulatory network is the intricate and recursive network of activation and repression mechanisms formed by proteins that act on genes to determine whether and when they should generate other proteins. As such it can be used to model interactions between the parameters that control the developing neural network over time.

An interest in neuroscience and biology would be beneficial for this project.

To discuss this project please contact Rod Adams.