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 »

An Anecdote to Norbert Wiener

At the end of this post is a funny anecdote about American theoretical and applied mathematician Norbert Wiener. He was a pioneer in the study of stochastic and noise processes, contributing work relevant to electronics and communication engineering. He is also known and probably best known for being the founder of cybernetics.

His 1948 book, Cybernetics: Or the Control and Communication in the Animal and the Machine is a must read though i have not been lucky enough to read it myself as it is very difficult to find. This book is very high on my list of “books that MUST be read”. I wouldn’t be shy in admitting that the single most important reason on why i would want to read it is that this book came as a seminal work in that field! and is considered the authority to this day!

The anecdote to this rather eccentric and great man follows and is as recounted by Howard Eves and is on his forgetful nature:

Norbert Wiener was renowned for his absent-mindedness. When he and his family moved from Cambridge to Newton his wife, knowing that he would be of absolutely no help, packed him off to MIT while she directed the move. Since she was certain that he would forget that they had moved and where they had moved to, she wrote down the new address on a piece of paper, and gave it to him. Naturally, in the course of the day, some insight occurred to him. He reached in his pocket, found a piece of paper on which he furiously scribbled some notes, thought it over, decided there was a fallacy in his idea, and threw the piece of paper away in disgust.

At the end of the day he went home – to the old address in Cambridge, of course. When he got there he realised that they had moved, that he had no idea where they had moved to, and that the piece of paper with the address was long gone. Fortunately inspiration struck. There was a young girl on the street and he conceived the idea of asking her where he had moved to, saying, “Excuse me, perhaps you know me. I’m Norbert Wiener and we’ve just moved. Would you know where we’ve moved to?” To which the young girl replied, “Yes Daddy, Mommy thought you would forget.”

In later posts i will try to write on cybernetics and Wieners work as a follow-up and will try to read that book as soon as possible! :)

Read Full Post »

The Working of a Bird Swarm

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 »

Morphogenesis and Swarm Robotics

Here is an amazing video!

Something about this video first from the you-tube information about it.

An introduction to swarm intelligence, swarm robotics and morphogenesis. This video won the Best Video award at the AAAI-07 conference Vancouver Canada. The scientific research was performed by Anders Lyhne Christsensen, Rehan O’Grady and Marco Dorigo. The video was directed by Andreia Onofre.

Swarm Intelligence is an AI technique that is based on the collective behavior of decentralised and self organised systems. Take an ant colony for example, an ant hill is an extremely complex structure, with even things like temperature control in place. It is difficult to imagine a simple ant doing any of it! So it is basically the “swarm” of ants that is responsible for such emergent and intelligent solutions though the “constituents” of the systems (i.e ants) are simple and independent “units”. Like ants also can pick up prey many times their weight by forming very precise structures encircling the object under consideration.

like in the picture below the ants take up a comparatively much heavier fly.

photo credit with full regards : here>>

The video basically explains the same and also gives an idea on how it could be done using robots. For example a bird swarm can make very different and complex shapes depending on the set of rules under use (which in turn will depend on the scenario). I will accompany this statement by a post on a bird swarm and how they do it sometime soon. If you change the set of rules you could change the shape you get, and most of these shapes could be used to perform some intelligent task. This gives the swarm a lot of flexibility. This is basically what is Morphogenesis.

Morphogenesis could be used by a swarm of robots to move heavy objects (as an illustration to this have a look at this video, in which a group of robots pull away a child. The video can be seen here>>) which could be used in fire-fighting applications etc, to bridge gaps etc. A swarm of nano-bots could use morphogenesis to perform very specific tasks inside the human body!

Please have a look at this award winning video!

I personally thank and congratulate the director of this video for putting it all so succinctly in a matter of under 5 minutes.

Read Full Post »

On Concepts and Lego

Quoting Swarm Intelligence and emergent systems guru Vitorino Ramos (1997)

“People should learn how to play Lego with their minds. Concepts are building bricks”

This happens to be one of my favorite quotes! I am sure all Lego lovers would or do love it!

Photo Credit: Here>>

Read Full Post »

What would Feynman do?

Here is a hilariously true flowchart of Feynmans decision making process from WellingtonGrey

Click to Enlarge

—

Related Posts on This Blog:

