Chemoton § Vitorino Ramos’ research notebook

Well just a fortnight or so back I discovered that Dr Radford Neal, one of the top researchers in Statistics and Machine Learning was blogging. And today morning I discovered Dr Vitorino Ramos has been blogging for over a week now too!

This comes as a surprise, but a very pleasant one. I am very glad to have found his page, it promises to be a very different Web-Log and could indeed grow into one of the top blogs on Swarming, Self-Organization, Complexity and Distributed Systems as it would be by a leading expert in the field. It would be great to catch up on his work. In the past I have tried to write on some of his interesting work on my own page. My posts can be found here.

[Vitorino Ramos: Image Source]

Dr Ramos’ research areas are chiefly in Artificial Life, Artificial Intelligence, Bio-Inspired Computing, Collective Intelligence and Complex Systems. He obtained his PhD in 2004 and has published about 70 papers in the above fields and their broad application areas. So put simply it can be said that the IQ of the “blogosphere” has gone up a little with this addition.

For starters I would recommend his article on Financial Markets (given the situation today), talking about the herd mentality and the resulting amplification in dumb investors and its results and what it could result in. Most investors do not understand much of the market mechanism. This is a bare fact put most aptly in this cartoon I found on his blog, and his post goes much beyond that.

[Image Source]

Click to Enlarge

And going by the website and blog name, it seems that Dr Ramos is now interested in some sense in Tibor Ganti’s Chemoton Theory.

—

Quick Links:

1. Vitorino Ramos’ Homepage.

2. Dr Ramos’ Publications. (PDFs available online)

—

Onionesque Reality Home >>

Read Full Post »

Kafka to Red Ant: A Strange Metamorphosis

Before I make a start I would want to make it very clear that inspite of what that the title may suggest, this is not a “sensational” post. It is just something that really intrigued me. It basically falls under the domain of image segmentation and pattern recognition, however it is something that can intrigue a person with a non-scientific background with a like (or dislike) for Franz Kafka’s work equally. I keep the title because it is the title of an original work by Dr Vitorino Ramos and hence making changes to it is not a good thing.

Note: For people who are  not interested in technical details can skip those parts and only read the stuff in bold there.

Franz Kafka is one writer whose works have had a profound impact on me in terms that they disturbed me each time I thought about them. No, not because of his writings per se ONLY but for a greater part because i had read a lot on his rather tragic life and i saw a heart breaking reflection in his works of what happened in his life (i see a lot of similarities between Kafka’s life and that of Premchand albeit that Premchand’s work got published in his lifetime mostly, though he got true critical acclaim after his death). Yes i do think that his writings give a good picture of Europe at that time, on human needs and behavior, but the prior reason outweighs all these. Kafka remains one of my favorite writers, though his works are basically short stories. He mostly wrote on a theme that emphasized the alienation of man and the indifferent society. Kafka’s tormenting thoughts on dehumanization, the cruel world, bureaucratic labyrinths which he experienced as being part of the not so liked Jewish minority in Prague, his experiences in jobs he did, his love life and affairs, on a constant fear of mental and physical collapse as a result of clinical depression and the ill health that he suffered from, reflected in a lot of his works. Including in his novella The Metamorphosis.

W. H Auden rightly wrote about Kafka:

“Kafka is important to us because his predicament is the predicament of the modern man”

In metamorphosis the protagonist Gregor Samsa turns into a giant insect when he wakes up one morning. It is kind of apparent that the “transformation” was meant in a metaphorical sense by Kafka and not in a literal one, mostly based on his fears and his own life experiences. The Novella starts like this. . .

As Gregor Samsa awoke one morning from uneasy dreams he found himself transformed in his bed into a monstrous vermin.

—

While rummaging through a few scientific papers that explored the problem of pattern recognition using a distributed approach i came across a few by Dr Ramos et al, which dealt with the issue using the artificial colonies approach.

In the previous post i had mentioned that the self organization of neurons into a brain like structure and the self organization of an ant colony were similar in more than a few ways. If it may be implemented then it could have implications in pattern recognition problems, where the perceptive abilities emerge from the local and simple interactions of simple agents. Such decentralized systems, a part of the swarm intelligence paradigm look very promising in applying to pattern recognition and the specific case of image segmentation as basically these may be considered a clustering and combinatorial problem taking the image itself as an ant colony habit.

