Swarm Intelligence
"The emergent collective intelligence of groups of simple agents" – Bonabeau et al , 1999
Swarm intelligence (SI) involves multiple simple agents interacting with each other and the environment to solve complex problems through their collective global behaviour. This is inspired by the intelligent behaviour seen in swarms of animals such as a colony of ants, flocks of birds or schools of fish.
SI systems have a number of features:
Flexibility: The system is constantly updating means it can respond to changes in the environment.
Robust: As the solution given is the global response this means the system will still give the correct response even if individual agents fail.
Decentralised: There is no hierarchy amongst the agents and central control system.
Self Organising: Solutions to a system are emergent rather than predefined.
Simplicity: Individual agents are typically very simple systems.
These features allow SI systems to handle many problems that are not suitable by traditional means. These include problems that are dynamic, non predictable, not defined or computationally hard.
As SI systems are inspired by natural biological swarms, standard algorithms are based on the search for food. The differences in food searching techniques lead to different SI algorithms, including:
Ant Colony Optimisation (ACO)
ACO replicate the natural behaviour of ants. Ants will randomly spread out and search for food. When food is discovered an ant will return to its base leaving a pheromone trail. Upon finding a pheromone trail another ant will follow that train and if it finds food on this trail it too will return to base, leaving its own pheromone trail. If an ant is on a pheromone trail and crosses a stronger pheromone trail it will follow the stronger trail. Pheromones decay over time allowing the removal of non optimal solutions. The ACO algorithm finds optimal solutions because shorter paths are traveled over faster and hence more often quickly leading to strong pheromone trails. Introducing new ants randomly over time allows responses to dynamic changes in the environment. ACO is typically used to find an optimal path.
Particle Swarm Optimisation (PSO)
This form of Swarm intelligence is based on schools of fish and flocks of birds finding food. PSO is used to find an optimal point in space.
Agents begin by being randomly spread out in the environment with random velocities. As the agents move they examine the area around them and communicate with the other agents their evaluations. This communication can either be a global communication or a local 'neighbourhood' communication. Based on their own findings and the findings communicated to them, agents will adjust their velocities to follow better solutions. As a result agents will begin to head into areas where the best solutions are being found and this leads to an optimal solution.
System design
The difficult task in swarm intelligence is to answer the question:
How do I program an individual agent so the entire global system behaves as I want it to?
The techniques to design and control individual agents are a standard AI problem and techniques like reinforcement learning, fuzzy logic, neural networks etc, can be used.
When designing an SI system both the individual agents' ability to search and evaluate its area as well as a means for communication need to be considered. Many of the global emergent behaviour are difficult to predict.
Applications
Swarm Intelligence is utalised in the following areas:
Crowd simulation: Used to predict crowd movement in transportation problems, or to simulate crowds in movie special effects.
Crowd control: Used to control the distribution and behaviour of multiple agents over an area. E.g. collective robotics.
Path optimization: Used to solve the typical 'traveling salesman' problem.
Complex optimization: Used to solve dynamic, nonlinear complex optimization problems like scheduling.
From
P.Sruthi
07681A0571
