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:
-
Biology-ignorant computer scientists think that important events in natral
evolution include: flight, moving onto land, the eye and occasionally,
language, multi-cellular organisms. Real biologists cite: self-replicating
molecules -> RNA, evolution of chromosomes, prokaryotes -> eukaryotes,
single-to-multi-cellular orgainsms, sexual populations, and social species
[John Maynard-Smith and Szathmary]. CS gets one right (and a half for language<=>social
species, maybe). Why do real evolutionary biologists have such a different
list? Mostly just because lay people are size-ist and animal-centric. But
also because we are thinking about the results rather than the mechanism
- being able to breath air, fly, or detect electro-magnetic radiation are
results. But these were all found using the same adaptive mechanism - gradual
adaptation within a fixed representation/reproductive mechanism. The "major
transistions" cited by JMS et al, are not chosen because they had cool
results - they are chosen because they break a previous 'mold'. Each transition
corresponds to the formation of a new "unit-of-selection" - entities which
were adapting independently became reproductively dependent, and fused
into a new entity. This is not part of 'survival of the fittest', 'differential
descent with modification' or 'mendellian genetics' - its deeper than that.
-
Lets take a different angle: Computer scientists spend a lot of time trying
to figure out good representations with which to evolve cool things. In
natural evolution finding the right representation is part of the process.
Natural evolutin has not used the same representation throughtout. It has
used the same representation for all animals, for example - but hey, all
animals are practically identical from an evolutionary standpoint. We talk
about individuals and species and sexes like they are givens that have
always been there... well they havn't. Natural evolution invented the concept
of individual as we know them, and species, and sex.
-
For example, you know that when cells do that spliting thing where the
chromoses gravitate to opposite sides of the cell and then it divides -
well, it hasnt always been like that. How do the little bits move around
in that little dance and organise themselves? How did it get to be like
that? Lyn Margulis spearheads the notion that the microtubules that are
responsible for providing motility within the cell came from protozoa that
infected the cell - or something like that. Anyhow, the point is that being
able to do that litlle dance is not a feature of the host cell that was
gradually adapted - it is a feature of the community of little protozoa
things and the host cell. Of course, this little community became reproductively
dependent a long time ago, and since then they have lost the ability to
survive independently from each other.
-
Cool isnt it? you actually create this new unit - the miotic cell (or whatever
its called), which we now take for granted.
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.
-
How is that complex systems may emerge without design effort?
-
Is it always the case that the complexity must be implicit somewhere
- if not in the adaptive mechanism then in the environment? -or, is there
a way to get more complexity out than you put in?
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:
-
the equivalence of evolutionary adaptation and reinforcement learning
-
co-evolution, speciation, resource-based competition in un-bounded population
sizes
-
heterogeneous systems/ modularity
-
cooperative systems/ mutually benefitial groups/ ecosystems
-
The role of competition and cooperation in evolutionary search
-
Building-block hypothesis, Royal-Road functions
-
Evolving recurrent Neural nets
-
Population dynamics
-
"encapsulation", any process whereby a group of species become reproductively
dependent
-
"Symbiogenesis", eg."different bacteria form consortia that, under ecological
pressures, associate and undergo metabolic and genetic change such that
their tightly integrated communities result in individuality at a more
complex level of organisation" Margulis 92ish
-
Relationship between micro-level and macro-level structures
-
relationship of group and individual reward functions
-
reward allocation - credit assignment, avoiding exploitative parasitism
-
formation of higher-level morphological structures from morphological primitives
-
finding solutions by modelling sub-problems or sub-classes of problems
as resources for an heterogeneous ecosystem of specialists to solve between
them - and take a look at the balance between specialisation and generalisation,
and see if this is related to interdependence of the sub-problems/sub-classes
of problem. (society of mind taken litterally)
-
note the difference between societies and heterogeneous modular individuals
- ie, reproductive dependence -> cooperation is expected when reproductively
dependent
-
evolution of complex heterogeneous individuals via the encapsulation of
complex heterogeneous groups of simple individuals
-
evolution of RNN with tractable reinforcement learning properties
-
formation of higher-level morphological structures from morphological primitives
embodying GAs using recycling of redundant robotic elements and, recruitment
via robot-robot programming