Feeds:
Posts
Comments

Posts Tagged ‘Decentralized Systems’

There are four distinct advantages in using self organized, emergent, decentralized or “swarm intelligent” systems [1], these are in fact the benefits of a social insect colony as well. We see these colonies as the inspiration to developing artificial decentralized systems.

  1. Flexible: The system can react to internal and external changes.
  2. Robust: Tasks are completed even if some individuals fail
  3. Decentralized: There is no central control over the system
  4. Self Organized: Paths to solutions are emergent rather than pre-defined which leads to better utilization of resources and gives a dynamic character to the solution finding process.

Ants Behavior, Stigmergy and cues in Routing
Ants are very simple insects but collectively they can perform complex tasks with good consistency. Examples of such complex problem solving behavior have been documented, and a few examples are as follows.

  1. Building nests (ant hills) and maintenance.
  2. Regulating nest ambient temperature fluctuations very low and maintaining required levels of oxygen with small variations.
  3. Co-operating in carrying large prey.
  4. Finding the shortest routes from the nest to the food.
  5. Prefentially exploiting the richest food source available.

Stigmergy refers to communication indirectly, by using markers such as pheromones in ants. In the above examples, two distinct types of stigmergy are observed. One is called sematectonic stigmergy, it involves a change in the physical environment characteristics. An example of sematectonic stigmergy is nest building wherein an ant observes a structure developing and adds its ball of mud to the top of it. Another form of stigmergy is sign-based and hence indirect. Here something is deposited in the environment that makes no direct contribution to the task being undertaken but is used to influence the subsequent behaviour that is task related.

Here is an example of what sematectonic stigmergy can achieve (one has to keep in mind that individual termites are very simple creatures):

stigmergy1.jpg

Sign based stigmergy is very highly developed in ants. Ants use chemicals called as pheromones to develop a very sophisticated signaling system. Ants foraging for food lay down some pheromone which marks the path that they follow. An isolated ant moves at random but an ant encountering a previously laid trail will detect it and decide to follow it with a high probability and thereby reinforce it with a further quantity of pheromone. Since the pheromone will evaporate the lesser used paths will gradually vanish. We see that this is a collective behaviour.

The foraging behavior in ants can be best understood with the following illustrations.

Two ants start with equal probabilities of going on either path.

picture1.png

Ant taking the “lower” path has a shorter to and fro time from the nest to the food.

picture2.png

picture3.png

The pheromone density on the path traversed by ant on the lower path is greater because of the two passes by that ant on this path. Hence other ants say C and D are bound to follow this path because of the stronger scent.

picture6.png

Over many iterations many ants start using this path thus further reinforcing it and after a while this path i.e the shorter path is almost exclusively used.

So we see how randomness is followed by “positive feedback” which causes amplification and the consequent exclusive use of the shortest path. This is an apt example of how ants choose shortest paths.

Now if the shorter path is blocked or unavailable, then in this scenario the longer route may still be used and made the preferred route by repeated use(positive feedback) and the consequent amplification.

By repeated use of the other path, the pheromone concentration here gets stronger that leads to that path being used. Thus this is how ants develop a solution when a path is blocked. Thus this illustrates how swarm intelligent systems adapt with changes in the environment.

Mathematically we put the above as : Suppose the distance between two points i and j is dij and τij is the pheromone concentration on the link ij. Suppose ‘m’ agents are traversing this link and building a tour. At each step of the tour, the probability to go from one point ‘i’ to another point ‘j’ is (τij)a (dij)-b .

After building a tour of length L each agent reinforces the edges it has used by an amount proportional to 1/L. Also the pheromone evaporates such that τà(1-ρ)τ.

The above is used to solve the traveling salesman problem as well. There are a few key concepts that we gather from the above illustrations.

A) Positive feedback – build a solution using local solutions, by keeping good solutions in memory.

B) Negative feedback – want to avoid premature convergence, evaporate the pheromone.

C) Time scale – number of runs are also critical.

These key points then in turn can be summed up for an ant colony as very simple rules: lay pheromone, and follow trails of other ants.

Applications to Routing Scenarios
Routing is the mechanism that handles and directs messages at switching stations. The important points we see are that messages must reach their destinations, it should take as little time as possible to reach from source to destination, and also the traffic is constantly changing hence routing should adapt accordingly. The inspiration for using the example of ants for routing in communications networks arises from the fact that the present routing systems depend upon global information for their efficient operation. Ant systems on the other hand, rely on pheromone traces that are laid down in the network as the ant moves through the network. Global information is frequently out of date and transmission of the information required from one node to all others consumes considerable network bandwidth. Ideally, we would like to have the network adapt routing patterns to take advantage of free resources and move existing traffic if possible.

Now if we consider a telephone network. A telecommunication environment is highly unpredictable. With delays or problems when least expected at times. Suppose a phone call is made form Mumbai to Shanghai. This phone call has to go through several intermediate steps/nodes such as maybe Kolkatta and Bangkok etc. such a system requires a routing mechanism that will tell the call where it should hop next to establish a connection, a good routing technique as we have already listed would minimize this time (ants finding shortest path) and avoid congestions. Backup routes are very important in such a system. In some special circumstances when there is an explosion or if there is a news programme that requires calling, then it leads to localized surges in the phone traffic. This then requires the phone traffic to be re routed to the less congested parts of the network (ants adapting and finding an alternative path).

