Artificial Evolution of Adaptive Software: An Application to Autonomous Robots

Artificial evolution of computer software (evolutionary neural networks, genetic programming, evolutionary fuzzy systems, etc.) has been shown to generate software that in many cases is more performant than that designed by engineers. Evolved software performs well under the same conditions used during evolutionary training. However, in situations where unpredictable change may affect normal operation, evolved systems often fail. In this paper we describe a new approach for evolving software that remains adaptive and is therefore very robust to unpredictable change after evolution. To illustrate the idea, we present the case of evolutionary robots that quickly and reliably adapt online to several types of new situations, including sensory, environmental, and mechanical change, while still performing their task. The core of the methodology consists of evolving the mechanisms of parameter adaptation instead of the parameters themselves. We shall conclude by showing how this methodology can be applied to a variety of other situations beyond robotics.

Evolutionary synthesis of analog networks

Claudio Mattiussi

The significant increase in the available computational power that took place in recent decades has been accompanied by a growing interest in the application of the evolutionary approach to the synthesis of many kinds of systems and, in particular, to the synthesis of systems like analog electronic circuits, neural networks, and, more generally, autonomous systems, for which no satisfying systematic and general design methodology has been found to date. Despite some interesting results in the evolutionary synthesis of these kinds of systems, the endowment of an artificial evolutionary process with the potential for an appreciable increase of complexity of the systems thus generated appears still an open issue. In this thesis the problem of the evolutionary growth of complexity is addressed taking as starting point the insights contained in the published material reporting the unfinished work done in the late 1940s and early 1950s by John von Neumann on the theory of self-reproducing automata. The evolutionary complexity-growth conditions suggested in that work are complemented here with a series of auxiliary conditions inspired by what has been discovered since then relatively to the structure of biological systems, with a particular emphasis on the workings of genetic regulatory networks seen as the most elementary, full-fledged level of organization of existing living organisms. In this perspective, the first chapter is devoted to the formulation of the problem of the evolutionary growth of complexity, going from the description of von Neumann's complexity-growth conditions to the specification of a set of auxiliary complexity-growth conditions derived from the analysis of the operation of genetic regulatory networks. This leads to the definition of a particular structure for the kind of systems that will be evolved and to the specification of the genetic representation for them. A system with the required structure — for which the name analog network is suggested — corresponds to a collection of devices whose terminals are connected by links characterized by a scalar value of interaction strength. One of the specificities of the evolutionary system defined in this thesis is the way these values of interaction strength are determined. This is done by associating with each device terminal of the evolving analog network a sequence of characters extracted from the sequences that constitute the genome representing the network, and by defining a map from pairs of sequences of characters to values of interaction strength. Whereas the first chapter gives general prescriptions for the definition of an evolutionary system endowed with the desired complexity-growth potential, the second chapter is devoted to the specification of all the details of an actual implementation of those prescriptions. In this chapter the structure of the genome and of the corresponding genetic operators are defined. A technique for the genetic encoding of the devices constituting the analog network is described, along with a way to implement the map that specifies the interaction between the devices of the evolved system, and between them and the devices constituting the external environment of the evolved system. The proposed implementation of the interaction map is based on the local alignment of sequences of characters. It is shown how the parameters defining the local alignment can be chosen, and what strategies can be adopted to prevent the proliferation of unwanted interactions. The third chapter is devoted to the application of the evolutionary system defined in the second chapter to problems aimed at assessing the suitability in an evolutionary context of the local alignment technique and to problems aimed at assessing the evolutionary potential of the complete evolutionary system when applied to the synthesis of analog networks. Finally, the fourth chapter briefly considers some further questions that are relevant to the proposed approach but could not be addressed in the context of this thesis. A series of appendixes is devoted to some complementary issues: the definition of a measure of diversity for an evolutionary population employing the genetic description introduced in this thesis; the choice of the quantizer for the values of interaction strength between the devices constituting the evolved analog network; the modifications required to use the analog electronic circuit simulator SPICE as a simulation engine for an evolutionary or an optimization process.

EPFL2005

The evolution of communication in robot societies

Sara Mitri

Communication is fundamental to life on earth. All social organisms, from bacteria to humans, use communicative signals to coordinate their behaviors with members of their own and other species. Despite its key role in social organization, many questions regarding the evolution of communication are yet to be answered. This is in part due to the difficulty of conducting experimental evolution on social species, and the challenges in experimentally manipulating and measuring signaling and response strategies in communicating organisms. In this thesis, we circumvent these problems by using a system of experimental evolution with groups of foraging robots that could emit and perceive light to communicate. With this system, we have explored how communication can emerge and how different evolutionary conditions can determine the level of reliability of evolving signals. Our experiments revealed that foraging robots initially produced inadvertent cues providing information to other robots about the location of the food. This resulted in increased foraging efficiency, and consequently, in competition near the food, which drove the co-evolution of signaling and response strategies. The reliability of the resulting communication system was found to depend on the level of relatedness between robots in a group and the level at which they were selected. Robots that were highly related or selected at the group level evolved reliable signals. In contrast, when relatedness between robots in a group was low and selection was acting at the level of the individual, robots were selected to suppress the inadvertent cues produced while foraging. However, because of the effect of mutations, these cues were never completely suppressed and some variability in signaling was maintained. Because similar co-evolutionary processes should be common in natural systems, our findings explain why communicative strategies are so variable in many animal species when interests between them conflict. They also predict that relatedness will play an important role in the evolution of signal reliability in natural systems of communication. Additionally, our analyses have led us to devise a quantitative measure of signal reliability, which may be applied to measure reliability in natural systems of communication. The results of this study, together with an extensive review of the literature, illustrate how evolutionary robotic systems can be used to explore issues that cannot easily be studied experimentally with living organisms, and thus contribute to our understanding of biological systems.

EPFL2009

The evolution of communication in robot societies

Sara Mitri

EPFL2009

Evolutionary synthesis of analog networks

Claudio Mattiussi

EPFL2005