Collective Intelligence in Social Insects
By ai-depot | January 20, 2003
Particle Swarm Optimisation
Particle Swarm Optimisation
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.
Swarm Robotics
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:
- Rather than develop big, expensive and complicated robots, many cheap and simple ones can be used to achieve the same goal.
- Many robot environments are precarious. If one robot is incapacitated in the traditional approach, you’ve lost your robot and can’t go on. One individual in a swarm, however, is relatively expendable.
- If your robot is faced with too big a task (e.g. an object too heavy to lift), ordinarily it would be back to the drawing-board, but where a swarm is involved solutions are often inherently scalable.
Back to the Ants’ Nest�.
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.
Collective Box-Pushing
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:
- Move at random until a light source is located, if forward movement is restricted the source is probably a box side.
- Once the box is located, use another upward pointing light sensor to check if the box is between the robot and the goal, if not reposition.
- Once the box is definitely between the robot and the goal, push!
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.
Swarm-bots
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:
- Dynamic shape and formation change, where randomly positioned s-bots will be able to group together to form swarm-bots with various features, e.g. high stability structures, positioning of sensors (imagine a swarm of robots raising the special robot with the video camera up to peek over a wall) and ultimately methods for removing ‘dead’ - i.e. no longer functioning - s-bots.
- Rough terrain navigation, where s-bots in certain formations will be able to successfully traverse, and even pathfind, on unknown terrain. For example, forming a chain in order to cross gaps wider than an individual s-bot could.
- Scaling up, where the above objectives will be achievable, and more effective, using increasing numbers of s-bots.
The swarm-bots project is currently at a simulation stage, with the first prototype s-bot projected for January 2003.
Tags: none
Category: essay |