1. Richard Feynman: Sciences Elvis

2. The Feynman Principle

3. Smart Man, Wise man, Feynman!

Read Full Post »

A Chip in Your Body

Some months ago i was a part of an IEEE community development program, organized by the power electronics society. It required us to travel to villages and semi-urban schools and give seminars on wireless communications to school children. Our aim was not only to try give them something new and extra from the school curricula, but also fire up their imagination in thrust areas so as to try and motivate them to take up a career in science and technology.

After the session on mobiles and how they worked and taking all sorts of questions (literally :D) from the students on the same. I (and my other group members) tried to give a picture of how wireless communications might be like in a vector of another 5 decades. In giving so i gave the example of Kevin Warwick, the genius but also highly criticized (by some sections) University of Reading professor of Cybernetics.

Something from his work through the wikipedia entry on him.

Probably the most famous piece of research undertaken by Warwick is the set of experiments known as Project Cyborg, in which he had a chip implanted into his arm, with the aim of “becoming a cyborg”.

The first step, involved a simple RFID transmitter being implanted beneath Warwick’s skin, and used to control doors, lights, heaters, and other computer-controlled devices based on his proximity. The main purpose of this experiment was said to be to test the limits of what the body would accept, and how easy it would be to receive a meaningful signal from the chip.

The second stage involved a far more complex chip, and which interfaced directly into Warwick’s nervous system. The electrode array inserted contained around 100 electrodes, of which 25 could be accessed at any one time, whereas the median nerverobot arm developed by Warwick’s colleague, Dr Peter Kyberd, was able to mimic the actions of Warwick’s own arm.

By means of the implant, Warwick’s nervous system was connected onto the internet in Columbia University, New York. From there he was able to control the robot arm in Reading University and to obtain feedback from sensors in the finger tips. He also successfully connected ultrasonic sensors on a baseball cap and experienced a form of extra sensory input.

There have been experiments time and again that have proved the ability to convert the power of thoughts into action, this could not only someday aid in communicating truly “wirelessly” or almost “telepathically” but will also might help paralysed people walk and help forgetful people remember common stuff like where thy kept car or bike keys among other almost countless possibilities. Researchers, scientists etc like the idea of a chip implanted in the body for improvement, but is the general public ok with it and what could be the social implications? It is not clear what the general public think of chip implants for self-improvement i.e for non-medical reasons. In medical cases such as Alzheimer’s chip implants could really help the patient in storing medical information.

I read something on essentially the same theme in the economic times some weeks back. Of which i happily took a clipping! :)

Experiences of those who have experimented with embedded chips give some clues to how useful these could be for the masses. In one instance an American physician tried to study the medical legal, moral and privacy aspects of an embedded device.

The implantation of a RFID chip in his upper right arm was a five minute painless procedure. There were no physical side effects like itching or changes in skin appearance. The implant enabled the physician to carry out routine functions without any hindrance and the chip was not detected by airport scanners or metal detectors, making live easy.

However, when the physician entered a retail store, the device set off anti-theft alarms, as it worked at the same frequency as the retail security systems! Thankfully the stores haven’t forced him to strip naked to ensure that he wasn’t stealing anything. While he didn’t experience any medical changes even after the chip was in the body for over two years, risks are there. These include infection and pain.

However non-medical risks may be more acute. The physician started receiving e-mails that he had lost some of his humanity and was a human-machine hybrid. Also, chips run the risk of being scanned by an unidentified person and can infringe on privacy by giving a third party access to an individual’s information like medical records.

He concluded that perhaps the best non-medical use could be as a source of secure identity and a store of personal records, for people given to forgetting things frequently. Indeed if chips could help reduce identity related financial frauds, the devices could help check over $5 billion a year of such frauds that individual consumers suffer annually, according to the US Federal Trade Commission.

As pointed out in the above excerpt, chip implants could take hacking up one more level in which a clone of the implant could be made and misused! There are many ethical issues raised by various religious organizations. There could be some previously unimagined downsides like divorces with one partner leaving the other for someone with a “better” chip ;)

The medical advantages however, make it look very promising!

In the future as embedding RFID chips or other smart chips in the human body grows the debate in this concern will only hot up!

Read Full Post »

Doppler Effect

