Behavior-finding

Behavior-finding problems are a new class of problems that search for solutions whose behavior (as the result from the interaction of its form with an environment) verifies a set of restrictions. Consequently, the fitness of a solution is evaluated as how it behaves in a concrete environment, in contrast with the traditional form-finding problems, where solutions are evaluated according directly to their shape.

We have proposed and tested evolutionary developmental models, inspired in natural evolution and the developmental process and regulation of organisms, to solve behavior-finding problems. The results demonstrate the benefits of the models compared to traditional direct encoding approaches, such as high diversity, regularity, organicity, generalization, and modularity; properties that are highly valuable in an engineering context.

In the following sections, we present two evolutionary developmental models that have been tested in finding structures that can land properly or that can follow a predetermined path.

 

Landing of tensegrity structures

We describe in this section the first evolutionary developmental model proposed, which has been tested to solve the problem as to how a vehicle, configured as a mass-spring network, might land properly when falling from a given height.

The evolutionary model is based in an indirect developmental encoding with a grammatical nature. An individual represent a structure encoded as a graph and it develops according to the information contained in its genome, by regulated rewriting of an initial graph under the control of a regulated graph grammar. The following diagrams show the rules implemented in the model and an example of the development of an individual.

1.grammar
 
Production system of the regulated graph grammar. Every rule represent a developmental action that cells can perform during development (left) and how the rest of their expression domain is distributed among the new cells (right).
 
 
2.derivation
 
Derivation steps of the development of an example organism. Edges express the first gene in their expression domain (blue), applying the corresponding grammar rule and distributing the rest of the domain among their new edges.
 

In this way, every edge of the graph represents a cell of the individual and includes the genetic and physical cellular information. Accordingly, the nodes of the graph constitute the adhesion points of neighboring cells. The following diagram represents a developing individual and the information stored in every cell.

3.organism
Diagram of a developing multicellular individual, representing the genetic and physical cellular information.
 

Edges have been modeled as damped springs, while nodes are free movable joints. In this way, a physical simulator has been implemented (freely downloadable here) to test the behavior of the evolved spring networks during the landing test. Hence, the fitness of an individual in the evolutionary algorithm represents how well it managed landing, by minimizing the distance traveled during the landing and impact force (jerk).

Additionally, the proposed model has been compared with a traditional direct encoding scheme. The following figure compares the performance of both encodings, showing the average fitness curves over 50 runs. In both cases, it is observed a quick fitness improvement in the first 100 generations, followed by a gradual refinement as the evolution progresses.

4.evoDirect 5.evoIndirect
Direct encoding   

                     Indirect encoding

Average best, mean, and worst fitness for each generation of 50 evolutionary runs using direct encoding (left) and indirect encoding (right). Both encoding strategies can find good solutions to the landing problem.

 

The best tensegrity structures evolved in six different evolutionary runs with the direct encoding method are represented below. The edges of the structures are colored according to its internal tensile state, being red edges compressed and blue edges stretched. They are characterized by its irregular shapeless organization and lack of modularity.

6.resultsDirect

Best tensegrity structures evolved in six different evolutionary runs using direct encoding. They are characterized by its irregular shapeless organization and lack of modularity.

 

In clear contrast, the proposed method based on graph grammars generates structures that follow patterns and regularities due to their rewriting nature. Diverse examples are presented in the following figure, which shows the phylogeny of evolved tensegrity structures using indirect encoding. Each row represents a selection of evolutionary steps of the best evolved tensegrity structures in five different evolutionary runs, ordered from the first generation (left) to the last generation (right).

7.resultsIndEvo

Phylogeny of evolved tensegrity structures in five different runs using the proposed indirect encoding. Each row shows a selection of representative milestones in the evolution of the structure. Regularly and symmetry can be already found in some early structures, and evolution proceeds by modifying, adding, or substituting modules.

 

The ontogeny of the best tensegrity structures found is shown in the following figure. A zygote is made of a single edge of one unit length. Here, the complexity of the structures increases monotonically through development, as it generally does along natural evolution.

 

