07-07-2012, 02:16 PM
SWARM INTELLIGENCE
Introduction about Swarm Intelligence
•SI is the property of a system whereby the collective behaviors of agents interacting locally with their environment cause coherent functional global patterns to emerge .
•SI provides a basis with which it is possible to explore distributed problem solving without centralized control or the provision of a global model.
•One of the cores tenets of SI work is that often a decentralized, bottom-up approach to controlling a system is much more effective than traditional, centralized approach.
•“Groups performing tasks effectively by using only a small set of rules for individual behaviour is called swarm intelligence.”
•“Swarm Intelligence is a property of systems of non-intelligent agents exhibiting collectively intelligent behaviour.”
•In Swarm Intelligence, “…two individuals interact indirectly when one of them modifies the environment and the other responds to the new environment at a later time.”
Where did the Concept arise?
•For years scientists have been studying about insects like ants, bees, termites etc.
•The most amazing thing about social insect colonies is that there’s no individual in charge. For eg: consider the case of ants.
•But the way social insects form highways and other amazing structures such as bridges, chains, nests and can perform complex tasks is very different: they self-organize through direct and indirect interactions.
Self Organization
•Errors and randomness are not “bugs”; rather they contribute to success by enabling them to discover and explore in addition to exploiting.
•Self-organization feeds itself upon errors to provide the colony with flexibility and robustness..
•A very different mindset from the prevailing approach to software development and managing vast amounts of information: no central control, errors are good, flexibility, robustness (or self-repair).
Characteristics of Social Insects
1.Flexibility
2.Robustness
3.Self-organization
Human beings suffer from a “centralized mindset”; But inserting the human factor into the loop is against SI.
Big Issue
How should we program the individual virtual ants so that the network behaves appropriately at the system level?
There is always a fear of these systems going out of control as there is no central control nor the emergent behaviour of the whole system is predefined only the agents are predefined.
We don’t always know ahead of time what emergent solutions will come out because emergent behaviour is unpredictable.
If applied well, self-organization endows your swarm with the ability to adapt to situations that you didn’t think of.
Characteristics of Self Organizing Behaviour
1.Positive reinforcement
2.Negative reinforcement
3.Amplification of fluctuations
4.Multiple interactions
1.Positive reinforcement
•Many ant species forage for food using a trail-laying trail-following behaviour.
•It is a self-fulfilling prophecy, “ants following pheromone trails will tend to congregate simply from the fact the pheromone density increases with each additional ant that follows”.
•This self- perpetuating mechanism is known as “mass recruitment” and is the primary reinforcement of the foraging behaviour.
Pheramone Trails
•Individual ants lay pheromone trails while travelling from the nest, to the nest or possibly in both directions.
•The pheromone trail gradually evaporates over time.
•But pheromone trail strength accumulate with multiple ants using path.
2.Negative Reinforcement
•Negative reinforcement can be seen in crowding at the food source, limitation of population, or food source exhaustion.
•In case food source exhaustion, then no more pheromone is deposited on the trail. The pheromone currently on the trail will evaporate, eventually falling to zero.
•No pattern is formed if the pheromone signal is too weak.
4.Multiple interactions
•A minimum saturation is required for a pattern to emerge
•Self organization “usually requires a minimal density of mutually tolerant individuals”.
•Each individual should be able to use the results of its efforts and those of nest mates possibly being able to distinguish exactly which individual performed the task.
In order to understand swarm intelligence we have to analyze few questions:
•How are jobs scheduled and assigned?
•How are jobs executed?
•How do individuals choose or change a job?
•How is equilibrium achieved among all individuals for all jobs in the colony?
We can analyze the job assignment strategy as it is the only question which can be give an answer in specifics.
Job Assignment: Four Ways
•Age
•Morphology
•Individual – Individual (I-I) communication
•Environment – Individual (E-I) communication
1) Age Job Assignment
•Among certain social insects, individuals prefer to take certain jobs based on their age.
•With honey bees
– Young workers do hive chores such as building and repairing the hive, ventilation, defense, food preparation, etc…
– Older workers gather nectar, pollen, and water.
•In SI our virtual agents work in the same way older agents will have more updated rules, newer agents will have some specific job.
2) Morphology Job Assignment
•Some individuals may be better suited for one job over another due to their physical form.
•Thus they tend toward a certain set of jobs (or may be capable of only those jobs).
3) Individual - Individual Communication Job Assignment
•For those species with evolved communication skills, one individual may recruit another, via direct communication, to help with a certain job.
•We have applied these concepts to a variety of technology problems, such as distributed data storage in a computer network, and the creation and management of ad hoc wireless networks.”
4)Environment - Individual Communication Job Assignment
•Stigmergy: a kind of indirect communication and learning by the environment found in social insects is a well known example of self-organization, providing not only vital clues in order to understand how the components can interact to produce a complex patterns as can pinpoint simple biological non-linear rules and means to achieve an improved design of artificial intelligent systems.
Adventages of using Mobile Agents and Stigmentory
1.Scalability
2.Fault tolerance
3.Adaptation
4.Speed
5.Modularity
6.Autonomy
7.Parallelism
Swarm Systems Exhibits
•Multiple lower level competences
•Situated in environments
•Limited time to act
•Autonomous with no explicit control provided
•Problem solving is emergent behaviour
•Strong emphasis on reaction and adaptations
Applications of SI
Theoretical
1.Ant-Based Control: developed for telephone networks.
2.AntNet: Adaptive agent-based routing algorithm
Ant Net
•Routing is determined by complex interactions of forward & backward network exploration agents.
•Forward ants: No node routing updates. They report N/W delay conditions to Backward ants.
•Backward ants: inherit the raw data & update routing table of nodes.
•Entries of routing table are probabilities.
Probabilities serve a dual purpose
1.To decide the next hop to a destination.
2.Data packets deterministically select the path with the highest probability for the next hop.
Actionsin Ant Net
1.Each n/w node launches forward ants to all destinations in regular time intervals
2.Ant finds path to destination based on current routing tables.
3.Forward ants create Stacks, pushing Trip times for every node.
4.When the destination is reached, backward ant inherits the stack.
5.It pops the stack entries & follows path in reverse.
6.Node tables of each visited node are updated based on trip times.
Practical Applications
•UAV (Unmanned Air Vehicle) & Robots
•Business
UAV (Unmanned Air Vehicles) and Robots
Being able to control swarms or teams of UV vehicles could lead to novel peace time applications.
•Fisheries: to track schools of fish or whales in the ocean
•Robots: to explore and clean up hazardous sites
•Pico-satellites: survey asteroid belts and gather scientific information
–Only small simulation exists.
–Formal modeling is currently underway.
–Conceptual development needs to be done.
Business Applications of Swarm Intelligence
“Swarm Intelligence” had been used successfully to address notoriously difficult business problems. Some clients are:
•South West Airlines
•Pina Petroli
•Distribution Centres (“Bucket Brigade”)
Introduction about Swarm Intelligence
•SI is the property of a system whereby the collective behaviors of agents interacting locally with their environment cause coherent functional global patterns to emerge .
•SI provides a basis with which it is possible to explore distributed problem solving without centralized control or the provision of a global model.
•One of the cores tenets of SI work is that often a decentralized, bottom-up approach to controlling a system is much more effective than traditional, centralized approach.
•“Groups performing tasks effectively by using only a small set of rules for individual behaviour is called swarm intelligence.”
•“Swarm Intelligence is a property of systems of non-intelligent agents exhibiting collectively intelligent behaviour.”
•In Swarm Intelligence, “…two individuals interact indirectly when one of them modifies the environment and the other responds to the new environment at a later time.”
Where did the Concept arise?
•For years scientists have been studying about insects like ants, bees, termites etc.
•The most amazing thing about social insect colonies is that there’s no individual in charge. For eg: consider the case of ants.
•But the way social insects form highways and other amazing structures such as bridges, chains, nests and can perform complex tasks is very different: they self-organize through direct and indirect interactions.
Self Organization
•Errors and randomness are not “bugs”; rather they contribute to success by enabling them to discover and explore in addition to exploiting.
•Self-organization feeds itself upon errors to provide the colony with flexibility and robustness..
•A very different mindset from the prevailing approach to software development and managing vast amounts of information: no central control, errors are good, flexibility, robustness (or self-repair).
Characteristics of Social Insects
1.Flexibility
2.Robustness
3.Self-organization
Human beings suffer from a “centralized mindset”; But inserting the human factor into the loop is against SI.
Big Issue
How should we program the individual virtual ants so that the network behaves appropriately at the system level?
There is always a fear of these systems going out of control as there is no central control nor the emergent behaviour of the whole system is predefined only the agents are predefined.
We don’t always know ahead of time what emergent solutions will come out because emergent behaviour is unpredictable.
If applied well, self-organization endows your swarm with the ability to adapt to situations that you didn’t think of.
Characteristics of Self Organizing Behaviour
1.Positive reinforcement
2.Negative reinforcement
3.Amplification of fluctuations
4.Multiple interactions
1.Positive reinforcement
•Many ant species forage for food using a trail-laying trail-following behaviour.
•It is a self-fulfilling prophecy, “ants following pheromone trails will tend to congregate simply from the fact the pheromone density increases with each additional ant that follows”.
•This self- perpetuating mechanism is known as “mass recruitment” and is the primary reinforcement of the foraging behaviour.
Pheramone Trails
•Individual ants lay pheromone trails while travelling from the nest, to the nest or possibly in both directions.
•The pheromone trail gradually evaporates over time.
•But pheromone trail strength accumulate with multiple ants using path.
2.Negative Reinforcement
•Negative reinforcement can be seen in crowding at the food source, limitation of population, or food source exhaustion.
•In case food source exhaustion, then no more pheromone is deposited on the trail. The pheromone currently on the trail will evaporate, eventually falling to zero.
•No pattern is formed if the pheromone signal is too weak.
4.Multiple interactions
•A minimum saturation is required for a pattern to emerge
•Self organization “usually requires a minimal density of mutually tolerant individuals”.
•Each individual should be able to use the results of its efforts and those of nest mates possibly being able to distinguish exactly which individual performed the task.
In order to understand swarm intelligence we have to analyze few questions:
•How are jobs scheduled and assigned?
•How are jobs executed?
•How do individuals choose or change a job?
•How is equilibrium achieved among all individuals for all jobs in the colony?
We can analyze the job assignment strategy as it is the only question which can be give an answer in specifics.
Job Assignment: Four Ways
•Age
•Morphology
•Individual – Individual (I-I) communication
•Environment – Individual (E-I) communication
1) Age Job Assignment
•Among certain social insects, individuals prefer to take certain jobs based on their age.
•With honey bees
– Young workers do hive chores such as building and repairing the hive, ventilation, defense, food preparation, etc…
– Older workers gather nectar, pollen, and water.
•In SI our virtual agents work in the same way older agents will have more updated rules, newer agents will have some specific job.
2) Morphology Job Assignment
•Some individuals may be better suited for one job over another due to their physical form.
•Thus they tend toward a certain set of jobs (or may be capable of only those jobs).
3) Individual - Individual Communication Job Assignment
•For those species with evolved communication skills, one individual may recruit another, via direct communication, to help with a certain job.
•We have applied these concepts to a variety of technology problems, such as distributed data storage in a computer network, and the creation and management of ad hoc wireless networks.”
4)Environment - Individual Communication Job Assignment
•Stigmergy: a kind of indirect communication and learning by the environment found in social insects is a well known example of self-organization, providing not only vital clues in order to understand how the components can interact to produce a complex patterns as can pinpoint simple biological non-linear rules and means to achieve an improved design of artificial intelligent systems.
Adventages of using Mobile Agents and Stigmentory
1.Scalability
2.Fault tolerance
3.Adaptation
4.Speed
5.Modularity
6.Autonomy
7.Parallelism
Swarm Systems Exhibits
•Multiple lower level competences
•Situated in environments
•Limited time to act
•Autonomous with no explicit control provided
•Problem solving is emergent behaviour
•Strong emphasis on reaction and adaptations
Applications of SI
Theoretical
1.Ant-Based Control: developed for telephone networks.
2.AntNet: Adaptive agent-based routing algorithm
Ant Net
•Routing is determined by complex interactions of forward & backward network exploration agents.
•Forward ants: No node routing updates. They report N/W delay conditions to Backward ants.
•Backward ants: inherit the raw data & update routing table of nodes.
•Entries of routing table are probabilities.
Probabilities serve a dual purpose
1.To decide the next hop to a destination.
2.Data packets deterministically select the path with the highest probability for the next hop.
Actionsin Ant Net
1.Each n/w node launches forward ants to all destinations in regular time intervals
2.Ant finds path to destination based on current routing tables.
3.Forward ants create Stacks, pushing Trip times for every node.
4.When the destination is reached, backward ant inherits the stack.
5.It pops the stack entries & follows path in reverse.
6.Node tables of each visited node are updated based on trip times.
Practical Applications
•UAV (Unmanned Air Vehicle) & Robots
•Business
UAV (Unmanned Air Vehicles) and Robots
Being able to control swarms or teams of UV vehicles could lead to novel peace time applications.
•Fisheries: to track schools of fish or whales in the ocean
•Robots: to explore and clean up hazardous sites
•Pico-satellites: survey asteroid belts and gather scientific information
–Only small simulation exists.
–Formal modeling is currently underway.
–Conceptual development needs to be done.
Business Applications of Swarm Intelligence
“Swarm Intelligence” had been used successfully to address notoriously difficult business problems. Some clients are:
•South West Airlines
•Pina Petroli
•Distribution Centres (“Bucket Brigade”)