Research (download as word doc)

Social insect colonies dynamically allocate individuals, resources and tasks to collectively solve many computationally difficult problems without centralized control. System behavior appears out of local interactions between individuals with simple rule sets and no global knowledge. Furthermore, such behavioral algorithms are typically robust to change, maintaining their effectiveness in highly varied environments or resource distributions over a wide range of tasks. The mechanisms of such behavior are of great interest from a biological standpoint because they provide insight into how organization appears in nature [1, 2]. Concepts such as collective intelligence and self-organization are also finding increasingly successful application in many non-biological fields such as robotics, artificial intelligence, data mining and network routing [e.g. 3, 4-6]. However, non-biological applications are usually based on generalized metaphors of social insect behavior rather than a direct knowledge and application of the rules actually used by insects [7, 8]. While there are obviously different constraints on non-biological systems, the goals and problems such systems are being designed to solve can be remarkably similar to those facing living systems. This is particularly true in the design of multi-agent autonomous systems where groups of interacting agents or robots attempt to collectively solve a problem. It is probable that there are basic laws governing how individual rules scale to system-level behaviors [2], yet developing a rigorous description of these rules has proven very difficult. To this end, more research is needed on natural systems in which the emergent behaviors or "goals" of the system and the behaviors of the individuals can be quantitatively described and modeled. I believe that the appearance of coordinated system-level behavior and optimal task allocation in social insects is, in a large part, dependent on rates of feedback and communication between individuals. My research focuses on identifying the mechanisms governing the organization and coordination of swarming behavior in the New World army ant, Eciton burchelli, through field work and computer modeling. Accurate computer models of such systems will allow researchers to examine precisely the influence that specific mechanisms such as individual behavioral rules or communication rates have on the system's function and how changes in these rules affect the system's efficiency.

The life-cycle of Eciton burchelli army ants provides an ideal model system in which to examine questions relating to collective intelligence and agent-based behavioral algorithms. Colonies of E. burchelli forage in massive, highly organized swarms involving complex organizational processes and information sharing between hundreds of thousands of ants of multiple castes. Swarm behavior is not centrally organized but generated completely through individual interactions involving ant-ant contact and pheromone trails. Every day, E. burchelli army ants efficiently solve a very computationally complex question - how to distribute as many as 200,000 nearly blind individuals over a 1,500 square meter area to capture, process and retrieve more than 30,000 mobile prey items while sharing only local information [9-11]. Prey can be hundreds of times larger than the ants themselves and must be broken down into pieces small enough to be transported to the nest by single ants or ants working in teams [12]. Army ant behavioral algorithms are robust to drastic changes in swarm size - from a few thousand to a few hundred thousand ants - and huge variations in substrate type. Ant swarms can cross streams up to 2 meters across by making temporary bridges with their bodies [13], and the substrate on which they forage can vary from completely clear ground to massive tree-fall areas hundreds of meters square and 5-10 meters deep.

Nearly 70 years of field work on Eciton has yielded great advances in our understanding of the life-history and biology of army ants [13-16, 17 and others]. But no one has yet quantitatively measured the communication and feedback processes underlying the organization of E. burchelli swarms. The few existing computer models of E. burchelli swarm behavior contain limited biological parameters and were not designed to specifically address the questions detailed above [18, 19]. I hypothesize that the bulk of basic observed behaviors in E. burchelli swarms can be explained through simple interaction rules based on ant density, pheromone concentrations and resource distribution.

To examine the behavioral rules involved in the organization of E. burchelli swarms, I am creating a detailed individual-based computer simulation of swarm behavior based on parameters determined through my field work and from the literature. Predictions of the model will be tested in the field to verify the accuracy of the model and the modeling work will inform and shape the direction of my field work and allow me to investigate questions that are not easily addressed in the field.

Specific Research Goals

(I) Biology
The primary biological goals of this research are 1) to identify which behavioral parameters play important roles in organizing swarm behavior in E. burchelli, 2) measure those parameters in the field through behavioral observations and quantitative analysis of video of army ant swarms, and 3) expand on existing knowledge of army ant life-history. Video analysis and marking of individuals are being used to generate quantitative data on contact rates, turn angles, ant density, velocity and behavioral interactions.

(II) Modeling
In the Spring of 2001 I created a model replicating previous modeling work [see 18, 19, and "Existing Models" section below]. This summer I will begin to extend the model using data measured in (I) to incorporate more biologically realistic descriptions of ant behavior. Once the new data is integrated the model will be tested quantitatively and qualitatively with field-collected data on swarm patterns. Previously measured energy-use values for army ant foraging [20-22] will then be introduced to add an accurate measure of efficiency and fitness. When completed, the model will be used to suggest behavioral manipulations that can be performed in the field to validate model predictions and to address questions relating to self-organizing processes and the design of multi-agent systems.

