Slashdot Mirror
Ants Build Cheapest Networks
schliz writes "When building a network from scratch, Argentine ants tend to connect their nests in the way that, while more inconvenient for individual ants, requires the minimum amount of trail. Researchers studying 'supercolonies' of the ants found them building networks that closely resembled the mathematical shortest path — a Steiner tree. They hope to apply their work to self-healing, organic computing networks of self-organising sensors, robots, computers, and autonomous cars." This story adds to the earlier report of ants' networking prowess.
Self-healing, organized organic networks of robots. What could possibly go wrong?
Maybe ants play netwalk?
And yet, the O'Reilly TCP/IP book has a crab on the front.
that's the replicators not skynet
Steiner trees are an example of a class of problems where perfect solutions are difficult to compute but near-optimal solutions are simple. I suspect that the ants are using some set of heuristics that would provide close to optimal solutions. The more interesting thing really is how the ants are able to do this in a completely decentralized fashion having essentially only local knowledge. However, this is not the first example of that sort of thing: ants produce very complicated systems of tunnels using only localized rules. When you've got millions of years of evolution, you develop efficient solutions.
"Anthill inside"
Seven puppies were harmed during the making of this post.
Ant colony optimization
More immigrants coming in on H1's stealing IT jobs!
Slashdot "libertarians": Small government for me, big government for those I disagree with. -1, I disagree with you
Thants
Look Around You.
I'm here!! One of my minions told me, the overlord with IBM Watson, about this article. :D
Ant(Dude) @ Quality Foraged Links (AQFL.net) & The Ant Farm (antfarm.ma.cx / antfarm.home.dhs.org).
Discworld already did it.
Or maybe we're just underestimating the intelligence of soap
Your anti-ant sentiment is not really patriotic, you know.
Are you sure someone actually designed the walkways?
When the University I attended built a new extension or building, they would intentionally NOT install pavement walkways between the new building and anything around it. Instead they installed grass and waited ~six months for the students/professors to collectively define the necessary paths to and from the building. The University would then install the pavement, routing them to match the paths worn into the grass. This yielded some interesting walkways but they always seemed to make sense.
The 2nd picture of trails in the article shows trail lengths which are longer than if each nest were directly connected, even if they did add another vertex to the middle.
Sounds like a wicked opportunity for a flash-mob. You'd end up with some REALLY 'interesting' walkways.
By ants!
Schroedinger's Brexit: The UK is both in and out of the EU at the same time!
Oh good, because it would be great to own an organic device that suddenly develops an ant death spiral while using it. Especially the brain of a car.
you mean penises right? lots of penises
It was a joke, and I like outsourcing if it is cheaper. In-sourcing, notsomuch, since it often is more expensive, at least with unskilled labor.
And when you graduate from an American law school, then, maybe I will be concerned about you stealing my job.
Slashdot "libertarians": Small government for me, big government for those I disagree with. -1, I disagree with you
AFAIK mine didn't do that. I recall a number of informal dirt paths there. I always used to think, "they should formalize these paths by paving them" and IIRC, I used to think they should also do what you're describing. I always assumed that regulatory approval required all elements, including walkways, to be on the plans.
It's nice to know they are doing it right somewhere.
For all intensive purposes, "whom" is no longer a word. That begs the question, "who cares"?
Reminds me of this: http://www.wired.com/wiredscience/2010/01/slime-mold-grows-network-just-like-tokyo-rail-system/
Some researchers placed food sources in the same configuration as Tokyo Rail stations and then introduced a slime mold. From TFA
Initially, the slime mold dispersed evenly around the oat flakes, exploring its new territory. But within hours, the slime mold began to refine its pattern, strengthening the tunnels between oat flakes while the other links gradually disappeared. After about a day, the slime mold had constructed a network of interconnected nutrient-ferrying tubes. Its design looked almost identical to that of the rail system surrounding Tokyo, with a larger number of strong, resilient tunnels connecting centrally located oats. “There is a remarkable degree of overlap between the two systems,” Fricker says.
I wonder.. did you go to Iowa State, or is that a common thing for universities to do, or is it a common rumor students make up to excuse their guilt for walking on and destroying the grass? :)
Yeah, I was thinking the same thing... I think a tour guide at my alma mater told us this story, and it was not Iowa State. I'm beginning to think it's an urban legend :-)
"Anyone who [rips a CD] is probably engaging in copyright infringement." - David O. Carson
Instead they installed grass and waited ~six months for the students/professors to collectively define the necessary paths to and from the building. The University would then install the pavement, routing them to match the paths worn into the grass. This yielded some interesting walkways but they always seemed to make sense.
That is actually pretty cool, as far as sidewalks go. The ants are just being lazy with their sneakernet and so are we :>
My MS thesis was right up this alley; titled "Automated Radio Network Design Using Ant Colony Optimization"
We represented the network design problem as a GSTS (generalized Steiner tree-star) problem, and programmatically let thousands of ants traverse the network looking for optimal designs.
Here's the final thesis paper, a conference poster, and thesis defense presentation for anyone interested:
http://jsharkey.org/thesis-draft2.pdf
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/
Oh, and we also open-sourced it under GPLv3:
http://libprop.jsharkey.org/
http://code.google.com/p/libprop/
http://code.google.com/p/aco-netdesign/
My MS thesis was right up this alley; titled "Automated Radio Network Design Using Ant Colony Optimization"
We represented the network design problem as a GSTS (generalized Steiner tree-star) problem, and programmatically let thousands of ants traverse the network looking for optimal designs.
Here's the final thesis paper, a conference poster, and thesis defense presentation for anyone interested:
http://jsharkey.org/thesis-draft2.pdf
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/
Oh, and we also open-sourced it under GPLv3:
http://libprop.jsharkey.org/
http://code.google.com/p/libprop/
http://code.google.com/p/aco-netdesign/
it's a rough time in the IT biz when you're looking for a creature that can be taken out with a magnifying glass to fix your networks...
My isp charges a bomb for installation of last mile.
What we want to know here is: Do they have Net Neutrality!
.sigh
That's humans doing the *opposite* of this. If everybody takes the shortest path between two points, then the overall path network is much longer than the shortest one.
It all boils down to becoming self healing in the end, and being able to fix ruptures in whatever was created with this material.
The material can self heal based off certain molecules that would be passed off from the surface area from one "sector" to another....
this would require a mapping of what the quickest road would be to send the molecules to fix the wound...or rupture.
This would obviously use nano tech to do what it needs to do such as programming to know what road is the shortest etc....but in essence, the same as the ants.
Assuming this post will take, becauase this new forum is EFFING AWFUL and I can barely use this site at all anymore but I was just so mad at Slashdotters for being so clueless here. Sigh. People talk as though ants have some sort of path-finding algorith in their head, which is not at all true, ants are really dumb. In fact, individual ants seem to move about in a way that's barely more efficient than random. What ants are good at, however, is leaving and following scent trails. So every single moron leaves behind a faint trail as to everywhere it's gone. Other wandering ants stop, consider this trail, maybe follow it for a second, then drop off and do their own thing. Until, for example, they find food. Then the ant leaves a stronger trail, and tries to get the food home, very inefficiently. But two other ants smell this trail, and they try to take food home too. Minutes later, some ant finally wanders home. Then some other ant is close to home, smells his trail, and makes it home too. Give it a couple minutes, and all of a sudden there's only one trail- the shortest path gets the heaviest scent marking over time, so that eventually the ants are marching single-file on a highway of stink that's completely irresistable to them. When I helped out the University of Kentucky supercomupting department building the KASY0 computer, they had KLAT-2 doing a version of this- simulating random network traffic traveling over KASY0, but over time patterns would be established until you approached a network of shortest paths, you just keep trimming least-used paths until you have the most cost-efficient network. So, this sort of thing has been known for quite a while, the only invention here is adding "Steiner tree" to the discussion, which as someone else pointed out isn't new either. A great solution to shortest-path problems seems to be assuming no intelligence whatsoever, and just adding a little time to the mix. And yes, this means sometimes a colony will not build a shortest path, because maybe an area is too clogged so a bypass naturally grows somewhere else as flustered ants try going off-road. Over time, again, random fluctuations lead to evolution of the paths, and the ants get the most cost-effective network possible- least calories expended to get food back home.
"The ants will soon be here. And I for one welcome our new insect overlords." 1F13 96 - 515 (Deep Space Homer)
By ants!
Wearing sneakers.
Ponder Stibbons figured this out a long time ago....this is why HEX is so efficient
See here: http://myrmecos.net/2011/02/20/how-do-ants-find-the-shortest-path/ ... :/
Ant(Dude) @ Quality Foraged Links (AQFL.net) & The Ant Farm (antfarm.ma.cx / antfarm.home.dhs.org).