8.resultsIndDev

Ontogeny of evolved tensegrity structures using the proposed indirect encoding. Each row corresponds to a representative selection of snapshots during the developmental process of the structure. Triangular and square pyramids, bipyramids, and bilateral and rotational symmetries are formed during the developmental process.

 

In the previous two figures, it can be observed the formation of triangular and square pyramids, bipyramids, and bilateral and rotational symmetries. Additionally, grammar productions are regulated by a string that is copied and transmitted during the edge duplication rules, analogously to the mechanisms of copy and transmission of the genome during the division of biological cells. This process causes the reuse of genetic information (during both, evolution and development), what allows the repetition of modules in the structures.

The landing test performance of the best structures evolved with both encodings is drawn in the following diagrams, including their initial position after development and final position after landing. It can be observed that the structure obtained with direct encoding (left) adopts the form of an irregular tensegrity, which helps in the impact absorption (see movie below). Similarly, the structure evolved with indirect encoding (right) develops tensegrities with some differences, since they show a regular geometry, are organized modularly, and are strategically distributed in the organism.

 

9.landing

                             Direct encoding                                      Indirect encoding

Best evolved tensegrity structures during the landing test using the direct encoding (left) and indirect encoding (right). The distance traveled is represented with a grey line. The trajectory of the center of mass is also included, along with the jerk values (colored circles).

 

The following movies show the landing test performed by a random structure and the best tensegrity structures evolved with the direct and indirect encodings.

 

download
Landing test performed by a random structure. It can be observed how a random design cannot absorb the impact, resulting in a behavior characterized by several bounces and a long displacement distance.
 
 
download
Landing test performed by the best tensegrity structure with direct ecoding.
 
 
download
Landing test performed by the best tensegrity structure with indirect ecoding.

The presented results demonstrate that both encoding strategies can find good solutions to the form-finding problem. The difference is more on their particular way to prospect candidate forms, mainly derived from the search-space that each type of encoding defines. As a result, we have shown that the use of an indirect encoding facilitates the emergence of qualitative biological properties in the solutions, including regularity, organicity, generalization capacity, modularity, and manufacturability.

In conclusion, we have presented an effective and novel method for the general indirect encoding of structures, particularly the tensegrity structures, which have demonstrated their usefulness in evolutionary design towards a desired behavior. The results obtained qualitatively differ from those generated under a direct encoding scheme. These differences resemble properties found in biological organisms and emerge as a result of the developmental mechanism introduced in the evolution of the structures. The results demonstrate that these biological properties, especially those regarding modularity, symmetry, and manufacturability, are particularly valuable in engineering in the new class of behavior-finding problems, such as the design of tensegrity vehicles and robots that behave well in a defined problem.

For reference purposes and further information, please use the following citation:

D. Lobo and F.J. Vico, Evolutionary development of tensegrity structures. BioSystems 101(3), pp. 167-176, 2010.

 

Path-following

The second evolutionary developmental model proposed is described in this section. It has been tested in the behavior-finding problem of path-following. The evolutionary developmental simulator written for this project can be freely downloaded from here .The developmental model proposed to encode the path-following organisms is divided in three levels. First, an Artificial Genome, made up of a sequence of digits (bases), encodes a regulatory network. The function of this regulatory network is equivalent to a Boolean network. Hence, an organism in the model is represented by a geometrical graph, which grows during the organism development according to a graph grammar regulated by the Boolean network encoded in the organism's genome. The following diagram represents the proposed morphogenetic model.

1.model

Morphogenetic model consisting on a derivation of a graph grammar regulated by a Boolean network encoded in a sequential genome.

In this way, a derivation in the grammar represents the morphogenesis of an organism, as shown in the following figure.

2.derivation

Example of morphogenesis of an organism regulated by the genome presented in the previous figure. The first graph to the left is the zygote. Each edge has been labeled with its expression state.

