ANTS HAVE ALGORITHMS

ANTS HAVE ALGORITHMS

Iain Couzin [3.11.08]

...we've been investigating...huge swarms of Mormon crickets. If you look at these swarms, all of the individuals are marching in the same direction, and it looks like cooperative behavior. Perhaps they have come to a collective decision to move from one place to another. We investigated this collective decision, and what really makes this system work in the case of the Mormon cricket is cannibalism.

IAIN COUZIN is Assistant Professor in the Department of Ecology and Evolutionary Biology at Princeton University. His research focuses on understanding collective behavior; how large-scale biological patterns result from the actions and interactions of the individual components of a system. He studies self-organized pattern formation in a wide range of biological systems, including ants, fish schools, bird flocks, locust/cricket swarms and human crowds.

Iain Couzin's Edge Bio Page


ANTS HAVE ALGORITHMS

I certainly find that the way we interface with the technology is very important. Because despite the fact I use computers and do simulations and taught myself to program computers, I was a reluctant individual. I first started my Ph.D. in '96—I'm 33—I didn't have email, and then I realized initially that what I wanted to do was to get a computer to see for me. If I am observing an ant colony, and there are hundreds of ants doing things at the same time, I have a very limited view of that.

I also have all of these biases in my own perception and in my own judgments. I first started out trying to program a computer to look at the trajectories of these individuals and then I became interested in developing these simulated models. But I still find my innovating with computers is very clumsy. I don't like Windows, I don't like Unix, I don't like the Apple system. These systems do not gel with me at all; it is always a struggle to get beyond a threshold at which I will force myself to learn a new technique.

When I was a kid in Scotland—I was brought up in a town about 16 miles north of Aberdeen, in the far northeast of Scotland—my brothers are all allergic to fur and I was always interested in animals, but I was never allowed to keep a pet in the house since even a hamster was too much of an allergen risk. So I became very interested in little things like insects, which I could keep in the house and observe and so on. I was very interested in the social insects in particular and how they function together as a little society, which always intrigued me.

I saw a natural history documentary about these army ants, and there was this guy romping around the forests of Panama studying these army ants. I was about nine, and I thought, that looks great, I would love to do that. I ended up doing my Ph.D. with the guy in the program, working on these ants. Ever since I was a kid I was drawing pictures of animals, I was collecting bones; I was just a naturalist.


A fundamental question in biology is how the functioning of collective systems works—whether you are dealing with the function of a tissue and how the cells within a tissue interact, or whether you're dealing with ecologies or even ecosystems. We really need to build a new understanding and new tools that allow us to integrate across these scales. People refer to top-down and bottom-up; in some sense we have to take both approaches to try to understand these systems.

There is no characteristic scale that is the right scale to observe a system—one of the reasons I studied animal groups is that the systems can be taken apart and put together very easily. Some of the models and the understanding that we get from how these groups function—we are all familiar with the dramatic collective patterns exhibited by schools of fish or flocks of birds—and the way we can take these systems—like an ant colony—apart to see how they really function gives us deep insights.

So one line of research is to do specific testable ideas on specific systems. But another line of research is to try to find the fundamental principles that underlie, for example, collective decision-making in biological systems. And what we find remarkable is, when we actually look at the algorithms used by, say, an ant colony, or used by a school of fish, when making collective decisions, at a certain level of description, the types of algorithms they use are also the types of algorithms we now know humans use in the visual system, for example, to make decisions about what we are seeing.

Natural selection has found these same principles time and time again and included them in different systems in different ways, but fundamentally the principles are the same. I think this is a growing new area of research; we are really trying to build across these different systems.

Ants have algorithms. If you think about an ant colony, it's a computing device; there's some wonderful work by Jean-Louis Deneubourg in Brussels and his collaborators that really started this field in a way with Ilya Prigogine and later on Jean Louis Deneubourg looking at the ways in which social insect colonies can interact. One example would be—it sounds trivial, but if you think about it, it is quite difficult—how can a colony decide between two food sources, one of which is slightly closer than the other? Do they have to measure this? Do they have to perform these computations?

