Incorporating Swarm Intelligence Into Computer AI 64
An anonymous reader writes "From optimizing truck delivery routes to inspiring nerve-cell-based cognition models, ant intelligence has arrived. From the Economist: 'In 1992 Dr. Dorigo and his group began developing Ant Colony Optimisation (ACO), an algorithm that looks for solutions to a problem by simulating a group of ants wandering over an area and laying down pheromones. ACO proved good at solving travelling-salesman-type problems. Since then it has grown into a whole family of algorithms, which have been applied to many practical questions. ... Ant-like algorithms have also been applied to the problem of routing information through communication networks. Dr. Dorigo and Gianni Di Caro, another researcher at IDSIA, have developed AntNet, a routing protocol in which packets of information hop from node to node, leaving a trace that signals the "quality" of their trip as they do so. Other packets sniff the trails thus created and choose accordingly. In computer simulations and tests on small-scale networks, AntNet has been shown to outperform existing routing protocols."
/.'rs disagree. (Score:1, Funny)
Re: (Score:2)
I made a visualization of ant pixel bots wandering around a map and laying down virtual pheromone trails as an art project. The results are pretty psychedelic
Java applet written in Processing [processing.org] years ago:
http://object404.com/lab/bloodlines [object404.com]
Interestingly, I was able to reproduce the conditions that made ants wander in weird circular loop swarms in Brazil
Hill Climbing (Score:2)
It just sounds like the classic hill climbing algorithm [wikipedia.org] to me.
Re:Hill Climbing (Score:5, Insightful)
It just sounds like the classic hill climbing algorithm to me.
That's because it's very similar -- with a massive stochastic component. It might be effective at routing, but I image leaving "pheromone traces" over network routes to indicate quality (latency, bandwidth, whatever) is something that will make sure security researchers have jobs for a long, long time.
Re: (Score:2, Insightful)
but I image leaving "pheromone traces" over network routes to indicate quality (latency, bandwidth, whatever) is something that will make sure security researchers have jobs for a long, long time.
Why? I don't see why you'd need uniquely identifiable information left behind in the "pheromone". Hopefully a decent spec would also be sensitive to privacy concerns and would simply have an "off" bit as well.
Re: (Score:2)
Hopefully a decent spec would also be sensitive to privacy concerns and would simply have an "off" bit as well.
I wasn't talking about privacy, but rather security in terms of the routing algorithm being gamed for malicious reasons.
Re: (Score:1)
Re: (Score:1)
Re: (Score:2)
I concur! The concept of particle swarm optimizations is so simple.. (and me being fairly dumb, me like so much).
One particular approach I like is where you have randomly defined neighborhoods for your particles. And as the simulation progresses.. members of the neighborhood that do well get more random connections to other algorithms while ones that do worse lose connections.
Then, the particles just move towards (with some random perturbations) whatever member of the neighborhood is doing "better" (howev
RE: (Score:1)
IDSIA (Score:1, Insightful)
I split in their general direction.
Who/what the fuck are they, Mr. Summary Writer?
Re: (Score:2)
I split in their general direction.
Who/what the fuck are they, Mr. Summary Writer?
http://www.lmgtfy.com/?q=IDSIA [lmgtfy.com]
The Ant Networking Protocol was a huge success (Score:5, Funny)
Until it passed by a group of people having a picnic.
Re: (Score:2, Funny)
or until someone breaks out the Magnifying Lens Protocol.
Swarm UDP? (Score:2)
Re: (Score:2)
The swarm could be at the connection level -- swarms of connections finding the best routes over time, but within any given established connection, packets still travel single-file (like sand people, to hide their numbers.)
Re:Swarm UDP? (Score:4, Funny)
Re: (Score:2)
so, much like existing auto-generating routing protocols?
Re:Swarm UDP? (Score:4, Insightful)
I'm not sure I understand your post.
UDP packet order is already unreliable. You have to build in your own sequencing and error-correction logic at the application level (if you need it).
Again, UDP does not fit this description. Are you sure you're not confusing TCP and UDP?
http://en.wikipedia.org/wiki/User_Datagram_Protocol#Comparison_of_UDP_and_TCP [wikipedia.org]
Re: (Score:1)
No, RTP requires that sufficient data arrive in time to reconstruct the original sound, not in sequence. RTP has sequence control built into the protocol. The packets can come in in any sequence they want, but any packets that don't make it in time to be integrated into the sound are discarded because it's too late.
Let's say I send you an RTP VoIP stream that encoded to 10 packets, numbered 0 through 9, which I sent as 0123456789. Variable latency and entropy set in, and when your decoder receives them i
Re: (Score:2)
UDP packet order is already unreliable. You have to build in your own sequencing and error-correction logic at the application level (if you need it).
For both UDP and TCP, most actual uses require packet order to be almost-maintained. TCP gets basically useless if there is more than a little bit of packet reordering, and VoIP with packet reordering is no fun at all.
Nothing new here... (Score:4, Informative)
Dorigo et al. made their groundbreaking paper in 1996 (based on observations by Deneubourg in 89), and then nothing. Nothing new on the theoretical part, no new application. Even routing using ACO like algorithm has been published as early as 1994. The newest extension based on these algorithms is an interactive distributed image retrieval system by Picard et al. back in about 2006 (as far as I know). So nothing new nor groundbreaking here.
Absolutely (Score:2)
Can I join in with your sentiment, and just say, WTF?
It's like Slashdot has just discovered early 1990s AI research and confused it with modern news. ACO has been around for so long now that it's a standard tool in the toolbox of the developer who has a basic grounding in AI along with genetic algorithms and particle swarm optimisation. As the AC says, it's already been used in routing protocols.
Why is Slashdot reporting this? What is the story meant to be here exactly? Even TFA just seems to be a very very
And this is different from OSPF how? (Score:3, Informative)
How is "AntNet, a routing protocol in which packets of information hop from node to node, leaving a trace that signals the "quality" of their trip as they do so..." any different from bog standard hop count updates on existing routers, and routing on the basis of the shortest path?
I think the authors are playing semantic games here, not doing research.
Re: (Score:2)
OSPF weights each hop according to speed. The exceptions to its results are rare, but definable, and other routing protocols are used where they're expected.
Re: (Score:3, Interesting)
Well, for one, ants don't do OSPF...
It's been many years since I read up on this, but here goes: Like pheromone, the traces decay, or "evaporate", over time. Yet the next packet deposits new pheromone. Do this a number of times over a number of paths through a number of nodes, and statistically the shortest path will accumulate the most pheromone, and hence the shortest path will "emerge" from the rest.
OSPF and hop counts are deterministic. This method is a lot more stochastic, and hence could be easier to
Re: (Score:1)
you should read the original papers before saying that the authors play semantic games ;-)
http://www.idsia.ch/~gianni/antnet.html [idsia.ch]
the differences are many, here are some important ones. Full paths are explicitly sampled by control packets (the 'ants') (wich is quite different from locally observing link costs and then flooding them). Sampling full paths also involves some
core issues that do not find any counterpart in ospf: how often ants are generated (i.e., when, how often, do I need to refresh my local ro
Re: (Score:3, Interesting)
It's very different. OSPF requires everyone to know the layout of the complete network. For mesh networks, OSPF is useless, it never converges. Attempts to amend OSPF to work for mesh networks have so far failed.
AntNet works quite badly, but it does get most of the traffic to its destination most of the time. That is a lot better than anyone else does.
Interesting Paper (Score:4, Informative)
I just covered Ant-based load balancing on communications networks in a distributed systems class. Here's the paper we read. It's an easy read, and quite interesting.
http://www.hpl.hp.com/techreports/96/HPL-96-76.pdf [hp.com]
Re: (Score:3, Informative)
that was one of the original papers on the topic, I suggest also to read the (a bit later) AntNet papers I wrote with Dorigo. I have a web page on the topic (nothing much, but there are some good references there):
http://www.idsia.ch/~gianni/antnet.html [idsia.ch]
So, basically an adaptive traceroute? (Score:3, Insightful)
Kinda sounds like an adaptive traceroute. Perhaps traceroute was antlike before it became in vogue :)
Obligatory... (Score:5, Funny)
Yer kidding, right? (Score:2)
You mean to say that this thing is measured as outperforming non-statistical recursive routing methods?
"good at solving" - define "good" here, and how does it compare to a directed algorithm
"good at thinking up solutions" - wait, this is different. now they're not solving, they're thinking-up solutions. instead of being dumb actors with rule-based behaviors and reacting to external stimuli, they're now using their own internal models to plan how they will route themselves. (no, it isn't, i'm being sarcas
Re: (Score:1, Interesting)
- i think my brain just asploded.
That's because you were acting and not thinking.
Slightly more seriously, the above post acts as a nice illustration of the fact you can go on ranting about your own private brand of Cartesian dualism all you like, just so long as you're always allowed to shut down anyone talking to you by redefining terms every now and then.
In this case, it's done by trying to enforce a specific, private, and egocentric definition of "think". It's one of those irregular verbs: I think, you may or may not think, that non-ant
Re: (Score:2)
Your hypocrisy is noted and dismissed as ludicrous flaming.
My criticism of their use of the word "think" is appropriate. I bet you think that evolving an instinct is "learning" and colony collapse is "forgetting".
Re: (Score:2, Interesting)
Re: (Score:2)
Some of the weasely bits were in quotes. I'll wait for the movie.
Console message (Score:3, Funny)
>ANT: We must save the queen!
>ANT: Which one of us is the queen?
>ANT: I'm the queen!
>ANT: No, I'm the queen!
(smashing of glass sound)
>ANT: Freedom! Horrible, horrible freedom!
Re: (Score:1)
Economist Article (Score:3, Insightful)
Why are we reposting an economist article? I would think SlashDot could come up with an article that goes somewhat deeper than this.