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


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


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


Symbiotic Evolutionary Adaptation Algorithm


Hierachical IF-and-only-iF


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


Embodied Evolution