Recently it has been demonstrated that collaboration between automated algorithms and human users can be especially ef-fective in robot behavior optimization tasks. In particular, we recently introduced a Fitness-based Search with Preference-based Policy Learning (FS-PPL) approach, in which the algo-rithm models the user based on her preferences and then uses the model, along with the fitness function, to guide search. However, so far only interaction between a single human user and an evolutionary algorithm was considered. If multiple users contribute preferences, the algorithm must determine whether to model them separately or jointly. In this paper we describe an algorithm in which one evolutionary algorithm in-teracts with two users and determines the best way to model them automatically. We test the algorithm with automated substitutes for human users and show that it performs better for two users working together than for the same users work-ing separately, thus demonstrating the potential for crowd-sourcing robot behavior optimization.

Interactive Evolutionary Algorithms (IEAs) use human input to help drive a search process. Traditionally, IEAs allow the user to exhibit preferences among some set of individuals. Here we present a system in which the user directly demonstrates what he or she prefers. Demonstration has an advantage over preferences because the user can provide the system with a solution that would never have been presented to a user who can only provide preferences. However, demonstration exacerbates the user fatigue problem because it is more taxing than exhibiting preferences. The system compensates for this by retaining and reusing the user demonstration, similar in spirit to user modeling. The system is exercised on a robot locomotion and obstacle avoidance task that has an obvious local optimum. The user demonstration is provided through low-level control. The system is compared against a high-level fitness function that is susceptible to becoming trapped by a local optimum and a mid-level fitness function designed to remove the local optimum. We show that our proposed system outperforms most variants of these completely automatic methods, providing further evidence that Evolutionary Robotics (ER) can benefit by combining the intuitions of inexpert human users with the search capabilities of computers.

Methodologies are emerging in many branches of computer science that demonstrate how human users and automated algorithms can collaborate on a problem such that their combined solutions outperform those produced by either humans or algorithms alone. The problem of behavior optimization in robotics seems particularly well-suited for this approach because humans have intuitions about how animals---and thus robots---should and should not behave, and can visually detect non-optimal behaviors that are trapped in local optima. Here we introduce a multiobjective approach in which a surrogate user (which stands in for a human user) deflects search away from local optima and a traditional fitness function eventually leads search toward the global optimum. We show that this approach produces superior solutions for a deceptive robotics problem compared to a similar search method that is guided by just a surrogate user or just a fitness function.

Interactive Evolutionary Algorithms (IEAs) have much potential for allowing a human user to guide a search algorithm, but have struggled to overcome the limitations of slow, easily-fatigued human users. Here we describe The Approximate User (TAU) system in which these limitations are overcome by using a model of the user's preferences - which are continuously built and refined during the search process - to drive the search algorithm. Two variations of a user-modeling approach are compared to determine if this approach can accelerate IEA search. The two user-modeling approaches compared are: 1. learning a classifier which correctly determines which of two designs is better; and 2. learning a model which predicts a fitness score. Rather than having people do the user-testing, we propose the use of a simulated user as an easier means to test IEAs. Both variants of the TAU IEA are compared against a basic IEA and it is shown that TAU is up to 2.7 times faster and 15 times more reliable at producing near optimal results. In addition, we see TAU as a step toward building a more general Human-Computer Collaborative system.

Whereas the current practice of designing antennas by hand is severely limited because it is both time and labor intensive and requires a significant amount of domain knowledge, evolutionary algorithms can be used to search the design space and automatically find novel antenna designs that are more effective than would otherwise be developed. Here we present our work in using evolutionary algorithms to automatically design an X-band antenna for NASA's Space Technology 5 (ST5) spacecraft. Two evolutionary algorithms were used: the first uses a vector of real-valued parameters and the second uses a tree-structured generative representation for constructing the antenna. The highest-performance antennas from both algorithms were fabricated and tested and both outperformed a hand-designed antenna produced by the antenna contractor for the mission. Subsequent changes to the spacecraft orbit resulted in a change in requirements for the spacecraft antenna. By adjusting our fitness function we were able to rapidly evolve a new set of antennas for this mission in less than a month. One of these new antenna designs was built, tested, and approved for deployment on the three ST5 spacecraft, which were successfully launched into space on March 22, 2006. This evolved antenna design is the first computer-evolved antenna to be deployed for any application and is the first computer-evolved hardware in space.

The fundamental dichotomy in evolutionary algorithms is that between exploration and exploitation. Recently, several algorithms [8, 9, 14, 16, 17, 20] have been introduced that guard against premature convergence by allowing both exploration and exploitation to occur simultaneously. However, continuous exploration greatly increases search time. To reduce the cost of continuous exploration we combine one of these methods (the age-layered population structure (ALPS) algorithm [8, 9]) with an early stopping (ES) method [2] that greatly accelerates the time needed to evaluate a candidate solution during search. We show that this combined method outperforms an equivalent algorithm with neither ALPS nor ES, as well as regimes in which only one of these methods is used, on an evolutionary robotics task.

