Columns

Swarm Intelligence

• By John D. Williams
• September 1, 2001

In the past, I've done work with agent technology to explore its value in building IT applications. Recently, that work has taken an interesting turn. In previous columns, I've talked about understanding systems and in particular the interactions that cause unexpected behavior.

I've been doing some work with systems that depend on this emergent behavior for their functionality. What happens when you use agents that aren't too bright, but their collective behavior is useful? Nature shows us some successful precedents for systems of this type. In the agent world, this is known as swarm intelligence.

Nature is a great place to go for inspiration when you want to see systems that are robust and have been around for millions of years. Nature provides the inspiration for swarm intelligence. Look at the emergent behavior observed in ants, termites, bees and others. We see very simple creatures, performing complex behavior as a group. How does this work and how does this help us with swarm intelligence?

Consider the Lasius Niger ant. Biologists have observed these ants form bridges and raid specific areas for food as a group. They build and protect their nests. They sort their brood and food items. These ants cooperate in carrying large items and in the emigration of a colony. They will find the shortest route from nest to food source and will preferentially exploit the richest food source available. How do creatures as simple as ants perform such complex behavior as a group?

We call this type of behavior swarm intelligence. Gerardo Beni—a professor and researcher at the University of California, Riverside—first defined swarm intelligence as "a property of systems of non-intelligent robots exhibiting collectively intelligent behavior." That's a good start for our thinking, but what are the characteristics of a swarm that are important for our agents? Swarms are distributed and have no central control or data source. The agents of a swarm must be capable of sensing their environment and perceiving changes in it. These agents must also have the ability to change their environment.

Swarm systems are basically examples of behavior-based systems. They have low-level agents with minimum competency. These agents are placed in a specific environment and have a limited time to act. Each agent acts autonomously; there is no central control. The problem solving nature of the swarm comes from its emergent behavior. The system emphasis is on adaptation and reaction.

So how do these agents interact in their environment and communicate? Ants may use direct communication when they touch legs or antennae, but they typically communicate indirectly with one another through the environment. This indirect communication is called stigmergy. There are two basic types of stigmergy. With sematonic stigmergy, the action of an agent is directly related to problem solving and the agent's behavior affects the behavior of other agents. For example, an ant may orient itself in a certain way to stimulate other ants to begin building a bridge. There is also sign-based stigmergy. In this case, the agent does something that affects the environment, that is not directly related to problem-solving behavior. We see this behavior when ants find food.

Ants are unsophisticated in their behavior, yet together they perform complex tasks. One mechanism they have to assist in this behavior is a sophisticated sign-based stigmergy. Essentially, ants communicate using pheromones. Trails of pheromone are laid down by a given ant, which can be followed by other ants. Depending on the species, ants lay trails traveling from the nest, to the nest or possibly in both directions. The pheromones evaporate over time. Pheromones also accumulate with multiple ants using the same path. The end result of this stigmergy is a stronger trail laid to food sources. As those sources are depleted, the trails evaporate and new ones will be built as new sources of food are discovered. How complicated do ants have to be for this behavior to emerge? Let's look at a natural agent system implemented as software.

Ants finding and bringing food back to the nest can be thought of as path planning. The system behavior we see shows that ants construct networks of paths that connect nests and food sources. The networks form minimum spanning trees. We know that graph theory defines algorithms for computing minimum spanning trees. Ants do not use these conventional algorithms. Instead, their optimal path structure emerges from the simple actions of the individual ants.

For this to work, ants need six basic rules, which are:

1. The ants avoid obstacles.
2. They wander about randomly.
3. If an ant is holding food, it drops pheromones at a constant rate as it walks.
4. If an ant finds itself at food and is not holding any, it picks up the food.
5. If an ant finds itself at the nest and is carrying food, it drops it.
6. If an ant is searching for food and comes upon a pheromone trail, it follows it toward the food.

How does this system work? Because only food-carrying ants drop pheromone, and because ants can carry food only after picking it up at a food source, all pheromone paths lead to a food source. Paths tend to merge together into a trace that becomes straighter the more it is used.

This approach to optimal paths has already been used successfully in telephone switching. Imagine you are in New York and you are calling someone in Los Angeles. What path will your call use to reach the other person? At different times, some lines or switches may be bogged down with traffic while others are wide open. Experiments have been done using ant path-finding techniques to find the shortest route through the telephone network.

Another interesting example of swarm intelligence can be found with termites. Tropical termites can build mounds more than 15 feet high and 10 tons in weight. These mounds are multi-story structures that provide storage for food, house the brood and protect the population. In spite of the mound's complexity, there is no chief architect or engineer in charge of the construction.

These mounds can be built using four simple rules:

1. The termites metabolize bodily waste, which contains pheromones.
2. They wander randomly, but prefer the direction of the strongest local pheromone concentration.
3. At each step, they decide stochastically whether to deposit the current load of waste.
4. The probability of making a deposit increases with the local pheromone density.

What is the result of this behavior? The stochastic algorithm leads to the generation of scattered initial deposits. These deposits attract visitors and increase the probability that these visitors will make reinforcing deposits. The most recent deposits at the center of the pile are the strongest and piles tend to grow upward rather than outward, forming columns. When columns grow near, the scent of each attracts termites of the other, thus pulling subsequent deposits into the shape of an arch. A similar dynamic works to form floors joining multiple arches. When one floor is complete, the cycle repeats to construct the next. Pretty amazing behavior from such a simple set of rules.

Swarm intelligence has been used in a number of interesting applications. It has optimized delivery for trucking companies using different size trucks and different types of loads. This approach has been used to train neural networks for analyzing tremors in patient's hands. Swarm intelligence has found the best combination of moves for end milling in machining with multiple heads. A utility company has used this approach to help control voltage. Another company has used it to do battery voltage charge estimation for electric carts. There are other applications as well, and we are certain to hear about more over time.

So what have we learned from the behavior of these systems? Are there new design principles that would help us build better swarm intelligence systems? We've learned that agents, like good objects, should match things in the problem domain rather than be abstract functions. Agents should be small in size, time and scope. They should be decentralized. This avoids creating systems with a single point of failure. Agents should be diverse in nature. We've also learned that randomness and repulsion are important tools for establishing and maintaining this diversity. Finally, agents should plan and execute concurrently rather than sequentially.

Swarm intelligence is one approach to agents that seems to hold promise in several areas. Various types of optimization problems have already benefited from this approach. The study of these systems also helps us understand emergence and the interaction of systems. I also believe the design principles we learn from these systems can help us build better IT systems. After all, like nature, we need our systems to be robust and adaptable. While swarm intelligence is still a new field of exploration, I believe we will hear more of this concept in the future.