Follow Slashdot blog updates by subscribing to our blog RSS feed

 


Forgot your password?
Close
typodupeerror
×
Network AI Math Science Technology

Ants Build Cheapest Networks 108

Posted by timothy 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.
This discussion has been archived. No new comments can be posted.

Ants Build Cheapest Networks More

Ants Build Cheapest Networks

Comments Filter:
  • Self-healing, organized organic networks of robots. What could possibly go wrong?
  • Maybe ants play netwalk [softpedia.com]?

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

  • Evolution is smarter than you. (Score:5, Insightful)

    by JoshuaZ ( 1134087 ) on Thursday February 17, 2011 @06:36PM (#35238934) Homepage
    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. (Score:5, Interesting)

      by Monkeedude1212 ( 1560403 ) on Thursday February 17, 2011 @06:45PM (#35239030) Journal

      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. (Score:4, Informative)

        by khallow ( 566160 ) on Thursday February 17, 2011 @06:55PM (#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: (Score:2)

        by raddan ( 519638 ) *
        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 vari

      • Re: (Score:2)

        by hitmark ( 640295 )

        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.

    • The amazing things animals can do without intelligence to get in the way.
      • 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 a

      • Just like humans.

    • Research on "Ant colony optimization" (Score:5, Interesting)

      by jsharkey ( 975973 ) on Thursday February 17, 2011 @11:17PM (#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: (Score:1)

        by xtracto ( 837672 )

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

    • Re: (Score:1)

      by Anonymous Coward

      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 t

    • 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: (Score:3)

      by blair1q ( 305137 )

      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 (Score:4, Funny)

        by c0lo ( 1497653 ) on Thursday February 17, 2011 @07:34PM (#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.

        • 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: (Score:2)

            by Inda ( 580031 )
            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.
      • 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"

      • "And oh yeah...they HATE it when you do this! [youtube.com]"

  • Great, just what beleaguered US tech workers need (Score:4, Funny)

    by unassimilatible ( 225662 ) on Thursday February 17, 2011 @06:51PM (#35239074) Journal
    More immigrants coming in on H1's stealing IT jobs!

    • Re: (Score:2)

      by blair1q ( 305137 )

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

  • Thanks Ants (Score:3)

    by Culture20 ( 968837 ) on Thursday February 17, 2011 @06:54PM (#35239106)
    Thants
    Look Around You.

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

  • Discworld [wikipedia.org] already did it.

  • Them ants is smart (Score:4, Insightful)

    by blair1q ( 305137 ) on Thursday February 17, 2011 @07:09PM (#35239228) Journal

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

  • Not a Steiner tree (Score:4, Informative)

    by White Flame ( 1074973 ) on Thursday February 17, 2011 @07:45PM (#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.

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

      • 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: (Score:2)

          by Mr Z ( 6791 )

          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

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

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

    To

  • Slime molds (Score:3, Interesting)

    by thetaco82 ( 791202 ) on Thursday February 17, 2011 @09:42PM (#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.

  • 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://jsha [jsharkey.org]

  • 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!

  • 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 esse

  • 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
  • "The ants will soon be here. And I for one welcome our new insect overlords." 1F13 96 - 515 (Deep Space Homer)

  • Ponder Stibbons figured this out a long time ago....this is why HEX is so efficient

Slashdot Top Deals

If all the world's economists were laid end to end, we wouldn't reach a conclusion. -- William Baumol

Close