Collective Intelligence in Social Insects
David Gordon
David Gordon
Indirect stigmergic communication is only part of the story when it comes to social insects. One of the rising stars of Collective Intelligence is Particle Swarm Optimisation (PSO), developed in 1995 by James Kennedy, a social psychologist, and Russell Eberhart, an electrical engineer[9]. Although the end result, when put to work in a 3D problem space, looks something like a swarm of bees, the authors' initial aim was to model human social interaction using emergent behaviours such as bird flocking.
According to Kennedy and Eberhart, the motivations at work on individuals in a flock - the need to match velocity and maintain distance from neighbours - are analogous to human social motivations, except that rather than moving through 3D space, people move in an n-dimensional social space. The assumption is that like the societies of the birds and the bees, people are motivated to maintain a certain proximity and heading with each other, not in the physical world but in the social world of beliefs and desires.
After a series of experimental alterations, Kennedy and Eberhart realised that, rather than simply a social simulation, they were looking at a powerful new search algorithm, capable of optimising a wide range of n-dimensional problems. Although the final PSO algorithm does not offer the most convincing representation of physical swarm movement, it is surprisingly effective at training neural nets and optimising hard functions. The most surprising thing about the PSO algorithm is how simple it is.
Each solution is represented as a series of coordinates in n-dimensional space. A number of particles are initialised randomly within the search space. Each particle has a very simple 'memory' of its personal best solution so far, called 'pbest'. The global best solution for each iteration is also found and labelled 'gbest'. On each iteration, every particle is moved a certain distance from its current location, influenced a random amount by the pbest and gbest values.
for each particle p
for each coordinate c
p.c = p.c + 2 * rand() * pbest.c - p.c + 2 * rand() * gbest.c - p.c
(rand() is a random number in the range [0, 1])
In action, the algorithm is very easy to understand. Imagine a flock of starlings looking for a wheat field: they maintain their velocity as they move towards the field, then when their target is beneath them, some of them overshoot. Realising their error, they double back towards the centre of the flock. Gradually, through a process of circling and swinging around the centre of the flock they all settle in a good spot. PSO is an abstraction of this process, with the physical constraints removed, thus each individual automatically knows where the most successful individual is (more effective and quicker than calculating the centre of the swarm) and suffers no physical constraints in changing direction and location.
PSO is one of the finest examples of the algorithmic elegance and power of nature. I have prepared a very (very) simple visual demonstration of the algorithm, available at the end of this article.
Honda have started to make their humanoid ASIMO robot available for rental in Japan, while Roomba, the first affordable consumer robotics device is now available for a mere $199 in the US. It looks like the android-assisted future sci-fi has been promising us all these years might finally be coming true. But some researchers believe that the articulate, bipedal machines of Star Wars and Spielberg's recent film AI, are far from what we should expect to see when robots become a fixture of everyday life.
Although the multi-agent approach to robotics is not a new idea, social insect studies have demonstrated how to make such an approach worthwhile. The advantages to roboticists are many:
Ants crop up again and again in collective intelligence, simply because they are so versatile. The success of the ant is witnessed by the fact that ants are believed to make up about 10% of the world's animal biomass. They have adapted successfully to a huge range of environments and consequently provide an almost limitless fountain of robotics applications. A few examples are Weaver ants, which can form chains of their own bodies, enabling them to cross wider gaps than individuals might; cooperative transport, readily observable in many ant species which can collectively transport objects many thousands of times the weight of an individual ant; cemetery organisation and brood sorting, whereby a group of ants can collect and organise dead ants and larvae without direct communication; and the building behaviours we've already seen in termites. Swarm robotics applications tend not to be inspired as directly from social insects as ant search algorithms, but ants nevertheless provide a valuable proof of concept.
C.Ronald Kube and Hong Zang[10] of the University of Alberta have programmed khepera robots to reproduce a simple version of collective transport. They set a group of robots a simple task: to collectively move an object which was too heavy for an individual robot to push. The robots were equipped with light sensors which could tell them the location of the light-box they were to move, and the goal they had to move it to. Their program was very basic:
Although the end result is not optimal, the robots are always successful at pushing the box into the goal, and without any direct or indirect communication of any sort. They are robust and very simple to program and flag a promising direction for development of robots for use in harsh environments (e.g. marine, extraterrestrial) where minimising the number of crucial links in the integrity of the system is always a bonus.
Another interesting feature of the box-pushing robots is the resemblance of their actions to the ants that inspired them, clearly visible in the videos accessible from Kube’s web page.
A collaboration between a group of European institutions has come up with the Swarm-bots project[11], the ultimate aim of which is (unsurprisingly) to produce a 'swarm-bot', which they define as an 'artefact composed of a number of simpler, insect-like, robots', which they call 's-bots'. Each s-bot will be just 116 mm wide, with a rotating motorised base, mobilised by a track system. On the top of the robot will be two 'arms', enabling rigid and flexible connections to be formed between robots. Each s-bot is also able to lift other s-bots, opening the door to more complex 3D structures.
There are currently three main objectives for the swarm-bot project, although applications and extensions of these basic functions are plentiful:
The swarm-bots project is currently at a simulation stage, with the first prototype s-bot projected for January 2003
Remember you can visit the Message Store to discuss this essay. Comments are always welcome!. There are already replies in the thread, why not join in?