We now know that this is not the case. Chris Langton and other researchers have also investigated these properties, whereby individuals just by virtue of the fact that one food source is closer, even if they are searching more or less at random, have a higher probability of returning to the nest more quickly. Which means they lay more chemical trail, which the other ants tend to follow. You have this competition between these sources. You have an interaction between positive feedback, which is the amplification of information—that's the trail-laying behavior—and then you have negative feedback because of course if you just have positive feedback, there is no regulation, there is no homeostasis, you can't create these accurate decisions.

There's a negative feedback, which in this case is the decay of the pheromone, or the limited number of ants within the colony that you can recruit, and this delicate balance of positive and negative feedback allows the colony to collectively decide which source is closest and exploit that source, even though none of these individuals themselves have that knowledge.

One can also build analogies with neural systems. Here the ants are able to move around and interact with each other, but in principle they're using relatively simple rules. We have learned that you can have a suite of chemicals—and we're now becoming aware that it is a bit more complicated than originally anticipated where there is this extra sort of suite of abilities that the ants have and they are just allowed very effective collective decision-making.

The reason these ants don't have traffic jams the way humans would is that they're related. As I say in every talk, I always refer to these ants as 'she' and as 'her'. That is because almost every ant most people see is female, and so they're related by a genetic determinism called haplodiploidy, which means they're more related to each other than to their own kin, so of course they function together as colonies.

When we look at the optimization of an ant trail, we can look at what optimizes the benefit for all of the individuals. We also model human crowds, and when we model human crowds, we use a different algorithm entirely; we have a game theoretic algorithm where individuals may minimize their own travel times, but may do so at the expense of others because they don't necessarily care whether they cause congestion for other individuals.

In this particular species, the ants are sterile; in other species, the worker ants can produce haploid eggs, which develop into males so there is some conflict within the colony. An ant colony is not just some completely cohesive working together unit; there is actually conflict within the colony because there is some work of reproduction in some species—in many species, in fact.

In this particular species, the army ant, the workers are completely sterile, so our optimization algorithm on them is on the benefit of the colony. This is of course inappropriate for understanding humans, but if you look at the types of principles that we use in terms of the modeling techniques, they are very applicable. You just change the level at which selection is acting.

So the male ants are expendable. The males reproduce—it depends on the species—but perhaps only once a year in the case of the army ants—they are not really capable of feeding themselves, they are only produced for the purposes of reproduction, and so of course you want to have the minimal amount of energy that allows them to function. They will then reproduce with the fertile females who then become queens, and these females store the sperm for their entire lives—decades in the case of queen ants.

Then of course one can have a turnover of queens within a colony, so say the same ant colony can actually persist in the same location, with a turnover of the number of the workers rapidly and the slower turnover of the reproductives, for hundreds of years. So it's really a remarkable example of a sort of superorganism where you can have these multiple overlapping generations.

One of the big challenges that still remains, and one that we're beginning to address—I'm not saying it's a new question; I'm not saying people haven't addressed it—is the level at which selection is acting within populations. The view of individual level selection, and selection at the level of genes, of course, holds. But if you consider, say, a school of pelagic fish—these large schools that make these dramatic maneuvers—the individuals are unrelated to each other. They drift around as pelagic larvae, so when their schools are comprised as adults, they're completely unrelated.

And yet the individuals' functioning is entirely within the context of these schools; you can see the integration of the behavior when they are attacked by predators, you can see why in the '40s people thought there must be thought transference, must be telekinesis, because of these remarkable maneuvers. We now know that these maneuvers are created by the relatively local interactions among the individuals. But if you take an individual, say, a herring, from the school and isolate it, it will die of stress.