After development has completed, an organism is physically simulated in a flat world where they have to follow a path and go as far as possible in a constant time. The path difficulty (the sharpness of the bends) has been parameterized, resulting in a set of possible paths according to its difficulty, as shown below.

3.paths
Difficulty of the path as given by the value of a parameter.

Similarly to the previous model, edges have been modeled as damped springs and nodes are free movable joints. Yet, in addition to normal edges, organism cells can differentiate into motor cells, which push forward in a continuous way, and sensor cells, which transduce the physical world information to the organism by increasing their size according to the amount of edge falling outside the path. In the following diagrams, motor edges are represented in red, cyan edges are sensors (with white bands to better compare relative lengths), and structural edges (regular springs) are the green ones.

In spite of the simple building blocks available for the organisms, 4 clearly different steering behaviors have evolved. Next, we present a representative organism for each resulting behavior, including their epigenetic and ontogenetic history, and their characteristic behavior.

Behavior A: emergence of bilateral sensors

The simplest path-follower we can think of would include sensors in both sides to correct the direction and a motor in between. The following figure shows the evolution, trajectory, lineage and development of an organism that shows this behavior. Note that, in order to avoid overspecialization of the organisms, a path is tested twice, such that in the second simulation it is flipped along the horizontal axis.

4.behaviorA

Evolved behavior A: bilateral sensors. (a) Best and mean fitness of the population in each generation during the evolution. (b) Paths and trajectories described by the best evolved organism. (c) Lineage of the best evolved organism. (d) Morphogenesis of the best evolved organism.

The following animation shows the steering behavior of the organism. When the organism is on the path (in gray), the forces of its two motor edges are compensated, resulting in a straight movement. When one of the sides exits the path, the sensor becomes longer, transmitting a positional change to the motor edges. This corrects the direction of movement, pointing now to the interior of the path.

download

 

Steering behavior of the organism with bilateral sensors. The path is the area in gray. It can be seen how the elongation of the sensor that exits the path steers the pair of motor edges towards the path, correcting the direction and bringing the organism back to the path.
 
 

Behavior B: emergence of turning by friction

This is an interesting behavior that exploits a completely different aspect of the physics. The morphology of the organism integrates a more sophisticated sensory system: 8 sensor edges and a single central motor edge. This configuration exploits the friction forces that the nodes bear, allowing a smooth steering over the edges of the path. The following figure shows an evolved organism with this behavior.

 
5.behaviorB
 
Evolved behavior B: turn by friction.
 

The animation below shows the behavior of this organism. It moves straightforward while inside the path; but, when the organism starts exiting the path, the external skeleton of structural edges forces the sensors to reconfigure internally and the symmetry breaks down due to the elongation of some sensors. In the asymmetrical configuration, more nodes concentrates in the side opposite to the exiting border, producing a higher overall friction on that side that generates a bent movement towards the path.

 
 
download
Steering behavior of the organism that turns by friction. As some sensors exit the path, their change in length pushes some nodes towards the path. This shifts the forces of friction in a way that corrects the direction of the organism, recovering its original configuration when it travels again over the path.

Behavior C: emergent spinning

Contrary to what could be expected, the second behavior preferred by evolution had to do with spinning organisms. A combination of sensor and motor edges arranged in a sort of quadrilateral pattern favors a rotational movement. Additionally, when a path border is transgressed, the organism adopts a slightly different dynamical configuration; the sensors elongate cyclically during the rotation, which causes the organism to follow the edge of the path, keeping its centroid inside most of the time. The following diagrams show an organism that has implemented this behavior.

6.behaviorC
Evolved behavior C: emergent spinning.

The following movie presents the behavior of this organism. In this case, the organism spins counterclockwise, but clockwise spinning is also common in other experiments. The slight asymmetry of the organism causes the initial displacement towards the path border. Then, the rotation over the border makes the motor edges to change cyclically their angles due to the repetitive elongations of the sensor edges, allowing the organism to steer following the path border.

