2.1. Artificial self-organizing systems

Artificial self-organizing systems are systems built by man that display self-organizing behavior similar to natural systems. Artificial self-organizing systems can be built for research, practical purposes, or simply enjoyment. Various systems such as robot swarms can be described as self-organizing systems, and some examples are reviewed below.

Werfel (Reference Werfel, Doursat, Sayama and Michel2012) demonstrated a promising application for CSO systems: collective construction. Drawing inspiration from social insects such as termites, which can build mounds up to 8 m tall (Korb Reference Korb, Bigness, Roisin and Lo2011), Werfel developed a system of swarm robots that can build a prespecified two-dimensional shape out of square bricks. Localization and gripping are the main barriers to this type of construction, but Werfel introduced simple remedies for both problems. Claytronics (Goldstein & Mowry, Reference Goldstein and Mowry2004) is an attempt to create millions of tiny interacting robots with no moving parts that can use one another as anchor points for locomotion and ultimately become a new, three-dimensional medium for communication. Beckers et al. (Reference Beckers, Holl, Deneubourg, Bielefeld and Bielefeld1994) describe a robotic gathering system, where robots move around an arena collecting pucks. Robots are more likely to drop pucks in an area of high puck density. This causes a positive feedback loop that results in a single group of all available pucks.

In all of these cases, the agents fulfilling the task had very little knowledge of the global-level functional requirement. Communication with near neighbors was required in Claytronics, but only indirect communication via the state of the task completion was used in the gathering and collective construction tasks. The agents used were very simple, but with the proper selection of local interaction rules, useful emergent behavior was demonstrated.

2.2. Evolutionary optimization of complex systems

Computer optimization of complex problems is an active area of research in mathematics, computer science, and artificial intelligence. Optimization of such systems is difficult, because the link between the input parameters and the global measured behavior is often unclear and nonlinear. In addition, the behavior of interest may be transient, emergent, or otherwise hard to measure (Calvez & Hutzler, Reference Calvez, Hutzler, Sichman and Antunes2006). Nonetheless, there are many successful demonstrations of evolutionary optimization of complex systems in the literature.

Ueyama et al. (Reference Ueyama, Fukuda and Arai1992) used a GA to optimize a path-planning algorithm in a simulation of their distributed CEBOT robotic swarm. Stonedahl and Wilensky (Reference Stonedahl and Wilensky2010) used a GA to develop flocking rules that would exhibit emergent behavior such as cohesive flocking, V-formation, and volatility. GA has been used to tune the update rules of cellular automata in order to complete the “majority classification” task (Mitchell et al., Reference Mitchell, Crutchfield and Hraber1994; Crutchfield et al., Reference Crutchfield, Mitchell and Das1996). The GA evolved intelligent update rules that allowed cellular automata cells to distribute information about local densities to other remote cells. GA's close relative genetic programming was used in (Van Berkel et al., Reference Van Berkel, Turi, Pruteanu and Dulman2012) to combine functional primitives to recreate natural collective phenomena such as firefly synchronization and ant foraging.

These examples show that, given a proper fitness function, evolutionary approaches are a viable strategy for the optimization of complex and self-organizing systems. By application of GAs, genetic programming, or other approaches, researchers have been able to efficiently explore vast search spaces and optimize systems that display complex behavior and require the simultaneous tuning of many input variables.

2.3. Evolutionary and computational design

Automated approaches to traditional design can be aided by processes that build up system functions from component primitive functions. Given a set of primitives, and a grammar for combining them, some of the design work can be done by computers (Sridharan & Campbell, Reference Sridharan and Campbell2005), and GAs have been used to automatically develop function–structure diagrams for routine designs (Jin & Li, Reference Jin and Li2007). These approaches have found success in the computational synthesis of simple designs. The complex interactions among the agents of self-organizing systems make a function–structure approach to their design very difficult to implement.

Our evolutionary optimization of CSO systems is most similar to the concept of evolutionary embryogeny, which has been used to evolve growth rules for vertical structures that must support a horizontal load (Yogev et al., Reference Yogev, Shapiro and Antonsson2008). In our approach, and in the embryogeny approach, the description of the system goes through a mapping process before the structure of the system is determined. This mapping process is the self-organized task completion in our CSO systems and the growth process in artificial embryogeny. This indirect mapping allows more complex structures to arise from simpler descriptions, which can shorten the description required and shrink the space of the search for a proper description (Bentley, Reference Bentley1999). Unlike artificial embryogeny, we do not allow the cells of our system to grow and divide. Another subtle but important difference is that in artificial embryogeny, the self-organizing rules are executed at design time, specifying the final geometric structure of the system, whereas in our CSO systems, the rules themselves are the product of the design, and the system is allowed to self-assemble at run time.

