Swarm Intelligence

Swarm Intelligence

Nature harbours a wide variety of intelligent species. Humans tend to believe that they embody the ultimate form of intelligence, but generally speaking they also agree that more creatures can be labeled intelligent to some extent. In their habitat, animals and humans share the ability to respond to inputs from their surroundings, explore their environment, memorize information, and learn from events. These abilities constitute what we call intelligent behavior.

Scientists have long been trying to mimic this intelligent behavior, leading to the establishment of artificial intelligence. This field has given rise to a variety of software and hardware capable of behaving intelligently. In analogy to natural intelligence, this includes responding to sensory inputs, exploring different behaviors, storing information in memory, and even learning from the outcome of actions. Subjects of artificial intelligence research include neural networks (simulating brain functions), genetic algorithms (simulating evolution by natural selection), fuzzy logic (reasoning with linguistic terms), and reinforcement learning (simulating learning from experience).

Apart from these individual forms of intelligence, there is also such a thing as collective swarm intelligence. Swarm intelligence entails the intelligent behavior of groups of individuals that may in themselves have only a very limited intellectual capacity. A good example is the behavior of ant colonies. While individual ants have only very limited capabilities of sensing their environment, making decisions, and storing information, the colony as a whole is very capable in these respects. In this article, we will discuss the main principles of swarm intelligence and how inspiration from natural swarms has led to the development of engineered swarms.

Collective Behavior in Nature

The main mechanism for swarm intelligence is that the collective behavior of the individuals in a swarm benefits the survival or reproduction of these individuals. In nature we see examples of this collective behavior all around us, such as flocks of birds, schools of fish, clouds of insects, herds of antelopes, groups of humans, and some say even the cells in a body. This latter example is not as strange as it might seem when we realize how on a larger scale, swarms appear to behave like a single organism.

Swarms emerge from the interactions of their members. While the behavior of the individuals is encoded in their DNA and possibly also in their memory, the behavior of the swarm as a whole is encoded in its members and in the interactions between them. On a micro scale, the swarm behaves chaotically, even though the behavior of the individuals is very simple. Swarms can be more effectively studied on a macro scale, where the individuals appear to act as one. The magic of swarms lies in the simple set of rules dictating the behavior of each swarm member, inducing complex and seemingly disordered behavior from the interaction of the members on a micro scale, but producing understandable and ordered behavior of the swarm on a macro scale. This is called self-organization.

The key concepts in swarm intelligence are emergent behavior and self-organization. We have so far implicitly assumed that all individuals are the same, and are only initialized differently. We call such swarms homogeneous. On the other hand, if one or more individuals are different from the rest, the swarm is called heterogeneous. Most swarms in nature are more or less homogeneous. However, with some types of insects, for instance with ants, the individuals may be different from each other in both physical characteristics and in their functions within the swarm. The soldier ants are much stronger than the workers (all female), and they are both different from the males, whose only task is to inseminate the queen. The workers may have different tasks, and also switch between these tasks; some are occupied with building the nest, some with nurturing the larvae, and some with foraging for food. If a substantial source of food is found, other worker ants are recruited to switch to foraging. If the nest has been damaged, other workers may be recruited to help repair the nest. A colony of ants is thus a heterogeneous swarm, while a school of fish is generally a homogeneous swarm.

Swarm Intelligence in Engineering and Computer Science

The exact same principles of swarm intelligence in nature can be used in engineering swarms that can be of use to humans. The basic idea of an engineered swarm is that it consists of a set of cooperating autonomous individuals, also called agents. These agents try to satisfy their own objectives through cooperation with other agents. Communication and coordination are central to achieving this, but are often limited to a certain range, so that cooperation between agents only takes place locally.

Engineered swarms have certain advantages that make them useful for applications in artificial intelligence. These advantages relate to scalability, robustness, flexibility, and production costs. Scalability means that individuals may be added to the swarm without the need of more resources in all other individual agents. The key factor here is that individuals typically have a limited range of interaction, so that the introduction of a new individual only directly influences the behavior of a few others and not that of the whole swarm. Indirectly though, through communication within the swarm, the new individual may influence all the others, but this can only be achieved through a series of interactions between others in the swarm.

With respect to robustness, the limited range of interaction prevents the malfunctioning or removal of a single individual from influencing the complete swarm instantly. If well designed, the individuals within the range of the faulty one may compensate for its malfunctioning behavior, or replace it completely by taking over its functionality. The rest of the swarm will only be influenced in a much-reduced manner. Flexibility means that the swarm may adapt to different circumstances. A well-designed robot swarm may in one situation spread out in order to explore an unknown territory, while in another situation when they face a wide gap that a single individual would not be able to cross, they may physically connect, helping each other to the other side of the gap.

The fourth main advantage of engineered swarms is that when such a swarm typically consists of many similar individuals, these may be produced in series, reducing the cost per unit. These costs may already be quite low, as individuals in a swarm are typically relatively simple and can sometimes even be built using cheap components, because of the robustness property described earlier.

Of course the main difficulty in engineering swarms is that we must design the individuals and the specifics of their interaction in such a way that the resulting behavior on the global level is as desired. This is a challenging difficulty and it is the central question in all research on engineering swarm intelligence. It is however not the only difficulty. An important question is how to mathematically guarantee performance. How to test a swarm and measure its performance? How do delays in communication and errors propagate through a swarm, and how does this influence behavior? How do external influences (disturbances) affect the swarm?