It is a bit like taking cells from your body—when you take them outside the body, they are unable to function. Of course it is not as closely integrated as a body, it is not as closely integrated as an ant colony. But there is this high level of integration among unrelated individuals. And in terms of how the genes are going to propagate, genes that allow individuals to function collectively as a group are going to be extremely important. So one has to then begin to think about the level at which selection is actually functionally acting. There is nothing new in terms of the genetics here, but it just in terms of how you begin to understand how the collective behaviors emerge and evolve within these types of systems.

Another example that we've been investigating arehuge swarms of Mormon crickets. If you look at these swarms, all of the individuals are marching in the same direction, and it looks like cooperative behavior. Perhaps they have come to a collective decision to move from one place to another. We investigated this collective decision, and what really makes this system work in the case of the Mormon cricket is cannibalism.

You think of these as vegetarian insects—they're crop pests—but each individual tries to eat the other individuals when they run short of protein or salt, and they're very deprived of these in the natural environment. As soon as they become short of these essential nutrients, they start trying to bite the other individuals, and they have evolved to have really big aggressive jaws and armor plating over themselves, but the one area you can't defend is the rear end of the individual—it has to defecate, there has to be a hole there—and so they tend to specifically bite the rear end of individuals. It is the sight of others approaching and this biting behavior that causes individuals to move away from those coming towards them. This need to eat other individuals means you are attracted to individuals moving away from you, and so this simple algorithm essentially means the whole swarm starts moving as a collective.

When we see these types of behaviors—you look at a bird flock and a fish school and a human crowd and these Mormon crickets—the danger, and there has been this tendency in the literature, is for people to say, well, we can use flocking algorithms to explain all of these behaviors. But if you actually look in detail, the mechanisms and the reason why these forms are functioning the way they do can be completely different. It is a danger called the reminiscence syndrome. One pattern is reminiscent of another, so we think it is the same mechanism, but of course that is not necessarily the case.

To my knowledge, some of the earliest work was actually done in Japan, and published in Japanese, looking at fish schooling. This has been a classic system—people have always wondered how they can coordinate these behaviors. This work was relatively poorly known, but they first started using computers to start simulating how the interactions among individuals—relatively simple interactions—will scale up to collective behaviors. Because it is not actually necessarily intuitive. You cannot scale up through verbal argument alone, and it is not possible, at least with conventional techniques, to solve these equations of motion.

Say, for example, in a computer you can define that individuals when they have become too close to each other will tend to be repelled. This again is analogous to some previous work which had been done on physical systems, where you hve repulsion and attraction fields around individuals, and likewise attractions cause these groups to stick together, and there may or may not be a tendency for individuals to align their directions of travel. These types of rules actually initially started off in the late '70s and early '80s, and then there was the very famous model by Craig Reynolds, who actually sort of rediscovered these phenomena and implemented them in a model called Boids, which was very influential particularly in the computer game industry and film industry.

There has been an idea that these interactions can scale up, but what we are now beginning to do is try to go beyond just a description of what is going on to try to link this in with real experimental data—try to link together what we understand now from statistical mechanics and statistical physics and these types of groups. One principle from statistical physics that has been very important for us is the concept of a phase transition. We know this table is wood, we know this is a solid. This // presumably referring to another object but reads strangely here is a different material, but we still would call this a solid. If you think about all the types of materials we have, a liquid is a liquid, whether it's liquid metal or whatever—there are fundamental states of matter, and these states can transition from one to the other. Heatable liquids above the boiling point will turn to gas—if you heat up a magnet beyond the Curie point, the particles in the magnet will become unaligned with the thermal noise and it will lose its magnetism. It doesn't lose it gradually, it loses it suddenly.

