Swarm Intelligence

[Triple Zero]

This post is a spinoff from my Urban Swarm Art post in O:MF.

"Swarm intelligence" techniques are another example of biologically inspired forms of artificial intelligence. Currently they are in use in network routing and congestion prevention systems, using "digital pheromone trails" (basically packet counts) in order to locally determine the most efficient routes for network traffic. Correction: Wikipedia says "As the system behaves stochastically and is therefore lacking repeatability, there are large hurdles to commercial deployment."

Another application is real world traffic jam prevention. I expect these algorithms to be on the market within a year, maybe two [should probably call that in the 2010 predictions thread], using our ubiquitous navigation software/apps/devices [at least in the Netherlands, nearly everybody has a TomTom, dunno if US is ahead or behind in adoption].

Cars would leave a "virtual pheromone trail" on the roads they travel. In its simplest form, this slowly evaporating trail would represent a measure of how crowded a certain part of the road is. This would already allow navigation software to locally query this crowdedness and calculate optimal alternatives on-the-fly. A more advanced system could also use a variety of different "digital smells" to represent maximum speed of the car and perhaps a rough indication of the destination. Both pieces of data could be used to optimize routing even further.

This may seem really straightforward, and in a sense it really is. However, a proper Swarm Intelligence algorithm not only has the property that it can locally produce a (near-) optimal solution, but due to the way the information propagates through the swam, it also optimizes the solution globally.

Of course this "virtual pheronome trail" brings with it huge privacy implications. Even though these particular algorithms suit themselves very well for a decentralized anonymous peer-to-peer solution, the digital representation of it will probably be stored in a centralized server. At least, I expect this because it will be Google, TomTom, Nokia or some similar big corp to first implement this solution and naturally they will want to get their hands on that data. Unless somehow an Open Source solution appears on the market first. The problem with that however, will be that this Swarm Intelligence stuff will not work unless a significant amount of traffic participates. So in that way, it can only be successfully implemented by the local (to a country/continent) market-leader in navigation systems. Unless they happen to have a really open platform.

Some wikipedia links for those interested in the topic:

http://en.wikipedia.org/wiki/Ant_colony_optimization (specific)
http://en.wikipedia.org/wiki/Swarm_intelligence (medium)
http://en.wikipedia.org/wiki/Metaheuristic (really broad)
http://en.wikipedia.org/wiki/Emergence (similarly broad and because everybody loves the concept--I can really recommend reading this page btw)



(EDIT FOR NOT BEING ABLE TO SPELL SWARM RIGHT)

[Shai Hulud]

Fascinating stuff!  I have a couple questions:

However, a proper Swarm Intelligence algorithm not only has the property that it can locally produce a (near-) optimal solution, but due to the way the information propagates through the swam, it also optimizes the solution globally.

What are the global implications?  Are you still talking about traffic patterns here or does this extend to airplane flight patterns and such?

The problem with that however, will be that this Swarm Intelligence stuff will not work unless a significant amount of traffic participates.

This is another thing I'm confused about, because I think what you're talking about here is that it won't work without most cars opting in to the program to give off the pheromones in the first place.  Or, and here's something I'm probably misunderstanding, do you mean that it won't work if the drivers don't choose to follow the pheromones?  If I get the analogy to the ants, the reason the pheromones work so well is that there are so many ants blindly following pheromone trails, and the bigger ones with more ants have more pheromones to attract more ants and so on.  But if drivers don't bother taking the advice of their GPS and go their own way then the pheromones they give off won't leave trails that are as effective.  Or does the behavior of the driver even matter at all?

[BabylonHoruv]

Fascinating stuff!  I have a couple questions:

However, a proper Swarm Intelligence algorithm not only has the property that it can locally produce a (near-) optimal solution, but due to the way the information propagates through the swam, it also optimizes the solution globally.

What are the global implications?  Are you still talking about traffic patterns here or does this extend to airplane flight patterns and such?

The problem with that however, will be that this Swarm Intelligence stuff will not work unless a significant amount of traffic participates.

This is another thing I'm confused about, because I think what you're talking about here is that it won't work without most cars opting in to the program to give off the pheromones in the first place.  Or, and here's something I'm probably misunderstanding, do you mean that it won't work if the drivers don't choose to follow the pheromones?  If I get the analogy to the ants, the reason the pheromones work so well is that there are so many ants blindly following pheromone trails, and the bigger ones with more ants have more pheromones to attract more ants and so on.  But if drivers don't bother taking the advice of their GPS and go their own way then the pheromones they give off won't leave trails that are as effective.  Or does the behavior of the driver even matter at all?

I'm pretty sure he is saying that if the vast majority don't choose to emit pheremones it wont work properly.  In a traffic routing system the goal is to avoid the path the other cars have taken, rather than follow it, so people who emit pheremones but don't follow the suggested optimal route are only screwing themselves.

On the other hand in something like the bar experiment that 000 links to in the parent thread someone not following the stickers and still stickering their own would actually throw a cog into the whole system.

[Triple Zero]

Guy: with "global" I meant, as opposed to "local". see the cars only act on local information (reading and writing location-based pheromone data), but in doing so, they will optimize the global traffic behaviour. that is, global within the system of roads. not global as in "worldwide around the globe".

And unless GPS devices emit erroneous data on purpose, it would be pretty hard to throw a cog into the system.

And yes, the amount of participation is proportional to how well it works. But still, even if a small portion of cars manages to avoid traffic jams, those cars will benefit, as well as those traffic jams being slightly less crowded.

Same goes if only few cars join the project and submit pheromone data. Even then, if the pheromone data also specifies the speed of the car, the algorithm can make a reasonable guess about traffic congestion.

But the system would exponentially improve the more cars join. Especially once it's the majority, the few non-players might even benefit a littlebit "similar to "herd immunity" cause there are less jams overall.

[Rococo Modem Basilisk]

I like this idea. It could possibly be used in networking (think some frame packet header metainfo about the route taken -- the IP at every hop and the time it took to make the hop?), making packets semi-intelligently avoid cramming themselves into small pipes way out in the internets (try routes that have historically been fast to the sender first?). I can't imagine anyone bothering implementing it there, of course, and there won't be a major benefit outside of a very large network.

[Jasper]

I really like the idea of swarm intelligence.  I'm looking forward, beyond robotic cars, to robotic cars that act like a swarm to optimize route times.

I'm looking forward to it because when it happens, I will buy one of these.

[Requia ☣]

A problem with using traffic optimization.

Everybody who has ever been on I-15 during rush hour more than once knows that there is a 10 mile long traffic jam there at rush hour.  Every day.

And yet they keep getting on I-15 at rush hour.

I think we need smarter platforms than humans before this starts to be helpful.