In our research, we apply GA to evolve the self-organization mechanisms. The challenge is to develop a generic self-organization parametric model that is general enough to characterize the rich self-organizing behavior of agents, and constrained so that it will work within the GA framework for computational synthesis. We introduce a two-field based model below.

3.1. Task field

The task field of a CSO system represents the agents' perception of fixtures of the environment and objects involved in the system's tasks. Here we include terrain, laws of nature, responses to obstacles, and attraction of the system's goal (when applicable) as elements giving rise to the task field. In the multiagent box-pushing example (Chen & Jin, Reference Chen and Jin2011), the mCells do not communicate in any substantial way, but act entirely based on the task field caused by attracting and repelling forces in the environment. For an agent i, and m objects to be approached and n objects to be avoided in the field, the task field seen by the agent i can be expressed as

(1)$$tFiel{d_i} = {\rm FL}{{\rm D}_{\rm T}}\left ( {{{\rm \theta }_1}\comma \ {{\rm \theta }_2}\comma \ .\ .\ .\ \comma\ {{\rm \theta }_m}\comma \ {{\rm \beta }_1}\comma \ {{\rm \beta }_2}\comma \ .\ .\ .\ \comma \ {{\rm \beta }_n}} \right) \comma$$

where FLD_T is a task field generation operator.

In some self-organizing systems, the agents interact with the object of the tasks in such a way that updating its state gives agents information on how to further update its state toward the final goal; this is called stigmergy and is a way of using a changing task field to generate emergent behavior. Stigmergy, or work-creating-work, can be thought of as a dynamic task field. Stigmergy in collective robotics can be used for gathering tasks (Beckers et al., Reference Beckers, Holl, Deneubourg, Bielefeld and Bielefeld1994; Song et al., Reference Song, Kim, Shell, Dorigo, Birattari, Blum, Christensen, Engelbrecht, Groß and Stützle2012) and has been shown to be the mechanism by which termites organize to build their mounds (Korb, Reference Korb, Bigness, Roisin and Lo2011). “Extended stigmergy” (Werfel & Nagpal, Reference Werfel and Nagpal2006) is a more extreme example, where blocks in a building task are encoded with radiofrequency identification chips or other mechanisms for conveying more precise messages from agent to agent. In each case of stigmergic self-organization, the interactions among agents were indirect and unsynchronized, meaning that there was a possible delay between the time a message was sent and the time it was received. Because the medium of signaling was also the task object of interest, we can classify this self-organizing behavior as a response to a changing task field.

3.2. Social field

In addition to task situations, an agent's behavior can be affected by other agents. The social field arises from agents' influence on one another and forms another layer of information for the system to use. Explicitly distinguishing between task field and social field allows us to design needed social structures for agents to complete their tasks in variable task environments. To cope with a given task field, an agent can explore and develop its social relations (i.e., agent–agent relations), which should resolve possible conflicts and foster cooperative interactions.

Researchers have used various communication strategies among agents to explore social fields. In some systems (Reynolds, Reference Reynolds1987; Cucker & Smale, Reference Cucker and Smale2007; Chiang & Jin, Reference Chiang and Jin2011), agents sense one another's presence and react directly while traveling mostly through empty space. Thus they have little concern with a task field, and the social field dominates. Signals can also be used to build a social field. Communication strategies such as “pherobots” (Payton et al., Reference Payton, Daily, Estowski, Howard and Lee2001) or hormone-inspired robotics (Shen et al., Reference Shen, Salemi and Will2002) can be described as different ways of creating a social field. An extreme example of a social field is given in Bai and Bree (Reference Bai, Bree, Doursat, Sayama and Michel2012). These authors use genetic programming to evolve mathematical formulas for field generation. Each agent in their simulation propagates a field in its local vicinity according to a complicated mathematical function, and senses the fields generated by others. Agents then follow the gradients of the field to form shapes.

In our research, an agent constructs its social field based on its relations with observable neighboring agents. For agent i with n observable neighboring agents, we have

(2)$$sFiel{d_i} = {\rm FL}{{\rm D}_{\rm s}}\left({{{\rm \varphi }_{i1}}\comma \ {{\rm \varphi }_{i2}}\comma \ .\ .\ .\ \comma \ {{\rm \varphi }_{in}}} \right)\comma \$$

where FLD_s is a social field generation operator and φ_i1, φ_i2, … , φ_in are agent i's relations with other agents. If the social relations can be captured simply by attraction, repulsion, and state information, then we have

