Swarm-Based Morphogenetic Artificial Life

Abstract

We present a swarm-based framework for designing and implementing morphogenetic artifacts that can grow, self-organize and self-repair in a fully decentralized manner. Artifacts are realized as swarms of multiple types of very simple, kinetically interacting particles with no elaborate sensing, computation, or communication capabilities. The proposed framework is based on our earlier work, Swarm Chemistry, a computational model of particle swarms where mobile particles with different kinetic properties interact with each other to produce dynamic structures and behaviors spontaneously. The features of emergent patterns are implicitly encoded through interactive evolutionary design methods into a set of kinetic parameter values, called a recipe. In this chapter, we summarize several extensions of the model for morphogenetic engineering and demonstrate a variety of morphogenetic processes that can be achieved by using simple particles with minimal capability. Specifically, we show (1) diversity of self-organizing patterns that can be generated by simple particle swarms in our framework, (2) robustness of those patterns against external perturbations, (3) growth and self-assembly by local information transmission between particles and their stochastic differentiation, and (4) self-repair by stochastic re-differentiation of particles.

This chapter is an extended version of [1]

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

Morphogenesis of biological organisms is a programmed yet self-organizing emergent phenomenon that has a lot to offer to engineering designs of man-made robotic systems [2, 3]. Such growing, self-repairing and self-replicating artifacts have been a subject of investigation for long [4–7], and a number of theoretical models and implementations have been produced in Artificial Life and Bio-Inspired Robotics research communities [8–14].

Three different architectures have so far been utilized for morphogenetic robotics: lattice (grid), chain (tree) and mobile (swarm) [13]. The first two architectures use mechanical/electrical connections between modular robots to build physical structures and communication channels. They can achieve highly complex self-assembly and self-reconfiguration with either centralized or decentralized control. However, individual robotic modules in these architectures tend to be complex and expensive because they have to be equipped with mechanical/electronic devices to achieve physical couplings with other modules.

Compared to the above two, the mobile (swarm) architecture is a relatively unexplored yet highly promising approach, where mobile autonomous robots are used as building blocks to form large-scale spatial patterns and behaviors [2, 15–22]. A swarm-based architecture can make the entire system fully decentralized, highly flexible and less vulnerable to various forms of perturbations. Another salient feature of swarms is that individual agents can be made relatively simple compared to those used in the other two architectures. However, earlier work on morphogenetic artifacts still often uses complex agents that are equipped with sophisticated communication and computation capabilities, such as pheromone/morphogen-based communication mechanisms [2, 16], coordinate system sharing [17], evolved neural network controllers [18], preprogrammed gene-regulatory networks [2, 20, 21], logical behavior control described in high-level programming languages [15, 16, 19, 22], and even mechanical devices that create physical bonds between them [15, 18, 19]. These observations naturally lead us to the following research question: How much can one simplify the individual modules of morphogenetic artifacts?

To provide a potential solution to the above question, we propose here a swarm-based framework for designing and implementing morphogenetic artifacts by using very simple, mobile particles that have no elaborate sensing, computation, or communication capabilities. The original key ingredients of our framework are (1) a combination of multiple kinetically distinct types of particles to achieve self-organization of nontrivial structures and behaviors, and (2) local information transmission and stochastic, independent differentiation of the particles to achieve growth and self-repair of swarms without complicated control mechanisms. These properties make the basic components of morphogenetic artifacts extremely simple.

In this chapter, we aim to explore and demonstrate what kind of robust morphogenetic processes can be achieved by using such simple particles with minimal capability. As a basis of the proposed framework, we utilize our earlier work, Swarm Chemistry [23, 24], which already possesses the first key ingredient mentioned above (type mix). Based on this model, we first demonstrate the potential diversity of self-organizing dynamic patterns through systematic experiments and interactive evolutionary explorations, as well as the robustness of those patterns against external perturbations. We then extend the model to implement the second key ingredient mentioned above (communication), so that each particle can contain and transmit information about the composition of the whole swarm and stochastically differentiate/re-differentiate based on its contents. This simple model extension naturally enables growth and self-assembly of swarms, and moreover, self-repair by stochastic re-differentiation of particles. Limitations and future research directions will also be discussed.