download
Steering behavior of the organism that spins. Differently from other strategies, this one attaches the organism to one border of the path, changing the angles of the external motor edges with respect to the central motor edge. This provides the organism with a net movement that tracks the border of the path.

Behavior D: emergent rectification

Finally, some organisms revealed a much more elaborate behavior. Remarkably, this behavior emerged with the simplest possible sensory system: one sensor edge. An organism with such a behavior is showed in the following diagrams. Notice that the evolution stopped after reaching the maximum number of generations (a); at that point, the best evolved organism had a fitness of 0.5. Though, given enough simulation time, the organism managed to complete the path (b).

7.behaviorD
Evolved behavior D: rectification.

The following animation shows in detail the rectification behavior. While the organism is inside of the path, and as a result of balanced motor actions, all the edges get arranged in a single line, and the organism follows a straightforward movement. When the sensor exits the path, its elongation breaks the previous configuration, initiating a long sequence of actions (the rectification) which force the organism to go backwards, return to the path, and start another trajectory, shifted some degrees with respect to the original one.

download
Steering behavior of the organism that rectifies its trajectory. The organism moves straightforward while inside the path; but, when it exits the path, the sensor elongates and provokes an unstable equilibrium, since a pair of motors moves forward. This equilibrium breaks at some point and forces the organism to return, since the pair of motors now points backwards. Back in the path, the initial configuration is restored, keeping the organism trailing the path again.

Behaviors described above were obtained under particular settings. Additionally, in order to test the robustness of their behaviors, they have been simulated for a range of path difficulties and friction parameters. The following figures represent the results of this study. The results reveal that the more complex behavior is also the most robust to changes in the curvature of the path: behavior D performs well in any path. In the case of different friction constant, the performance degrades in all cases as it gets more slippery.

8a.generalization8b.generalization

Generalization of the evolved behaviors in different environments. The path difficulty (left) and friction of the medium (right) are varied separately to test the robustness of each organism to changes in the environment where it has evolved. This study reveals that the more complex behavior (D) is also the most robust to changes in the curvature of the path. However, the performance degrades in all cases as it gets more slippery, since motor edges propel the organism too fast.

 
 

The following animation shows how behavior D deals successfully with the path of maximum difficulty, demonstrating the generalization capacity of its evolved behavior.

 

 

download
Steering behavior of the organism that rectifies the trajectory (behavior D) in the case of maximum difficulty of the path.
 

Additionally, some behaviors have the capacity of reentering the path, as it is illustrated in the following diagram. The snapshots illustrates how the organism with behavior B follows a straight trajectory when outside the path, with the sensory system arranged in a star-like configuration; as some sensors enter the path, their change in length pushes some nodes towards the path, changing friction forces and correcting the direction of the organism.

 

10.reenter

Capacity of behavior B to reenter the path after quitting it. The organism changes from a straight trajectory to a curve towards the path as some sensors reenter the path.
 

We have defined and studied a model that integrates a considerable amount of biological features: (1) an encoding method based on sequence genotypes; (2) gene regulation by Boolean networks; (3) multicellular development through a fixed set of simple structural genes; (4) cell differentiation; and (5) evolution of morphologies and locomotive behaviors in a particular environment. Despite the simple and fixed set of structural genes implemented, a rich variety of body plans have evolved, providing the organisms with appropriate steering strategies. Furthermore, the evolved organisms presented a rich variety of behaviors, concluding that the developmental model presented in this work has been shown to be adequate for the class of behavior-finding problems.Finally, a remarkable result is how such a biological model obtains very simple structures that show a very complex behavior. This quite striking diversity of forms and behavioral strategies is connected to the diversity of forms and features found on earth, suggesting that such morphological richness should not be considered a surprising fact, but rather an inevitable consequence of the variability of gene regulation.

 

For reference purposes and further information, please use the following citation:

D. Lobo and F.J. Vico, Evolution of form and function in a model of differentiated multicellular organisms with gene regulatory networks. BioSystems 102(2-3), pp. 112-123, 2010.