(3)$${{\rm \varphi}_{ij}} = \left\{{\matrix{ {{{\rm \alpha }_j}} \cr {{{\rm \rho }_j}} \cr {{{\rm \sigma }_j}} \cr } } \right\}\comma \;$$

where α, ρ, and σ represent a neighbor's attraction, repulsion, and state, respectively.

In self-organizing systems, communication among agents is often not one-to-one. Rather, agents create a field of influence in their vicinity. The omission of one-to-one messaging makes it possible to have a truly distributed and decentralized system, where an individual agent does not even have a unique identification. This adds resilience to the system, because the failure of one agent does not immediately imply failure of the system; another identical agent can always take its place.

With limited sensory capabilities, no complete and static field function can be generated for self-organizing systems, because agents' perception of field values changes with their position (e.g., if a repelling object moves into or out of an agent's sensory range). This makes mathematical proofs of stability difficult, so simulation is used to give statistical confidence in system performance.

3.3. Cellular (agent) behavior

In a CSO system, the behavior of an individual mCell is defined by a mapping process:

(4)$$b = \left\{{{S_E}\comma \; {A_E}} \right\}\to {A_N}\comma \;$$

where S _E and A _E are the mCell's current sensory information and actions, respectively, and A _N is the mCell's next chosen action. The overall behavior of the system (BoS) is then

(5)$${\rm BoS} = \left\{{{B_1}\comma \ {B_2}\comma \ .\ .\ .\ \comma \ {B_n}} \right\}\comma \$$

where B _i represents the set of all possible behaviors {b ₁, b ₂, . . .} of mCell i. A designer must develop a correct behavioral mapping such that the BoS fulfills the system's functional requirements. An FBR has been proposed (Jin & Chen, Reference Jin and Chen2012) for the single task field models. In this research, we consider two fields, task field and social field. Figure 1 illustrates our field-based cellular behavior regulation in the two-field based model context. Equation (6) is a two-field based FBR for given function requirements (FR), environment (Env), and agents (a ₁, … , a _n):

(6)$$\eqalign{{b_{t + 1}} & = {\rm FB}{{\rm R}_{{\rm BS}}}\lpar {\rm FB}{{\rm R}_{{\rm FT}}}\lpar {\rm FL}{{\rm D}_{\rm T}}\lpar {{\rm SN}{{\rm S}_{\rm T}}\lpar {{\rm F}{{\rm R}_{\rm t}}\comma \; {\rm En}{{\rm v}_{\rm t}}} \rpar } \rpar \; \cr & \quad \times {\rm FL}{{\rm D}_{\rm S}}\lpar {{\rm SN}{{\rm S}_{\rm S}}\lpar {{a_{1t}}\comma \ {a_{2t}}\comma \ .\ .\ .\ \comma \; {a_{nt}} } \rpar \comma \; {\rm \; state}}\rpar \rpar \rpar \comma} \;$$

where SNS_T/S is the task/social field sensing operator; FLD_T/S is the task/social field generation operator; FBR_FT is the task to behavior field transformation regulator; FBR_BS is the behavior selection regulator; tField is FLD_T(task information), which is FLD_T(SNS_T(FR_t, Env_t)): task field; sField is FLD_S(social information), which is FLD_S(SNS_S(a _1t, a _2t, … , a _nt), state): social field; bProfile is FBR_FT(tField, sField): behavior profile; and b _t+1 is FBR_BS(bProfile): selected behavior for the action of the next step.

Fig. 1. The two-field based model context field-based behavior regulation .

Every mCell makes this decision and acts in parallel in discrete time steps. The behavior output process is a function of the state of an mCell and its neighbors, the social field (sField), the task field (tField), and the set of behavioral primitives, where state can consist of internal state variables known to a particular agent (e.g., memory, sensor values, and contents) and external variables known to all agents (e.g., location, speed, and color).

SNS_T and SNS_S are sensing operators that identify an mCell's task environment and social environment, respectively. The task field formation operator FLD_T abstracts task and environmental stimuli to create a mathematical task field. At the same time, the mCell can also identify its neighboring agents and form a social field through its social field operator FLD_S. Based on the information defined by the two interacting fields, the mCell creates a behavioral profile through the operator FBR_FT. The resulting behavioral profile is composed of a set of (behavior, preference) pairs. The final step is behavior selection based on operator FBR_BS.

The sField contains all social relationships affecting an agent. The sField must contain both a topology and a policy. The topology determines the allowable agent relationships (i.e., which relationships have any meaningful effect). The policy determines the strength of interactions between the agents who fulfill one of the allowable relationships. In a general heterogeneous system with M number of agent types, the topology can be described as a matrix of relationships:

