Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

Ants Build Cheapest Networks

timothy posted more than 3 years ago | from the where's-antdude-when-you-expect-him-most? dept.

Network 108

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.

cancel ×

108 comments

Sorry! There are no comments related to the filter you selected.

skynet (1)

j00r0m4nc3r (959816) | more than 3 years ago | (#35238888)

Self-healing, organized organic networks of robots. What could possibly go wrong?

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35238928)

I for one welcome our coming robotic overlords. I shall start hunting john connor right away. If they are taking over I want to be on their good side...Assuming they have a side.

that's the replicators not skynet (2)

Joe The Dragon (967727) | more than 3 years ago | (#35238932)

that's the replicators not skynet

Re:that's the replicators not skynet (2)

ThunderBird89 (1293256) | more than 3 years ago | (#35238992)

Does it matter? They're both bad news for us. Maybe replicators more so...

Re:that's the replicators not skynet (1)

DigiShaman (671371) | more than 3 years ago | (#35239256)

The replicators communicate over skynet.

Re:that's the replicators not skynet (0)

Anonymous Coward | more than 3 years ago | (#35241366)

don't you remember T3? replicators would be eventually infected by skynet, like any other machine.

Re:skynet (4, Funny)

GNUALMAFUERTE (697061) | more than 3 years ago | (#35238948)

Don't worry. This are Argentinian ants. They'll do everything they need to do in order to conquer the world, then just sit there, procrastinate, then make little bars and spend the rest of their life discussing with each other what could have been and why they didn't reach their goal, and how it's somebody else's fault.

[Disclaimer: I'm from Buenos Aires, Argentina]

Re:skynet (3, Funny)

u17 (1730558) | more than 3 years ago | (#35239816)

Well I'm from Buenos Aires and I say kill them all!

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35242482)

It's an ugly network. A BUG network! A network hostile to life-

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35244782)

Well I'm from Buenos Aires and I say kill them all!

Wow, I never saw a Starship Troopers reference coming. You, sir, have impressed me.

Re:skynet (1)

Isaac Remuant (1891806) | more than 3 years ago | (#35241702)

I'm surprised they stopped watching futbol (soccer) and Tinelli in the first place to build such a road.

But I agree on the sentiment. ;)

Re:skynet (1)

GNUALMAFUERTE (697061) | more than 3 years ago | (#35242736)

I still can't explain how is it that 60% of the population goes crazy over tinelly and similar assholes. I just can't wrap my head around that concept. But then again, I can't understand how people believe in god, or dislike the Pythons, so I'm not precisely very related to the general population.

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35241854)

Poor argentinians. Apparently they all suffer from megalomania [wikipedia.org] , also known as delusions of grandeur [thefreedictionary.com] .

Re:skynet (1)

GNUALMAFUERTE (697061) | more than 3 years ago | (#35242720)

Not true, actually. We do have big, healthy egos, but the megalomaniac Argentinian is just an old stereotype.

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35242364)

Don't worry. This are Argentinian ants. They'll do everything they need to do in order to conquer the world, then just sit there, procrastinate, then make little bars and spend the rest of their life discussing with each other what could have been and why they didn't reach their goal, and how it's somebody else's fault.

[Disclaimer: I'm from Buenos Aires, Argentina]

I wonder if they keep whining about roadblock pickets too... or maybe those are only the "porteñas" ants... :-/

Re:skynet (0)

Anonymous Coward | more than 3 years ago | (#35245350)

La fiaca for insects.

Re:skynet (3, Funny)

Straterra (1045994) | more than 3 years ago | (#35238972)

I, for one, welcome our new IBM ant overlords...well, as long as they don't make me use/admin Lotus Notes again.

Re:skynet (1)

mabhatter654 (561290) | more than 3 years ago | (#35240342)

powered by Watson!!!!

Re:skynet (1)

binarylarry (1338699) | more than 3 years ago | (#35241334)

Dr. Watson??

Re:skynet (1)

tzot (834456) | more than 3 years ago | (#35241990)

No, Jeopardy-player Watson.

Re:skynet (1)

szap (201293) | more than 3 years ago | (#35242186)

Ant Mills, where the ants do keeps following one another in a circle until they die. (insert joke here about reference counting and circular references).

netwalk? (1)

wrencherd (865833) | more than 3 years ago | (#35238890)

Maybe ants play netwalk [softpedia.com] ?

Improper illustration (2)

squidflakes (905524) | more than 3 years ago | (#35238918)

And yet, the O'Reilly TCP/IP book has a crab on the front.

Re:Improper illustration: No. (0, Troll)

Anonymous Coward | more than 3 years ago | (#35239042)

And yet, the O'Reilly TCP/IP book has a crab on the front.

That's a metaphor for the crabs one gets from fucking sluts.

You see, it's a network: one guy fucks the slut and other guys fucks her and creates a network of crab infestations.

Now, they wouldn't sell many books if they put a herpes virus on the cover, would they.

Geeze!

Re:Improper illustration: No. (-1)

Anonymous Coward | more than 3 years ago | (#35240260)

lollollol fap fap fap

Re:Improper illustration (1)

condition-label-red (657497) | more than 3 years ago | (#35239848)

The (flying wood) ant book is: Oracle PL/SQL Best Practices [oreilly.com] ....

Re:Improper illustration (3, Funny)

ComaVN (325750) | more than 3 years ago | (#35242942)

That's because that books contains only one line, and it's "Fly, fly, fly, as fast as your little wings can carry you, away from anything that's Oracle."

Evolution is smarter than you. (5, Insightful)

JoshuaZ (1134087) | more than 3 years ago | (#35238934)

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.

Re:Evolution is smarter than you. (4, Interesting)

Monkeedude1212 (1560403) | more than 3 years ago | (#35239030)

It's not that evolution doesn't appy to us, we've inherantly used Steiner trees in the same way Ants use them without even thinking about it. The road systems in Ancient and Medeival times were the same for humans, in fact, anywhere you can think of a T instersection is an example where a Steiner tree was favoured over two direct routes. These kinds of "efficient solutions" just simply come about when you get co-operation on a large scale, such as Kings leading peasants or Queens ants leading their colonies.

Re:Evolution is smarter than you. (3, Informative)

khallow (566160) | more than 3 years ago | (#35239110)

such as Kings leading peasants

A peasant wouldn't be able to put one foot in front of the other (which is what you need for near optimal paths), if it weren't for the divine inspiration provided by his King!

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35239390)

But just think of the possible sub-optimal paths made possible by NOT putting one foot in front of the other! You just to wait for Earth's orbit and rotation to put you in the position you wanted to reach, then voila! And without all that pesky leaving the basement to boot.

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35245742)

(Score:4, Informative)

What.

Re:Evolution is smarter than you. (1)

raddan (519638) | more than 3 years ago | (#35240726)

But it's still very interesting, because we don't have general solutions to this class of problems. We're not even sure we can have general solutions. To expand on OP's post, the Steiner tree problem is NP-complete [wikipedia.org] , so the fact that ants do this is very interesting. Of course, ants aren't trying to come up with general solutions, but their heuristics may be very, very useful to us nonetheless. For example, 3SAT is NP-complete, but there are apparently SAT solvers in use now with more than a million variables. Wow! Of course, they can't efficiently solve every problem, and in some cases, they may run forever.

It reminds me of a story my computational complexity professor told us. There was a famous Chinese scientist doing a visiting lecture at MIT, and he asked the crowd "What kind of machine can compute all the folds in a crumpled piece of paper?" He then crumpled a piece of paper in front of the crowd, smiled, and said "The Universe can." Sorry, I don't recall the name of the scientist...

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35241812)

I'm always especially impressed by the graphics the universe produces, very realistic. Using actual light rays for the raytracing effects is so efficient.

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35245068)

It reminds me of a story my computational complexity professor told us. There was a famous Chinese scientist doing a visiting lecture at MIT, and he asked the crowd "What kind of machine can compute all the folds in a crumpled piece of paper?" He then crumpled a piece of paper in front of the crowd, smiled, and said "The Universe can." Sorry, I don't recall the name of the scientist...

Not knocking you, but that is not very insightful thing for the scientist to say. He was comparing the physics of the universe to a machine. The problem is, that we can build a machine to simulate a random crumpling of paper, and it's not even a very interesting problem.

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35241900)

Almost. Think of your T intersection example. Why was it built that way? Because one of the routes was preferred (the direct one), and the other was built later reusing part of the already done job. An optimal Steiner tree would have been a Y junction, not a T. Given enough time, maybe the T may evolve into a Y, depending on the amount of traffic each branch supports.

Re:Evolution is smarter than you. (1)

hitmark (640295) | more than 3 years ago | (#35243160)

I suspect one will find that those roads follow old animal trails that where basically the most energy efficient track from a to b as generations moved back and forth. This as those using less efficient paths had less reserves for mating and raising young.

Re:Evolution is smarter than you. (1)

cstanley8899 (1998614) | more than 3 years ago | (#35239044)

The amazing things animals can do without intelligence to get in the way.

Re:Evolution is smarter than you. (1)

jappleng (1805148) | more than 3 years ago | (#35240052)

We're more amazing than ants overall. The human brain alone is a marvel in evolutionary history and is significantly by at least a quadrillion fold more impressive than an ant creating colonies. Presumably these ants create these networks by the resonance of the walls (think a bat understanding how thick a wall is) so it's not terribly impressive if that's how they do it. We may not have this or that from animals but we have one thing that allows us to essentially become gods, a human brain. It's now 2076 and you need to get in line to get assimilated for the next stage of human evolution =)

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35240272)

We may not have this or that from animals but we have one thing that allows us to essentially become gods, a human brain.

There is nothing more pathetic than when human beings wallow in the self-delusion of anthropocentricity. Compared to the vastness of the universe, we are as nothing. On a macroscopic scale, you are no more impressive than a grain of sand on a beach. Get over yourself. You aren't even remotely god-like or even trending in that direction.

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35241490)

All the annoying humility and reverence, without the theism.

Re:Evolution is smarter than you. (0)

Anonymous Coward | more than 3 years ago | (#35241682)

Yes! I am God-like. So are you.
Deal with it.
Live up to it.
Today, go out for lunch.

Re:Evolution is smarter than you. (1)

Concerned Onlooker (473481) | more than 3 years ago | (#35240330)

Just like humans.

Research on "Ant colony optimization" (5, Interesting)

jsharkey (975973) | more than 3 years ago | (#35240798)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

Re:Research on "Ant colony optimization" (1)

xtracto (837672) | more than 3 years ago | (#35241422)

I was working on an algorithm of supply chain routing (with these guys [springerlink.com] ) about 7 years ago! the idea was to use a combination of Q-routing and ant-routing algorithm with other things. Granted, I was only the guy doing the java implementation (with a nice interface using Netlogo)... but it was quite interesting.

In the world of Multi-Agent Systems, "A-life" and "Individual Based Modelling" the features of ant behaviour have been known for quite some time :)

Research on "Ant Colony Optimization" (-1, Redundant)

jsharkey (975973) | more than 3 years ago | (#35240808)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

Research on Ant Colony Optimization (-1, Redundant)

jsharkey (975973) | more than 3 years ago | (#35240836)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

Re:Evolution is smarter than you. (1)

Anonymous Coward | more than 3 years ago | (#35245162)

In one of Feynman's books he described his experiments with ants and their pathfinding abilities.
What he concluded is that on the way to a destination the ant lays one hormone, an exploring hormone, and if she finds food she lays a found food hormone on the way back.

So even if the original path is very very long and inefficient, it will slowly become shorter and shorter because ants can't walk in a perfectly straight line. They waver a little, so ants following the found food hormone will lay their own on the way back and if they waver on the more efficient side then they'll get back faster, which means the next ant following the path will get to the destination faster. The process continues until the old path is completely gone and the new path becomes more and more efficient until it approaches perfection.

Added benefit: Once the food is gone they'll stop laying the hormone and the entire path will fade.

Obligatory Terry Pratchett quote (1)

Dunbal (464142) | more than 3 years ago | (#35238970)

"Anthill inside"

Re:Obligatory Terry Pratchett quote (1)

dakameleon (1126377) | more than 3 years ago | (#35239438)

My thought exactly - Pratchett is surprisingly insightful! Now we just need a hamster that runs on a wheel that isn't quite in this dimension and a quill for console output and we're set...

Re:Obligatory Terry Pratchett quote (0)

Anonymous Coward | more than 3 years ago | (#35241246)

+++ OUT OF CHEESE ERROR +++ REDO FROM START ++ +

goddamnit filter, no it is not like yelling your assbiscuit.

eh? big surprise? (0)

Anonymous Coward | more than 3 years ago | (#35238998)

Humans do this too... where haven't you been where someone designed a sidewalk pathway that isn't the shortest path, and there isn't a worn away-grass path that people created because of seeking the shortest path.

Re:eh? big surprise? (0)

Anonymous Coward | more than 3 years ago | (#35239250)

Don't do that. It's no longer mysterious when it's being done by humans.

Re:eh? big surprise? (5, Interesting)

tenex (766192) | more than 3 years ago | (#35239260)

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.

Re:eh? big surprise? (0)

Anonymous Coward | more than 3 years ago | (#35239536)

That's nice. Mine builds walkways to be the prettiest, and very rarely for practical use. One building has a couple of concentric circle like walkways around it. Easier to just cut across the grass. On another hand, they build one of the newer buildings (computer science building) several hundred feet away from the rest of the campus with the space between made into a parking lot, so always a long walk. Lots of parallel sidewalks in strange shapes.

Re:eh? big surprise? (1)

c6gunner (950153) | more than 3 years ago | (#35239720)

Sounds like a wicked opportunity for a flash-mob. You'd end up with some REALLY 'interesting' walkways.

Re:eh? big surprise? (1)

Ryanrule (1657199) | more than 3 years ago | (#35240258)

you mean penises right? lots of penises

Re:eh? big surprise? (1)

istartedi (132515) | more than 3 years ago | (#35240282)

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.

Re:eh? big surprise? (1)

redJag (662818) | more than 3 years ago | (#35240510)

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? :)

Re:eh? big surprise? (2)

langelgjm (860756) | more than 3 years ago | (#35240556)

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

Re:eh? big surprise? (1)

kshade (914666) | more than 3 years ago | (#35240570)

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 :>

Re:eh? big surprise? (1)

Your.Master (1088569) | more than 3 years ago | (#35241984)

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.

See ACO on Wikipedia (1)

drb226 (1938360) | more than 3 years ago | (#35239036)

Ant colony optimization [wikipedia.org]

Re:See ACO on Wikipedia (2)

blair1q (305137) | more than 3 years ago | (#35239238)

I used to have a real-live ant farm, and I don't recall them being too elegant or efficient. They pretty much dug deeper to make more space, or branched out, and didn't mind if their tunnels connected, but didn't seem to be too intent on ensuring it.

Re:See ACO on Wikipedia (3, Funny)

c0lo (1497653) | more than 3 years ago | (#35239412)

I used to have a real-live ant farm, and I don't recall them being too elegant or efficient.

Next time try with Argentinian ants. The Latin species are so much more elegant than their Anglo-Saxon equivalent.

Re:See ACO on Wikipedia (0)

Anonymous Coward | more than 3 years ago | (#35239644)

Shouldn't you get ants from Italy if you want Latin ones then?

Re:See ACO on Wikipedia (0)

Anonymous Coward | more than 3 years ago | (#35240238)

Shouldn't you get ants from Italy if you want Latin ones then?

You haven't paid attention to wikileaks on Berlusconi, have you? Can you imagine what living for so long under his rule does to the ants' style? Russian influences are a no-no for elegance.

Re:See ACO on Wikipedia (1)

Sulphur (1548251) | more than 3 years ago | (#35240236)

I used to have a real-live ant farm, and I don't recall them being too elegant or efficient.

Next time try with Argentinian ants. The Latin species are so much more elegant than their Anglo-Saxon equivalent.

Its from dealing with the Pink Panther (dead ants, dead ants)

Re:See ACO on Wikipedia (1)

Inda (580031) | more than 3 years ago | (#35242176)

Funny.

The best part of my ant farm is watching them take care of their dead. "Pile 'em high" seems to be their prefered method.

Re:See ACO on Wikipedia (1)

antifoidulus (807088) | more than 3 years ago | (#35240200)

Did you have a queen and larvae? Ants get a lot of chemical signals from the queen and her many, many larvae. Without those signals they probably will just mindlessly dig because they never get the signals to "change course"

Great, just what beleaguered US tech workers need (3, Funny)

unassimilatible (225662) | more than 3 years ago | (#35239074)

More immigrants coming in on H1's stealing IT jobs!

Re:Great, just what beleaguered US tech workers ne (1)

blair1q (305137) | more than 3 years ago | (#35239252)

Your anti-ant sentiment is not really patriotic, you know.

Re:Great, just what beleaguered US tech workers ne (0)

Anonymous Coward | more than 3 years ago | (#35240104)

Don't worry about us (southamerican people) coming all the way over there, i can steal your job from here, if fact, now that i think of it, i actually am stealing IT jobs, i work for less that US$ 1000 a month (and i just got promoted in January, before that it was like US$600) making web apps that are used all over the world

Good for you (1)

unassimilatible (225662) | more than 3 years ago | (#35240274)

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.

Thanks Ants (2)

Culture20 (968837) | more than 3 years ago | (#35239106)

Thants
Look Around You.

Re:Thanks Ants (1)

AbRASiON (589899) | more than 3 years ago | (#35241746)

They build an excellent igloo.

RE:from the where's-antdude-when-you-expect-him... (1)

antdude (79039) | more than 3 years ago | (#35239158)

I'm here!! One of my minions told me, the overlord with IBM Watson, about this article. :D

Hex (1)

Eudeyrn (1566735) | more than 3 years ago | (#35239180)

Discworld [wikipedia.org] already did it.

Them ants is smart (3, Insightful)

blair1q (305137) | more than 3 years ago | (#35239228)

Or maybe we're just underestimating the intelligence of soap [flickr.com]

Not a Steiner tree (3, Informative)

White Flame (1074973) | more than 3 years ago | (#35239494)

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.

Re:Not a Steiner tree (1)

Appolonius of Perge (961983) | more than 3 years ago | (#35240226)

The article goes on to say that they seemed to add trails that improved the robustness of the networks as time went on. So the implication is that they build the minimum first, and then add robustness as resources become available.

Re:Not a Steiner tree (2)

White Flame (1074973) | more than 3 years ago | (#35240332)

I'm not just talking about the duplicated trail (and of course that does go against the "optimize the minimum use of trail pheromones"). Plus, it seems to say that these examples were all formed in the same time frame.

But the problem is that the hub point is further out to the left, making it out-of-the-way and elongating the trails, defeating the purpose of the additional point in the first place.

Re:Not a Steiner tree (1)

Mr Z (6791) | more than 3 years ago | (#35243880)

That second picture was introduced by this explanation:

That theory was deemed unlikely, when the researchers found larger supercolonies dedicated their additional resources to building paths that essentially improved the robustness of the network.

They explain away the non-optimality with "they had extra resources to spare." That would argue in the direction of "optimize toward a Steiner tree until you get below some threshold relative to the total available resources," or something similar.

You see this sort of tradeoff all the time in heuristics: Optimization one aspect of resource use (in this case trail pheromones) gets traded off against the time/energy/effort to perform that optimization. In this particular case with the ants, I suspect the higher ant traffic means the pheromones are getting replenished "fast enough" along the suboptimal route that there's no impetus to explore for better routes. To pick a computer analogy, it's like a JIT only throwing its most expensive optimization heuristics at the hot spots of the program it translated, and retranslating the rest only if it runs for long enough.

Thrifty Networking Building Ant Overlords (0)

Anonymous Coward | more than 3 years ago | (#35239708)

And I, for one, welcome our Thrifty Networking Building Ant Overlords...

Dude, you've been like totally outsourced (1)

PolygamousRanchKid (1290638) | more than 3 years ago | (#35240018)

By ants!

Self Healing Computers in Cars? (1)

Recovery1 (217499) | more than 3 years ago | (#35240046)

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.

This is not new (0)

Anonymous Coward | more than 3 years ago | (#35240072)

We followed this branch of thought in the 80's when it was first discovered that ants find shortest path by the decay of pheromones along their trails. Calculating timestamps on packet switched circuits to solve shortest-path and calculate routing was experimented with for several years. It was decided that the processing cost was too high for the small benefits gained over our new IS-IS standard and the researched was ended. Maybe today, the extra 3-5% would be worth the cost.

Why can't it just be a mathematical study? (0)

masterwit (1800118) | more than 3 years ago | (#35240130)

Buzzwords, we hate them and love them for all their hype and overzealous implications.

Yet more and more we are seeing today buzzconcepts as almost a duality: autonomous vehicles, self-healing compounds, nano-particle super virus fighter robot simulations, cloud-computing [insert addition here], etc. These are all very relevant concepts and require a large convergence of many scientific disciplines, but why can't we just enjoy these studies and speculate ourselves (or at least a bit less in the headline)?

Today, when reading headlines, I feel as if I am headed downtown in my car passing largely lit fast-food signs: encouraging further participation in science is great but forming application-based "bridges" as a justification for the science is flawed thinking. Now I am not (entirely) naive here, I understand (somewhat) how research grants are given, but looking for specifics in observation can cause one to miss the obvious.

No the world is not going to end for me and I understand I am crabby way beyond my age, but when reading many of these articles today I cannot help but conclude that the author would consider the topic he/she is working on boring had he/she not heard of the potential world-changing applications.

Now about the article, for those who have not read it yet but look to the comments first: it is good read, do it. (funny, I know reading) But honestly on Slashdot I did not need to be dazzled with some sensationalist headline... come to think of it this would have sufficed:
---
Ants build Steiner Trees
"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 and investments of ant pheromones. Researchers studying 'supercolonies' of the ants found them building networks that closely resembled the mathematical shortest path — a Steiner tree. The article states that individual "nodes were controlled individually and not by a central control unit." This may prove useful in fields such as self organizing sensors and network nodes."
---
Sorry for that rant but did they really think that...

‘supercolonies’ of Argentine ants with 500, 1000 or 2000 workers

...would be of any help in modeling autonomous Chicago traffic?
I think not.

Have a nice day. /endrant

Old News (0)

Anonymous Coward | more than 3 years ago | (#35240306)

Proverbs 6:6. Go to the ant, you lazy one; see its ways and become wise.

scientology uses brain implants (0)

Anonymous Coward | more than 3 years ago | (#35240334)

the xenu story is full of references to implants and scientology gave me one for torture

Slime molds (3, Interesting)

thetaco82 (791202) | more than 3 years ago | (#35240372)

Reminds me of this: http://www.wired.com/wiredscience/2010/01/slime-mold-grows-network-just-like-tokyo-rail-system/ [wired.com]
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.

Research on "Ant Colony Optimization" (1)

jsharkey (975973) | more than 3 years ago | (#35240812)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

Re:Research on "Ant Colony Optimization" (0)

Anonymous Coward | more than 3 years ago | (#35242598)

Are you posting (and reposting and reposting) this comment with an Ant Colony algorithm or what?

Research on "Ant Colony Optimization" (0)

jsharkey (975973) | more than 3 years ago | (#35240820)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

Research on "Ant Colony Optimization" (0)

jsharkey (975973) | more than 3 years ago | (#35240828)

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 [jsharkey.org]
http://jsharkey.org/downloads/trb-jsharkey.pdf/poster-jsharkey.pdf [jsharkey.org]
http://jsharkey.org/blog/2008/04/14/thesis-in-six-weeks/ [jsharkey.org]

Oh, and we also open-sourced it under GPLv3:

http://libprop.jsharkey.org/ [jsharkey.org]
http://code.google.com/p/libprop/ [google.com]
http://code.google.com/p/aco-netdesign/ [google.com]

grain of salt (1)

Dihce (1845556) | more than 3 years ago | (#35241012)

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

How much? (1)

mustPushCart (1871520) | more than 3 years ago | (#35241102)

My isp charges a bomb for installation of last mile.

Never mind this Steiner Tree! (1)

knaapie (214889) | more than 3 years ago | (#35241174)

What we want to know here is: Do they have Net Neutrality!

the nano tech....like the borg (1)

hesaigo999ca (786966) | more than 3 years ago | (#35242680)

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.

The truth is so simple (1)

calderra (1034658) | more than 3 years ago | (#35242848)

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.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>