The basis for this post was laid down in the previous post on colony cognitive maps. We observed the evolution of a pheromonal field there and a simple model for the same:

[Evolution of a distribution of (artificial) ants over time: Image Source]

Click to Enlarge

The above is the evolution of the distribution of artificial ants in a square lattice, this work has been extended to digital image lattices by Ramos et al. Image segmentation is an image processing problem wherein the regions of the image under consideration may be partitioned into different regions. Like into areas of low contrast and areas of high contrast, on basis of texture and grey level and so on. Image segmentation is very important as the output of an image segmentation process may be used as an input in object recognition based scenarios. The work of Ramos et al (In references below) and some of the papers cited in his works have really intrigued me and i would strongly suggest readers to have a look at them if at all they are interested in image segmentation, pattern recognition and self organization in general, some might also be interested in implementing something similar too!

—

In one of the papers a swarm of artificial ants was thrown on a digital habitat (an image of Albert Einstein) to explore it for 1000 iterations. The Einstein image is replaced by a map image. The evolution of the colony cognitive maps for the Einstein image habitat is shown below for various iterations.

[Evolution of a pheromonal field on an Einstein image habitat for t= 0, 1, 100, 110, 120, 130, 150, 200, 300, 400, 500, 800, 900, 1000: Image Source]

The above is represented most aptly in a .gif image.

[Evolution of a pheromonal field on an Einstein habitat: Image Source]

Now instead of Einstein a Kafka image was taken and was subject to the same. Image Source

The Kafka image habitat is replaced by a red ant in the second row. The abstract of the paper by the same name goes as.

Created with an Artificial Ant Colony, that uses images as Habitats, being sensible to their gray levels. At the second row,  Kafka is replaced as a substrate, by Red Ant. In black, the higher levels of pheromone (a chemical evaporative sugar substance used by swarms on their orientation trough out the trails). It’s exactly this artificial evaporation and the computational ant collective group synergy reallocating their upgrades of pheromone at interesting places, that allows for the emergence of adaptation and “perception” of new images. Only some of the 6000 iterations processed are represented. The system does not have any type of hierarchy, and ants communicate only in indirect forms, through out the successive alteration that they found on the Habitat.

Now what intrigues me is that the transition is extremely rapid. Such perceptive ability with change in the image habitat could have massive implications at how we look at pattern recognition for such cases.

Extremely intriguing!

—

Resources on Franz Kafka:

1. A Brief Biography

2. The Metamorphosis At Project Gutenberg. Click here >>

3. The Kafka Project

References and STRONGLY recommended papers:

1. Artificial Ant Colonies in Digital Image Habitats – A Mass behavior Effect Study on Pattern Recognition. Vitorino Ramos and Filipe Almeida. Click Here >>

2. Social Cognitive Maps, Swarms Collective Perception and Distributed Search on Dynamic Landscapes. Vitorino Ramos, Carlos Fernandes, Agostinho C. Rosa. Click Here >>

3. Self-Regulated Artificial Ant Colonies on Digital Image Habitats. Carlos Fernandes, Vitorino Ramos, Agostinho C. Rosa. Click Here >>

4. On the Implicit and the Artificial – Morphogenesis and Emergent Aesthetics in Autonomous Collective Systems. Vitorino Ramos. Click Here >>

5. A Strange Metamorphosis [Kafka to Red Ant], Vitorino Ramos.

Onionesque Reality Home >>

Read Full Post »

Colony Cognitive Maps

Some posts back, i posted on Non-Human Art or Swarm Paintings, there I mentioned that those paintings were NOT random but were a Colony Cognitive Map.

This post will serve as the conceptual basis for the Swarm Paintings post, the next post and a few future posts on image segmentation.

Motivation: Some might wonder what is the point of writing about such a topic. And that it is totally unrelated to what i write about generally. No! That is not the case. Most of the stuff I write about is related in some sense. Well the motivation for reading thoroughly about this (and writing) maybe condensed into the following:

1. The idea of a colony cognitive map is used in SI/A-life experiments, areas that really interest me.

2. Understanding the idea of colony cognitive maps gives a much better understanding of the inherent self organization in insect swarms and gives a lead to understand self organization in general.

3. The parallel to colony cognitive maps, the cognitive maps follow from cognitive science and brain science. Again areas that really interest me as they hold the key for the REAL artificial intelligence evolution and development in the future.

—

The term “Colony Cognitive Map” as i had pointed earlier is in a way a parallel to a Cognitive Map in brain science (i use the term brain science for a combination of fields like neuroscience, Behavioral psychology, cognitive sciences and the likes and will use it in this meaning in this post ) and also that the name is inspired from the same!

There is more than just a romantic resemblance between the self-organization of “simple” neurons into an intelligent brain like structure, producing behaviors well beyond the capabilities of an individual neuron and the self-organization of simple and un-intelligent insects into complex swarms and producing intelligent and very complex and also aesthetically pleasing behavior! I have written previously on such intelligent mass behavior. Consider another example, neurons are known to transmit neurotransmitters in the same way a social insect colony is marked by pheromone deposition and laying.

[Self Organization in Neurons (Left) and a bird swarm(Below).  Photo Credit >> Here and Here]

First let us try to revisit what swarm intelligence roughly is (yes i still am to write a post on a mathematical definition of the same!), Swarm Intelligence is basically a property of a system where the collective actions of unsophisticated agents, acting locally causes functional and sophisticated global patterns to emerge. Swarm intelligence gives a scheme to explore decentralized problem solving. An example that is also one of my favorites is that of a bird swarm, wherein the collective behaviors of birds each of which is very simple causes very complex global patterns to emerge. Over which I have written previously, don’t forget to look at the beautiful video there if you have not done so already!

Self Organization in the Brain: Over the last two months or so i had been reading Douglas Hofstadter’s magnum opus, Gödel, Escher, Bach: an Eternal Golden Braid (GEB). This great book makes a reference to the self organization in the brain and its comparison with the behavior of the ant colonies and the self organization in them as early as 1979.

[Photo Source: Wikipedia Commons]

A brain is often regarded as one of the most if not the most complex entity. However if we look at a rock it is very complex too, but then what makes a brain so special? What distinguishes the brain from something like a rock is the purposeful arrangement of all the elements in it. The massive parallelism and self organization that is observed in it too amongst other things makes it special. Research in Cybernetics in the 1950s and 1960s lead the “cyberneticians” to try to explain the complex reactions and actions of the brain without any external instruction in terms of self organization. Out of these investigations the idea of neural networks grew out (1943 – ), which are basically very simplified models of how neurons interact in our brains. Unlike the conventional approaches in AI there is no centralized control over a neural network. All the neurons are connected to each other in some way or the other but just like the case in an ant colony none is in control. However together they make possible very complex behaviors. Each neuron works on a simple principle. And combinations of many neurons can lead to complex behavior, an example believed to be due to self-organization. In order to help the animal survive in the environment the brain should be in tune with it too. One way the brain does it is by constantly learning and making predictions on that basis. Which means a constant change and evolution of connections.

Cognitive Maps: The concept of space and how humans perceive it has been a topic that has undergone a lot of discussion in academia and philosophy. A cognitive map is often called a mental map, a mind map, cognitive model etc.

The origin of the term Cognitive Map is largely attributed to Edward Chace Tolman, here cognition refers to mental models that people use to perceive, understand and react to seemingly complex information. To understand what a mental model means it would be favorable to consider an example I came across on wikipedia on the same. A mental model is an inherent explanation in somebody’s thought process on how something works in the spatial or external world in general. It is hypothesized that once a mental model for something or some representation is formed in the brain it can replace careful analysis and careful decision making to reduce the cognitive load. Coming back to the example consider a mental model in a person of perceiving the snake as dangerous. A person who holds this model will likely rapidly retreat as if is like a reflex without initial conscious logical analysis. And somebody who does not hold such a model might not react in the same way.

Extending this idea we can look at cognitive maps as a method to structure, organize and store spatial information in the brain which can reduce the cognitive load using mental models and and enhance quick learning and recall of information.

In a new locality for example, human way-finding involves recognition and appreciation of common representations of information such as maps, signs and images so to say. The human brain tries to integrate and connect this information into a representation which is consistent with the environment and is a sort of a “map”. Such spatial (not necessarily spatial) internal representations formed in the brain can be called a cognitive map. As the familiarity of a person with an area increases then the reliance on these external representations of information gradually reduces. And the common landmarks become a tool to localize within a cognitive map.