There are a lot of opportunities for engineering swarms. One may think of a swarm of satellites, dynamically optimizing their coverage for observing the earth, for providing communication, or for global positioning. Other swarms of space vehicles could be deployed to explore unknown regions of space, or planets. On Earth, a swarm of rescue robots could be developed to rescue people in inaccessible places, such as in a tunnel filled with smoke. In traffic, cars might be understood as swarm members and the overall performance of the traffic network might be improved by self-organization of the vehicles. The engineering of swarms, however, does not have to be limited to the physical world. Various classes of swarm intelligence algorithms have been developed for solving various types of optimization problems. In these problems, the swarms operate in a virtual world, called the optimization or parameter space, in which their objective is to find the parameter values that optimize a certain cost function. The most prevalent swarm intelligence optimization methods are particle swarm optimization and ant colony optimization.

Particle Swarm Optimization

In many optimization problems, the size of the search space rapidly increases with the number of variables and the range of the values they can take. Finding an optimum in these search spaces quickly becomes an intractable problem, due to what is referred to as the curse of dimensionality. This curse means that adding one variable doubles the time needed to find the optimum. One can imagine that this quickly gets out of hand when several variables are present in the optimization problem. Rather than finding the absolute optimal solution, optimization heuristics have been developed to find sufficiently good solutions in a short time. Swarm intelligence presents a class of such heuristics. Particle swarm optimization, or PSO, has been developed to solve multidimensional optimization problems. In analogy to a flock of birds, PSO casts the optimization problem in a parameter space, through which a number of particles fly. However, as opposed to birds, which fly in a three-dimensional space, the space through which the particles move can be of arbitrary dimension. The particles search this space on a local level for good solutions. They keep one another updated as to the best solutions found so far and attract each other to the more promising regions of the search space. Altogether, this results in the swarm coming closer to achieving the goal as time progresses and eventually finding the optimal solution.

Ant Colony Optimization

The basis for ant colony optimization has been the double bridge experiment, in which ants forage for food and must choose between two branches of a bridge. This experiment has demonstrated that ants find the shortest paths in a distributed manner by communicating through chemical trails, called pheromone trails. A shorter path results in a faster accumulation of pheromones, which biases other ants to choose that same path as well.

After the publication of the results of the double bridge experiments, it did not take long before researchers realized that the problem of finding shortest paths, which ants had so elegantly solved, was related to many very difficult problems in computer science, namely those known as combinatorial optimization problems. Perhaps the best-known example of such a problem is the traveling salesman problem. In this problem, the task is to find the shortest tour in a graph, visiting all nodes exactly once and finishing in the starting node. This relates to a salesman who needs to travel to a number of cities and return home in time for dinner. He needs to find the optimal tour in order to optimize his travel time. It is generally believed that the time and resources required for finding the solution to such a problem grow exponentially for a linearly increasing number of nodes in the graph. The class of algorithms that was developed is called ant colony optimization, or ACO, and has proven to be very successful in solving a wide variety of combinatorial optimization problems. Examples of the application of ACO to real-world problems are the optimization of travel times for trucks and the optimization of routing internet data traffic.

Concluding Remarks

In this article, we have argued that intelligent behavior in nature is a great source of inspiration for scientists and engineers. The focus has been on swarm intelligence, the way in which the collective behavior of simple individuals results in useful behavior on a global level. We have seen that swarm intelligence is prevalent throughout nature and that the principles of self-organization and emergent behavior are very useful to engineering and computer science. In the future, we will get to see many more engineered swarms all around us. Navigation systems, for instance, may use ant-inspired software to optimize routes. And the cars themselves may communicate with each other to coordinate their movements and route choices. In situations of natural disasters, swarms of robots may be deployed to analyze the situation, localize the victims and coordinate rescue operations. Swarms may bring many advantages to our society. However, before we will be able to fully benefit from them, much more research is needed in order to completely understand, predict, and design perfect swarms.

References

Deneubourg, J.-L., Aron, S., Goss, S., and J.-M. Pasteels, ‘The self-organizing exploratory pattern of the Argentine ant, in: Journal of Insect Behavior, 3, 2, 1990, pp. 159–168.

Dorigo, M. and T. Stützle, Ant Colony Optimization, Cambridge, MA, 2004.

Gazi, V. and B. Fidan, ‘Coordination and control of multi-agent dynamic systems: Models and approaches’, in: Sahin, E., Spears, W.M. and A.F.T. Winfield (eds.), Lecture Notes in Computer Science: Swarm Robotics, 4433, 2007, pp 71–102. 

Gordon, D. M., Ants at Work: How an Insect Society is Organized, New York, 1999.

Kennedy, J. and R. C. Eberhart, ‘Particle Swarm Optimization’, in: Proceedings of the IEEE international Conference on Neural Networks, 4, 1995, pp. 1942–1948

Kennedy, J. and R. C. Eberhart, Swarm Intelligence, San Francisco, CA, 2001.

Jelmer van Ast behaalde in 2005 zijn master Electrical Engineering aan de Technische Universiteit Delft. Sinds 2006 is hij bezig met een promotieproject bij het Center for Systems and Control, eveneens aan de TU Delft. In zijn onderzoek houdt hij zich voornamelijk bezig met computationele toepassingen van swarm intelligence in het bijzonder de ontwikkeling van optimalisatie-algoritmes geïnspireerd op het gedrag van mierenkolonies.

Leave a Reply

Your email address will not be published. Required fields are marked *