Genetic representation and evolvability of modular neural controllers

The manual design of con- trol systems for robotic devices can be challenging. Methods for the automatic synthesis of control systems, such as the evolution of artificial neural networks, are thus widely used in the robotics community. However, in many robotic tasks where multiple interdependent control problems have to be solved simultaneously, the performance of conventional neuroevolution techniques declines. In this paper, we identify interference between the adaptation of different parts of the control system as one of the key challenges in the evolutionary synthesis of artificial neural networks.As modular net- work architectures have been shown to reduce the effects of such interference, we propose a novel, implicit modular genetic representation that allows the evolutionary algorithm to automatically shape modular network topologies. Our experiments with plastic neural networks in a simple maze learning task indicate that adding a modular genetic representation to a state-of-the-art implicit neuroevolution method leads to better algorithm performance and increases the robustness of evolved solutions against detrimental mutations.

Genetic Representation of Adaptive Neural Controllers

Peter Dürr

The manual design of adaptive controllers for robotic systems that face unpredictable environmental changes is often challenging. There is thus a growing interest in the development of automatic design tools to assist control engineers. One of the most common approaches in this domain is the evolutionary synthesis of Artificial Neural Networks (ANNs), which allows the automatic design of control systems with little or no human intervention. The performance of evolved neural controllers, however, critically depends on the choice of a suitable genetic representation, i.e., a description of the ANN on which the evolutionary search can operate effectively. In this thesis, I propose an alternative to existing representations for neural controllers based on an extension of Analog Genetic Encoding (AGE), an abstraction of the regulatory networks that control the expression of genes in biological organisms. The proposed approach unites three characteristics that have separately been considered advantageous, but have so far not been aggregated into a single representation: (1) it can be used to effectively synthesize the topology, weights, and numerical parameters of arbitrary networks; (2) it permits the use of heterogeneous ANN models that feature multiple types of signals; and (3) it facilitates the evolution of modular controllers. The results of a series of experiments demonstrate the advantages of these characteristics: (i) neural architectures synthesized with the proposed method display a performance competitive to the best hand-designed networks and networks synthesized with other representations; (ii) in tasks that feature an unpredictable changing environment, controllers with a heterogeneous ANN model outperform controllers with conventional, homogeneous ANN models; and (iii) in tasks that feature multiple modular sub-problems, the proposed representation allows the automatic decomposition of the problem, leading to a substantial improvement in the performance of the evolved controllers. In summary, the proposed representation in combination with a heterogeneous ANN model and an evolutionary algorithm represents a promising method for the automatic synthesis of adaptive control systems for robots.

EPFL2011

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

Synthesis, modeling, and experimental validation of distributed robotic search

James Pugh

The work of this thesis centers around the research subject of distributed robotic search. Within the field of distributed robotic systems, a task of particular interest is attempting to locate one or more targets in a possibly unknown environment. While numerous studies have proposed and analyzed methods to accomplish this, there is currently a lack of a strong foundation of tools and techniques that can be used to facilitate the development and evaluation of different approaches to distributed robotic search. In this work, we aim to provide such a foundation through tools, methods, models, and analysis of experimentation. An often overlooked aspect of the distributed robotic research process is the development and analysis of tools and modules to be used with robotic systems. These may include plug-ins for realistic robotic simulators, software/hardware systems to track multiple mobile robots in real-time, extension boards for robotic platforms, and the robots themselves. Along with other tools developed and used for this work, we focus particularly on the development, characterization, and validation of a fast, accurate on-board system for relative positioning and communication between robots, a capability which is critical for effective distributed robotic search. Designing individual robot controllers to generate a specific group behavior is a difficult and often counter-intuitive process. A possible alternative to hand-crafting distributed search controllers is automatic synthesis using machine-learning techniques. We explore the effectiveness of using a noise-resistant version of the Particle Swarm Optimization algorithm to optimize the weights of an embedded Artificial Neural Network, allowing the robot to learn obstacle avoidance behavior (a common benchmark for robotic learning techniques); we find that this technique appears to offer superior performance as compared to the canonical approach of using Genetic Algorithms for this type of learning. A method for faster learning using distributed evaluation in a robot team is tested and is found to offer comparable performance using only a fraction of the original learning time. This technique can be used for fast, effective learning and adaptation in a distributed robotic system performing search. The process of designing and analyzing algorithms for distributed robotic systems can be greatly facilitated if models are available to describe the dynamics of the algorithm at an abstract level. Inspired by previous examples in the distributed robotic field, we work to design a model of robotic search that captures the system at different levels of abstraction, ranging from accurately recreating the details of individual robots to describing the entire system as an indivisible whole. To capture the entire search process, we model both the exploration phase, where robots cover an environment in an effort to detect traces of targets, and the localization phase, where robots use target emission sensing to navigate towards the target. The utility of our models is demonstrated by using them to develop an effective technique for the declaration phase of search, where robots decide that a target has been accurately localized and announce its position. In distributed robotics research, it is important that techniques developed with abstracted simulations and models are ultimately validated using real robotic platforms in order to verify their correctness. In that spirit, we run systematic sound search experiments using teams of up to ten real robots. These experiments utilize the tools developed throughout the research process, demonstrate the utility of our learning technique for fast search adaptation, and serve to validate our models of distributed robotic localization. In addition, they allow us to analyze and better understand the subtle dynamics of the search process, providing information which should be useful for any future work on distributed robotic search.

EPFL2008