(7)$$R = \; \left[{\matrix{ {{r_{11}}} & \cdots & {{r_{1M}}} \cr \vdots & \ddots & \vdots \cr {{r_{M1}}} & \cdots & {{r_{MM}}} \cr } } \right]\comma \;$$

(8)$$r_{ij}^k = \left\{{{\rm trigger}\comma \; p\left({S{E^k}\comma \; {c^k}} \right)} \right\}\comma \;$$

where r _ij is the policy of an agent of type i toward an agent of type j. The trigger is a condition that causes the relationship to take effect. Here, p is a reaction to the external state of neighboring mCell k and its communication, if any. In general, we want these relationships to be anonymous and not determined for any specific mCells, just for mCell types, so r _ij should be the same for every agent k of type j. The matrix is not necessarily full or symmetric.

The tField contains important objects, locations, and constraints in the system's task and environment:

$${\rm tField} = \lcub {{\rm TO}\comma \ {\rm TL}\comma \ {\rm EO}\comma \ {\rm EL}} \rcub$$

$${\rm TO} = \lcub {{\rm t}{{\rm o}_1}\comma \ {\rm t}{{\rm o}_2}\comma \ .\ .\ .\ \comma \ {\rm t}{{\rm o}_{\rm p}}} \rcub$$

$${\rm TL} = \lcub {{\rm t}{{\rm l}_1}\comma \ {\rm t}{{\rm l}_2}\comma \ .\ .\ .\ \comma \ {\rm t}{{\rm l}_{\rm q}}} \rcub$$

$${\rm EO} = \lcub {{\rm e}{{\rm o}_1}\comma \ {\rm e}{{\rm o}_2}\comma \ .\ .\ .\ \comma \ {\rm e}{{\rm o}_{\rm r}}} \rcub$$

$${\rm EL} = \lcub {{\rm e}{{\rm l}_1}\comma \ {\rm e}{{\rm l}_2}\comma \ .\ .\ .\ \comma \ {\rm e}{{\rm l}_{\rm s}}} \rcub \comma$$

where TO, TL, EO, and EL are task objects, task locations, environmental objects, and environmental locations, respectively. The address of a goal is an example of a tl_i, and a set of obstacles is an example of the list of environmental objects.

Generally speaking, social field manipulation is associated with a self-organized structure of the system. The fulfillment of the task requirements often depends on the structure of the system. Organization theory claims that organizations form structures that are dependent on their task and environment (Thompson, Reference Thompson1967). This suggests that better system functionality can be achieved through the self-organized emergence of complementary social structure and behavior, and we propose the use of a social field and task field to generate this.

5.1. COARM behavioral model

An in-depth description of flocking capabilities in a CSO system is given in (Chiang, Reference Chiang2012), where various relative weights given to flocking behaviors at the local level result in standard flocking, spreading, obstacle avoidance, or searching activity at the system level. This paper's flocking simulation was inspired by the work of Reynolds (Reference Reynolds1987) and Wilensky (Reference Wilensky1998b). The flocking mCells represent small robots moving on a two-dimensional surface in a torroidal (wrapped) world. Each mCell has a limited sensory range and very little memory. At each time step, an mCell will sense the positions and heading of all the other mCells within its radius of vision and react according to a set of predefined rules. These rules take the form of five competing desired step vectors. The five mCell behaviors are defined as

1. 1. cohesion: step toward the center of mass of neighboring agents

2. 2. avoidance: step away from agents that are too close

3. 3. alignment: step in the direction that neighboring agents are headed

4. 4. randomness: step in a random direction

5. 5. momentum: step in the same direction as the last time step

The acronym COARM is used to refer to these behaviors (Chiang & Jin, Reference Chiang and Jin2011). An agent calculates the cohesion, avoidance, and alignment directions according to its locally sensed sField. Because this is a homogeneous system, the sField description includes only one type of relationship r ₁₁, whose trigger is proximity (within three mCell diameters). Essentially, the mCell is responding to attraction (C) and nonlinear repulsion (O), and tries to match velocity (A) for each other cell in its neighborhood. The relevant state variables are the output of a random number generator for the randomness behavior, and an mCell's last step, which creates the momentum behavior. There are no tField objects:

(9)$${b_{t + 1}} = {\rm FB}{{\rm R}_{{\rm BS}}}\left({{\rm FB}{{\rm R}_{{\rm FT}}}\left({{\rm FL}{{\rm D}_{\rm S}}\left({{\rm SN}{{\rm S}_{\rm S}}\left({{a_{11}}} \right)} \right)} \right)\comma \; {\rm State}} \right).$$