What people like Murray Gell-Mann have found out is that certain details of the system do not matter at these phase transitions. For example, the molecular composition of the liquid does not change the order of the phase transition. Biologists typically have been very involved in finding details. One example would be the locust that we studied. The locust is one of the best-studied organisms for physiology and neurobiology. It is really an amazing model system for looking at these principles. Yet the last time people looked at the swarming behavior of locusts in the lab was in 1954. So there is this dearth of information, and no matter how much you look at a locust, and how much you know about the biology of a locust, you cannot predict what will happen when you start to put these organisms in swarms.

What the statistical physics tells us is that you needn't necessarily have that knowledge. Issues like the dimensionality of the problem are important; issues such as certain details of the interactions are not important if you want to understand the general principles of how it changes—the phase transition is very important for us in the case of locusts because, as everyone knows, locusts are always around. But then suddenly there is this transition from one state to another almost liquid state—so its driven liquid-type state—where the swarms can become enormous.

The interaction length scales is centimeters. The swarms are kilometers long, marching through, and it's the density of insects that causes massive problems. It's an enormous problem—locusts can actually invade up to one-fifth of the Earth's land surface during plague years. The Food and Agriculture Organization of the United Nations estimates they affect the livelihood of one in ten people on the planet.

So what we've been trying to do is build our understanding by setting up artificial experiments, very much like how physicists would study particle interactions. We can set up the locusts within an arena in the laboratory, and we can change the density of these individuals, the density of these so-called particles. The individuals are moving, they're self-propulsive; that's what is different from standard physics. And it changes things enormously. Tamas Vicsek and others have looked at the physics of these far-from-equilibrium systems—if you let the system rest, it still has energy, it pushes itself. You do not have to add energy to it.

What we do find is that using these types of models from physics, we can explain very accurately these transitions. So we develop computer software that tracks the motion of all the individuals simultaneously, and we get this transition. We go from this gaseous-like phase into this sort of driven-fluid phase. And the way that transition works is exactly what we find within very simplistic models of how magnets work. You basically take a model for magnetic particles and allow them to move, and that explains this large-scale collective behavior.

We can begin to put together ideas that have been simmering and developing different fields, and try to find ways of linking them together to understand biological systems. I think there is amazing work still to be done in, say, the development of organisms. How our bodies develop. How cells migrate. How information is transferred within these groups. Also within, say, tumors. And how these systems work. This links together ideas about levels of selection, modern technology and modern imaging tools, and really new ideas and new modeling ways to synthesize these systems within computers to get a deeper understanding and to make testable predictions for how these systems work.

We have been extending these types of flocking models to understand information transfer within groups. What these models initially did, and what was very important to show in the '80s and '90s is that you don't need a leader. You do not need a commander to tell individuals what to do. Previously when people looked at, say, ant colony raiding patterns—and this was in the '40s and '50s—they thought they had to be preconcerted, there had to be a word of command, there had to be a commander. We then learned that that is not the case. We also now know that there are differences among individuals, that information differs, that individuals are moving around interacting relatively locally with their environment. But when you see another individual, that individual may also have information, just from its motion path.

So what do you do? Do you rely on your local information, or do you tend to follow that individual? These types of rules, these types of interactions, and these types of passive information transfer mechanisms can be important. And what we have shown is that individuals, if there is a difference in opinion within groups, can come to a consensus without being able to count, without needing signaling, without needing individual recognition, just by using very simple little rules of thumb.

In the human sphere it takes us a great deal of effort and complex cognitive abilities to decide what to do if we are going to decide in a collective. What we can now show is that animal groups, with really simple cognitive powers, can actually perform these types of computations. What we now want to understand is under what conditions these types of cognitive capacities work. How can these animal groups take information from multiple sources; how do they filter out noise and yet amplify weak signals? If you think about that, then you are automatically drawn into neuroscience, and what's going on in neuroscience.

How do neurons, with their relatively simple filing properties, tend to decode information. Again there is this issue of spontaneous activity within the network—how do you have spontaneous activity and yet balance that with being able to process information coming into the network?

