Feeds:
Posts
Comments

Archive for January, 2008

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.

Advertisements

Read Full Post »

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!

norbert_wiener_3.jpg

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 »

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 »

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

greentreeant.jpg

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)

vramos.jpg

“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 »

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

What would Feynman do?

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 »

This post is as a follow-up to the previous post.

If Idoya could talk she would have plenty to boast about!

On Thursday, the 12-pound, 32-inch monkey made a 200-pound, 5-foot humanoid robot walk on a treadmill using only her brain activity.

“They should be able to move the arm with their thoughts,” he said. “This is science fiction coming to life.”

0115-sci-robota_large.jpg

The complete news about the pivotal event can be read here>> complete with videos and pictures. The above illustration is also credited to the NY times. I would recommend the complete article!

Read Full Post »

Older Posts »