Figure 4 displays the spatial coordinates that an mCell's SNS operators obtain. The field transformation operator will assign a field value to every point within its stepsize limit. The field transformation functions are given in the following equations, based on sField and state, respectively:

(10)$${\rm FL}{{\rm D}_{\rm s}}\left({r\comma \; {\rm \theta }\comma \; {\rm \phi} } \right)= - r + \displaystyle{{ - 1} \over r} +\Vert v\Vert \cos \left({{\rm \theta } - {\rm \phi} } \right)\comma \;$$

(11)$${\rm FLD}\left({r\comma \; {\rm \theta }\comma \; {\rm \phi} } \right)= \Vert{v_0}\Vert\cos \left({\rm \phi} \right)+ {\rm step} \times \cos \left({{\rm RA} -{\rm \phi} } \right)\comma \;$$

where v ₀ is an mCell's current velocity (last step), RA is an angle output by a random number generator, step is the magnitude of the random behavior, ϕ is the angle from an mCell's current heading, v is a neighbor's velocity, θ is a neighbor's current heading relative to the mCell, and r is the scalar distance from the neighbor. Note that terms involving r are measured from the neighbor's position, and terms involving angles are measured with the mCell at the origin with a heading of 0 degrees.

Fig. 4. A mechanical cell and neighbor frames of reference.

The social field policies are applied to every neighbor in an mCell's radius of detection, and all terms from Equations (10) and (11) are added together in a parameterized sum to perform the FBR_FT operation:

(12)$$\eqalign{{\rm FLD}\lpar r\comma \; {\rm\theta} \comma \; {\rm \phi} \rpar = \ & c \times \displaystyle{{ - 1} \over N}\sum\limits_{\rm i \in \eta }^N {{r_i} + o \times \displaystyle{{ - 1} \over N}} \sum\limits_{\rm i \in \eta }^N {\displaystyle{1 \over {{r_i}}}} \cr & \! + A \times \displaystyle{1 \over N}\sum\limits_{\rm i \in \eta }^N {{\rm \Vert }{v_i}{\rm \Vert }\cos \lpar{\rm \theta} - {\rm \phi} \rpar + R \times {\rm step}} \cr & \! \times \cos \lpar {\rm RA} - {\rm \phi} \rpar + M \times {\rm \Vert }{v_o}{\rm \Vert }\cos \lpar {\rm \phi} \rpar, }$$

where the COARM acronym returns, this time to represent the parameters in the field transformation equation. This equation maps each point in the plane to a preference value, creating the necessary (behavior, preference) set for behavior selection. The behavior selection is to simply move to the location within the maximum stepping distance with the highest preference. We allow the GA to change the relative weights of the COARM parameters, which will change the behavior of each mCell and consequently the emergent behavior of the system.

5.2. Flocking

To evolve flocking, an initial population of 15 candidate genomes was generated. The genomes consist of 40-bit binary strings, which can be parsed as five 8-bit, binary numbers. Each binary number sets the relative weight of a COARM parameter, and the parameters varied from 0.02 to 50. After mapping the genome to COARM parameter values, a simulation with these parameters was created in NetLogo. In the simulation, 30 mCells were initially placed on the field and allowed to run for 250 time steps.

The normalized total momentum of the system at the end of the run is used as the fitness function. This will have a value of 1.00 if all agents are moving in the same direction with maximum step size, and an expected value of 0.00 if agents are moving in random directions.

(13)$$\mathop{M} \limits ^{{\rightharpoonup}} = \sum\limits_{i\,=\,1}^N {\mathop{v} \limits ^{{\rightharpoonup}}}_i\comma$$

(14)$${\rm fitness} = \displaystyle{ {\Vert\mathop{M} \limits ^{{\rightharpoonup}} \Vert}\over N}\comma \;$$

where N is the total number of mCells. Fitness scaling (Sadjadi, Reference Sadjadi2004) was used so that the best candidate in any generation had a fitness 30% greater than the average of all candidates in that generation. The best candidate at each generation was cloned to the next generation, and the remaining candidates were stochastically selected, with replacement, for single-point crossover with probability proportional to their fitness, until the next generation of 15 candidates was full. All nonclones were allowed to mutate, with a probability of 1% per bit of genome. This process was repeated for 40 generations. A full GA run required 11–14 min on a laptop computer with an Intel 2.2-GHz dual core processor and 4 GB of RAM.

