Slashdot Mirror

← Back to Stories (view on slashdot.org)

Ants Build Cheapest Networks

Posted by timothy on from the where's-antdude-when-you-expect-him-most? dept.

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.

21 of 108 comments (clear)

  1. Improper illustration by squidflakes · · Score: 2

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

    1. Re:Improper illustration by ComaVN · · Score: 3, Funny

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

      --
      Be wary of any facts that confirm your opinion.
  2. that's the replicators not skynet by Joe+The+Dragon · · Score: 2

    that's the replicators not skynet

    1. Re:that's the replicators not skynet by ThunderBird89 · · Score: 2

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

      --
      Hyperbole: I use it liberally!
  3. Evolution is smarter than you. by JoshuaZ · · Score: 5, Insightful

    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.

    1. Re:Evolution is smarter than you. by Monkeedude1212 · · Score: 4, Interesting

      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.

    2. Re:Evolution is smarter than you. by khallow · · Score: 3, Informative

      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!

  4. Re:skynet by GNUALMAFUERTE · · Score: 4, Funny

    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]

    --
    WTF am I doing replying to an AC at 5 A.M on a Friday night?
  5. Re:skynet by Straterra · · Score: 3, Funny

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

  6. Great, just what beleaguered US tech workers need by unassimilatible · · Score: 3, Funny

    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
  7. Thanks Ants by Culture20 · · Score: 2

    Thants
    Look Around You.

  8. Them ants is smart by blair1q · · Score: 3, Insightful

    Or maybe we're just underestimating the intelligence of soap

  9. Re:See ACO on Wikipedia by blair1q · · Score: 2

    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.

  10. Re:eh? big surprise? by tenex · · Score: 5, Interesting

    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.

  11. Re:See ACO on Wikipedia by c0lo · · Score: 3, Funny

    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.

    --
    Questions raise, answers kill. Raise questions to stay alive.
  12. Not a Steiner tree by White+Flame · · Score: 3, Informative

    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.

    1. Re:Not a Steiner tree by White+Flame · · Score: 2

      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.

  13. Re:skynet by u17 · · Score: 3, Funny

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

  14. Slime molds by thetaco82 · · Score: 3, Interesting

    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.

  15. Re:eh? big surprise? by langelgjm · · Score: 2

    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
  16. Research on "Ant colony optimization" by jsharkey · · Score: 5, Interesting

    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/