Back in 11th grade i used to cycle 10kms to listen to some lectures given by an old Physics professor, Mr M.L.Ogalapurkar, he has easily been one of the best professors who has taught me physics. So i would absolutely love the two hours spent there every Friday and Saturday.

One fine day he taught us Doppler effect and took some problems, then extended the concept to include the asymmetric effect i.e in light.
Then he took a simple question. This is question number 5.233 in I.E Irodov which says –
(i have the 1988 edition of “problems in general physics“)
“How fast should a car move for the driver to perceive a red traffic light as a green one?”
on reading this question his face lighted up and he put down the book. Slowly took the chair (he limps) and started.

There was this physics professor, he always got late. So as usual this fine morning he was late again, so he just took one Physics book – his favourite and threw it in his car and sped off to the university.
Now late, he knew he was over-speeding and hoped no cops stop him. Just as he hoped he broke a traffic light in his hurry. He could see it was red but ignored it as anyway the roads were empty. Just as he was starting to get a relaxed look on his face on breaking the signal, a cop signaled him to stop and then he had to.
The cop said “Sir, you have broken the signal, i must ticket you”.
the professor thought for a minute and his hand moving towards the wallet stopped and then he thought
“this is a police cop what will he know about physics?” and he said
“Officer, i have not broken any signal, i saw the traffic signal as Green not as Red”
The Cop: “Well are you trying to kid me? how is that possible”
Professor: “Blame physics for it, see equation 17.68 here in this book makes this possible and i just experienced it! If you travel fast enough then the frequency appears altered and Red appears Green”
now confused the cop said “Well, i don’t know but i can’t let you go just like that, you can say all this in the court”

in the courtroom the judge asked him the same thing.
“Professor i got a complaint that you broke the signal?”
the professor gave the same answer as he gave to the cop.
the Judge too got confused, and said
“i have no qualification in Physics so i can’t really say anything on this. i shall consult some qualified person and then pass the judgment”
and just as he was to adjourn the proceedings a person seated there got up and said
“Judge, i am a qualified person and i am working in the JPL, will you consider my opinion”
the judge saw his i-card and said
“your opinion may be considered as valid as you are qualified to have an opinion on this”
the JPL scientist then said “Sir, the professor is absolutely right! this effect is called the Doppler effect and it happens”
and then he gave him the example of a whistling train.
The judge still not convinced says “Well but how does that make a Red signal appear Green?”
The scientist got up and took the Physics book the professor was carrying, using equation 17.68 he worked out the problem and then showed the judge his calculations!
he said “judge, see this is possible i have worked out that a Red signal will appear green when the car is moving at almost thirty percent of ‘c’. and so the professor is absolutely right!”
the judge studies the problem and then speaks out

“well. professor you are absolved of the charge that you broke a signal”
The professor now very relieved gets ready to leave, just as he turns..
the judge speaks out

“but you have exceeded the speed limit!”

*SIGH*

PS: I do not know the exact source for this joke, i just remember Dr M.L.Ogalapurkars words and obviously not exactly as how he told me.

Read Full Post »

The Turing Test – I

Via BBC-h2g2:

A test for artificial intelligence suggested by the mathematician and computer scientist Alan Turing. The gist of it is that a computer can be considered intelligent when it can hold a sustained conversation with a computer scientist without him being able to distinguish that he is talking with a computer rather than a human being.

Some critics suggest this is unreasonably difficult since most human beings are incapable of holding a sustained conversation with a computer scientist.

After a moments thought they usually add that most computer scientists aren’t capable of distinguishing humans from computers anyway.

:D

xkcd makes it even better with a cartoon on it. I love xkcd ! ;)

Read Full Post »

On Assumptions

Quoting Freeman Dyson FRS

In desperation I asked Fermi whether he was not impressed by the agreement between our calculated numbers and his measured numbers. He replied, “How many arbitrary parameters did you use for your calculations?” I thought for a moment about our cut-off procedures and said, “Four.” He said, “I remember my friend Johnny von Neumann used to say, with four parameters I can fit an elephant, and with five I can make him wiggle his trunk.” With that, the conversation was over.

Source: “A meeting with Enrico Fermi” in Nature 427 (22 January 2004), p. 297

Read Full Post »