Ants Build Cheapest Networks 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.
Re:Evolution is smarter than you. (Score:5, 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.
Re:eh? big surprise? (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.
Slime molds (Score:3, Interesting)
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" (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 [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]