Self-organizing heterogeneous swarms designed through evolutionary methods.

Self-propelled particle swarm models are computational models of many particles capable of autonomous acceleration and local kinetic interaction. Their dynamics have been extensively studied in physics, theoretical biology, and computational science communities because of their useful implications for the understanding of collective behavior of various autonomous agents (e.g., bacteria, fish, birds, pedestrians) as well as their potential of application to practical problem solving. Earlier studies mostly focused on homogeneous swarms, assuming that the same (or quantitatively similar) set of kinetic rules uniformly apply to all the particles. Some literature also assumed intra-specific variations among particles (such as in body size or velocity) but none of them systematically considered interactions between kinetically distinct types of particles. In real biological/ecological systems, however, there are cases where multiple distinct types of organisms interact to form nontrivial patterns. In a herd of animals, for example, males and females, or parents and offspring, occupy different ecological positions and therefore adopt distinct behavioral rules. A unique formation may arise within the herd from interactions between those different types of organisms. Such self-organization of heterogeneous swarms could also be useful for engineering design purposes. We therefore extend our scope to heterogeneous self-propelled particle swarm systems in which more than one type of particles can co-exist and interact with each other in the same space. Our model, “Swarm Chemistry” (Sayama, ECAL 2007, p.675, Springer), assumes self-propelled particles moving in a two-dimensional infinite continuous space. Each particle can perceive only the local center of mass and the average velocity vector of other particles within its local perception range, and change its velocity in discrete time steps according to kinetic rules similar to those of Reynolds’ Boids (Reynolds, 1987, Computer Graphics, 21(4), p.25). Each particle is assigned with its own kinetic parameter settings that specify preferred speed, local perception range, and strength of each kinetic rule. Particles that share the same set of kinetic parameter settings are considered of the same type. Using this model, we computationally studied what kind of patterns/motions could emerge out of the mixtures of multiple types of particles. In the first experiments testing the effects of two-type interactions, we found that heterogeneous particle swarms usually undergo spontaneous mutual segregation, often leading to the formation of multilayer structures. Driven by their own endogenous self-propulsion forces, the aggregates of particles may additionally show more dynamic macroscopic behaviors, including oscillation, rotation, and linear or even chaotic motion. Moreover, to explore the possibilities of more than two type interactions, we developed an interactive simulation tool with which a human experimenter can select, perturb, mix, and mutate heterogeneous swarms using an interactive evolutionary method. The second experiments using this interactive tool and human participants further revealed unexpected possibilities of more complex, mechanical, and/or even biological-looking structures and behaviors when several different types are mixed appropriately. Specifications of those patterns were indirectly and implicitly woven into a list of different kinetic parameter settings and their proportions, which would be hard to obtain through conventional design methods but can be obtained heuristically through evolutionary design methods. These results suggest a novel direction of understanding and engineering collective behavior of physical agents, such as distributed robotic systems. The interactive simulation tool is implemented in Java and available at http://bingweb.binghamton.edu/ sayama/SwarmChemistry/ . Readers are invited to participate in the ongoing exploratory efforts of this project.