Stanford Biologist and Computer Scientist Discover the 'Anternet'(engineering.stanford.edu)
engineering.stanford.edu
Stanford Biologist and Computer Scientist Discover the 'Anternet'
http://engineering.stanford.edu/news/stanford-biologist-computer-scientist-discover-anternet
13 comments
He complements afterwards:
Prabhakar said that had this discovery been made in the 1970s, before TCP was written, harvester ants very well could have influenced the design of the Internet.
Prabhakar said that had this discovery been made in the 1970s, before TCP was written, harvester ants very well could have influenced the design of the Internet.
I'm not convinced ants actually know anything. Just like we don't know how our brains work despite living inside them, ants don't know why they do things.
was about to comment on that, too
It has been known for a while that ants have algorithms - although the similarity to TCP is a new interpretation. From an article in Edge [1]:
Ants have algorithms. If you think about an ant colony, it's a computing device; there's some wonderful work by Jean-Louis Deneubourg in Brussels and his collaborators that really started this field in a way with Ilya Prigogine and later on Jean Louis Deneubourg looking at the ways in which social insect colonies can interact. One example would be—it sounds trivial, but if you think about it, it is quite difficult—how can a colony decide between two food sources, one of which is slightly closer than the other? Do they have to measure this? Do they have to perform these computations? [1] : http://edge.org/3rd_culture/couzin08/couzin08_index.html
Ants have algorithms. If you think about an ant colony, it's a computing device; there's some wonderful work by Jean-Louis Deneubourg in Brussels and his collaborators that really started this field in a way with Ilya Prigogine and later on Jean Louis Deneubourg looking at the ways in which social insect colonies can interact. One example would be—it sounds trivial, but if you think about it, it is quite difficult—how can a colony decide between two food sources, one of which is slightly closer than the other? Do they have to measure this? Do they have to perform these computations? [1] : http://edge.org/3rd_culture/couzin08/couzin08_index.html
OT: that headline is a really interesting sentence. There are two people, the biologist and the computer scientist, and the word discover is singular. Note that if it were one person who was both a biologist and computer scientist, we'd say "biologist and computer scientist discovers", with the plural form of discover.
I'm a native English speaker, and have no trouble understand the sentence. However, I kind of slacked off in elementary school and high school English classes so I can't actually explain WHY we use the singular 'discover' when the discovery is made by two people, and we use the plural 'discovers' when the discovery is made by one person.
I really should learn my native language sometime!
I'm a native English speaker, and have no trouble understand the sentence. However, I kind of slacked off in elementary school and high school English classes so I can't actually explain WHY we use the singular 'discover' when the discovery is made by two people, and we use the plural 'discovers' when the discovery is made by one person.
I really should learn my native language sometime!
The 's' on the end of verbs has no relation to the plural 's'. It's simply how regular English verbs are inflected in the third-person singular.
The link provided by jacobolus should tell you all you need to know.
The link provided by jacobolus should tell you all you need to know.
Ant behavior has also served as the model for solving traditionally "hard" optimization problems....
http://en.wikipedia.org/wiki/Ant_colony_optimization_algorit...
http://en.wikipedia.org/wiki/Ant_colony_optimization_algorit...
A great book on all of this stuff, if anyone is interested:
http://www.amazon.co.uk/Self-Organization-Biological-Systems...
each ant is a router?
Dr. Anteater and Aunt Hillary [0] probably knew this all along.
[0]: http://themindi.blogspot.co.uk/2007/02/chapter-11-prelude-an...
[0]: http://themindi.blogspot.co.uk/2007/02/chapter-11-prelude-an...
Fun result. It reminds me of the stories Dr. Feynman would tell about what he learned by watching ants.
Could you please elaborate? Were you referring to the stories told in his book, or were you actually one of Feynman's students?
Here's the written story of Feynman's experimentation with ants if anyone is interested: http://books.google.com/books?id=7papZR4oVssC&pg=PA94...
Here's the written story of Feynman's experimentation with ants if anyone is interested: http://books.google.com/books?id=7papZR4oVssC&pg=PA94...
Those are the ones. He came to USC and as a guest lecturer for my quantum mechanics class and recounted this story. I really like it because it crystallized in me the understanding that this is how you figure out systems for which there is no manual or documentation. Observe the working system, inject change in various ways, measure the effects of that change. Rinse and repeat and learn.
Once at NetApp there was a question about whether or not we were wasting all of our time randomly seeking the drives (drive seeks being of course the worst if you're looking to improve performance). But the code paths were very complex, asynchronous, and difficult to model. We figured it out by injecting random seeks which was pretty easy to do. You could flood the disk driver with random seeks and get the 'floor' of performance, then you could back off on the random seek injection to see where performance started to pick up. That told us that counter to our thinking we weren't actually being plagued by seeks, the performance issue was elsewhere in the system.
That the ants had, through natural selection, derived a congestion control system that is very close to the TCP one is a fun result because it suggests that the TCP one is probably close to optimal. (Ants have been working on it a lot longer)
Once at NetApp there was a question about whether or not we were wasting all of our time randomly seeking the drives (drive seeks being of course the worst if you're looking to improve performance). But the code paths were very complex, asynchronous, and difficult to model. We figured it out by injecting random seeks which was pretty easy to do. You could flood the disk driver with random seeks and get the 'floor' of performance, then you could back off on the random seek injection to see where performance started to pick up. That told us that counter to our thinking we weren't actually being plagued by seeks, the performance issue was elsewhere in the system.
That the ants had, through natural selection, derived a congestion control system that is very close to the TCP one is a fun result because it suggests that the TCP one is probably close to optimal. (Ants have been working on it a lot longer)
Does a long period of evolution actually imply it is "probably close to optimal"? I don't know a huge amount about evolution, but my two lines of logic would be:
First, given the huge diversity of life on Earth, how can we argue that any species is "optimal".
Secondly, the same argument could be made of life 500 million years ago, that it had been evolving for so long that it must be optimal, no?
First, given the huge diversity of life on Earth, how can we argue that any species is "optimal".
Secondly, the same argument could be made of life 500 million years ago, that it had been evolving for so long that it must be optimal, no?
It's actually a common misunderstanding of evolution to assume that it is optimising anything other than suitability to a particular environment (see http://en.wikipedia.org/wiki/Objections_to_evolution#Definin...). So no, it doesn't make sense to use evolution as evidence that suitability in one domain implies suitability in another domain, especially when the domains have almost nothing in common except a shared requirement for management of scarce resources in a very abstract sense.
I don't think you are seeing the parallels here. When you look closer you'll see that the domains are different but the problems are very similar and not so abstract, which explains the high degree of simularity and effectiveness of the congestion control algorithm.
I would also take issue with what you see as a common misunderstanding. Evolution is, by it's very definition a process which adapts to a specific environment. Nothing more, no design, but optimal for any given environmental condition. When the environment changes rapidly, the pace of evolution increases, and vice versa. I don't think this is commonly misunderstood at all. Some people will always have no clue and of course there are those that think the fossils were planted by god, but aside from the out of band idiots, evolution is commonly correctly understood.
I would also take issue with what you see as a common misunderstanding. Evolution is, by it's very definition a process which adapts to a specific environment. Nothing more, no design, but optimal for any given environmental condition. When the environment changes rapidly, the pace of evolution increases, and vice versa. I don't think this is commonly misunderstood at all. Some people will always have no clue and of course there are those that think the fossils were planted by god, but aside from the out of band idiots, evolution is commonly correctly understood.
I reason about it this way, I observe that natural systems seek the lowest possible energy state. Selection forces on systems like these select for the most gain with the smallest investment in energy, which is an analog for lowest possible energy state. The rationale for this force on selection is that an organism is more successful the more food it gets vs the energy it expends to get the food. So any small change that increases net food energy returned contributes to the success of the organism, and an organism that is fed, reproduces to the next generation.
Is it optimal for all possible cases? We can't say, just like a rock rolling into a gully has achieved the lowest potential energy it can when considered as a section of terrain it sits in, may not have the lowest energy possible when you consider the whole planet. So for the carpenter ants, which have a worst case generation length of roughly 15 years [1] over a million years you have at least 67 thousand generations in which to find the lowest energy solution. So for the food gathering problem I would expect its pretty close to optimal.
[1] http://www.orkin.com/ants/carpenter-ant/carpenter-ant-queens...
Is it optimal for all possible cases? We can't say, just like a rock rolling into a gully has achieved the lowest potential energy it can when considered as a section of terrain it sits in, may not have the lowest energy possible when you consider the whole planet. So for the carpenter ants, which have a worst case generation length of roughly 15 years [1] over a million years you have at least 67 thousand generations in which to find the lowest energy solution. So for the food gathering problem I would expect its pretty close to optimal.
[1] http://www.orkin.com/ants/carpenter-ant/carpenter-ant-queens...
For any living system that has had sufficient time to adapt to its environment, it can generally be assumed that the system has reached (or nearly reached) a local optimum for that environment, for the same reason that if you let a marble roll around on a surface for a long enough time, you can generally assume that it will come to rest at a local minimum. Of course, just as the local minimum of the marble is defined by the surface, the local optimum in the evolution of a trait is defined relative to the current environment. If the environment is rapidly changing, then you cannot assume near-optimality, just like you cannot assume the marble will come to rest on a constantly undulating surface.
> For any living system that has had sufficient time to adapt to its environment, it can generally be assumed that the system has reached a local optimum for that environment
Really? Think about humans, in our current environment, can you not think of any adaptations to our bodies that would improve us as a species? If in 100 million years our environment doesn't change at all (hypothetical) will we not evolve any more?
Really? Think about humans, in our current environment, can you not think of any adaptations to our bodies that would improve us as a species? If in 100 million years our environment doesn't change at all (hypothetical) will we not evolve any more?
Humans have not been in an unchanging environment for the past several thousands years at least, and by their nature (constant technological development, etc.) are unlikely to be so ever again.
Hence I said hypothetical, I wasn't predicting the future, just the fact that were we to be in an unchained environment the chances are we would evolve to become improved, rather than stay the same.
[deleted]
You might find this study fun too: Slime Mold Grows Network Just Like Tokyo Rail System
http://www.wired.com/wiredscience/2010/01/slime-mold-grows-n...
Original article: http://www.sciencemag.org/content/327/5964/439.abstract
http://www.wired.com/wiredscience/2010/01/slime-mold-grows-n...
Original article: http://www.sciencemag.org/content/327/5964/439.abstract
I wouldn't say 'just like'. There were some differences. The slime mold has to worry about its connections getting severed, so there were some extra edges which are redundant.
This is because the Tokyo Rail System engineers didn't have the same concerns, that tunnels would suddenly get cut off and blocked.
This is because the Tokyo Rail System engineers didn't have the same concerns, that tunnels would suddenly get cut off and blocked.
Very cool. Does anybody here know how the forager traffic is actually regulated? Is it centrally managed by the queen, or is there some sort of chemical signal that individual ants can produce to spread the word?
AFAIK, it's completely decentralized. When a scout ant finds food, it returns back to the nest leaving a strong trail of pheromone. Ants tend to follow a pheromone trail and reinforce it on their return if they find food, so when a good source of food is found, a strong pathway is quickly established by a growing number of ants following the same route.
An ant may randomly leave a pheromone trail, which ensures that other, perhaps more attractive food sources are not missed. In general, the stronger the signal, the faster ants move with the less probability of diverging from the path.
This strategy ensures optimal area exploitation under varying conditions. For instance, if the food is concentrated in one or a few locations, you'll see a single column between the nest and the source, but when the food is scattered through the area, the ants would disperse too.
Source: an excellent book "Cells, Embryos and Evolution" where it was used as an example of how complex and seemingly organized and directed behavior could be achieved by a population of identical individuals acting under uniform rules.
An ant may randomly leave a pheromone trail, which ensures that other, perhaps more attractive food sources are not missed. In general, the stronger the signal, the faster ants move with the less probability of diverging from the path.
This strategy ensures optimal area exploitation under varying conditions. For instance, if the food is concentrated in one or a few locations, you'll see a single column between the nest and the source, but when the food is scattered through the area, the ants would disperse too.
Source: an excellent book "Cells, Embryos and Evolution" where it was used as an example of how complex and seemingly organized and directed behavior could be achieved by a population of identical individuals acting under uniform rules.
Interesting, but as I understand the article, ants also use a TCP like protocol to make sure that make sure they don't send to many ants to a given food source. It sounds like the system you are describing would strengthen the trail until the food ran dry, regardless of if there are already more ants at the food than can take a piece at a given time.
Also, I remember learning about the pheromone trail years ago as established fact, so I'm pretty sure they are talking about a different system. It would be interesting to look at how the two interact (along with the other systems they use we have yet to discover).
Also, I remember learning about the pheromone trail years ago as established fact, so I'm pretty sure they are talking about a different system. It would be interesting to look at how the two interact (along with the other systems they use we have yet to discover).
You are right, now that I read the original article, it appears the particular ant genus they were studying does not use pheromone trails. Since this ant species gather seeds which are scattered by wind and could be brought back by a single ant, they don't need to build paths to the food source. Instead a returning ant interacts with other ants which are ready to leave and the rate at which ants leave the nest grows with the rate at which ants return back (so a leaving ant is a data packet, a returning ant is an ACK packet).
The paper: http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...
The paper: http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...
From my knowledge, ants operate with no leadership, completely self-organizing. The term "queen" is inaccurate. The queen really just lays eggs; she does not act as a leader. The true brilliance of ants comes from the fact that they can literally think as a group, kind of like neurons. Each one on its own is essentially worthless, but in a communicating, non-hierarchical group, the whole becomes much more than the sum of the parts.
I do know that most communication is done via chemical exchange between individuals, but as far the "algorithms" the ants use, I don't know much about them. I'm sure it has been fine-tuned over millions of years though ;).
I do know that most communication is done via chemical exchange between individuals, but as far the "algorithms" the ants use, I don't know much about them. I'm sure it has been fine-tuned over millions of years though ;).
My guess is chemical signal. This is based on my knowledge of there tracking system. When a forager finds food, it leaves a chemical trail on its way back to the nest. Future ants follow that trail to the food source. If they find food, they also leave a trail on there way back, otherwise they don't and the old trail fades away.
Also, given there small size, I can't imagine how they could have an effective central command structure, especially when there are simple protocols that allow each ant to act autonomously while still being highly effective for the hive.
Also, given there small size, I can't imagine how they could have an effective central command structure, especially when there are simple protocols that allow each ant to act autonomously while still being highly effective for the hive.
I think the real amazing thing is that the protocols for the internet took brilliant people years to figure out. Ants do it as one self-organizing body, anarchically.
I've always been fascinated by the collective intelligence of an ant colony. This drives it home even more.
I've always been fascinated by the collective intelligence of an ant colony. This drives it home even more.
Ants had millions of years to evolve the algorithms. And I don't think it qualifies as a collective intelligence, I prefer to view "hive mind" systems as multiple instances of the same object, so the beauty of the ant isn't that it has a massive collective intelligence, or self organizes, but rather that it has a protocol small enough to fit into their tiny brain, but elegant enough to make ants one of the largest bio-mass of all species.
It is a very similar situation to the inside of any organism. You have a bunch of cells, none of which has significant intelligence, but which follow a set of protocols that allows them to work together and form an organism capable of duplication. Or you can look at how a single cell is composed of molecules that follow a set of even simpler protocols that still causes self duplication. Or you can look at how a bunch of atoms came together in such a way that allowed self duplication, and error propagation, until the 'arms race' between these molecules led to the creation of a group of entities who cannot even comprehend how such a system can occur without thinking of the single molecules as being alive.
Personally, I appreciate the mathematical elegance that flowers use to optimize their leaf coverage. (They start with an even arrangement of growth hormone, and then the region that is over crowded has less hormone then the region that is under-crowded, so new leaves grow where they are most needed, resulting in Fibonacci spirals).
Sorry if this post came across as condescending, but I feel that blind awe at the intelligence of nature tends to diminish the mathematical elegance it exploits; I much prefer to view ants as an example of an extremely simple and elegant algorithm that can make use of many stupid entities, as apposed to a massive hive-mind, with access to the brain power of thousands of ants, that still can't do better then the simple algorithm.
It is a very similar situation to the inside of any organism. You have a bunch of cells, none of which has significant intelligence, but which follow a set of protocols that allows them to work together and form an organism capable of duplication. Or you can look at how a single cell is composed of molecules that follow a set of even simpler protocols that still causes self duplication. Or you can look at how a bunch of atoms came together in such a way that allowed self duplication, and error propagation, until the 'arms race' between these molecules led to the creation of a group of entities who cannot even comprehend how such a system can occur without thinking of the single molecules as being alive.
Personally, I appreciate the mathematical elegance that flowers use to optimize their leaf coverage. (They start with an even arrangement of growth hormone, and then the region that is over crowded has less hormone then the region that is under-crowded, so new leaves grow where they are most needed, resulting in Fibonacci spirals).
Sorry if this post came across as condescending, but I feel that blind awe at the intelligence of nature tends to diminish the mathematical elegance it exploits; I much prefer to view ants as an example of an extremely simple and elegant algorithm that can make use of many stupid entities, as apposed to a massive hive-mind, with access to the brain power of thousands of ants, that still can't do better then the simple algorithm.
Condescending or not, I don't agree. Your view is very reductionist. From what I gather, you are saying that ants can be described by the mathematical formulas of their behavior. This is true for just about any phenomena. It can be described and calculated. The fact that creatures as simple as ants, completely helpless on their own, can do such incredible things when in groups is most certainly worthy of awe. How many people, with all of our intelligence, could program homogeneous robots that are able to burrow into the ground and meet two tunnels underground from either end by only exchanging rudimentary signals with each other? Not may, if any people could do this.
My point is that there is more here than simple math, and it does deserve awe. There is collective intelligence. Ants in a group have an understanding of their surroundings in ways that we cannot comprehend. I tend to view them as neurons of a larger brain. Each neuron receives inputs, processes, and gives an output based on a very simple formula. Put a few hundred million of them together, and you get something that math cannot describe: consciousness. Ants individually are very simple creatures, but en masse are greater than the sum of the parts.
I don't think they are the end all be all of evolution nor do I think their methods particularly apply to us, but I think they are worthy of admiration.
My point is that there is more here than simple math, and it does deserve awe. There is collective intelligence. Ants in a group have an understanding of their surroundings in ways that we cannot comprehend. I tend to view them as neurons of a larger brain. Each neuron receives inputs, processes, and gives an output based on a very simple formula. Put a few hundred million of them together, and you get something that math cannot describe: consciousness. Ants individually are very simple creatures, but en masse are greater than the sum of the parts.
I don't think they are the end all be all of evolution nor do I think their methods particularly apply to us, but I think they are worthy of admiration.
> How many people, with all of our intelligence, could program homogeneous robots that are able to burrow into the ground and meet two tunnels underground from either end by only exchanging rudimentary signals with each other?
Well, this is not far off: http://en.wikipedia.org/wiki/Channel_Tunnel#Tunnelling
Well, this is not far off: http://en.wikipedia.org/wiki/Channel_Tunnel#Tunnelling
You're describing emergence
http://en.wikipedia.org/wiki/Emergence
http://en.wikipedia.org/wiki/Emergence
[deleted]
That's like saying things fall because if gravity, all you've done is given something a label, it doesn't help anything.
Read Richard Feynman for more details, he explains it well.
Read Richard Feynman for more details, he explains it well.
If I had been talking about how objects of mass attracted each other (or some similar system), him saying 'gravity' would also serve to provide me with textbooks of information and research that might be relevant to what I was talking about. As it so happens, I was aware of the term 'emergence', but if I was not, then his mentioning it makes it far easier for me to do further research on that thing I described in my first post.
I simply offered a lexical correlation; from your response one might think I murdered your children.
Cool photo by Steve Jurvetson of DFJ.
Looks like it was a photo of one of these tanks: http://www.amazon.com/Fascinations-ANTW2-AntWorks-Illuminate...
The original paper, which is quite informative and easy to read: http://www.ploscompbiol.org/article/info%3Adoi%2F10.1371%2Fj...
Isn't it more like we discovered an algorithm that they know well, considering that they came up with it first?