Unrestricted, the GA will quickly maximize the relative weight of the alignment behavior for this fitness function. Figure 5 displays the evolution of the average parameter values among the 15 genomes at each generation. The relative weight of randomness was fixed at 1.00 because it was primarily the ratios of weights that mattered, not the absolute magnitude. The figure clearly shows a population takeover by systems with large alignment parameters.

Fig. 5. Flocking average parameter values.

Figure 6 displays the progression of fitness across generations for the same GA, where the fitness of the best candidate at each generation and the average of all candidates at each generation are plotted separately.

Fig. 6. Flocking fitness evolution.

This optimization strategy seemed obvious, because the alignment behavior causes agents to match their heading with their neighbors. Given enough time, it seems intuitive that a system of agents focused on local alignment will eventually reach a state of global alignment, so in order to further challenge the algorithm, a new flocking behavioral model was established with the restriction that the relative weights of alignment and randomness must be equal (set to 1 in this instance). This makes the optimization much more difficult, because randomness counteracts the tendency toward coherent flocking that alignment builds. The results are given in Figures 7 and 8.

Fig. 7. Flocking fitness with equal alignment and randomness.

Fig. 8. Flocking parameter values with equal alignment and randomness.

These results showed more inconsistency when compared to the unrestricted flocking example, but by the final generation, the best-of-generation candidates did display high fitness values, indicating that they were moving as a group with a single heading. The “strategy” found by the GA was to make both alignment and randomness mostly irrelevant by keeping the momentum weight very high. As long as the cohesion and avoidance balanced each other (it was sufficient that they differ by a factor of <5), the momentum could act as a system memory, allowing the alignment tendency to slowly build up during the course of the simulation, while the randomness effects cancelled themselves out.

5.3. Territory exploration

One of the goals in designing self-organizing systems is flexibility, so we attempted to use the same hardware assumptions and behavioral model as the flocking simulation to perform a different task: exploration. The change in functionality is a result of the change in relative parameter values. Here, 11 mCells are initially placed in a line in the center of the world and allowed to uncover white patches by moving near them and darkening them. A run lasted 200 time steps, and the fitness of the run depended on how closely the system came to matching the desired amount of exploration. The desired exploration amounts ranged from 0% to 100%. Because GAs are stochastic, there is no guarantee that multiple runs will converge to the same set of parameters. While the results were mostly consistent in the flocking experiments, in the exploration experiments, qualitatively different behavioral strategies for the same FR were often evolved in different GA runs. These systems appear to work very differently, but their overall fitness scores are similar. Figures 9 through 12 show the behaviors evolved for 25% and 100% exploration, respectively.

Fig. 9. High-avoidance, low-momentum for 25% exploration.

It can be seen from these figures that two distinct successful behavioral profiles were developed for each of 25% and 100% exploration. The high-avoidance, high-momentum strategy for 100% exploration (Fig. 11) can be thought of as the intuitive strategy. The high avoidance and high momentum cause the mCells to immediately spread out in different directions and continue in straight lines until they come near each other, when they diverge again. This causes the mCells to independently explore most of the field without wasting time by following one another and poring over trodden ground. The fanning and sweeping strategy of Figure 12 was actually more effective and relied on a novel combination of flocking and expansion. With high alignment, and a proper ratio between cohesion and avoidance, the mCells in this simulation were able to spread to the width of the arena and complete a full lap within the 200 time step limit, uncovering almost 95% of the field.

Fig. 10. High-alignment, high-cohesion for 25% exploration.

Fig. 11. High-avoidance for 100% exploration.

Fig. 12. High-alignment, high-momentum fan/sweep behavior for 100% exploration.

The 25% exploration task required a method of slowing down the exploration so that the system was not penalized for uncovering too much of the field (the mCells were forced to run for the full 200 time steps regardless of their progress). Figure 9 shows one successful strategy for halting exploration at the correct percentage. In this configuration, the mCells are assigned high avoidance and very low momentum. This causes an initial expansion, but the trajectories are unsustainable because there is no momentum to carry the mCells forward. Once they are out of one another's sensory radius, their randomness dominates because cohesion, avoidance, and alignment are only active when there are neighbors nearby. As a result, after the initial short expansion, the mCells tend to stay in place and randomly move about a point, not uncovering much new territory, so that by the end of the run, as a system they have uncovered approximately 25% of the field. Figure 10 shows a more novel behavioral strategy for 25% exploration that was evolved by some applications of the GA. In this case, the mCells' high alignment and cohesion tendencies caused them to form single-file lines. After the initial formation of the file, the swarm would extend out from its starting point and uncover a narrow swath of new territory. This system actually exploited the time limit as a resource, because it was still exploring new territory up until the cutoff, but the time required to initially form the structure and the slow rate of discovery reliably led it to discover close to 25% of the field just before the simulation stopped.