2 Baseline Model: Swarm Chemistry

We use Swarm Chemistry [23, 24] as the basic model for the proposed design framework. Swarm Chemistry is an artificial chemistry [25] model for designing spatio-temporal patterns of kinetically interacting heterogeneous particle swarms using evolutionary methods. A swarm population in Swarm Chemistry consists of a number of simple particles that are assumed to be able to move to any direction at any time in a two-dimensional continuous space, measure average positions and velocities of other particles within its local perception range, and change its velocity in discrete time steps according to the following kinetic rules (adopted and modified from the rules of Reynolds’ Boids [26]; see Fig. 8.1):

• If there are no other particles within its local perception range, steer randomly (Straying).

• Otherwise, steer

  • to move toward the average position of nearby particles (Cohesion, Fig. 8.1a).

  • toward the average velocity of nearby particles (Alignment, Fig. 8.1b).

  • to avoid collision with nearby particles (Separation, Fig. 8.1c).

  • randomly with a given probability (Randomness).

• Approximate its speed to its own normal speed (Self-propulsion).

Fig. 8.1

Kinetic interactions between particles. Top: Particle $i$ senses only positions and velocities of nearby particles within distance $R^i$. Bottom: a Cohesion. Particle $i$ accelerates toward the center of mass of nearby particles. b Alignment. Particle $i$ steers to align its orientation to the average orientation of nearby particles. c Separation. Particle $i$ receives repulsion forces from each of the nearby particles whose strength is inversely related to distance

Fig. 8.2

The algorithm used to simulate the behavior of particles (taken and slightly modified from [24]). $\mathbf{{x}}_i$, $\mathbf{{v}}_i$ and $\mathbf{{v}}_i^{\prime }$ are the location, the current velocity, and the next velocity of the $i$th particle, respectively. $\mathbf{{a}}$ is a local variable temporarily used to represent an acceleration. $r$ and $r_{\pm p}$ represent random numbers taken from $[0,1]$ and $[-p,+p]$, respectively

These rules are implemented in the algorithm given in Fig. 8.2. Kinetic parameters used in this algorithm are listed and explained in Table 8.1. The kinetic interactions in our model uses only one omni-directional perception range ($R^i$), which is much simpler than other typical swarm models that use multiple and/or directional perception ranges [17, 26–30]. Moreover, the information being shared by nearby particles is nothing more than kinetic (i.e., relative position and velocity), which is externally observable metrics and therefore can be shared without any specialized communication channels (an exception is local information transmission during particle recruitment processes, which will be discussed later in this chapter). These features make our framework uniquely simple compared to other swarm-based morphogenetic systems.

Each particle is assigned 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. Particles do not have a capability to distinguish one type from another; all particles look exactly the same to themselves.

For a given swarm, specifications for its macroscopic properties are indirectly and implicitly woven into a list of different kinetic parameter settings for each swarm component, called a recipe (Fig. 8.3) [24].

3 Dynamics of Homogeneous Swarms

To understand the basic dynamics of swarms in Swarm Chemistry, we first conducted a systematic parameter sweep experiment of homogeneous swarms made of a single type of particles. More than 100,000 Monte Carlo simulation runs were conducted, each starting with randomly positioned particles. For each simulation run, the strengths of cohesion, alignment and separation forces ($c_1$, $c_2$ and $c_3$) were randomly selected from their domains, while other parameters were kept constant ($N=300$, $R=200$, $V_n=10$, $V_m=40$, $c_4=0$ and $c_5=0.5$). Each run was simulated for 200 time steps and then several observational measurements were computed based on the final configuration of the swarm, including: average velocity of particles (velocity as a vector), average of absolute velocity of particles (absolute velocity as a scalar, i.e., speed), and average distance from the center of mass.