Cognitive maps store conscious perceptions of the sense of position and direction and also the subconscious automatic interconnections formed as a result of acquiring spatial information while traveling through the environment. Thus they (cognitive maps) help to determine the position of a person, the positioning of objects and places and the idea of how to get from one place unto another. Thus a cognitive map may also be said to be an internal cognitive collage.

Though metaphorically similar the idea of a cognitive map is not really similar to a cartographic map.

Colony Cognitive Maps: With the above general background it would be much easier to think of a colony cognitive map. As it is basically a analogy to the above. As described in my post on adaptive routing, social insects such as ants construct trails and networks of regular traffic via a process of pheromone deposition, positive feedback and amplification by the trail following. These are very similar to cognitive maps. However one obvious difference lies in the fact that cognitive maps lie inside the brain and social insects such as ants write their spatial memories in the external environment.

Let us try to picture this in terms of ants, i HAVE written about how a colony cognitive map is formed in this post without mentioning the term.

A rather indispensable aspect of such mass communication as in insect swarms is Stigmergy. Stigmergy refers to communication indirectly, by using markers such as pheromones in ants. 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 behavior that is task related. 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 behavior.

Now we assume that in an environment the actors (say for example ants) emit pheromone at a set rate. Also there is a constant rate at which the pheromone evaporates. We also assume that the ants themselves have no memory of previous paths taken and act ONLY on the basis of the local interactions with pheromone concentrations in the vicinity. Now if we consider the “field” or “map” that is the overall result and formed in the environment as a result of the movements of the individual ants over a fixed period of time. Then this “pheromonal” field contains information about past movements and decisions of the individual ants.

The pheromonal field (cognitive map) as i just mentioned contains information about past movements and decisions of the organisms, but not arbitrarily far in the past since the field “forgets” its distant history due to evaporation in time. Now this is exactly a parallel to a cognitive map, with the difference that for a colony the spatial information is written in the environment unlike inside the brain in the case of a human cognitive map. Another major similarity is that neurons release a number of neurotransmitters which can be considered to  be a parallel to the pheromones released as described above! The similarities are striking!

Now if i look back at the post on swarm paintings, then we can see that the we can make such paintings, with the help of a swarm of robots. More pheromone concentration on a path means more paint. And hence the painting is NOT random but is EMERGENT. I hope i could make the idea clear.

How Swarms Build Colony Cognitive Maps: Now it would be worthwhile to look at a simple model of how ants construct cognitive maps, that I read about in a wonderful paper by Mark Millonas and Dante Chialvo. Though i have already mentioned, I’ll still sum up the basic assumptions.

Assumptions:

1. The individual agent (or ant) is memoryless.

2. There is no direct communication between the organisms.

3. There is no spatial diffusion of the pheromone deposited. It remains fixed at a point where it was deposited.

4. Each agent emits pheromone at a constant rate say .

Stochastic Transition Probabilities:

Now the state of each agent can be described by a phase variable which contains its position and orientation . Since the response at any given time is dependent solely on the present and not the previous history, it would be sufficient to specify the transition probability from one location to another place and orientation an instant later. Thus the movement of each individual agent can be considered roughly to be a continuous markov process whose probabilities at each and every instance of time are decided by the pheromone concentration .

By using theoretical considerations, generalizations from observations in ant colonies the response function can be effectively summed up into a two parameter pheromone weight function.

This weight function measures the relative probabilities in moving to a site with the pheromone density .

Another parameter may be considered. This parameter measures the degree of randomness by which an agent can follow a pheromone trail. For low values of the pheromone concentration does not largely impact its choice but higher values do.

At this point we can define another factor . This signifies the sensory capability. It describes the fact that the ants ability to sense pheromone decreases somewhat at higher concentrations. Something like a saturation scenario.

Pheromone Evolution: It is essential to describe how the pheromone evolves. According to an assumption already made, each agent emits pheromone at a constant rate with no spatial diffusion. If the pheromone at a location is not replenished then it will gradually evaporate. The pheromonal field so formed does contain a memory of the past movements of the agents in space, however because of the evaporation process it does not have a very distant memory.