5.4. Foraging

Foraging is another task that can be performed by self-organizing systems. It is particularly interesting for us because, in addition to coordinating movements relative to other agents, agents in foraging must complete specific tasks of moving food from sources to home. With this case study, we intend to test how task requirements, such as moving food, can be modeled and captured by our task fields (tFields), and how such complex task fields can be coped with by more sophisticated relations (sFields) among the agents. Most foraging simulations are inspired by ants, which communicate via pheromones. Artificial systems could accomplish the foraging task using electromagnetic signaling. In our simulation, color signaling is assumed for the purpose of on-screen visualization. Our mCells are allowed to change color based on their current task and state. The parametric behavioral model is expanded so that mCells may have different reactions to other mCells of diverse states, a purposeful introduction of heterogeneity into the system.

The agents' visible states include location, color, and heading. The task object is the food, and the task goal is the home base where food is to be returned. The sField relationships are triggered by proximity within three mCell diameters. Food can be sensed within this same neighborhood, and the direction toward home can be sensed at all times. This simulates the situation where there is a central beacon (ants have the large concentration of pheromones emanating from their nest) signaling to all agents simultaneously, but not controlling any individual's actions. In a practical situation, the beacon could be broadcast from a boat at night in a search-and-rescue mission, from a disposal zone in a beach cleanup task, or from a silo in a harvesting system. The sField relationships are the same as in Equation (10), and the field transformations of tField and state parameters are modeled as:

(15)$$\eqalign{\hbox{FL D}_{\rm T}\lpar r\comma \; {\rm \theta }\comma \; {\rm \phi} \rpar & = {\rm step} \times \lpar \cos \lpar {\rm RA} - {\rm \phi} \rpar + \cos \lpar f - {\rm \phi} \rpar \cr & \quad + \cos \lpar h - {\rm \phi} \rpar \rpar \comma}$$

where f and h are the angles toward food (when sensed), and home, respectively.

Because an individual mCell's behavior must be different depending on whether it is carrying food, mCell behaviors are highly dependent on state. Because the mCells are allowed to differentiate, the description of the sField and the decision structure must be more complex than in the flocking and exploration tasks. Here, we assume that mCells will differentiate into two types: those with food and those without. Because we rely on the GA, it is feasible to define a large number of allowable relationships. We define the maximum number (4) based on the number of distinct agent types (2). In larger systems, it may be desirable to limit the interactions among different sets of agents. In any case, if the social topology is too interconnected for the task, we should expect the GA to minimize interaction magnitudes between agent types that should not be linked.

The policies defined for these relationships will be based on the cohesion, avoidance, and alignment parameters of the COARM model described earlier. Momentum is not used, and randomness is treated separately because it does not depend on agent interactions. Once an mCell has identified its neighbors and their type, it will apply the parameters of its policy for each neighbor. The mCells generate their tField by sensing the home beacon and food, and their reactions are simple attraction or repulsion. The tField and sField are added together by the mCells to form the behavioral profile:

(16)$$\eqalign{{\rm FBR}_{\rm FT}\lpar r\comma \; {\rm \theta} \comma \; {\rm\phi} \rpar & = C \times \displaystyle{1 \over N}\sum\limits_{i \in \rm \eta }^N \lpar \!-\! {r_i}\rpar + O \times \displaystyle{1 \over N}\sum\limits_{i \rm \in \eta }^N \displaystyle{ - 1 \over r_i} \cr & \quad + A \times \displaystyle{ - 1 \over N}\sum\limits_{i \rm \in \eta }^N \Vert v_i \Vert \cos \lpar {\rm \theta} - {\rm \phi} \rpar \cr & \quad + {\rm step} \times \lpar R \times \cos \! \lpar {\rm RA} - {\rm \phi} \rpar \cr & \quad + {F} \times \cos \! \lpar f - {\rm \phi} \rpar + H \times \cos \! \lpar h - {\rm \phi} \rpar \rpar \comma \;}$$

where the relevant parameters are applied based on the mCell's state. If necessary, the summations are carried out twice with different parameters to account for a heterogeneous set of neighbors. Because the flocking behaviors are normalized before addition, a large flock with no food will have the same relative influence as a small flock with food and vice versa. Behavior selection is to simply choose the location within the maximum step size that has the highest field value.

When an mCell moves onto a patch that contains food, it extracts 5 units of food from the resource and changes its color to green. If it carries food back to the home base, it deposits the food and changes back to brown, and the simulation counts that toward the food-returned total. The fitness is then calculated according to

