Adaptive Routing taking Cues from Stigmergy in Ants

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):

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.

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

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.

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 d_ij 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 (d_ij)^-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.

Read Full Post »