Analysis: Another important parameter is the regarding the number of ants present, the density of ants . Thus using all these parameters we can define a single parameter, the average pheromonal field . Where is what i mentioned above, the rate of scent decay.

Further detailed analysis can be studied out here. With the above background it is just a matter of understanding.

[Evolution of distribution of ants : Source]

Click to Enlarge

Now after continuing with the mathematical analysis in the hyperlink above, we fix the values of the parameters.

Then a large number of ants are placed at random positions, the movement of each ant is determined by the probability .

Another assumption is that the pheromone density at each point at is zero. Each ant deposits pheromone at a decided rate and also the pheromone evaporates at a fixed rate .

In the above beautiful picture we the evolution of a distribution of ants on a 32×32 lattice. A pattern begins to emerge as early as the 100th time step. Weak pheromonal paths are completely evaporated and we finally get a emergent ant distribution pattern as shown in the final image.

The Conclusion that Chialvo and Millonas note is that scent following of the very fundamental type described above (assumptions) is sufficient to produce an evolution (emergence) of complex pattern of organized flow of social insect traffic all by itself. Detailed conclusion can be read in this wonderful paper!

References and Suggested for Further Reading:

1. Cognitive Maps, click here >>

2. Remembrance of places past: A History of Theories of Space. click here >>

3. The Science of Self Organization and Adaptivity, Francis Heylighen, Free University of Brussels, Belgium. Click here >>

4.   The Hippocampus as a Cognitive Map, John O’ Keefe and Lynn Nadel, Clarendon Press, Oxford. To access the pdf version of this book click here >>

5. The Self-Organization in the Brain, Christoph von der Malsburg, Depts for Computer Science, Biology and Physics, University of Southern California.

5. How Swarms Build Cognitive Maps, Dante R. Chialvo and Mark M. Millonas, The Santa Fe Institute of Complexity. Click here >>

6. Social Cognitive Maps, Swarm Collective Perception and Distributed Search on Dynamic Landscapes, Vitorino Ramos, Carlos Fernandes, Agostinho C. Rosa.

Related Posts:

1. Swarm Paintings: Non-Human Art

2. The Working of a Bird Swarm

3. Adaptive Routing taking Cues from Stigmergy in Ants

Possibly Related:

Gödel, Escher, Bach: A Mental Space Odyssey

Read Full Post »

Swarm Paintings: Non-Human Art

General Background: Since childhood i have enjoyed sketching and painting, and very much at that! Sometimes i found myself copying an existing image or painting, making small changes here and there in it. Yes, the paintings came out beautiful (or so i think!), but one thing always made me unhappy, i thought that the creativity needed to make original stuff was missing at times (not always). It was not there all the time. It came in bursts and went away.

I agree with Leonel Moura (from his article) that creativity is basically produced due to different experiences and interactions. Absence or lack of which could make art lose novelty.

Talking of novelty, how about looking at art in nature? Richard Dawkins states that the difference between human art or design and the amazingly “ingenious” forms that we encounter in nature, is due tho the fact that Human art originates in the mind , while the natural designs result from natural selection. Which is very true. However it is another matter that natural selection and cultural selection, that will ultimately decide on the “popularity” of an art don’t function in the same way. Anyhow How can we remove the cultural bias or the human bias that we have in our art forms?

.

Answers in Artificial Life: Artificial life may be defined as “A field of study devoted to understanding life by attempting to derive general theories underlying biological phenomena, and recreating these dynamics in other physical media – such as computers – making them accessible to new kinds of experimental manipulation and testing. This scientific research links biology and computer science.”

Most of the A-Life simulations today can not be considered truly alive, as they still can not show some properties of truly alive systems and also that they have considerable human bias in design. However there are two views that have existed on the whole idea of Artificial Life and the extent it can go.

Weak A-Life is the idea that the “living process” can not be achieved beyond a chemical domain. Weak A-life researchers concentrate on simulating life processes with an underlying aim to understand the biological processes.

Strong A-Life is exactly the reverse. John Von Neumann once remarked “life is a process which can be abstracted away from any particular medium“. In recent times Ecologist Tom Ray declared that his computer simulation Tierra was not a simulation of life but a synthesis of life. In Tierra, computer programmes compete for CPU time and access to the main memory. These programs are also evolvable, can replicate, mutate and recombine.