Table 8.1 Kinetic parameters involved in the simulation of particle behavior

Fig. 8.3

Example of a recipe, formatted as a list of kinetic parameter sets of different types within a swarm. Each row represents one type, which has a number of particles of that type at the beginning, followed by its parameter settings in the format of $(R^i, V^i_n, V^i_m, c^i_1, c^i_2, c^i_3, c^i_4, c^i_5)$

Fig. 8.4

Phase diagram of homogeneous swarm behavior. Three different measurements were plotted as order parameters (Left: average velocity; Middle: average absolute velocity; Right: average distance from the center of mass). Some sample snapshots are also shown on the left plot

The results revealed a few distinct classes of macroscopic behaviors similar to those reported in the literature [31–35], such as dispersal, coherent linear motion and random swarming (Fig. 8.4). The behavior depended primarily on the strengths of cohesion and alignment rules (parameters $c_1$ and $c_2$), while there was no significant dependence observed on the strength of the separation rule ($c_3$).

4 Dynamics of Heterogeneous Swarms I: Two-Type Interactions

Next we examined what kind of behaviors would arise from interactions between two distinct types of particles. This was investigated again by Monte Carlo simulations, with more than 50,000 trials. In each trial, two different parameter vectors $(c_1, c_2, c_3)$ were randomly generated, and three different simulation runs were conducted: (1) Simulation of 300 particles, all using the first parameter vector, (2) simulation of 300 particles, all using the second parameter vector, and (3) simulation of 150 particles using the first parameter vector together with the other 150 using the second, all mixed into one space. All other parameter values were the same as in the previous experiment.

Each run was, again, simulated for 200 time steps and then the same measurements were made on the final configuration of the swarm, plus one additional measurement called “local homogeneity” to quantify the level of spatial segregation between the two types of particles. Specifically, the local homogeneity was calculated by measuring, for each particle, the probability for its neighbor particle to be of the same type within its six nearest neighbors, and then averaging the measured probability across all the particles (Fig. 8.5). If this measurement is close to 1, it implies that the two types of particles spontaneously segregate from each other. Or, if it is close to 0.5, it implies that the two types are well mixed.

Fig. 8.5

Calculation of local homogeneity $H$. The local homogeneity of particle $i$ ($H_i$) is the probability for its neighbor to be of the same type as particle $i$. $H_i$ is then averaged over all the particles

Fig. 8.6

Typical examples of interactions between two kinetically distinct types (from [24]). Each image is a snapshot of the configuration of a swarm being simulated. Particles are colored by taking their $(c^i_1, c^i_2, c^i_3/100)$ values as their $(R, G, B)$ values, respectively. Top: Swarms of three different types (homogeneous populations made of identical agents). Bottom: Results of reactions (spatial patterns formed after mixing two swarms of different types). Gray lines are references drawn at constant intervals to show the scale and motion of swarms

Fig. 8.7

Local homogeneity measures. a Histogram of local homogeneity $H$ values taken from two-type swarm simulations. $H \approx 1$ most of the time. b Local homogeneity $H$ plotted over the difference in $c_1/c_3$ between two types. Mixing occurs only when $c_1/c_3$ is similar for both types

Visualization of simulation results clearly showed that different types of particles have a general tendency to undergo spontaneous spatial segregation, often leading to the formation of multilayer structures (Fig. 8.6). Consequently, the local homogeneity of swarms made of two types was very close to 1 most of the time (Fig. 8.7a). This inherent tendency of multi-type swarms to show spontaneous spatial segregation can be understood by considering the difference in their equilibrium distance that each particle prefers to maintain around it (analog to the “personal space” of humans). Specifically, by ignoring the alignment effect in line 8 of Fig. 8.2, the magnitude of the force that particle $i$ receives from its neighbor particle $j$ is approximated by

$$\begin{aligned} F \approx c^i_1 r - c^i_3 r/r^2, \end{aligned}$$

(8.1)

