1:04

And they are several attempt to try to describe it.

Â This attempt, try to detail the behavior of single ants and

Â then to validate this behavior by having a whole simulation with several ants.

Â I will present you two different approaches and see that at the end.

Â Both are able to solve the problem.

Â The first model is the one of Deneubourg.

Â Deneubourg is a scientist working on ant behavior.

Â 1:39

I will give you some references the end of the talk.

Â The idea is that in this model every ants, so the ant leaving the regular grid,

Â so they are presented in every sense a kind of Eulerian view.

Â And they can walk in a forward direction.

Â Northeast, southwest, there are no diagonals in that model.

Â And usually, they will do a random walk.

Â It means that at every direction they choose the next direction and

Â they move there.

Â So the walk is purely random.

Â [COUGH] And there, here we use a sequential asynchronous updating scheme.

Â So now, [COUGH] the idea is this one, when

Â a worker finds a dead ant,

Â it has a probability P of p of picking its corpse.

Â If the corpse is isolated or in a small cluster.

Â [COUGH] But,

Â with probability P of d, the worker will deposit a corpse,

Â a load of work of course, in a large cluster of dead bodies.

Â 2:52

That seem intuitive but

Â the question is how does the ant evaluate the cluster size?

Â Because the ant has really limited perception and

Â these piles can be quite big.

Â So in the Deneubourg approach,

Â we will give every ant memory, M, called M of size n.

Â And the memory represents if the ant have seen corpse in the last n iteration.

Â So if Mi is one.

Â It means that a time, t-i, where t is the current simulation time.

Â They were the ants have seen a corpse and zero otherwise.

Â You can see as a circular buffer,

Â where every iteration ants adds value,

Â depending of the what shift seen.

Â And using this buffer, we can compute this probability quite easily.

Â So first we sum the buffer, so

Â f is a kind of average of, if they were that ants or

Â not is the density of that ants seen at random in last iterations.

Â And with this f we can then compute these two probabilities,

Â Pp and Pd, where k1 and k2 are model parameters.

Â And results are quite interesting.

Â Here you can see the initial condition.

Â Every small green dot is a single dead ant.

Â And if you wait, and wait more, you will see some cluster appearing.

Â And if you wait quite a long time,

Â you would see a single cluster at one direction.

Â 4:50

So it seems to work, it works quite well.

Â Basic mechanism is intuitive, but it requires lots of

Â intelligence from ants, and we cross them to remember the last ant

Â step [INAUDIBLE] and to compute some probabilities and to draw some number.

Â 5:14

And simpler approach was proposed by in 2000.

Â And is really simple model.

Â So the idea stiller regular grid, but

Â here the ants have ate the possible direction that improves the diffusion,

Â so the stiller random walk so stiller diffusion process, but

Â since we have a direction the diffusion coefficient is larger.

Â And the thing is still asynchronous.

Â But the model is really really simple.

Â So first of all in that model,

Â in that approach the ants have to avoid all obstacles.

Â 5:56

They avoid the ant corpse, other working ants, and boundaries and walls.

Â And an unloaded ant will work at random, and

Â as soon as it found the corpse he will load the corpse

Â 6:15

And when unloaded ant finds another corpse,

Â he will always drop the current corpse.

Â It means that model is quite deterministic except for their movements.

Â And so if an ant has only

Â one thing to remember, is it loaded or not?

Â Is it carrying a body.

Â A dead ant, or not.

Â That's the only state.

Â It's a Boolean.

Â And all the rest of the behavior is really simple.

Â 6:47

So, if we try the same experiment, at first we have ants.

Â And if we wait, we see small cluster appearing and

Â more cluster and more cluster.

Â What is interesting here is that since the ants cannot walk on dead,

Â all of that answers quite astringent of stacking condition closer almost boss.

Â But, we clearly had one final cluster.

Â So the Simpro model works also, but

Â it's interesting to understand why because it's completely at random.

Â The ant you've deformed a corpse that pick it,

Â whether it's already in the cluster or not.

Â And the idea why it works is because there are two phenomena,

Â first of all, if a cluster is completely emptied it will never reappear.

Â Because an ant can drop a body only close to another one.

Â So if a cluster disappear for

Â any reason it will never reappear at this position.

Â The other thing to understand is that the ant have the same probability

Â to remove a corpse for my cluster, or to add a new corpse to my cluster.

Â But they will only interact with the interface of the cluster because they,

Â in that model they cannot work where they want.

Â 8:23

of disappearing, but a small cluster has more chance of disappearing.

Â And because all the ants, they move at random, there are lots of fluctuation and

Â so every cluster may eventually reach zero size.

Â 8:37

And the small cluster will reach as your size and average before, it means that,

Â at the end, only one cluster will appear.

