// The Song Remains The Same

(This is a thread of an ongoing series on Self Organization; The first article was Emergence, and the preceding article was Self Organization and Social Insects.)

In this article I want to explore discovery in social insects as it is a critical mechanic given that individuals in a colony have little beyond local perception yet employ decentralized discovery in an uncertain environment to survive. In articles that led up to this one I talked a lot about the principles of self organization and how they drive the decentralized activities of social insects, using techniques such as stigmergy and positive / negative feedback. Here I want to further expand on how stigmergy and feedback can drive discovery in natural systems such as social insects and begin to set the foundation for other lines of thought in terms of where decentralized discovery can be employed.

If you will recall from a previous article, we have established stigmergy as

…a method of communication, albeit in an indirect fashion, between two units or agents. Stigmergy is defined as information gathered from work in progress.

Indirect communication via “work in progress” could be achieved in many ways, but to isolate the concept in a concrete example, I want to look at foraging mechanics in ant colonies for the purposes of this article. The ant colony functions as a single machine, as a single organism; It is dependent on no single ant and can afford to lose individuals as long as it doesn’t lose a critical mass of its population, much the same as an organ in your body can lose cells as long as it doesn’t lose too much of its overall tissue.

An ant colony needs food or fuel just like any other animal or organism. Ants do not feed in an individual manner, but actively forage for quality food sources and bring these food sources back to the colony for processing. Just like most processes in an ant colony, foraging is a highly decentralized yet collaborative behavior. Amazingly enough, an ant colony has a system in place to continuously load balance the number of ants doing each type of task (forage, midden, defense, etc) with no central or hierarchical control directing those efforts (the mechanics of this are covered in the Swarm Intelligence book [1] by Marco Dorigo, and is a topic I want to touch on in a later article.)

There are multiple issues facing a colony during foraging:

• Before a food source can be retrieved, it must be discovered.
• Not all food sources are equal in value; how does the colony best deploy its resources to retrieve the most food in the shortest time?
• How does one ant communicate to the rest of the colony where a food source is located, and how do the other ants determine which food source to go after?

Let’s tackle the first issue of food source discovery; From a cold start where no ants have emerged from the nest, ants leave the nest in an exploratory walk in random directions. Ants have very limited vision and can only detect chemicals in their local area at each step, so a random walk for them can be fairly precarious. Now, at each step the ant lays down a small trace amount of pheromone to mark the trail taken. Pheromone is a key component to how stigmergy and ant colonies operate, and I liken it to the bread crumps left to mark a trail in the forest — just like animals will tend to eat some of the bread crumbs over time, pheromone evaporates over time. Eventually an ant will stumble upon a crumb of a cookie or other food source, and after determining it is an acceptable resource for the colony (taste test?), the ant will head back towards the nest.

Now, your first questions is “how is this simple agent going to get home with the food?” and this is where that pheromone chemical comes into play, and on many levels. At each step, the ant makes a directional decision in terms of where to go next. It has been shown in many experiments [1] that an ant is highly influenced to take a step in a direction that has pheromone, although it is still probabilistic — but just like in vegas, the odds win over time. The ant will find its way back home on its invisible trail of pheromone. Now, a subtle thing happens on the way back to the nest — the ant lays a more intense pheromone chemical at each step, reinforcing the trail back towards the food source. Now, a connection has been made for the colony between nest and food source, but we aren’t done. The colony has multiple food sources (hopefully) to harvest at all times, yet limited resources and time to invest in them; how does the colony best approach this issue?

As each ant moves out to forage over time it tends to take high pheromone paths, and as it has success, it lays even more pheromone on the return trip. High quality food sources very quickly have high intensity pheromone trails leading right to them (ever wonder why ants seem to know where all your good sugary food is, and they just keep coming?). Many aspects of these mechanics have been studied by biologists and scientists, breaking down the various properties of how the ants move into sets of equations. One of my early experiments was to see if I could replicate the foraging raid patterns pictured in the Swarm Intelligence book. My efforts are pictured to the right where I put together an openGL simulation of ants moving across a simulated world with random placement of different quality of food sources.

The image itself is nice, but watching the simulated colony explore and exploit various concentrations of food sources is very interesting, as you can see the colony “sample” various food sources and then tend to focus on a few relative to distance vs quality of the source. The positive feedback of adding pheromone to the landscape is balanced by the negative feedback of the evaporation of the pheromone. The evaporation of pheromone keeps the colony from converging on a suboptimal solution too quickly, and allows the colony to continually evaluate food sources based on quality vs distance. The colony is constantly using the mechanics of stigmergy to communicate in a decentralized manner and get the best yield on its foraging efforts while considering obstacles, resources, and load balancing.

As ants have been studied to understand their mechanics, these same principles and techniques have been applied to similar problems in other domains. A very early simulation that allowed the user to create rules for a set of agents in a simulation (which also employed pheromone as a form of stigmergy) is StarLogo by Mitchel Resnick at MIT. There have been many papers written on applying basic forms of swarm algorithms to the Traveling Salesman Problem, the quadratic problem, and other classical computer science benchmarks. As the field has become more mature, it has been used in data mining, search, and routing in networks.

The specific mechanics of discovery via stigmergy in swarm algorithms is being explored in many ways today. Particle Swarm Optimization (Kennedy and Eberhart, Indiana) is a specialized algorithm that uses many groups of agents which roam search space, communicating their best found solutions and influencing one another in how they “flock” through search space. One of the most interesting aspects of the technique is how it is robust in uncertain conditions that continually change, something that traditional search techniques have a very hard problem with. This has led to much research in swarm algorithms applied to network routing, such as algorithms like AntNet [2]. Swarm algorithms are very good at finding things under fairly chaotic conditions. In a near future article we are going to take a look at just how self organization, stigmergy, and discovery can be applied to ad hoc networks.

So we’ve seen some basic action of an ant colony in action and how it uses decentralized discovery in a very elegant and robust way. We’ve also alluded to the fact that much research is being done in various areas of computer science in the application of swarm intelligence, a field that I have been interested in and working in for a few years now. A new area that I have been working in is the auto discovery of linked data on the web, and ways to link up sets of decentralized services outside the normal mechanics of wiring directly to a single site api. This has led me to begin asking myself many questions, as I see so many parallels between today’s emerging linked data ecosystem, a very uncertain world, and the metaphors that have been extracted from ant colonies and swarm mechanics in general. A few things I want to take a look at in coming articles are:

• How does today’s web relate to an organic ecosystem?
• How can we apply some techniques such as dynamic discovery to the web in ways that make sense?
• What are other areas of similar swarm research application that we can take a look at and apply to linked data?
• How can we use self organization to make our systems more robust?

Today the internet is the most advancement interconnection of information we’ve ever known, but connecting distributed sources of data and finding what you want still remains troublesome in certain cases. Google talks about wanting to organize the world’s information as their mission, but isnt all that data in one “logical” place too much centralization? What if somehow data could self organize and emerge as if it lived in a biological ecosystem? In my graduate research I worked on the application of swarm algorithms to wireless mesh networks where decentralized discovery was a key component; As I move through this series of articles I want to draw parallels to how the ideas in the ad hoc network domain can be applied to the open linked data web, conceptually the “ad hoc web”.

My next few articles will touch on various aspects of discovery in other technologies such as ad hoc networks (my grad research on TinyTermite), indexes, and linked web data. I will pose more questions than I can answer in the short term, but mainly I want to address “what could the ad hoc web be?” and “how do we make our data and preferred services a little more decentralized, keeping them out of central gatekeepers, and in our control?” — and then follow some arcs of thought to see where that takes us.

References

[1] E. Bonabeau, M. Dorigo, G. Theraluz, Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press, 1999.

[2] Di Caro G., Dorigo M., “Two Ant Colony Algorithms for Best-Effort Routing in Datagram Networks” , Proceedings of PDCS’98 - 10th International Conference on Parallel and Distributed Computing and Systems, Las Vegas, Nevada, October 28-31, 1998, (also Technical Report IRIDIA 98-09).