where $r$ is the distance between particles $i$ and $j$. Letting $F\,{=}\,0$ gives $c^i_1 r^2\,{=}\,c^i_3$, which means that the ratio of the constants for cohesion and separation forces determines particle $i$’s equilibrium distance. When this distance is different between the two types of particles, their mixture is unstable and therefore the two types move until local homogenization is realized due to spatial segregation. This explanation was confirmed by the simulation results (Fig. 8.7b), where low local homogeneity values are achieved only if there is little difference between the two types regarding the $c_1/c_3$ ratio.

Fig. 8.8

Production of movement as a result of reaction between two types (from [24]). Left: Linear motion. Mixing two swarms of originally immobile types results in a polarized cluster, and their chasing/escaping behaviors create a linear motion of the entire population. Middle: Rotation. The small cluster rotates inside the other cluster. Right: Oscillation. The small cluster is continuously attracted by the main body of the population made of the other type and keeps moving back and forth through it

Fig. 8.9

A screen shot of the interactive evolutionary design software of Swarm Chemistry (version 1.2.0). Multiple swarms are displayed on a screen and simulated simultaneously. Positions and sizes of the windows are adjusted automatically using simple pseudo-kinetic rules. A human user can apply evolutionary operators (e.g., replication, mutation, removal, etc.) directly to each window, which will result in local modification of the population of designs (swarm patterns) leading to continuous, gradual generation change. For details of our interactive evolutionary design tool, see  [37, 38]

Furthermore, it was also found that the mixture of particles may additionally show dynamic macroscopic behaviors, including linear motion, rotation and oscillation (Fig. 8.8), sometimes even from two types that were originally immobile if simulated in isolation. These results illustrated the potential of multi-type interactions to exhibit more complex self-organization phenomena and dynamic, emergent behavior of morphogenetic artifacts.

5 Dynamics of Heterogeneous Swarms II: Interactive Evolutionary Explorations

We further explored the dynamics of heterogeneous swarms through interactive evolutionary design. Evolutionary design methods typically require quantitative fitness measures to evaluate the quality of design candidates and then create a next generation of design candidates based on them. However, we did not use this typical approach, because our objective was not to develop morphogenetic artifacts for specific tasks, but to explore and demonstrate the possibilities of the model behavior, where setting easily measurable metrics for automated fitness evaluation would necessarily limit the diversity and novelty of potential outcomes to be discovered.

Instead, we adopted interactive evolutionary methods [36] to discover interesting structures and collective behaviors through the active participation of human users. With the software that we developed, a human user can interactively investigate what kind of dynamic patterns or motions may emerge out of the mixtures of multiple types of particles and navigate the evolutionary design process by subjectively selecting and manipulating preferred swarm patterns (Fig. 8.9). For details of our interactive evolutionary design tools, see [37, 38]. The software tools were implemented in Java and are available online from the project website [39].

The interactive exploration was carried out online using our web-based applications. We did not set up any specific goals for the users; they freely explored Swarm Chemistry’s design space using their own subjective criteria to discover any patterns they deemed interesting. Through this exploratory effort, various self-organizing patterns were reported, including non-trivial pattern formation, mechanical or chaotic motion, and even biological-looking structures and behaviors [24, 39]. Some examples of complex self-organizing dynamic patterns acquired through interactive evolutionary design are shown in Fig. 8.10.

Fig. 8.10

Examples of self-organizing dynamic patterns evolutionarily designed in Swarm Chemistry. Many of these patterns show unique dynamic motions. To watch the actual behavior of each pattern, see the project website [39]

Fig. 8.11

Self-organization and robustness of dynamic patterns in Swarm Chemistry. a An initially randomized swarm of particles spontaneously self-organizes into a “swinger” pattern. b The “swinger” is being crushed by two invisible walls approaching from up above and underneath, but it quickly recovers when the walls move away

