Evolving ant behaviour

Example of simple ant behaviour - spiralling

I've been thinking for a while about how to program ant behaviour in my simulation. The difficulty is that even relatively simple behaviours (such as following a pheromone trail) are difficult to code as a behaviour at the agent (or ant) level. While I probably could come with a reasonable behaviour if I thought about it and tested various parameters, it seems a lot simpler to evolve a suitable behaviour. After all, that’s what ants did. The problem then is how to convert ant behaviours into an evolvable form (i.e. a string of numbers). In other words, I need to write ant behaviour in a programming language that can mutate and will give a valid program (i.e. behaviour) no matter what the mutation. The behaviour can be useless (e.g. just stay still), but the program needs to be able to run it.

Encoding behaviour

First, we have to define what we mean by a behaviour. At its most fundamental level, a behaviour is a group of if-then rules: if you find yourself in situation X, then do Y; if you find yourself in situation A, then do B. On the ‘then’-side of the rules, these ants have two possible outputs: either walk forward, or turn by some amount. In fact we can simplify things by having a single output: which direction to walk in (which can be a number between plus and minus infinity, converted to radians or degrees). However, since walking forward (relative to the direction the ant is currently walking), if likely to be the most common behaviour, I decided to make that the default behaviour. The ant will only turn if it receives a single telling it to turn.

So what about the ‘if’-side of the rules – the ant’s inputs. At a first glance it seems that there is only one input that will effect an ant’s behaviour – the concentration of pheromone it smells (assuming for now that there is a single pheromone and ignoring other objects, such as seeds, rocks and other ants). This highlights the difficulty the ants face in achieving their goal of collecting seeds.They have no other inputs – they can see the seeds, they don’t know where they are relative to the nest and they can only smell the pheromone in their immediate surroundings. It’s as if I asked you to collect seeds, but each turn only told you if you were standing on a seed or not, and gave you a number (corresponding to the pheromone – but you don’t even know that). In response you have to say a number (corresponding to a direction to move in), and the process repeats.

However, if you knew what the numbers you gave and received corresponded to, you might actually be able to do quite well. The main reason being that you have a memory. So if you start at the nest and move one step forward, you know the nest is one step south of you. Now, I don’t what to give my ants the ability to built a mental map of their world – partly because I don’t think real ants do (though there is evidence that some ants count the number of steps they make and use this information to find their nest – in an incredible ants-on-stilts experiment), but also because I wouldn’t know how to do so in a realistic way.

However, I think a simple sort of memory would be useful, for example, remembering the last time the ant made a turn, or what the level of pheromone has been over the last few steps. In fact, even bacteria has a simple memory that allows them to solve a very similar problem: how to chemotax. Chemotaxis is behaviour of bacteria to move towards or away from a chemical (actually a chemical gradient). Since bacteria are so small they can’t simply measure the concentration of a chemical on either side of them as there will be no significant difference. Instead of measuring concentration differences spatially, they measure them temporally – they basically measure whether the concentration of the chemical is more now than in was in the past. If it is an they ‘want’ to move towards the chemical, then they are more likely to keep swimming forward, otherwise they are more likely to change direction. They way they ‘remember’ previous chemical concentrations is very clever, I recommend reading about it on the Wikipedia page. This system works quite well in getting ants to move along concentration gradients, but I doubt it will work so well when the pheromone is in narrow lines.

Chemical memory

The question then is how to create a memory that can store information about previous inputs (pheromone levels) and outputs (turning/walking straight). What’s more the memory has to be able to evolvable (i.e. able to be reduced to a string of numbers). The way I plan to create the ants’ ‘brain’ is by using a simple ‘receptor’, that measures the concentration of a certain chemical in the ants’ brain and causes a specific outcome (e.g. turn left) if the chemical passes a certain threshold. The concentration of chemicals can then be altered in response to behaviours, time, or other chemicals.

For example, a realistic-looking ‘random’ behaviour can be achieved, with a single chemical and a single receptor. The receptor causes the ant to turn (say, between -90º and +90º) if the chemical concentration is above a random threshold between 0 and 100 units. If the chemical starts at 200 units, and decays by 1% per unit of time, and increases by 100 once the ant turns, then the ant moves in a straight line for 19 to about 40 units of time before turning randomly. Each of these values (the decay of the chemical, the amount it increases after a turn, the range of the random values for the threshold), can be evolved.

More complex behaviour can be achieved with more complex behaviours. For example, the picture shows spiralling behaviour created by an ant that only ever turns left, and does so at ever increasing intervals. The ever increasing interval can be ‘remembered’ as a second brain chemical that does not decay, but increases after every turn. The ant turning threshold for first chemical is dependent (with a random element) on the concentration of the second chemical. I now need to work out how many chemicals to use, how they can relate to one another, and how to encode the system as digital DNA.

Implementing evolution

The most obvious way to implement evolution would be to set up colony of ants each with the same random behaviour, run the simulation for an arbitrary length of time, and measure the success of the behaviour as how well the behaviour achieved what we want it to (e.g. how many seeds were returned to the nest). The we mutate the behaviour of the ants and run the simulation again. If the mutation is more successful then we keep the mutation, otherwise we revert to the original behaviour. A more direct way of simulating evolution would be to create say four colonies of ants, each with their own behaviour, and see which collects the most seeds in a certain length of time. Once the time is up, the behaviour of the winning colony would be mutated three times to create three more colonies to compete with the winner. The problem with both these methods is that they will take a very long time. As the genetic algorithm to create an image of Darwin showed, at least 4000 generations are required before anything approaching a good solution is achieved.

A faster way to evolve ant behaviour that I might try is to create a colony in which each of the ants is given a different genome. The ants can then compete with each other to collect seeds. The way I envision this working is release the ants into the virtual world, and whenever an ant returns to the nest with a seed, create a daughter ant the same genome, but slightly mutated. Then, to prevent overpopulation, a random ant is killed (which may or may not include the ant just ‘born’, I’m not sure). This should allow ant seed-finding behaviour to evolve much quicker. The only problem is that, unlike in a real colony, where the ants should be genetically identical or closely related, selfish behaviour might evolve rather than cooperative behaviour. It might be interesting to see what that behaviour would be though (e.g. would ants lay misleading pheromone trails?).

And finally: a cartoon illustrating the intelligence of ants: http://www.xkcd.com/638/

Post new comment

The content of this field is kept private and will not be shown publicly.