Possible Research Directions I was thinking about in summer 1998
I now have about 7 areas for further research (depending on how
you count). And I dont know which Im going to follow. I've listed them
in order with most-fundamentally-interesting-to-me first:
1. SECS: Spontaneous Emergence of Cool Stuff, minimal substrates for SECS
relates to CAs (esp. continuous valued versions), cybernetics (meta-stable
systems), ALife, and MOOVONS - 'neurons that move'. Take a moovon kind
of idea then strip away the making and breakng of connections - just have
every node 'connected' to every other inversly proportional to its distance.
Then take strip away the physical space and simply imagine a sytem of variable
that influence one another proportionate to their similarity (formerly
proximity). Now you have a continuous valued CA. I havnt really decided
whether Moovons or a continuous valued CA is the right way to go. see this
paper for interesting/related ideas Principles
of Systems and cybernetics: an evolutionary perspective
1.5 Moovons - neurons that move
a moovon can compute and move. Its movement in x/y is a function of its
inputs possibly a simple differential steer (i.e. 2 inputs correspond to
left and right 'motors speeds'?). Moovons make and break connections with
other nodes by approaching and retreating from them. But within the connected
range the weight of the connection is a function of the distance between
the nodes. The output of the node is propagated via the connections and
therefore affects the movements of the connected nodes and therefore affects
the weights/ connectedness of other nodes. In this manner we have a RNN
that can rearrange its connectivity dynamically and computes its own configuration.
And my imagination does the rest: composite structures that move around
gathering new nodes and assimilating them, creating copies of themselves,
doing all sorts of cool stuff.
2. POTS: Partially Ordered Tuples
a minimal substrate for examining circular dominance relations in coevolution
arms-races
3. SEAM: Symbiotic Evolutionary Adaptation Model
A GA varient with some similarity to Messy GAs based on the formation of
symbiotic relationships and the susequent joining (SEAMing) of individuals
into composite individuals.
4. H-IFF: Hierarchical IF-and-only-iF.
A formal Royal Road style test problem for GAs. Models the hierarchical
nature of BB structure supposedly ideal according to the BB hypothesis
(BB=building block)
5. NMB: Negative Mutation Bias, noise and handicapping.
As the number of correct bits in a genome increases (whether fixed length
or variable) the probability of a mutation being derimental rather than
advantageous also increases - there's more to mess up. When the probability
of negative mutations is higher than that of positive mutations we have
negative mutation bias. NMB when under effective selection pressure is
not a problem - it doesnt matter how many negative mutations occur so long
as you can reject them and only accept the positive ones. However, in the
case where there is noise in the evaluation metric (whether because of
innaccurate measurement or incomplete measurement (eg tournament selection
against finite population)) the chances of an inferior mutant being selected
is non-zero. Extreme NMB is not uncommon and, with just a little noise,
can result in as many inferior mutants being selected as superior mutants
- thus halting evolutionary progress.
6. Robotic Elements.
the idea is a soup of robotic components that self-assemble into composite
structures. Easy to say. Even easy to design. But not so easy to build.
I've put a bit of thought into what kind of mechanics and interface robotic
elements would need. And the Embodied Evolution stuff provides an evolutionary
substrate that could evolve group behaviours including attachement (ie.
formation of composites) if that is in their behvioural repertoir. There's
loads of interesting stuff to think about wrt how composites reproduce
- eg like colonies a la medusa jellyfish, like slime moulds, or true centralised
reproduction from a seed element -ie a robotic element that can reliably
induce the formation of the composite it came from.
7. EE: Embodied Evolution
done that
SECS
Spontaneous Emergence of Cool Stuff. What we all want really (loose sense
of all) - to get the computer to create something cool without us having
to tell it what we want. There are people in CS trying to do this all over
the place with various degrees of awareness. That is, its rare that people
expect our systems to provide some solution to a problem we couldnt already
do. The point is not what you get but how you get it - i.e. with as little
inductive bias as possible. The vision being that if we can create something
that does more than we told it to then (even though what it does so far
is pretty stupid) it has the potential to do something more than we can.
This has produced an emphasis (for the pure at heart, like myself) to prune
and trim our experiments until they have virtually nothing in them except
the essence of a learning or adaptive mechanism. ie. remove all domain
knowledge and inductive bias and mechanisms that do this and do that to
make the task easier. Hence we see people doing robotics by evolving RNN
(recurrent neural net) controllers where, instead of programming-in behavioural
modules, the idea is to provide a substrate thats capable of expressing
sufficient behaviours but we dont tell it anything about how to configure
this network.
But RNNs (especially when on a robot) are still quite high-level constructs
and they invariably do have quite a bit of domain knowledge built-in even
if only in the structure and size of the network - how many layers, degree
of connectivity, enabling recurrency, type of output functions, continous-time
or discreet. How could we get past all of this arbitrary/ad hoc structure?
How could we make all of the above into options that may be discovered
rather than design choices the rearcher has to make? (without just listing
them and enabling selection) Better, what kind of substrate would enable
these as specific configurations out of a broader canvas of possibilities.
And, then there's the problem of connecting them up to something so that
they do something. It's no good having a computational substrate andexpecting
it to learn to 'compute' if it doesn't have an environment in which computation
is necessary.
So we have some questions:
1. What is the minimal substrate for describing computational constructions?
2. What environment will promote the formation of interesting examples
of such constructions?
My basic answer to 2 is 'other constructions' - i.e. some form of coevolutionary
setup where the existance of interesting stuff requires/promotes the existance
of more interesting stuff.
(BTW - we dont use the word 'complex' to describe what we're looking
for because complexity is not sufficient - for example, the placement of
molecules in a bucket of water is complex, but not interesting. We havnt
yet found any really good way of describing what interesting is - that
balance between chaos and order - in acknowledgement of our ignorance I
adopt the phrase 'cool stuff'. )
But, what does that mean - what kind of interaction is there between
these constructions that could provide a pressure for increased interestingness?
So we have to define a physics of interaction (at least). Well, suppose
these things (whatever they are) have some kind of connection to oneanother
- eg output of A is connected to input of B.
this is silly I started from far too broad a perspective: the brief
summary at the beginning was closer
POTs
Partially Ordered Tuples
Evolutionary algorithms are a favourite tool for attempting SECS but
they usually dont deliver the goods. There are several theories about how
they fail / how to make them work better. Foremost in the running is coevolution
- the argument goes that EAs fail because although the substrate is capable
of expressing solutions and the fitness function is capable of rewarding
them there is no gradient/reward for sub-optimal candidates so selection
pressure is absent. Coevolution where individuals are rewarded for their
perfrmance with respect to other individuals instead of against a fixed
evaluation metric is intended to provide a gradient that does reward sub-optimal
candidates and keeps things moving. However, when individuals are rewarded
by a relative metric they can sometimes satisfy the relative metric without
making progress on the absolute metric - the one you really care about.
For example, game players may get better scores by playing mediocre games
that draw consistently than by taking the risk of exploring more sophisticated
strategies. Worse, if the other player is really crap then being pretty
crap yourself is sufficient since this always wins and therefore improvement
is not rewarded. And then there's other ways to get mediocre scores like
we each win half the time. Or more interestingly, A beats B beats C beats
A 'dominance cicularities' where behaviours outperform oneanother but dont
get better in absolute terms - see POTs.
In an attempt to understand some of these coevolution dynamics people
have been trying to find minimal substrates that enable analysis of performance
in both relative and absolute metrics. But its not easy to find a task
thats simple enough to be analysed unless you make it up and then you dont
really know how hard it is or whether it has the right properties for open-ended
evolution (see POTs).
SEAM
Symbiotic Evolutionary Adaptation Algorithm
H-IFF
Hierachical IF-and-only-iF
NMB
Negative Mutation Bias
Couple noisy evaluation with a NMB that produces many more inferior
candidates than positive ones and progress is halted (even though there
are still superior mutants being produced every now and then ). Assuming
non-perfect evaluation this causes a complexity ceiling that will necessarily
be reached sooner or later in open-ended evolution (i.e. unless the global
optima is reached first). One possible remedy is handicapping: for example
in coevolving game players with win/loose payoff the noise is highest when
players are close in ability - i.e. when equal in ability its down to luck
alone. One way to change the noise/signal ratio is to handicap the challenger
(i.e. new mutants are deliberately disadvantaged). If they win now its
probably by ability. This means that some slightly better mutants will
be rejected erroneously but progress that is slow but sure is better than
no progress.
Robotic Elements
EE
Embodied Evolution