A remarkable feature of these patterns is their completely decentralized, robust self-organization and dynamic elasticity. Despite the lack of global information, particles can spontaneously determine “where to sit” within the swarm due to spatial sorting [27, 29] caused by the differences in kinetic properties between different types of particles, such as those reported in the previous section. Figure 8.11a shows a self-organization process starting from particles at randomized initial positions. The topological features of the final configuration depend very little on initial conditions in general. It was also observed that, in some rare cases, swarms might show sensitivity to initial conditions caused by bistability between two different stable configurations [40].

Because there are no rigid physical bonds between the particles, the self-organized patterns are highly flexible and can easily adapt to external perturbations or constraints. Figure 8.11b shows a result of one experiment where the swarm is being squeezed between two moving walls. The structure of the swarm is distorted temporarily by this external constraint, but as the walls move away, it quickly regains its original shape.

6 Self-Assembly by Local Information Transmission and Stochastic Differentiation

Building on Swarm Chemistry, we developed in a second step a generalizable methodology for creating morphogenetic artifacts that can grow and form complex structures and behaviors in a fully decentralized manner. The following three assumptions were added to the model:

• 1. Growth of a swarm is achieved by recruiting, or “eating”, inactive blank particles provided by the environment. Active particles contain their recipe and transmit it to inactive ones when they collide (Fig. 8.12a, b).

• 2. Development of structures/behaviors is achieved through random differentiation of the recruited particles. When recruited, a particle receives a recipe and then randomly differentiates into one of the multiple types specified in the recipe, with probabilities proportional to their ratio in it (Fig. 8.12c).

• 3. The particles independently re-differentiate into another randomly selected type with a small probability $r$ at every time step.

Fig. 8.12

Recruitment of new particles. a An active particle (blue) collides with a blank particle (dark gray). b The blank particle receives a recipe from the active particle through local information transmission. c The blank particle randomly chooses one of the types written in the recipe and differentiates into the selected type (orange)

This local information transmission occurs only for recruitment and initialization of blank particles, and is not used at any other times. Therefore, once growth and development are over, there is no overhead due to information transmission while the swarm operates. Furthermore, if a recipe is preinstalled in each blank particle, local information transmission is not necessary at all. Instead, stochastic differentiation can be triggered by some kinetic stimulus coming from other particles.

Fig. 8.13

Morphogenesis through recruitment of blank particles. Three examples with different recipes are shown

We also note that the third assumption in the above list (stochastic re-differentiation) mathematically guarantees that the composition of different types within a swarm will asymptotically converge to the composition of the original design given in the recipe. This is a straightforward application of simple linear systems theory. The dynamics of the relative frequencies of different types in the swarm at time $t$, $\mathbf{{p}}_{t+1}$, can be approximately described, assuming fixed population size, by

$$\begin{aligned} \mathbf{{p}}_{t+1} = (1 - r) \mathbf{{p}}_t + r \mathbf{{p}}_d, \end{aligned}$$

(8.2)

where $\mathbf{{p}}_d$ is a probability vector that represents relative frequencies of different types in the original design of the recipe. The above recurrence equation can be solved analytically as

$$\begin{aligned} \mathbf{{p}}_{t+1} - \mathbf{{p}}_d&= (1 - r) (\mathbf{{p}}_t - \mathbf{{p}}_d),\end{aligned}$$

(8.3)

$$\begin{aligned} \mathbf{{p}}_t&= (1 - r)^{t} (\mathbf{{p}}_0 - \mathbf{{p}}_d) + \mathbf{{p}}_d , \end{aligned}$$

(8.4)

which directly implies $\mathbf{{p}}_t \rightarrow \mathbf{{p}}_d$ when $t \rightarrow \infty$ for $0 < r < 1$, regardless of the initial value $\mathbf{{p}}_0$.

Figure 8.13 shows examples of this morphogenetic process. A square region is initially filled with immobile blank particles with no recipe, which serve as raw material (Fig. 8.13, left). A single active particle that contains a recipe is introduced to the center of the region. The active particle collides with blank particles through its stochastic motion, transmitting the recipe to them and thereby recruiting them into the active group. Over time, the active group grows in number, begins to form a pattern, and eventually “hatches”, launching itself into the open space outside (Fig. 8.13, right). Such morphogenetic processes may occur instantaneously or may take a long period of time, depending on the nature of the recipes.