The objectives of this paper are to describe a steady-state version of theAge-LayeredPopulationStructure(ALPS)EvolutionaryAlgorithm (EA) and to compare it against other GAs on real-valued problems. Motivation for this work comes from our previous success in demonstrating that a generational version of ALPS greatly improves searchperformance onaGenetic Programmingproblem. Inmakingsteady-stateALPS,somemodificationsweremadetothe method for calculating age and the method for moving individuals upagelayers. TodemonstratethatALPSworkswellonreal-valued problems we compare it against CMA-ES and Differential Evolution (DE) on five challenging, real-valued functions and on one real-worldproblem. WhileCMA-ESandDEoutperform ALPSon the two unimodal test functions, ALPS is much better on the three multimodal test problems and on the real-world problem. Further examination shows that, unlike the other GAs, ALPS maintains a genotypically diverse population throughout the entire search process. These findings strongly suggest that the ALPS paradigm is better able toavoidpremature convergence then the other GAs. Categories andSubject Descriptors

There has been much research into the development of robotic controllers in educational, industrial and government research labs, but limited hardware budgets constrain the types of morphologies in which researchers can experiment with. One option is to use LEGO components or other toy-grade kits, but these have well-known limitations. Here we present a heterogeneous modular robotic platform that can be reconfigured to a wide variety of robot morphologies, such as legged robots and manipulator arms. In addition, we have developed a simulation environment for our modules allowing for the artificial evolution, or learning, of behaviors to occur in simulation for transfer to reality. We demonstrate the effectiveness of our system by evolving a quadruped gait in simulation which successfully transfers to a hardware version of this robot.

Necessary for furthering the development of more powerful evolutionary design systems, capable of scaling to evolving more sophisticated and complex artifacts, is the ability to meaningfully and objectively compare these systems by applying complexity measures to the artifacts they evolve. Previously we have proposed measures of modularity, reuse and hierarchy (MR&H), here we compare these measures to ones from the fields of complexity, systems engineering and computer programming. In addition, we propose several ways of combining the MR&H measures into a single measure of structure and organization. We compare all of these measures empirically as well as on three sample objects and find that the best measures of complexity are two of the proposed measures of structure and organization.

As the application and complexity of microelectromechanical (MEMS) devices increases, there is a corresponding need for automated design and optimization tools to augment engineers' design skills. Evolutionary computation provides a set of tools that may prove very effective in this application domain. Here we present a novel evolutionary computation encoding scheme for specifying MEMS designs, and use this scheme to evolve a MEMS meandering resonator. Using fewer evaluations, we are able to evolve designs that perform as well as those previous reported.

To reduce the problem of premature convergence we define a new method for measuring an individual's age and propose the Age-Layered Population Structure (ALPS). This new measure of age measures how long the genetic material has been evolving in the population: offspring start with an age of 1 plus the age of their oldest parent instead of starting with an age of 0 as with traditional measures of age. ALPS differs from a typical evolutionary algorithm (EA) by segregating individuals into different age-layers by their age and by regularly introducing new, randomly generated individuals in the youngest layer. The introduction of randomly generated individuals at regular intervals results in an EA that is never completely converged and is always exploring new parts of the fitness landscape. By using age to restrict competition and breeding, younger individuals are able to develop without being dominated by older ones. Analysis of the search behavior of ALPS finds that the offspring of individuals that are randomly generated mid-way through a run are able to move the population out of mediocre local-optima to better parts of the fitness landscape. In comparison against a traditional EA, a multi-start EA and two other EAs with diversity maintenance schemes we find that ALPS produces significantly better designs with a higher reliability than the other EAs.

For computer-automated design systems to scale to complex designs they must be able to produce designs that exhibit the characteristics of modularity, regularity and hierarchy -- characteristics that are found both in man-made and natural designs. Here we claim that these characteristics are enabled by implementing the attributes of combination, control-flow and abstraction in the representation.To support this claim we use an evolutionary algorithm to evolve solutions to different sizes of a table design problem using five different representations, each with different combinations of modularity, regularity and hierarchy enabled and show that the best performance happens when all three of these attributes are enabled.We also define metrics for modularity, regularity and hierarchy in design encodings and demonstrate that high fitness values are achieved with high values of modularity, regularity and hierarchy and that there is a positive correlation between increases in fitness and increases in the measured values of modularity, regularity and hierarchy.

We present the first hardware-in-the-loop evolutionary optimization on an ornithopter. Our experiments demonstrate the feasibility of evolving flight through genetic algorithms and adaptable hardware, without the requirement for a thorough knowledge of the aerodynamics of flapping flight. In this research we successfully optimized forward velocity and basic efficiency on an actual hardware ornithopter. The ornithopter was flown integrated to a "whirling-arm" test apparatus, allowing lengthy experimental flights without the risk of crashing. Flapping rate and tail position were controlled by an evolutionary algorithm with feedback of forward velocity and motor power. The system evolved an unexpected optimal configuration. This paper discusses the development of the test apparatus and experimental results from the initial phase of research.