These types of questions that we are beginning to ask with animal groups are analogous. We are really drawing these different fields together. We are also using control theory, which is developed in engineering, to start understanding how we can use these algorithms to control robotics, and how we can prove properties of these systems. We have been looking at issues of collective memory, how groups can incur a memory of a state, even though the individuals need have no knowledge of that state.

These are the types of principles that are taking the field beyond just the description of 'yes, local rules can scale to what looks like a flock.' We want to go beyond 'what looks like', beyond this reminiscence, and actually start testing these ideas and applying them to specific key areas, and then from that pull back to see whether we have elucidated some new fundamental principles that govern how information transfers within biological systems, how decisions are made in biological systems, how natural selection acts upon local rules and the balance of different forces. So it really is strongly experimentally-driven science.


Something we are interested in, which relates to humans, is the evolution of cooperation, and I am very interested in the formation of religions, and the spread of ideas. There is work started by people like Richard Dawkins, looking at memes and so on, but we are now using these types of models to understand in a more computational way what types of principles occur within these groups. Instead of animals moving through, say, space, and interacting with each other in their space, we can then abstract the mathematical tools that we have developed into multi-dimensional concept space.

Individuals can have a certain opinion on certain topics, and we can allow individuals to interact across a social network, and of course the social network's topology is partly defined by what opinions you have. You tend to interact more often with people who have similar opinions to yourself because you are more likely to meet them in your sphere of life. But interacting with people can change your opinions, which can then change your social network, which can change your opinions, so again we have this recursive feedback. And so we are using it to explore these types of properties?I am sure that these types of principles also would apply to understanding dynamics on the Web.

I know there's some excellent work by Duncan Watts on how individuals buy on-line, or how they judge information that they have on-line, how your judgment of something is dependant on what previous people have said about it. What they used was an on-line music store, where you either have information about what previous people have thought about a song, or you have no information and you just have to rank the song without that previous buyer. This strongly changes people's behavior because of course when you see what other people have been doing, you can have this autocatalysis, this positive feedback. You can tend to buy into that because you have seen other people do it.

We do not have time to take in all the information; if you need to buy something, if you need to buy an insurance policy, or you need to choose some sort of plan, you don't have time to do that, so you tend to ask friends, or you tend to assume. Of course this can build a network of information that can be highly functional, as is witnessed on the Web and in software products like Wikipedia. Once you have a search engine as efficient as Google, you have all of these other possibilities, and my new iPhone is testament to that?I am now permanently connected.

I personally find a transition in terms of how I interface with the world. I find that the hits that I wanted were much more accurate on Google than Alta Vista or the other ones that I was aware of. I still find it miraculous that I can press a button and 0.1 or 0.2 seconds later I have a comprehensive list of information out there.

It is very interesting to play around with models and to generate nice-looking patterns. But from a biologist's perspective it can be limiting in how rewarding that is because there are many different types of rules that can create what appear to be similar properties, and so in terms of understanding the fundamental principles or organizing this collective behavior, that then doesn't become particularly satisfying for me.

What we are really trying to do is make it a very empirically-driven research area where we are studying what real animals do. What we find when we look at that is that our assumptions can be completely incorrect. The way that we understand these systems, the models, can be completely wrong. The evolutionary pressures that underlie these behaviors can be completely wrong. What appears to be a similar process occurring across different systems can turn out to be something completely different.

Again, we are still using the models as ways of developing new concepts, as has been popular in the past. That is never going to stop, that is extremely useful, and I am not trying to at all be critical of previous work, especially the work in artificial intelligence and artificial life and so on, which has been extremely influential. But what we need to do now, when we are addressing problems such as how an embryo develops, is try to go beyond these caricatures and start building testable predictive models that allow us to test these properties within natural systems. And to do that we need a better understanding of molecular function.