(III) Generalization to multi-agent systems
A well designed computer model of army ant swarm behavior which incorporates real-world measures of efficiency provides a powerful tool for exploring key questions in multi-agent system design and collective intelligence. In particular, one can perform precise sensitivity testing to examine how specific parameters influence the ant swarm's ability to solve their collective goal of efficiently exploring the environment. The relative importance of communication rate, network size (number of ants), task fidelity and task specialization will be examined in detail.

Predictions for model

It is conventionally believed that searching behavior and recruitment rates play a large role in the organization of E. burchelli army ant swarms [13, 15]. However, my observations suggest that the main challenge faced by foraging E. burchelli is maintaining an optimal rate of exchange between covering the widest area possible to maximize food discovery while preserving a sufficiently uniform density of ants in all areas of the swarm to prevent prey from escaping. Because prey items can be as large as 10 cm, ants must also be efficiently allocated for prey processing which can take hours (personal observation). After processing, prey items must be returned to the bivouac along trails of limited width. The model will enable precise examination of what behavioral parameters are most important for maximizing fitness and producing observed swarm patterns over different variations in prey size and distribution.

Model Insights and generalizations

Examination of E. burchelli foraging behavior suggests the importance of understanding the type of information or resources the system being examined is designed to discover and the distribution of these resources in the environment. This is a crucial question in the development of multi-agent systems as well - what rule sets should agents have under a given set of assumptions about the agent's collective goals and the environment in which they will function. A well designed simulation of army ant swarming behavior offers a stepping-off point for examining many questions relating to collective intelligence and the design of self-organizing systems. Army ant foraging systems have three principle features that are essential to well designed multi-agent systems as well:

• Robustness - army ants can withstand significant colony disturbance without major impact to colony behavior;
• Scalability - system behavior is maintain across huge variation in system size;
• Flexibility - army ants can adapt to a varied environment and dynamically allocate individuals and tasks as needed.
  

The above three features of the E. burchelli system are most likely created through the interactions of four principle components: communication, network size, task fidelity and task specialization.

Communication: Swarm efficiency is influenced by 1) how many forms of communication or "channels" are available to the system and 2) the vocabulary size or range of communication available to each channel (i.e. bits / channel). As discussed earlier, E. burchelli have to make a trade-off between maintaining sufficient ant density in a given area, maximizing area covered, and allocating enough ants to process and retrieve prey items. This trade-off is mediated through two primary forms of communication in army ants, ant-ant contact rate and response to pheromone. Variations in contact rate happen on a fast timescale and give the ant feedback about local density. Variations in pheromone concentration give the ant temporal feedback about swarm behavior, direction of travel and foraging success. Density is most likely tuned by the relation between an ant's fidelity to trail pheromone, and turn angle as influenced by both pheromone concentration and contact rate (a direct measure of density). This hypothesis is supported by recent work modeling work showing that spontaneous lane formation can occur in model army ants responding only to pheromone and avoid collisions [23]. Pheromone response has been shown to be sigmoidal [24] but the behavioral effects of this response curve have been yet been quantitatively examined.

Network size: Although army ants can successfully swarm with even a few thousand individuals (personal observation), it is not yet known how swarm efficiency scales with swarm size. If self-organizing processes are at work, one would expect swarm efficiency to increase non-linearly. The size of this effect is of great interest both for increasing scientific understanding of self-organization and for providing insight into economies of scale in multi-agent system design. As system size increases, dynamic allocation of individuals and tasks also become increasingly important as do the consequences of unrestrained positive or negative feedback.

Task fidelity and task specialization: Task fidelity and task specialization play a huge role in organizing E. burchelli swarms [12, 25, 26]. One might expect that 1) the benefits of task fidelity or specialization should increase as potential tasks or environmental variation become more predictable and 2) system efficiency should increase with the systems' ability to allocate resources. In army ants, individuals involved in foraging and prey retrieval are found in three distinct caste sizes [26]. The largest-sized group, the "sub-majors", constitute only 3% of the ants in the colony but make up 26% of all ants retrieving prey. The other two castes also retrieve prey, often working in teams with the sub-majors, but they generally spend more time in the swarm and capturing prey than in prey retrieval [12]. However, there is wide variation both in the numbers and size classes of ants involved in prey retrieval [26]. The primary tools the colony has to control task allocation are communication and feedback. The effects of "noise" in the system must be considered as well. In particular, in a stochastic environment, too low fidelity leads quickly to chaos (ants keep switching tasks and never get anything done). But too high fidelity leads to inefficient resource allocation (all ants end up in one location or task).

References