Â There are some quantitative result too, we can compare both models.

Â 8:53

Here is the number of cluster,

Â the logarithmical number of cluster in function of the logarithmic time.

Â So the x axis, the logarithmic time.

Â The y axis is the logarithmic number of cluster has a function of time.

Â And every different color represent a configuration with several ends.

Â So 8 ends, 32 ends, 122 ends, and 512 ends.

Â And you can see the more ends, the faster it gets.

Â There's a first phase and then it drops soon.

Â You can see that's both model managed to arrive to a single cluster.

Â Here the log of 1 being 0.

Â But of course, the more end you have, the faster it is.

Â 9:44

The Deneubourg model with just one billion of memory, it

Â takes more time because it's more random even if the rules is more deterministic.

Â And what is interesting here is that we don't really have a cooperation effect,

Â the collecting effect because in fact if you double the number of ant,

Â you will roughly it's the same thing as

Â doubling the number of time, or doubling the number of ants is the same thing.

Â So there's no real cooperation between the ants here.

Â A single ant can do it.

Â 10:24

In a time but it's interesting to see that in both model it will work.

Â And we don't need a lot to explain that.

Â If we look at the final cluster of course, here it's the Deneubourg model but

Â with the direction to speed it.

Â And so the final cluster in the model in

Â 10:46

is clearly more sparse, because the ants, they won't cross across an existing body.

Â But at the end, it will be a single cluster.

Â What is more interesting now is if we had an obstacle.

Â So here is a kind of U shape, which is a real obstacle that the ant cannot cross.

Â And that's with the initial model, so we can see it's already in a later stage,

Â because we can see so much more cluster but if you wait,

Â you will see that cluster will be more often around the object.

Â And if you wait a little bit more, the cluster will be inside the obstacle.

Â And again, it's because it's an idea of the ratio between surface and volume.

Â Here, is that the surface is really small because here it's

Â protected by the obstacle.

Â So the surface of contact, where ants can destroy the cluster, and

Â brink is really small.

Â So, naturally, it will emerge, the fact

Â that if you have an obstacle it

Â will kind of break the symmetry of all possibilities and

Â you will always see the cluster inside the obstacle.

Â So this obstacle can be any room in an ant hill, for example.

Â 12:06

So in conclusion, we can explain

Â this corps pile construction just by statistical fluctuation, but

Â of course, if we add some intelligence it can speed the process.

Â And this model show that it's not really a collective effect,

Â it's just a collaboration with a linear speedup.

Â It means that, yeah, the two ants make the work

Â of two ants, not more, which is already great.

Â 12:36

Another thing that we can ask ourselves is,

Â are the ants marching off to compute probabilities, to draw random numbers,

Â and to remember the concentration of corps that the ants are sim.

Â And the question to answer is, yes, of course.

Â Because, first of all, even computing probability can seem difficult.

Â 12:59

The ant doesn't need to know arithmetic to do it.

Â Remember that the shells of not to use our other symbols,

Â sea snail for example, have a perfect logarithmic spiral in them.

Â We can dealt to that this kind of animal can do some logarithmic computation.

Â So the ant could intuitively compute these probabilities without noticing it.

Â The fluctuation, the randomness, the random is

Â an element of most molecular biology system when they

Â are not stable and they can change between two states.

Â And the communication of neurotransmitter can explain

Â the kind of memory of the ants.

Â So both model could be real.

Â To distinguish between the two only by logical experiment can impose.

Â But what is interesting is that we can show here that I think that global

Â knowledge is not needed, having a lot of intelligence is not needed.

Â 14:05

This body will appear quite naturally.

Â To conclude this small model, just an example.

Â So that's an example that I found in the net logo software.

Â It's software that I would recommend to you.

Â That allows you to play with the Edgemont model with a really simple language.

Â I will put in the reference the links.

Â 14:31

And that's a good example and this one is an example of Moving woodchips is quite

Â similar to the example of ants and symmetry.

Â To the simplest model that I'll show you.

Â The difference here is that's the termites, they can work on woodchips but

Â not on other termites.

Â And the white points are the termites, and the yellow points are woodchips.

Â And if I let the model go, you will see that, so the orange are loaded ants.

Â It's a bit fast, and I can just first slow it a bit to see the movement.

Â You can see that one termite moves every iteration.

Â So it's clearly a asynchronous update.

Â I will put it at normal speed again, it's really fast.

Â You already can see some cluster appearing.

Â And I try to speed it a bit.

Â 15:41

So, you can open this model if you don't look at logo,

Â along with lots of other interesting agent based models that

Â you can play with parameters, and so it's nice experimentation to do.

Â That's the end of this module, and the last one I will introduce you

Â to the example of chemotaxy in bacterias, again in the agent base molding.

Â [MUSIC]

Â