Log of research in progress - sept 1996 to dec 1998

Nov 1998

Embodied Evolution sexy page

Embodied Evolution not so sexy page

Aug 24th 98

So we actually got our first repeatable, verifiably-positive result. In fact, Embodied Evolution discovered a weight configuration that confered a higher hit rate than our hand-designed solution after about 2hrs of evolving. This was verified for an average of 6 runs of both EE and designed. So thats bloody cool.

See publications for the text of the poster we just displayed with our demo at SAB98.

So now I have about 7 research directions I could follow up

SECS, POTs, SEAM, HIFF, NMB, EE, and Robotic Elements see Research Directions

Aug 1st 98

Finally got my nearly-decomposable building-block model accepted (see publications).

C code for the HIFF function.

In the meantime the robot work on Embodied Evolution that I started fall 96 has also finally taken shape - because I got help. Sevan started working with me seriously late 97 (though he's always been contributing) and over this summer Prem Melville has been doing all the real work (i.e. making the hardware do what its supposed to do). Giovanni has been building hardware add-ons that have made it all possible too. This has enabled our first results recently (stay tuned for new tech report and a demo at SAB98).

What I said Jan 98

I just did (Jan 98) a couple of new papers, (See publications, (and the links really do work now BTW :)). These are probably the best indication of what I'm actually doing rather than what I like to think Im doing. However, if you like a good waffle, read on...

Evolving robot controllers and working with hardware is VERY time consuming, I havnt done any for a few months in favour of doing some science (see recent publications). Although, Im going to do some more robot work soon. That will involve "embodied evolution" - that is, evolving robot-controllers using a real population of robots that act in a real environment; and allowing the robots to 'reproduce' by passing program specifications from the more fit to the less fit when they meet one-another.

For the last 6 months I've been trying to formalise the concept of "partially-decomposable" problems spaces. I believe that most interesting problems have a hierarchically structured decomposition, but that the sub-problems are inter-dependent. Exactly what it might mean to be a sub-problem (implying independence) and at the same time non-trivially dependent on other sub-problems is a bit tricky. This is the subject of the "Hierarchical building-block problems..." paper. This paper introduces the Hierarchical-IFF function which defines a very simple abstract problem with the right properties - properties abscent from all the test functions in the GA literature BTW (well, all the ones I know of, including royal roads and NKs and Goldbergs "fully-deceptive" trap functions).

Then, armed with this nice formal test problem, I can take a look at various GA varients and see how they perform on this important problem-class. What do you know?... the standard GA doesnt do too good. Its much better if its steady state but even then it converges too quickly for this problem (the problem requires the maintenance of mutually exclusive schema for at least as long as it takes to resolve their interdependencies at the next level in the hierarchy). If we use a method of enforcing diversity (based on resource depletion, for example) to prevent over-convergence, the GA does fine... BUT only so long as it can use the heuristic of bit-adjacency. That is, the standard GA only represents building-blocks (BBs) via the weak heuristic of block-bits being adjacent on the genome - if we shuffle the bit-ordering, the standard GA cannot recombine blocks effectively.

So, the idea is to find an algorithm that allows the explicit representation of BBs when found. This is where all the 'individuals forming groups to find solutions' stuff that Ive been thinking about comes into play. Why not let each individual in a population be the explicit representation of a sub-solution. Then recombination can join individuals together to find solutions at the next level. Well this is exactly what the BB hypothesis has already said... except there it was assumed that an individual would code for many schema and recombination would cut-and-splice them together. Here I am saying that the individuals should represent only a single BB and only combine into 2-block composite individuals when they are compatible. (well, thats a bit obscure - read the paper :). So far, this is simply a Messy GA, with a few hacks, and with mutation and cut operations not used. Thats right - no mutation. no cross-over. Instead there is only 'splice' - the purely additive aspect of the 'cut-and-splice' recombination that MGAs use. This means that there are no bit-wise operations - the only unit-of-variation is the individual. And this means that the search is not hindered by the original representational choice - i.e. bits. In fact we see that as BBs are identified and their recombination proceeds to find bigger blocks, the performance of the search process increases exponentially (whereas in the latter stages of the regular GA search progress tails off). So, these results are shown in the SAB paper.

The trouble is, that now we have lost the implicit paralellism that GAs are supposed to offer. My next bout of research will implement the ideas Ive been pushing for for nearly two years - how to use an ecosystem of interdependent individuals to balance:

- the implicit paralellism that group evaluation affords, with

- the explicit BB representation that the individuals code for.

Stay tuned.....

Meanwhile here's some more keywords/ideas/ramblings:

What I said when in summer 97 when I thought robots could be fun

evolving robot controllers pics

What I said when I got here in Sept 96

In general, I'm looking for underlying principles of self-organising systems and complexity - the essence behind the 'something for nothing' that living systems seem to be. The particular direction of my current research focusses on the formation of mutually benefitial groups and their influence on the reward landscape of the individuals concerned. (See publications)

Other things/ related areas/ keywords that I'm thinking about: