Better Networking Through Nature

The New York Times has an interesting piece about applying lessons from nature - specifically ant colonies - to solving networking and other problems. Not quite on the same level as Spidergoats, but intriguing nonetheless.

Comments

Pratchett right all along

[Anonymous Coward]

The BBC had something on this on Tuesday:

http://news.bbc.co.uk/hi/english/sci/tech/newsid _1 537000/1537645.stm

Isn't this the way that HEX in the discworld novels works?

Classic /.

Not really new.

[rutger21]

I did some little research on this subject about two years ago. The goal of the project was complete autonomous network management. It has been a while ago, but IIRC the automatic routing adjustment worked like this:

a whole bunch of ants are randomly created at all routers in the network, with a mission to get to a random desitination

each router keeps a chance-table for each outgoing port for each destination (in the network), initially all outgoing ports have the same chance

ants start moving, pick an outgoing port randomly according to the chance table

ants remember their path and travelling time

if an ant reaches its destination, the trial it put down on its way over there affects the chance table in a positive way using the memory of the ant

It was rather fun, if I "removed" a router, ants really got adopted fast and found alternative routes. With redundant networks, routers started sending 50/50 to outgoing ports reaching the same destination. An{t,d} of course, as usual, many parts of this algorithms can be improved.

Limited practical uses

[mortenf]

While the principle of using ants is hardly news - Dorigo started his more than a decade ago - the use of ant colonies is not suitable for all problems of distributed nature.

I have worked on using ant colonies, basically a variation on Dorigos work, on problems related to floor planning and bin packing (those with danish capabilities could have a look here).

It seems as though the ants are very good at solving the "basic" problems of finding a shortest path, but that the method does not lend well to other optimization problems, even though it may seem that they over time should be able to figure out the best solution.

Routing on the Internet might be a problem that's worth attacking with this method, but aside from the similar issues, I can't see how this would benefit P2P networks.

Re:Rogue ants

[tolan's my name]

Real ants are genetically programmed with loyalty to their hive

This isnt actually true. Many experiments have been done were both adult ants and larve have been transported between hives, usually there is no difference in behavior to native ants.

There are even a number of ant species that have not worker caste of their own and survive by raiding other ant colonies [of a differing species] and stealing larve. These then hatch and act as workers for the new colony.

If ants are genetically programed to do anything it is to react to certain smells

Emergent behavior

[Nyrath the nearly wi]

I read something similar to this a long time ago, how tiny algorithms in individual simulated birds composing a simulated flock would automagically produce large scale flock behavior (the same behavior observed in real life flocks of birds).

Naturally the facination is with the big dividends paid to a tiny initial investment in algorithm.

Basic ant food gathering behavior exibits finely tuned feedback and efficency with similar tiny algorithms.

A scout ant searches for food. When it finds it, algorithm #1 kicks in:

• Grab as much food as you can carry.
• Run to the nest.
• If and only if there is food left at the site, leave a scent trail as you go to the nest.

Ants at the nest who are unassigned to task, upon smelling the scent execute algorithm #2, which is basically "follow the scent trail".

As more ants grab food and leave scent trails to the nest, the intensity of the scent induces more and more ants to execute algorithm #2.

When the food source is exhausted, no more scent is deposited on the trail, and the scent trail dissapates.

Re:Emergent behavior

[DrSkwid]

as far as i understand it (it was in the execllent "Predators" series on the bbc a couple of weeks ago) the ants are not as auto as that.

This was for Army Ants :

They lay a trail on the outgoing journey.

Each day the ants leave in a different direction to yesterday, covering about a 45 degree arc. and differing in direction about 135 degrees every day so they don't go near yesterdays trails but eventually cover the whole 360 degrees.

Once complete they move on and choose a different starting location.

The tv show did en excellent graphic of what was happening.

They do indeed lay a different trail when returning with food.

The behaviour is more complex than just rules #1 & #2

Swarm intelligence has been researched for awhile

[goldenfield]

There are actually quite a few uses for this type of technology (see my Master's thesis for references ). The AI community has been looking at swarm intelligence and multi-agent systems for years. NASA has sponsored research on using ant-like behavior in multiple robots to explore Mars (advantages in redundancy, system memory, command and control, etc...).

Also, check out The Swarm Development Group - you can download some software to play with alife sims, visualize really efficient search patterns, etc...

Further Reading...

[dfelznic]

You can see some of his papers at: http://citeseer.nj.nec.com/30955.html That is a cool site for any scientifc article lookups. Form that link you can see a lot more of his papers and related ones. Their is a new book coming out about this. I saw it in the article Emergence : The Connected Lives of Ants and their have been others to: Swarm Intelligence