.

Relating A-Life to Art: While researching on these ideas and the fact that these could be used to generate the art forms that i talked about in the first paragraph i came across a few papers by Swarm Intelligence Guru Vitorino Ramos and a couple of articles by Leonel Moura who had worked in collaboration with Dr Ramos on precisly this theme.

.

Swarm Paintings: Thus the idea as i had mentioned in my very first paragraph is to create an organism ideally with minimum pre-commitment to any representational art scheme or human style or taste. Sounds simple but is not so simple to implement!

There are a number of projects that have dealt with creating art, but these mostly have been evolutionary algorithms that learn from human behavior, and learn about human mannerisms and try to create art according to that. The idea here is to create art with a minimum of human intervention.

I came across a project by Dr Vitorino Ramos to which i had pointed out implicitly in the last paragraph. This project called ARTSBOT (ARTistic Swarm roBOTs) project. This project tries to address this issue of minimizing the human intervention in aesthetics , ethnicity, taste,style etc. In short their idea was to remove or to minimize the anthropocentric bias that pervades all our art forms. Obviously all this can have massive implications in our understanding of the biological processes also, however here we’ll talk of only art.

Two of the first paintings that emerged were:

(Source: Here)

(Source: Here)

.

These paintings were among the first swarm paintings by Leonel Moura and Vitorino Ramos. Now we see that these seem detached from a functional human pre-commitment. They don’t seem to represent any emotion or style or taste. However they still look very pleasant!

However the point to be understood and to be noted is that these are NOT random pictures created either by a programme or by a swarm of robots moving “randomly”. These pictures were generated by a horde of artificial ants and also by robots. They are not random, but they EMERGE from a process of pheromone deposition and evaporation as was simulated in this system from ants. Thus the result that we have above is a Colony Cognitive Map. The colony cognitive map is analogous to a cognitive map in the brain. I will cover the idea of a colony cognitive map in the next post.

A couple of more beautiful paintings can be seen below!

(Source for both images : Here>>)

Though i have already mentioned how these art forms emerge, i would still like to quote a paragraph from here:

The painting robots are artificial ‘organisms’ able to create their own art forms. They are equipped with environmental awareness and a small brain that runs algorithms based on simple rules. The resulting paintings are not predetermined, emerging rather from the combined effects of randomness and stigmergy, that is, indirect communication trough the environment.
Although the robots are autonomous they depend on a symbiotic relationship with human partners Not only in terms of starting and ending the procedure, but also and more deeply in the fact that the final configuration of each painting is the result of a certain gestalt fired in the brain of the human viewer. Therefore what we can consider ‘art’ here, is the result of multiple agents, some human, some artificial, immerged in a chaotic process where no one is in control and whose output is impossible to determine.
Hence, a ‘new kind of art’ represents the introduction of the complexity paradigm in the cultural and artistic realm.’

A Painting bot is something like in the picture shown below:

A swarm of robots at work:

The final art generated by the swarm of these robots is beautiful!

(Photo Credit for the three pictures above: Here>>

.

Conclusions:

The work of Dr Ramos and Leonel Maura can be summed up as:

1. The human is only the “art-architect”, the “swarm” is the artist.

.

2. The “life” of Artificial Life shows characteristics like natural life itself namely Morphogenesis, ability to adapt to changing environments, evolution etc.

.

Leonel Moura’s wonderful article states that the final aim is to create an “Artificial Autopoietic System”, intriguing indeed and eagerly awaited!!
Such simulations could change the way we understand the biological processes and life.

Also i am now thinking how could music be produced based on the same or similar ideas. I wonder if Swarm music could be available. It would be most interesting and i can’t wait to listen to it already!

.

Have a look at this video by Leonel Moura, having some time lapse footage of robots painting.

References:

1. Ant- Swarm Morphogenese By Leonel Moura

.

2. On the Implicit and on the Artificial – Morphogenesis and Emergent Aesthetics in Autonomous Collective Systems, in ARCHITOPIA Book, Art, Architecture and Science, INSTITUT D’ART CONTEMPORAIN, J.L. Maubant et al. (Eds.), pp. 25-57, Chapter 2, Vitorino Ramos.

.

3. A Strange Metamorphosis [From Kafka to Red Ant], Vitorino Ramos

.

Links:

Follow the following links to follow on more exciting papers and paintings.

1. Dr Vitorino Ramos

2. Leonel Moura

Onionesque Reality Home >>

Read Full Post »

Altruism in Animals

One of the problems that Swarm Intelligence research faces is a precise definition[1]. Many words that are associated with SI are generally Emergence, Self-Organization, Collective Intelligence etc. There is no general mathematical definition to it yet. This lack of a credible and workable framework has made research in this field ad-hoc. In simple words we need a theory to swarming. Is there a theory to swarming behavior or swarm intelligence? We basically have analogies. There is no theory yet i guess.

There have been efforts to rectify this and i will cover this in a post sometime soon.

However we also definitely need a theory to explain altruism in social insects (In a swarm), in animals or in Humans. I basically got interested in Altruism due to my interest in Swarm Intelligence and social insects.

Why does a honey bee do the ultimate sacrifice and lay down its life when it feels its kin is in danger? Why do walruses adopt orphans? How is it that dogs can adopt off-springs of cats, other dogs, and even tigers? There are scores of examples that show such altruistic behavior.There are variants obviously to the altruism that we are talking about.

Altruism as i have mentioned implicitly is a social behavior. A behavior is social if it has implications for both the actor and the recipient. Social behaviors can broadly be categorized depending on whether the actor or the recipients are benefited. Altruism is the category when the fitness level of the actor is reduced after a action and that of the recipient is increased. A selfish behavior contrasts the above exactly. Other two types are mutually beneficial and spiteful. Mutually beneficial is the type in which the fitness of both are increased and spiteful is the reverse of it.

In The God Delusion, Richard Dawkins summarizes some kinds of altruism and separates them and also gives some explanation.

1. The first kind he points out is altruism towards our kin, with individuals with whom we have common genes. The honey bee example in most probability fits into this “category”. Also like how we are evolved to be kind towards our kids. The genes that “code” for such behavior towards our kins people who share genes with us are more likely to survive. This is given by Hamilton’s Kin Selection Theory[2]. It states that altruism is favored when:

Where “c” is the fitness cost to the altruist, “b” is the fitness benefit to the recipient and “r” is a measure of their genetic relatedness.

2. The second kind is reciprocal altruism. The example of a buffalo / crow pair fits in here. This form does not require any sharing of genes. Individuals from VERY different species can actually exist in a symbiotic relationship through this altruistic form. Each individual contributes something that the other individual can not obtain on its own. Within a species, like in us humans, this trait has become more specific and has evolved into the form that we tend to do good to people who do/ can do good things for us.

3. Dawkins then also talks about the importance of building a good reputation.

4. One of the most interesting reasons that he mentions and which is very true IMO is that excessive altruism may be a show of superiority in some manner. That is that it can be because the person can afford to be “altruistic” This can in some way be understood as a payoff in a game theory scenario.

One interesting approach to the questions above is discussed in a nice paper that i read over the past week.

In this paper the two researchers, in their model consider a large and panmictic (unstructured) population where individuals interact pairwise in successive rounds.

Assumptions:

1. Number of rounds of interaction for an individual follows a geometric distribution with a parameter ω, which is a probability that an individual will interact with an individual after a round of interaction.
2. The Focal Individual can interact with two classes of individuals, one closely related genetically to it and the other not so closely related.
3. X is the probability of interacting non-randomly with an individual of the related class.
4. 1-X is the complimentary probability. 1− X interactions occur randomly with any member of the population.

All repeated rounds of interactions take place with the same partner. During each round of interaction the FI invests I• into helping with I• varying between 0 and 1. This investment incurs a cost CI• to the FI and generates a benefit BI• . A fraction ζ of the benefit generated by helping directly return to the FI and the complementary fraction 1−ζ goes to the partner[3].

The fecundity of FI can either be positive or negative depending on the value of the term:

ζBI• – CI•

The fecundity of the partner will always be positive unless the FI gets all the benefit of the act (i.e. ζ=1 ) or if it does not invest in helping at all (I• = 0). We noted earlier that the FI is interacting with two classes of individuals. And therefore the fecundity with both these classes of individuals will be different.

To generalise the relative fecundity of the FI interacting with a j class individual will be given by:

We assume that the individual follows a “tit for tat” kind of a approach i.e. that the investment level into helping at a given round depends linearly on the partner’s investment at the previous round. Hence, the investment depends on three traits:

1. the investment on the first round τ
2. The response slope β on the partner’s investment for the preceding round.
3. The memory m (varying between zero and one) of the partner’s investment at the preceding round.

“m” is the probability of not making an error in assignment by considering that a partner has not co-operated in the previous move when he infact has. τ and β can evolve. The paper gives a well put and terse presentation of the idea to generate a formula and then considers cases when co-operation and when altruism can evolve. I highly recommend this paper. It is a wonderful paper and a must read! I thoroughly enjoyed it. It can be obtained here.
The same problem has also been approached by Richard Dawkins comprehensively in the following video that was shown on the BBC. This video has been obtained courtesy of richarddawkins.net

In the video Dawkins starts off with how his seminal book “The Selfish Gene” was misunderstood and how it lead to the phrase “Nice Guys Finish Last”, this phrase was coined by Garrett Hardin to sum up the selfish gene idea. Then how do these “nice guys/altruistic agents” survive? Should not have natural selection wiped them off? Dawkins then argues that the idea of selfish genes can actually give rise to co-operative and altruistic behavior*. It leads to the development of a pre-wired programme or strategy for achieving some desired goal. This is analogous to human strategy in situations. Dawkins then moves to game theory and gives a wonderful explanation of the Prisoners Dilemma and concepts like the tragedy of the commons and tries to explain how altruistic behavior (coupled with a tit for tat kind learning behavior) can actually fetch best pay-offs. It is this “selfish” advantage that actually leads to altruistic behavior. And finally suggests that Hardin’s idea could be slightly modified after this analysis to “Nice Guys Finish First”, which also is the name of the programme.
To sum up, this wonderful video leads to the same conclusion in part as the paper described above does.

That is that the following conditions lead to the evolution of
altruism and cooperation :

1. Direct benefits to the individual performing a cooperative act.

2. Direct or indirect information allowing a better than random guess about whether a given individual will behave cooperatively in repeated reciprocal interactions.

3. Altruism or cooperation can evolve if the cost-to-benefit ratio of altruistic and cooperative acts is greater than a threshold value. The cost-to-benefit ratio can be altered by coercion, punishment and policing which therefore act as mechanisms facilitating the evolution of altruism and cooperation. [3] Dawkins explained this idea by the PD example in the video.

However integrating the four ideas mentioned at the start of the post is a problem. Can it be possible to do so? This can have massive implications in understanding social insect behavior and swarm intelligence among many others.

* Co-operative behavior may not always be altruistic.

References:

[1] Foundations of Swarm Intelligence: From Principles to Practice, Mark Fleischer, Institute for Systems Research, University of Maryland College Park.

[2] The genetical evolution of social behaviour. Hamilton, W. D. 1964. I. Journal of Theoretical Biology 7:1-16.

[3] The evolution of cooperation and altruism. A general framework and a classification of models. Laurent Lehmann and Laurent Keller.

Onionesque Reality Home >>

Read Full Post »

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 »

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 »

NetLogo Version 4.0.2 Released

Something that would make the AI and Swarm Intelligence enthusiast smile.

The latest version of NetLogo was released on December 05, 2007 and can be downloaded from here for free, i know i am late. But i just discovered that the new version was here! I am sure the people who have used it before must be very glad with the upgrade as i am!

For starters, NetLogo is a multi-agent programmable modeling environment and can be used to study/model emergent phenomenon. NetLogo was authored by Uri Wilensky, director of the CCL of the Northwestern University in 1999. It was authored in the spirit of the Logo programming language to be “low threshold and no ceiling”.

The Wikipedia page on Netlogo puts the usage of it very tersely!

It is particularly well suited for modeling complex systems developing over time. Modelers can give instructions to hundreds or thousands of independent “agents” all operating concurrently. This makes it possible to explore the connection between the micro-level behavior of individuals and the macro-level patterns that emerge from the interaction of many individuals.

Happy Modelling! ;)

Of related interest : StarLogo

Read Full Post »