1. Kauffman, S., The origins of order, self-organization and selection in evolution. 1993, NY: Oxford University Press.
2. Camazine, S., et al., Self-organization in biological systems. 2001, Princeton, NJ: Princeton University Press. 538.
3. Parpinelli, R.S., H.S. Lopes, and A.A. Freitas, Data mining with an ant colony optimization algorithm. IEEE transactions on evolutionary computation, 2002. 6(4): p. 321- 332.
4. Dorigo, M. and L.M. Gambardella, Ant colonies for the travelling salesman problem. Biosystems, 1997. 43: p. 73-81.
5. Wagner, I.A., M. Lindenbaum, and A.M. Bruckstein, Distributed covering by ant-robots using evaporating traces. IEEE Transactions on Robotics and Automation, 1999. 15(5).
6. Bonabeau, E., et al., Routing in telecommunications networks with ant-like agents. Lecture Notes in Computer Science, 1998. 1437: p. 60-?
7. Bonabeau, E., M. Dorigo, and G. Theraulaz, Inspiration for optimization from social insect behaviour. Nature (London), 2000. 406(6 July): p. 39-42.
8. Bonabeau, E., M. Dorigo, and G. Theraulaz, Swarm intelligence: From natural to artificial systems. Santa fe institute studies in the sciences of complexity (oxford university press). 1999, New York: Oxford University Press. 307.
9. Franks, N.R., Army ants: A collective intelligence. Am Scient, 1989. 77: p. 139-145.
10. Franks, N.R., Reproduction, foraging efficiency and worker polymorphism in army ants, in Experimental behavioral ecology and sociobiology: In memoriam karl von frisch,1886-1982, M. Lindauer, Editor. 1985, Sinauer Associates: Sunderland, Mass. p. 91-107.
11. Franks, N.R. and C.R. Fletcher, Spatial patterns in army ant foraging and migration: Eciton burchelli on barro colorado, panama. Behav Ecol Sociobiol, 1983. 12: p. 261-270.
12. Franks, N.R., et al., Convergent evolution, superefficient teams and tempo in old and new world army ants. Proc R Soc London Biol Sci, 1999. 266: p. 1697-1701.
13. Schneirla, T.C., Army ants. A study in social organization. (edited by h. R. Topoff.). 1971, San Francisco: W. H. Freeman & Co. xx + 349.
14. Franks, N.R., The evolutionary ecology of the army ant eciton burchelli on barros colorado island, panama. 1980, Ph.D. dissert., The University of Leeds, Leeds, England.
15. Gotwald, W.H., Jr., Army ants: The biology of social predation. The cornell series in arthropod biology. 1995, Ithaca, New York: Cornell University Press. 302.
16. Rettenmeyer, C.W., Behavioral studies of army ants. Univ Kans Sci Bull, 1963. 44: p. 281-465.
17. Topoff, H., Social organization of raiding and emigrations in army ants. Adv Stud Behav, 1984. 14: p. 81-126.
18. Deneubourg, J.L., et al., The blind leading the blind: Modeling chemically mediated army ant raid patterns. J Insect Behav, 1989. 2: p. 719-725.
19. Sole, R.V., et al., Pattern formation and optimization in army ant raids. Artificial Life, 2000. 6(3): p. 219-226.
20. Bartholomew, G.A., J.R.B. Lighton, and D.H. Feener, Jr., Energetics of trail-running, load carriage, and emigration in the column-raiding army ant eciton hamatum. Physiol Zool, 1988. 61: p. 57-68.
21. Feener, D.H., Jr., J.R.B. Lighton, and G.A. Bartholomew, Curvilinear allometry, energetics and foraging ecology: A comparison of leaf-cutting ants and army ants. Funct Ecol, 1988. 2: p. 509-520.
22. Feener, D.H., Jr., J.R.B. Lighton, and G.A. Bartholomew, Energetic costs of foraging: A comparison of leaf-cutting ants and army ants (hymenoptera: Formicidae). 1988, Proceedings of the 18th International Congress of Entomology, p. 233.
23. Couzin, I. and N.R. Franks, Self-organized lane formation and optimized traffic flow in army ants. Proc R Soc Lond B, 2003. 270(1511): p. 139-146.
24. Franks, N.R., et al., The blind leading the blind in army ant raid patterns: Testing a model of self-organization (hymenoptera: Formicidae). J Insect Behav, 1991. 4: p. 583-607.
25. Franks, N.R., The organization of working teams in social insects. Trends Ecol Evol, 1987. 2: p. 72-75.
26. Franks, N.R., Teams in social insects: Group retrieval of prey by army ants (eciton burchelli, hymenoptera: Formicidae). Behav Ecol Sociobiol, 1986. 18: p. 425-429.

SomeOther Interesting Questions

• What rules govern how organization emerges in complex systems?
  

• How do processes scale between levels?
  

• What will a given set of processes look like at the next scale up?
  

• What smaller processes make up the individual 'agents' at the current scale?

• What gives biological systems their stability?
  -> What different levels of structure are stable in different environments or under different situations;

• How can we tell how when a given level will be most important?
  Example: Evolution of social insects -- When did selection stop acting at the level of the individual and become more important at the level of the colony? Ants are a good system to look at because it forces one to think how the level at which selection is acting might change with circumstances.

• What role does noise play in biological systems?
  -> Is noise maintained or just eliminated as well as evolution can or needs to?
  Example: The degree to which Army ants react to each other and to other ants' chemical signals must be crucial to the stability of the swarm.