Even classic problems in embryology are now being turned on their head—things that we just assumed were right are suddenly maybe not quite so certain. This is largely driven through a better understanding of molecular biology and a better understanding of the models of these real systems and how models can be incredibly important in allowing us to tease out from among the many many many different experiments you could perform the models that can hone in on, well, if you do this manipulation, this can actually test between these two alternative hypotheses. The techniques themselves in terms of the modeling techniques are quite similar. But the way we are integrating these models within our understanding of reality has changed and will continue to change.

I don't have a five-year plan. I am not one of those people who has a fixed route to somewhere. I don't have a goal to get somewhere, other than just to explore stuff, and to have fun doing science, and fun doing research. There are so many different systems that I'm fascinated by, and what I would like to do here is build a world-class research group where I can find people from these different areas—from computer science, engineering, mathematics, evolutionary biology, psychology—and really integrate them. But in terms of the systems that we look at, this may well change.

When I started my Ph.D., I never had any interest in fish schools—I never thought I would work on that. I never thought I would be able to program a computer. So who knows. In the next five years, who knows where it will to go. There is so much good research going on at Princeton in neuroscience and psychology and economics— and there is a drive with the Institute for Advanced Study to study cooperation and the spread of social norms—normative behaviors in human populations. I am involved in that project, too.

There is a whole suite of different areas, and for me, they are not disparate—these are the same problems occurring time and time again in different systems. They are not disparate in terms of the techniques used to understand them—we still do not have a good thoughtful understanding of cooperation within societies in terms of the level of selection that is acting upon these societies and how that tends to change the optimization principles that underlie these different behaviors.

We still do not really understand  what is being optimized in many biology systems, and what the constraints are, or how these constraints act on the optimization process. We need to pull together understandings from physics, understandings from biology, understandings from economics. If you stop and think for a moment, there are so many things we fundamentally do not understand and cannot explain. I think if I can help guide research to what I find are very interesting gaps in our existing knowledge, and try to begin to fill those gaps, that would be very rewarding.

With regard to religions, the level of description that we tend to focus on at the moment is how these processes can occur—the types of copying behaviors within populations, and also people's natural social tendency to be repelled from other individuals who have different views from themselves, or how they exchange views. One of the dangers here is that again it can be too wishy-washy; it needs to be experimentally driven. We are now talking with a whole range of people; for example, art historians to understand how human interaction with the visual world has changed over time, and how certain fads and trends suddenly appear and how they spread, which potentially provide us some data.

We are constantly looking for areas where we can create a more data-driven science behind the spread of these normative behaviors. Of course religion is one such normative behavior, and one of the questions then that we are beginning to interpret with these sorts of models is, when you have could have a whole suite of different possibilities occurring in the world, why do societies collapse down to relatively narrow dimensions, in terms of what they become opposed on? And how did this occur?

How do these kind of processes, this reduction of these potential opportunities, collapse down on themselves? Can we make some predictions there? Can we create generic models that actually allow us to reveal some fundamental and testable predictions? There is evidence that people's belief can change things like their immune system and so on and that this tends to differ from person to person depending on experience and so forth. We are not really addressing it at that level yet, but I would be very interested in talking to people who are.

In science even if I wrote a paper just by myself and I was the only author, I would still write "we" in the paper. It is mostly a convention. But it is partly because you are always building upon what has come before. People would like to think that their work is brand new—it never is. Sometimes a different take on the same problem can be illuminating. I tend to interact with many people from different disciplines. Everything I have done is out of strong collaboration. I had strong collaborations at Princeton among different departments, and in Sydney—a guy called Steve Simpson; he was a professor at Oxford for about 20 years, and he is now a federation fellow at Sydney University; he is an absolute genius when it comes to nutritional ecology, trying to understand how we interact with our nutritional environment. I am interested in animals so we are beginning to work on these areas—it is very dynamic.

I want to dedicate my energy to finding out how these systems work and seeing whether we can develop a better understanding of collective behavior within biological systems.