7 Self-Repair by Stochastic Re-Differentiation

Finally, we demonstrate that the continuous stochastic re-differentiation introduced above naturally realizes a self-repair capability of swarms as it does not depend on any global information or centralized mechanisms. Figure 8.14 shows examples of such self-repair processes of swarms under two forms of major attacks. In Fig. 8.14a, 50 % of the particles are suddenly removed from the swarm during the simulation. Kinetic self-organization and stochastic re-differentiation quickly brings the swarm’s shape back to the original, only with its size halved. In Fig. 8.14b, particles of one type only are suddenly removed during simulation. Self-repair in this case takes longer than in (a), but re-differentiation gradually recovers the correct proportion between different types and the swarm’s shape eventually returns close to the original.

Fig. 8.14

Self-repair of swarms through stochastic re-differentiation. a Self-repair after removal of 50 % of the particles. b Self-repair after removal of the green particles. Re-differentiation probability is $r=0.005$

Note that re-differentiation of particles is always ongoing, and not caused by any trigger or feedback. Therefore the re-differentiation probability $r$ influences the pattern of the swarm even when it is not repairing itself, which may be varied to obtain different swarm properties. Greater values of $r$ results in faster self-repair, with more agitated, disorganized patterns, while smaller $r$ results in slower self-repair, but with more stable, organized patterns. This trade-off can be explored and the probability $r$ adjusted according to the designer’s needs.

8 Conclusions

We presented a swarm-based framework for creating morphogenetic artifacts with very simple kinetically interacting particles. Our framework assumes minimal complexity in those particles to coordinate their behaviors. The only explicit communication between particles is the one-time transmission of the recipe information from active to blank particles during the growth process. Once a particle is activated, it simply reacts kinetically to nearby particles and independently re-differentiates with small probability. This architecture demonstrates dynamic production and maintenance of patterns, which allows robust, adaptive behaviors under variable environmental conditions, including self-repair with no central controller. The simplicity of individual modules assumed in our framework will be a desirable property for low-cost hardware implementation in the future.

There are several limitations and open problems that will require attention and further investigation. First, our framework cannot produce arbitrary structures or behaviors. Since the morphogenesis depends on local kinetics only, it is not possible to create certain types of shapes, such as trees that were possible in other morphogenetic models. Identifying possible and impossible classes of patterns is therefore critical to fully understand and evaluate the potential of our framework. Introducing additional capabilities to the particles, such as cell-to-cell adhesion, should enhance the constructive capability of swarms, although at the cost of simplicity of their mechanisms.

Second, the self-organizing patterns produced in our framework moderately depends on the size of the swarm. If the number of particles is increased too much, the swarm loses coherence and the design embedded in the original recipe is not reproduced correctly. How one could (and whether one should) make a recipe truly scalable, i.e., to maintain the designed structure and behavior at a much larger scale, remains an open problem.

Third, the morphogenetic process in our framework currently has no growth-limiting mechanisms. If there are more blank particles provided in the environment, our swarms simply grow to become too big and eventually lose their unique properties. It is an interesting yet challenging question how to limit the growth of the whole swarm by using local information only.

Finally, the interactive evolutionary methods used to design recipes in the present work had several problems, such as significant cognitive burdens imposed on human designers, the lack of objective representation of specific design requirements, and obviously very limited design speed and exploratory capability. We have recently made progresses in making Swarm Chemistry spontaneously evolvable [41, 42], yet evolutionary design of swarms toward a particular target design has not been achieved yet.

In view of these limitations, our future research plans include: evaluation of programmability and scalability of this framework; exploration and implementation of distributed growth control mechanisms based on local information only; automated evolutionary acquisition of specific patterns using more objective, topological metrics; and evaluation of the applicability of the proposed framework in several scenarios relevant to real-world applications.