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.

3 of 108 comments (clear)

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

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

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