Swarm Intelligence Stigmergy And Computer Networking

Swarm Intelligence Stigmergy and Computer Networking By Martin Roth [email protected] Cornell University Tuesday, November 14, 2000

Computer Communication (Reality) Data can be difficult to send between computers. • • • •

connections are faulty transmission speeds vary delay is accumulated at every node all communication requires energy

Computer Communication (Utopia) Ideally, a computer network should be able to solve its functional requirements… • • • •

maximum packet delay minimum throughput minimum quality of service minimum network lifetime

…autonomously.

Network Control Computer network control may be: •

Centralized; problems are addressed at one master node

•

Distributed; problems are solved collectively by all nodes in the network

Social Insect Analogy In both social insect colonies and computer networks: • • •

Simple constituent elements must work in conjunction with others in order to survive. Individuals are not useful alone. The larger the group, the more powerful.

Swarm Intelligence (SI) In social insect colonies, a “disembodied intelligence” seems to direct the individuals in the swarm for the scheduling of necessary jobs, and in each individual job. How can this swarm intelligence be harnessed by a computer network to direct its operations and fulfill its service requirements?

Necessary Questions In order to understand swarm intelligence: • • • •

How are jobs scheduled and assigned? How are jobs executed? How do individuals choose or change a job? How is an equilibrium achieved among all individuals for all jobs in the colony?

No complete answers to these questions exist.

Job Assignment There are four ways in which a job may be assigned to an individual: • Age • Morphology • Individual – Individual (I-I) communication • Environment – Individual (E-I) communication

Age Job Assignment Among certain social insects, individuals prefer to take certain jobs based on their age. With honey bees1: •

•

Young workers do hive chores such as building and repairing the hive, ventilation, defense, food preparation, etc… Older workers gather nectar, pollen, and water.

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)2. In the Pheidole species of ant, Major workers with larger mandibles cut prey or defend the nest. Minor workers feed the brood or clean the nest. However, both sets are capable of overtaking the other’s jobs.

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. Honey bees do this with their waggle dance in order to recruit others in the hive to collect more nectar or water.

Environment – Individual Communication Job Assignment E-I communication is also known as: • Stigmergy • Sematectonic communication As defined by Swarm Intelligence3, “…two individuals interact indirectly when one of them modifies the environment and the other responds to the new environment at a later time.”

Stigmergy in Computer Networks Returning from the social insect analogy, • • •

How can stigmergy be used to control nodes in a network? How can swarm intelligence arise in networks relying on stigmergy for communication? Can such methods solve global issues?

A Termite Hill Stigmergy How can stigmergy be used to solve a complex problem? How can a distributed system coordinate its efforts on a global goal? Ants build nests… Wasps and Bees build hives… Termites build hills…

A Termite Hill Stigmergy Given a flat surface, some pebbles, and a few termites… • • • • •

Termites walk randomly over the surface, picking up pebbles and dropping them near others as they go. Each pebble is infused with a pheromone. Eventually a cluster of pebbles of critical size will be created. Each pebble has pheromone. All termites bring pebbles to that cluster, increasing size and pheromone content. The beginnings of a hill are made.

A Termite Hill Stigmergy The building process has two major phases: • •

Random walk (uncoordinated phase) Coordinated Phase

Phase transition is accounted for by positive feedback from cluster size and pheromone content.

A Termite Hill Stigmergy Note that if not enough termites exist, the pheromone will decay before a cluster of critical size is created. No hill will be built and the termites will die. A critical number of individuals are required for “intelligence” to arise.

A Termite Hill Stigmergy Unbounded building is controlled by negative feedback from additional responsibilities or stimuli on a particular individual. More complex construction is afforded by consulting a list of instructions and the local geography. This list is an evolved trait that is species dependant and yields specific architectures.

Stigmergy Summary • • • • •

Stigmergy is a type of Swarm Intelligence No direct communication takes place between individuals. Information is communicated through the state or changes in the local environment. For any job, an individual decides the next action based on a simple algorithm. Bottlenecks are designed into the algorithm such that prerequisites are ensured for future work.

Stigmergy in Networks Idea How should computer networks be designed to exhibit swarm intelligent behavior? How can stigmergy be used? Two approaches: • Software agents travel around the network, altering aspects of their environment (nodes in the network) in order to improve system performance. • Each network node is an agent itself, unable to move, but can communicate locally in order to instigate global actions that will improve its own performance.

Stigmergy in Networks Research Both approaches will require the balancing of positive and negative feedback. How should this be done? It is unclear what local actions produce what global effects. Is it possible to predict or design emergent properties in large systems? Stigmergy may be slow. Waiting for local actions to affect a global problem may cause severe problems during intermediate stages. How can the speed of the solution or information propagation be controlled?

Conclusions • • • •

•

Swarm Intelligence may be a useful technique for distributed control of a computer network. SI requires a large number of participating elements. It may be difficult to find the correct local actions matching necessary global effects. Stigmergy may allow for reduced network control traffic, while allowing for a robust global control mechanism (SI). Network specific application of SI is just beginning, there is a long way to go!

References 1. Bee Biology and Society 2. p.2, Swarm Intelligence; Bonabeau, Doringo, Theraulaz, 1999 3. p.14, Swarm Intelligence; Bonabeau, Doringo, Theraulaz, 1999