(17)$${\rm fitness} = {\rm foo}{{\rm d}_r} + \displaystyle{1 \over N} \sum\limits_{i=1}^N {\rm foo} {\rm d}_{c_i}\comma \;$$

where the summation occurs over each mCell. Subscript r represents the food returned to home before the time limit, and subscript c represents the food being carried by the agents at the time limit. The summation in this equation is used to differentiate systems early in the GA, where only a few systems return any amount of food. The design gets “partial credit” for at least finding food, and this behavior is eventually combined with other positive behaviors to create more successful systems in later generations.

An initial population was randomly seeded as 50, 144-bit, binary strings. Every 8 bits of the genome corresponds to one of the 18 agent parameters of Table 1. With 18 parameters to optimize, an exhaustive search would be very computationally expensive. A naïve parameter sweep, with just three levels for each variable (e.g., low, medium, and high), would require more than 3.8 million simulation runs. The use of an optimization algorithm cuts this number down substantially while still generating capable candidates. All of these GA experiments used fewer than 10,000 repeated simulation runs. The binary numbers were mapped to decimal numbers between 0.02 and 50 for cohesion, avoidance, and randomness. Alignment and the tendency toward food and home varied between –50 and 50. The best candidate of each generation was cloned directly to the next generation, and the remaining candidates were created using the same fitness scaling, selection, and crossover of the previous case studies. The mutation probability was 0.5% per bit of genome for all nonclones. A 100-candidate, 50-generation (5000 total fitness evaluations) GA run required approximately 14 h to complete.

Table 1. Foraging simulation parameters

It can be seen from Figure 13 that the GA showed continual improvement in the best-of-generation fitness and average fitness values. The best candidate of the first generation returned 30 units of food (6 round trips), and the best of the final generation returned 180 units of food (36 round trips). The best fitness found in any generation was 205 in the 41st generation. Owing to the elitism component of the GA, this candidate was cloned to the next generation, but it was unable to reliably reproduce such great results. It was eventually replaced, although its genes did propagate to future candidates. Other GA runs produced qualitatively similar results, with no obvious improvement in runs lasting longer than 50 generations. Because there were 18 variables to optimize, and the populations showed considerable diversity, it is not illuminating to show a plot of the average parameter values across generations. Instead, we look at the randomly chosen parameters of the best candidate of the first generation and compare them to the evolved parameters of the last generation's top candidate.

Fig. 13. Foraging experiment fitness evolution.

Table 2 shows the parameter values of the first generation's most successful candidate. The simulation screenshots in Figure 14 illustrate the behavior of this system. This candidate's behavior relied on a very high tendency toward home when an agent had food (H₁), and a very high tendency away from home when an mCell did not have food (H₂). This was enough to place one or two mCells on a straight line between the base and the food, allowing them to make about 6 round trips. The high cohesion/avoidance ratio among the mCells without food led to the ineffective grouping at the right edge of the field.

Fig. 14. Foraging behavior for best candidate of first generation. Home is at bottom left, and the food is at top right.

Table 2. Foraging parameters for best candidate of first generation

Table 3 shows the parameters that were evolved for the best candidate in the final generation. Note the very large negative alignment parameter between agents that both had no food (A₄). Generally, the mCells with food have a strong tendency to align with one another, while the mCells without food have a strong tendency to maintain opposite headings. The magnitudes of the interactions between agents of different states are small.

Table 3. Foraging parameters for best candidate of final generation

The “strategy” evolved was to use the edges of the arena to guide the agents toward the food, because the food was placed in a corner opposite the home base. To accomplish this, the mCells without food had negative alignment values toward one another. This caused an initial shuffling period because the group could not reach an equilibrium flocking heading. Eventually the mCells spread far enough apart that their negative home tendency dominated and drove them toward the top and right edges of the field, with a few mCells randomly finding the food area. The system eventually reached a state where most mCells without food were on an edge, but the negative alignment values ensured that they did not get stuck. If a new mCell arrived at the edge near another, one would have to change direction so that they could maintain opposite headings. This caused a chain reaction of mCells bumping each other off the edge until one reached the food, when its strong positive home tendency would take over. After returning the food, an mCell's negative home tendency would cause it to move toward an edge again, starting another chain reaction. This configuration persisted until the 1000 step time limit, as shown in Figure 15, allowing the system to return 180 units of food. In these lines of mCells on the edge, we see the social field giving rise to task-based structure that allowed the system to complete its FR.

Fig. 15. Foraging behavior for best candidate of final generation.