This can be simulated as follows. Hordes of agents can roam the network and leave bits of information which can be thought of as an analogous to pheromone to reinforce paths through uncongested areas. Phone calls are then routed by following the trails of these ants like agents. To exactly mimic the ants working, these “pheromones” can be evaporated by a certain mechanism by a rate that may be decided by certain considerations. Now if suppose a certain path that was very swift becomes congested then the agents to this route can be delayed by certain time spans. This time span will allow the virtual pheromone to evaporate and thus reinforcement process can be overcome. Hence after a while this route is abandoned. The ant-like agents (as seen above) can discover new paths to re-route the traffic. The advantages of such a system are: the calls get forwarded at a good speed and also the congested areas gradually get de congested. Also the bucket brigade process makes the routing process more robust.

A detailed approach to ant based routing has been described by White (1996)[2]. Such systems have three types of agents: explorers, allocators and deallocators. Explorer agents mimic the foraging behaviour of ants and follow trails of pheromones laid down by previous explorers (as quantitatively described in the Mumbai- Shanghai phone call example). Allocator agents move across the paths determined by explorer agents and allocate the bandwidth on the links used in the path. Similarly, when the path is no longer required deallocator agents traverse the path and deallocate the bandwidth used on the links.
References:

[1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artifcial Systems. NY: Oxford Univ. Press, 1999.

[2] White A.R.P., Routing with Ants, Nortel internal report, 1996.

Advertisement

Read Full Post »

This post is following the previous post in which i mentioned about the rules governing the motion of a bird swarm.

The video below is a breathtaking, sublime, amazing recording of thousands of starlings in a flock before roosting. This is from the UK country-side. While it is another awesome demonstration of how the “imagination” of nature can be like, it also gives a perfect example of how the entire swarm is organized and how it moves. Modern researchers are trying to imitate such emergent behavior to use in fields like robotics, data mining, internet mathematics, optimization etc etc.

How do birds exactly do this?

Here is an excerpt from a talk that i had given at a technical event in October ’07.

In a swarm if we say that there are ‘N’ number of agents, then we can say that these autonomous agents are in a way co-operating to achieve a global objective. This global objective can be better foraging, constructing shelter, serving as a defence mechanism among others. This apparent collective intelligence emerges from very simple individual agents. The actions of these agents are governed by local rules and through the interactions of the N agents the swarm achieves a global objective. A kind of “self organization” emerges in these systems. We see that there is no central controller in such cases. Swarm intelligence gives a basis which makes it possible to explore collective (or distributed) problem solving without centralized control or without the provision of a global model. [1]

The individual (but autonomous) agent does not follow directives from a central authority or work according to some global plan. As a common example, a bird in a flock, only adjusts its movements to coordinate with the movements of its flock mates or more precisely the members that are its neighbors. It simply tries to stay close to its neighbors, but avoid collisions with them. Each bird does not take commands from any leader bird since there is no lead bird. Any bird can fly anywhere in the swarm, either in the middle or the front or the back of the swarm. Swarm behavior gives the birds some distinct advantages like protection from predators, and searching for food (effectively in a swarm each bird is exploiting the eyes of every other bird). Scientists are trying to find out how these birds, fish etc move in flocks, schools in a way that appears orchestrated. A school of fish and a flock of birds move as if all the “steps” were pre planned. For one moment they are moving towards the left and in another they are darting towards the right. Among these researchers in 1987, Reynolds created a boidor bird-oid (bird like) model. This is a distributed behavioral model, to simulate the motion of a flock of birds on a computer [2]. Each boid is implemented as an agent which moves according to its own understanding of the dynamic environment. A boid observes the following rules. First, is that a boid must move away from boids that are too close, so as to reduce the chance of collisions. Second, boid must fly in the general direction that the flock is moving. Third, a boid should minimize exposure to the flock’s exterior by moving toward the perceived center of the flock. Flake later [3] added a Fourth rule, a boid should move laterally away from any boid that blocks its view. This boid model seems reasonable if we consider it from another point of view, that of it acting according to attraction and repulsion between neighbors in a flock. The repulsion relationship results in the avoidance of collisions and attraction makes the flock keep shape, i.e., copying movements of neighbors can be seen as a kind of attraction.

This is what i was talking about in the previous post. A certain set of rules is followed that would give a certain shape to the swarm, if the set is altered so will be the shape and maybe functionality as well!

Sounds nice, now how can these simple rules be modeled on a computer? They can be done using NetLogo. Here is a sample model . To get a good idea about the intricacies adjust the population, the turn angles and the vision. For playing around with the model and making your own you are instructed to go through the writeup to this model on the above page.

References:

[1] E. Bonabeau, M. Dorigo, and G. Theraulaz, Swarm Intelligence: From Natural to Artifcial Systems. NY: Oxford Univ. Press, 1999.

[2] C. Reynolds, ‘Flocks, herds, and schools: A distributed behavioral model,” Comp. Graph, vol. 21, no. 4, pp. 25{34, 1987.

[3] G. Flake, The Computational Beauty of Nature. Cambridge, MA: MIT Press, 1999.

Read Full Post »