A challenging task that must be accomplished for every legged robot is creating the walking and running behaviors needed for it to move. In this paper we describe our system for autonomously evolving dynamic gaits on two of Sony's quadruped robots. Our evolutionary algorithm runs on board the robot and uses the robot's sensors to compute the quality of a gait without assistance from the experimenter. First, we show the evolution of a pace and trot gait on the OPEN-R prototype robot. With the fastest gait, the robot moves at over 10 m/min, which is more than forty body-lengths/min. While these first gaits are somewhat sensitive to the robot and environment in which they are evolved, we then show the evolution of robust dynamic gaits, one of which is used on the ERS-110, the first consumer version of AIBO.

The field of evolutionary robotics has demonstrated the ability to automatically design the morphology and controller of simple physical robots through synthetic evolutionary processes. However, it is not clear if variation-based search processes can attain the complexity of design necessary for practical engineering of robots. Here, we demonstrate an automatic design system that produces complex robots by exploiting the principles of regularity, modularity, hierarchy, and reuse. These techniques are already established principles of scaling in engineering design and have been observed in nature, but have not been broadly used in artificial evolution. We gain these advantages through the use of a generative representation, which combines a programmatic representation with an algorithmic process that compiles the representation into a detailed construction plan. This approach is shown to have two benefits: it can reuse components in regular and hierarchical ways, providing a systematic way to create more complex modules from simpler ones; and the evolved representations can capture intrinsic properties of the design space, so that variations in the representations move through the design space more effectively than equivalent-sized changes in a nongenerative representation. Using this system, we demonstrate for the first time the evolution and construction of modular, three-dimensional, physically locomoting robots, comprising many more components than previous work on body-brain evolution.

One of the main limitations of scalability in body-brain evolution systems is the representation chosen for encoding creatures. This paper defines a class of representations called generative representations, which are identified by their ability to reuse elements of the genotype in the translation to the phenotype. This paper presents an example of a generative representation for the concurrent evolution of the morphology and neural controller of simulated robots, and also introduces GENRE, an evolutionary system for evolving designs using this representation. Applying GENRE to the task of evolving robots for locomotion and comparing it against a non-generative (direct) representation shows that the generative representation system rapidly produces robots with significantly greater fitness. Analyzing these results shows that the generative representation system achieves better performance by capturing useful bias from the design space and by allowing viable large scale mutations in the phenotype. Generative representations thereby enable the encapsulation, coordination, and reuse of assemblies of parts.

One of the applications of evolutionary algorithms is the automatic creation of designs. For evolutionary techniques to scale to the complexities necessary for actual engineering problems, it has been argued that generative systems, where the genotype is an algorithm for constructing the final design, should be used as the encoding. We describe a system for creating generative specifications by combining Lindenmayer systems with evolutionary algorithms, and we apply it to the problem of generating table designs. Designs evolved by our system reach an order of magnitude more parts than previous generative systems. Comparing it against a non-generative encoding, we find that the generative system produces designs with higher fitness and is faster than the non-generative system. Finally, we demonstrate the ability of our system to go from design to manufacture by constructing evolved table designs using rapid prototyping equipment.

Recent research has demonstrated the ability for automatic design of the morphology and control of real physical robots using techniques inspired by biological evolution. The main criticism of the evolutionary design approach, however, is that it is doubtful whether it will reach the high complexities necessary for practical engineering. Here we claim that for automatic design systems to scale in complexity the designs they produce must be made of re-used modules. Our approach is based on the use of a generative design grammar subject to an evolutionary process. Unlike a direct encoding of a design, a generative design specification can re-use components, giving it the ability to create more complex modules from simpler ones. Re-used modules are also valuable for improved efficiency in testing and construction. We describe a system for creating generative specifications capable of hierarchical modularity by combining Lindenmayer systems with evolutionary algorithms. Using this system we demonstrate for the first time a generative system for physical, modular, 2D locomoting robots and their controllers.

The difficulties associated with designing, building, and controlling robots have led their development to a stasis: Applications are limited mostly to repetitive tasks with predefined behavior. Over the last few years we have been trying to address this challenge through an alternative approach: Rather than trying to control an existing machine or create a general-purpose robot, we propose that both the morphology and the controller should evolve at the same time. This process can lead to the automatic design of special-purpose mechanisms and controllers for specific short-term objectives. Here we provide a brief review of three generations of our recent research, which underlies the robots shown on the cover of this issue: Automatically designed static structures, automatically designed and manufactured dynamic electromechanical systems, and modular robots automatically designed through a generative DNA-like encoding.

An evolutionary algorithm is used to evolve gaits with the Sony entertainment robot, AIBO. All processing is handled by the robot's on-board computer with individuals evaluated using the robot's hardware. By sculpting the experimental environment, we increase the robustness to different surface types and different AIBOs. Evolved gaits are faster than those created by hand. Using this technique we evolve a gait used in the consumer version of AIBO.