A central challenge in the progression of a variety of open questions in biology, such as morphogenesis, wound healing, and development, is learning from empirical data how information is integrated to support tissue-level function and behavior. Information-theoretic approaches provide a quantitative framework for extracting patterns from data, but so far have been predominantly applied to neuronal systems at the tissue-level. Here, we demonstrate how time series of Ca2+ dynamics can be used to identify the structure and information dynamics of other biological tissues. To this end, we expressed the calcium reporter GCaMP6s in an organoid system of explanted amphibian epidermis derived from the African clawed frog Xenopus laevis, and imaged calcium activity pre- and post- a puncture injury, for six replicate organoids. We constructed functional connectivity networks by computing mutual information between cells from time series derived using medical imaging techniques to track intracellular Ca2+. We analyzed network properties including degree distribution, spatial embedding, and modular structure. We find organoid networks exhibit potential evidence for more connectivity than null models, with our models displaying high degree hubs and mesoscale community structure with spatial clustering. Utilizing functional connectivity networks, our model suggests the tissue retains non-random features after injury, displays long range correlations and structure, and non-trivial clustering that is not necessarily spatially dependent. In the context of this reconstruction method our results suggest increased integration after injury, possible cellular coordination in response to injury, and some type of generative structure of the anatomy. While we study Ca2+ in Xenopus epidermal cells, our computational approach and analyses highlight how methods developed to analyze functional connectivity in neuronal tissues can be generalized to any tissue and fluorescent signal type. We discuss expanded methods of analyses to improve models of non-neuronal information processing highlighting the potential of our framework to provide a bridge between neuroscience and more basal modes of information processing.

The study of irreducible higher-order interactions has become a core topic of study in complex systems, as they provide a formal scaffold around which to build a quantitative understanding of emergence and emergent properties. Two of the most well-developed frameworks, topological data analysis and multivariate information theory, aim to provide formal tools for identifying higher-order interactions in empirical data. Despite similar aims, however, these two approaches are built on markedly different mathematical foundations and have been developed largely in parallel - with limited interdisciplinary cross-talk between them. In this study, we present a head-to-head comparison of topological data analysis and information-theoretic approaches to describing higher-order interactions in multivariate data; with the goal of assessing the similarities, and differences, between how the frameworks define "higher-order structures." We begin with toy examples with known topologies (spheres, toroids, planes, and knots), before turning to more complex, naturalistic data: fMRI signals collected from the human brain. We find that intrinsic, higher-order synergistic information is associated with three-dimensional cavities in an embedded point cloud: shapes such as spheres and hollow toroids are synergy-dominated, regardless of how the data is rotated. In fMRI data, we find strong correlations between synergistic information and both the number and size of three-dimensional cavities. Furthermore, we find that dimensionality reduction techniques such as PCA preferentially represent higher-order redundancies, and largely fail to preserve both higher-order information and topological structure, suggesting that common manifold-based approaches to studying high-dimensional data are systematically failing to identify important features of the data. These results point towards the possibility of developing a rich theory of higher-order interactions that spans topological and information-theoretic approaches while simultaneously highlighting the profound limitations of more conventional methods.

[RETRACTED]Data increasingly abounds, but distilling their underlying relationships down to something interpretable remains challenging. One approach is genetic programming, which `symbolically regresses' a data set down into an equation. However, symbolic regression (SR) faces the issue of requiring training from scratch for each new dataset. To generalize across all datasets, deep learning techniques have been applied to SR. These networks, however, are only able to be trained using a symbolic objective: NN-generated and target equations are symbolically compared. But this does not consider the predictive power of these equations, which could be measured by a behavioral objective that compares the generated equation's predictions to actual data. Here we introduce a method that combines gradient descent and evolutionary computation to yield neural networks that minimize the symbolic and behavioral errors of the equations they generate from data. As a result, these evolved networks are shown to generate more symbolically and behaviorally accurate equations than those generated by networks trained by state-of-the-art gradient based neural symbolic regression methods. We hope this method suggests that evolutionary algorithms, combined with gradient descent, can improve SR results by yielding equations with more accurate form and function.

Much is unknown about how living systems grow into, coordinate communication across, and maintain themselves as hierarchical arrangements of semi-independent cells, tissues, organs, and entire bodies, where each component at each level has its own goals and sensor, motor, and communication capabilities. Similar uncertainty surrounds exactly how selection acts on the components across these levels. Finally, growing interest in viewing intelligence not as something localized to the brain but rather distributed across biological hierarchies has renewed investigation into the nature of such hierarchies. Here we show that organizing neural cellular automata (NCAs) into a hierarchical structure can improve the ability to evolve them to perform morphogenesis and homeostasis, compared to non-hierarchical NCAs. The increased evolvability of hierarchical NCAs (HNCAs) compared to non-hierarchical NCAs suggests an evolutionary advantage to the formation and utilization of higher-order structures, across larger spatial scales, for some tasks, and suggests new ways to design and optimize NCA models and hierarchical arrangements of robots. The results presented here demonstrate the value of explicitly incorporating hierarchical structure into systems that must grow and maintain complex patterns. The introduced method may also serve as a platform to further investigate the evolutionary dynamics of multiscale systems.

Empowerment---a domain independent, information-theoretic metric---has previously been shown to assist in the evolutionary search for neural cellular automata (NCA) capable of homeostasis when employed as a fitness function [11, 17]. In our previous study, we successfully extended empowerment, defined as maximum time-lagged mutual information between agents' actions and future sensations, to a distributed sensorimotor system embodied as an NCA. However, the time-delay between actions and their corresponding sensations was arbitrarily chosen. Here, we expand upon previous work by exploring how the time scale at which empowerment operates impacts its efficacy as an auxiliary objective to accelerate the discovery of homeostatic NCAs. We show that shorter time delays result in marked improvements over empowerment with longer delays, when compared to evolutionary selecting only for home-ostasis. Moreover, we evaluate stability and adaptability of evolved NCAs, both hallmarks of living systems that are of interest to replicate in artificial ones. We find that short-term empowered NCA are more stable and are capable of generalizing better to unseen homeostatic challenges. Taken together, these findings motivate the use of empowerment during the evolution of other artifacts, and suggest how it should be incorporated to accelerate evolution of desired behaviors for them.1

Unconventional computing devices are increasingly of interest as they can operate in environments hostile to silicon-based electronics, or compute in ways that traditional electronics cannot. Mechanical computers, wherein information processing is a material property emerging from the interaction of components with the environment, are one such class of devices. This information processing can be manifested in various physical substrates, one of which is granular matter. In a granular assembly, vibration can be treated as the information-bearing mode. This can be exploited to realize "polycomputing": materials can be evolved such that a single grain within them can report the result of multiple logical operations simultaneously at different frequencies, without recourse to quantum effects. Here, we demonstrate the evolution of a material in which one grain acts simultaneously as two different NAND gates at two different frequencies. NAND gates are of interest as any logical operations can be built from them. Moreover, they are nonlinear thus demonstrating a step toward general-purpose, computationally dense mechanical computers. Polycomputation was found to be distributed across each evolved material, suggesting the material's robustness. With recent advances in material sciences, hardware realization of these materials may eventually provide devices that challenge the computational density of traditional computers.

A vital component of intelligent action is affordance detection: understanding what actions external objects afford the viewer. This requires the agent to understand the physical nature of the object being viewed, its own physical nature, and the potential relationships possible when they interact. Although robotics researchers have investigated affordance detection, the way in which the morphology of the robot facilitates, obstructs, or otherwise influences the robot's ability to detect affordances has yet to be studied. We do so here and find that a robot with an appropriate morphology can evolve to predict whether it will fit through an aperture with just minimal tactile feedback. We also find that some robot morphologies facilitate the evolution of more accurate affordance detection, while others do not if all have the same evolutionary optimization budget. This work demonstrates that sensation, thought, and action are necessary but not sufficient for understanding how affordance detection may evolve in organisms or robots: morphology must also be taken into account. It also suggests that, in the future, we may optimize morphology along with control in order to facilitate affordance detection in robots, and thus improve their reliable and safe action in the world.

Digital signal processors are widely used in today's computers to perform advanced computational tasks. But, the selection of digital electronics as the physical substrate for computation a hundred years ago was influenced more by technological limitations than substrate appropriateness. In recent decades, advances in chemical, physical and material sciences have provided new options. Granular metamaterials are one such promising target for realizing mechanical computing devices. However, their high-dimensional design space and the unintuitive relationship between microstructure and desired macroscale behavior makes the inverse design problem formidable. In this paper, we use multiobjective evolutionary optimization to solve this inverse problem: we demonstrate the design of basic logic gates embedded in a granular metamaterial, and that the designed material can be "reprogrammed" via frequency modulation. As metamaterial design advances, more computationally dense materials may be evolved, amenable to reprogramming by increasingly sophisticated programming languages written in the frequency domain.

This special issue highlights key selections from the 2020 Conference on Artificial Life, which is the primary international meeting organized yearly by the International Society for Artificial Life (www.alife.org). The conference themes broadly address the synthesis and simulation of living systems, welcoming scientific research that either deepens our understanding of life as we know it or broadens our conception of life as it could be (Langton, 1989).The 2020 conference, hosted by the University of Vermont and the Vermont Complex Systems Center, was originally intended to be held in Montréal, Québec, Canada. However, the global COVID-19 pandemic forced this event, like many others, to be held online. In truth, this challenge afforded a unique opportunity to hold a truly global conference, with 390 registered attendees from around the world.Of 183 submissions, 75 articles (41%) were accepted for full presentations at the conference and published in the proceedings (Bongard et al., 2020). An additional 11 submissions were presented as lighting talks and 24 as posters and were also included in the proceedings.Reflecting the highly interdisciplinary nature of the field, the topics covered in this special issue include evolutionary dynamics, artificial chemistry, agent-based modelling, game theory, genetic programming, neuroevolution, embodiment, and complex systems research: Ghouri, Barnes, and Lewis present a minimal version of the classic river crossing task, isolating the core task of building a bridge in a grid world for the purpose of increasing explainability of the original problem. Results with the minimal environment are consistent with results from the original version, highlighting the utility of the minimal environment for experiments on explainable evolutionary intelligence.Grove, Timbrell, Jolley, Polack, and Borg demonstrate that the mathematical color of noise in an environment has a significant impact on dynamics in evolving populations. In particular, their results call into question whether commonly employed Gaussian or white noise models should be the default.Lexicase selection in genetic programming is an alternative to traditional parent selection. Helmuth and Spector conduct an extensive benchmarking of a variant called down-sampled lexicase selection, showing that it outperforms standard selection, and investigate hypotheses about why it performs so well.Howison, Hugues, and Iida explore how morphology can be used to control and program interactions with the environment in their study of V-shaped falling papers. They also show how Bayesian optimization can be used to design functional constructs of nonliving materials in the real world.Hudcová and Mikolov provide a framework for classifying cellular automata complexity based on transients, which are parts of automata trajectories observed before entering into a loop. In particular, the presented classification is based on the asymptotic growth of the average transient length with increasing grid size. This framework is intended to aid the identification of interesting phenomena in evolving systems.Krellner and Han study the evolution of cooperation among agents playing a donation game. In particular, this work introduces a novel approach to information sharing to solve the problem of private information.Kruszewski and Mikolov develop an artificial chemistry based on combinatory logic, showing that complex structures emerge over time from a simple dynamical system. This work explicitly addresses the origins of open-ended evolution, which is a longstanding pursuit for the field of Artificial Life (and science in general).Miller re-envisions the artificial neuron model to better reflect natural evolution and development processes. Using this model, evolved programs can construct artificial neural networks that can be broken down into smaller networks that each solve distinct tasks.The 2020 conference theme “New frontiers in AI: What can ALife offer AI?” asked the community to consider how the unbridled and sometimes unconventional creativity of Artificial Life research might inspire innovation in mainstream Artificial Intelligence. In fact, the two fields share a deeply intertwined history, as some of the greatest pioneers in early Artificial Intelligence work also (or first) pursued what would now be called Artificial Life. As an example, Shannon (1940), often referred to as the father of information theory, wrote his doctoral dissertation An Algebra for Theoretical Genetics 16 years before he helped found the field of Artificial Intelligence at the Dartmouth Conference.At the same time, the Artificial Life community continues in its own myriad pursuits, recapitulating and reinventing nature often with computational tools, as evidenced by the works contained in this volume. Evolution on Earth gave rise to natural intelligence, and so evolution in silico (a mainstay of Artificial Life research) similarly bears the potential for creating Artificial Intelligence open-endedly; such is the foundational assumption of research on open-ended evolution. What ALife can offer AI is, among other things, an invitation to question what about life and intelligence might transcend substrates and, in doing so, to discover how what is might inspire what will be.

Morphology of a robot design is important to its ability to achieve a stated goal and therefore applying machine learning approaches that incorporate morphology in the design space can provide scope for significant advantage. Our study is set in a domain known to be reliant on morphology: flapping wing flight. We developed a parameterised morphology design space that draws features from biological exemplars and apply automated design to produce a set of high performance robot morphologies in simulation. By performing sim2real transfer on a selection, for the first time we measured the shape of the reality gap for variations in design complexity. We found for the flapping wing that the reality gap changes non-monotonically with complexity, suggesting that certain morphology details narrow the gap more than others, and that such details could be identified and further optimised in a future end-to-end automated morphology design process.

Many factors influence the evolvability of populations, and this article illustrates how intrinsic mortality (death induced through internal factors) in an evolving population contributes favorably to evolvability on a fixed deceptive fitness landscape. We test for evolvability using the hierarchical if-and-only-if (h-iff) function as a deceptive fitness landscape together with a steady state genetic algorithm (SSGA) with a variable mutation rate and indiscriminate intrinsic mortality rate. The mutation rate and the intrinsic mortality rate display a relationship for finding the global maximum. This relationship was also found when implementing the same deceptive fitness landscape in a spatial model consisting of an evolving population. We also compared the performance of the optimal mutation and mortality rate with a state-of-the-art evolutionary algorithm called age-fitness Pareto optimization (AFPO) and show how the two approaches traverse the h-iff landscape differently. Our results indicate that the intrinsic mortality rate and mutation rate induce random genetic drift that allows a population to efficiently traverse a deceptive fitness landscape. This article gives an overview of how intrinsic mortality influences the evolvability of a population. It thereby supports the premise that programmed death of individuals could have a beneficial effect on the evolvability of the entire population.

Enabling machines to respond appropriately to natural language commands could greatly expand the number of people to whom they could be of service. Recently, advances in neural network-trained word embeddings have empowered non-embodied text-processing algorithms, and suggest they could be of similar utility for embodied machines. Here we introduce a method that does so by training robots to act similarly to semantically-similar word 2vec encoded commands. We show that this enables them to act appropriately, after training, to previously-unheard commands. Finally, we show that inducing such an alignment between motoric and linguistic similarities can be facilitated or hindered by the mechanical structure of the robot. This points to future, large scale methods that find and exploit relationships between action, language, and robot structure.

Generally intelligent agents exhibit successful behavior across problems in several settings. Endemic in approaches to realize such intelligence in machines is catastrophic forgetting: sequential learning corrupts knowledge obtained earlier in the sequence, or tasks antagonistically compete for system resources. Methods for obviating catastrophic forgetting have sought to identify and preserve features of the system necessary to solve one problem when learning to solve another, or to enforce modularity such that minimally overlapping sub-functions contain task specific knowledge. While successful, both approaches scale poorly because they require larger architectures as the number of training instances grows, causing different parts of the system to specialize for separate subsets of the data. Here we present a method for addressing catastrophic forgetting called developmental compression. It exploits the mild impacts of developmental mutations to lessen adverse changes to previously-evolved capabilities and 'compresses' specialized neural networks into a generalized one. In the absence of domain knowledge, developmental compression produces systems that avoid overt specialization, alleviating the need to engineer a bespoke system for every task permutation and suggesting better scalability than existing approaches. We validate this method on a robot control problem and hope to extend this approach to other machine learning domains in the future.

Typically, AI researchers and roboticists try to realize intelligent behavior in machines by tuning parameters of a predefined structure (body plan and/or neural network architecture) using evolutionary or learning algorithms. Another but not unrelated longstanding property of these systems is their brittleness to slight aberrations, as highlighted by the growing deep learning literature on adversarial examples. Here we show robustness can be achieved by evolving the geometry of soft robots, their control systems, and how their material properties develop in response to one particular interoceptive stimulus (engineering stress) during their lifetimes. By doing so we realized robots that were equally fit but more robust to extreme material defects (such as might occur during fabrication or by damage thereafter) than robots that did not develop during their lifetimes, or developed in response to a different interoceptive stimulus (pressure). This suggests that the interplay between changes in the containing systems of agents (body plan and/or neural architecture) at different temporal scales (evolutionary and developmental) along different modalities (geometry, material properties, synaptic weights) and in response to different signals (interoceptive and external perception) all dictate those agents' abilities to evolve or learn capable and robust strategies.

Different subsystems of organisms adapt over many time scales, such as rapid changes in the nervous system (learning), slower morphological and neurological change over the lifetime of the organism (postnatal development), and change over many generations (evolution). Much work has focused on instantiating learning or evolution in robots, but relatively little on development. Although many theories have been forwarded as to how development can aid evolution, it is difficult to isolate each such proposed mechanism. Thus, here we introduce a minimal yet embodied model of development: the body of the robot changes over its lifetime, yet growth is not influenced by the environment. We show that even this simple developmental model confers evolvability because it allows evolution to sweep over a larger range of body plans than an equivalent non-developmental system, and subsequent heterochronic mutations 'lock in' this body plan in more morphologically-static descendants. Future work will involve gradually complexifying the developmental model to determine when and how such added complexity increases evolvability.

In some evolutionary robotics experiments, evolved robots are transferred from simulation to reality, while sensor/motor data flows back from reality to improve the next transferral. We envision a generalization of this approach: a simulation-to-reality pipeline. In this pipeline, increasingly embodied agents flow up through a sequence of increasingly physically realistic simulators, while data flows back down to improve the next transferral between neighboring simulators; physical reality is the last link in this chain. As a first proof of concept, we introduce a two-link chain: A fast yet low-fidelity ( lo-fi) simulator hosts minimally embodied agents, which gradually evolve controllers and morphologies to colonize a slow yet high-fidelity ( hi-fi) simulator. The agents are thus physically scaffolded. We show here that, given the same computational budget, these physically scaffolded robots reach higher performance in the hi-fi simulator than do robots that only evolve in the hi-fi simulator, but only for a sufficiently difficult task. These results suggest that a simulation-to-reality pipeline may strike a good balance between accelerating evolution in simulation while anchoring the results in reality, free the investigator from having to prespecify the robot's morphology, and pave the way to scalable, automated, robot-generating systems.

The non-embodied approach to teaching machines language is to train them on large text corpora. However, this approach has yielded limited results. The embodied approach, in contrast, involves teaching machines to ground abstract symbols in their sensory-motor experiences, but howor whether humans achieve this remains largely unknown. We posit that one avenue for achieving this is to view language acquisition as a three-way interaction between linguistic, sensorimotor, and social dynamics: when an agent acts in response to a heard word, it is considered to have successfully grounded that symbol if it can predict how observers who understand that word will respond to the action. Here we introduce a methodology for testing this hypothesis: human observers issue arbitrary commands to simulated robots via the web, and provide positive or negative reinforcement in response to the robots resulting action. Then, the robots are trained to predict crowd response to these action-word pairs. We show that robots do learn to ground at least one of these crowd-issued commands: an association between jump, minimization of tactile sensation, and positive crowd response was learned. The automated, open-ended, and crowd-based aspects of this approach suggest it can be scaled up in future to increasingly capable robots and more abstract language.

The concept of morphological computation holds that the body of an agent can, under certain circumstances, exploit the interaction with the environment to achieve useful behavior, potentially reducing the computational burden of the brain/controller. The conditions under which such phenomenon arises are, however, unclear. We hypothesize that morphological computation will be facilitated by body plans with appropriate geometric, material, and growth properties, while it will be hindered by other body plans in which one or more of these three properties is not well suited to the task. We test this by evolving the geometries and growth processes of soft robots, with either manually-set softer or stiffer material properties. Results support our hypothesis: we find that for the task investigated, evolved softer robots achieve better performances with simpler growth processes than evolved stiffer ones. We hold that the softer robots succeed because they are better able to exploit morphological computation. This four-way interaction among geometry, growth, material properties and morphological computation is but one example phenomenon that can be investigated using the system here introduced, that could enable future studies on the evolution and development of generic soft-bodied creatures.

The Web has created new opportunities for interactive problem solving and design by large groups. In the context of robotics, we have shown recently that a crowd of non-experts are capable of designing adaptive machines over the Web. However, determining the degree to which collective contribution plays a part in these tasks requires further investigation. We hypothesize that there exist subtle yet measurable social dynamics that occur during the collaborative design of robots on the Web. To test this, we enabled a crowd to rapidly design and train simulated, web-embedded robots. We compared the robots designed by a socially-interacting group of individuals to another group whose members were isolated from one another. We found that there exists a latent quality in the robots designed by the social group that was significantly less prevalent in the robots designed by individuals working alone. Thus, there must exist synergies in the former group that facilitate this design task. We also show that this latent quantity correlates with the desired design outcome, which was fast forward locomotion. However, the quantity when distilled into its component parts is not more prevalent in one group than another. This finding demonstrates that there are indeed traces left behind in the machines designed by the crowd that betray the social dynamics that gave rise to them. Demonstrating the existence of such quantities and the methodology for extracting them presents opportunities for crafting interfaces to magnify these synergies and thus improve collective design of robots over the web in particular, and crowd design activities in general.

The field of evolved virtual creatures has been suspiciously stagnant in terms of complexification of evolved agents since its inception over two decades ago. Many researchers have proposed algorithmic improvements, but none have taken hold and greatly propelled the scalability of early works. This paper suggests a more fundamental problem with co-evolving both the morphology and control of virtual creatures simultaneously one cemented in the theory of embodied cognition. We reproduce and explore in greater detail a previous finding in the literature: premature convergence of the morphology (compared to the convergence point of optimizing controllers), and discuss how this finding fits as a symptom of the proposed problem. We hope that this improved understanding of the fundamental problem domain will open the door for further scalability of evolved agents, and note that early findings from our future work point in that direction.

Identifying and communicating relationships between causes and effects is important for understanding our world, but is affected by language structure, cognitive and emotional biases, and the properties of the communication medium. Despite the increasing importance of social media, much remains unknown about causal statements made online. To study real-world causal attribution, we extract a large-scale corpus of causal statements made on the Twitter social network platform as well as a comparable random control corpus. We compare causal and control statements using statistical language and sentiment analysis tools. We find that causal statements have a number of significant lexical and grammatical differences compared with controls and tend to be more negative in sentiment than controls. Causal statements made online tend to focus on news and current events, medicine and health, or interpersonal relationships, as shown by topic models. By quantifying the features and potential biases of causality communication, this study improves our understanding of the accuracy of information and opinions found online.

Maintaining population diversity has long been considered fundamental to the effectiveness of evolutionary algorithms. Recently, with the advent of novelty search, there has been an increasing interest in sustaining behavioral diversity by using both fitness and behavioral novelty as separate search objectives. However, since the novelty objective explicitly rewards diverging from other individuals, it can antagonize the original fitness objective that rewards convergence toward the solution(s). As a result, fostering behavioral diversity may prevent proper exploitation of the most interesting regions of the behavioral space, and thus adversely affect the overall search performance. In this paper, we argue that an antagonism between behavioral diversity and fitness can indeed exist in semantic genetic programming applied to symbolic regression. Minimizing error draws individuals toward the target semantics but promoting novelty, defined as a distance in the semantic space, scatters them away from it. We introduce a less conflicting novelty metric, defined as an angular distance between two program semantics with respect to the target semantics. The experimental results show that this metric, in contrast to the other considered diversity promoting objectives, allows to consistently improve the performance of genetic programming regardless of whether it employs a syntactic or a semantic search operator.

We present a survey of the first 21 years of web-based artificial life (WebAL) research and applications, broadly construed to include the many different ways in which artificial life and web technologies might intersect. Our survey covers the period from 1994-when the first WebAL work appeared-up to the present day, together with a brief discussion of relevant precursors. We examine recent projects, from 2010-2015, in greater detail in order to highlight the current state of the art. We follow the survey with a discussion of common themes and methodologies that can be observed in recent work and identify a number of likely directions for future work in this exciting area.

Although recent work has demonstrated that modularity can increase evolvability in non-embodied systems, it remains to be seen how the morphologies of embodied agents influences the ability of an evolutionary algorithm to find useful and modular controllers for them. We hypothesize that a modular control system may enable different parts of a robot's body to sense and react to stimuli independently, enabling it to correctly recognize a seemingly novel environment as, in fact, a composition of familiar percepts and thus respond appropriately without need of further evolution. Here we provide evidence that supports this hypothesis: We found that such robots can indeed be evolved if (1) the robot's morphology is evolved along with its controller, (2) the fitness function selects for the desired behavior and (3) also selects for conservative and robust behavior. In addition, we show that if constraints (1) and (3) are relaxed, or structural modularity is selected for directly, the robots have too little or too much modularity and lower evolvability. Thus, we demonstrate a previously unknown relationship between modularity and embodied cognition: evolving morphology and control such that robots exhibit conservative behavior indirectly selects for appropriate modularity and, thus, increased evolvability.

Soft robots have become increasingly popular in recent years -- and justifiably so. Their compliant structures and (theoretically) infinite degrees of freedom allow them to undertake tasks which would be impossible for their rigid body counterparts, such as conforming to uneven surfaces, efficiently distributing stress, and passing through small apertures. Previous work in the automated deign of soft robots has shown examples of these squishy creatures performing traditional robotic task like locomoting over flat ground. However, designing soft robots for traditional robotic tasks fails to fully utilize their unique advantages. In this work, we present the first example of a soft robot evolutionarily designed for reaching or squeezing through a small aperture -- a task naturally suited to its type of morphology. We optimize these creatures with the CPPN-NEAT evolutionary algorithm, introducing a novel implementation of the algorithm which includes multi-objective optimization while retaining its speciation feature for diversity maintenance. We show that more compliant and deformable soft robots perform more effectively at this task than their less flexible counterparts. This work serves mainly as a proof of concept, but we hope that it helps to open the door for the better matching of tasks with appropriate morphologies in robotic design in the future.

Despite recent demonstrations that deep learning methods can successfully recognize and categorize objects using high dimensional visual input, other recent work has shown that these methods can fail when presented with novel input. However, a robot that is free to interact with objects should be able to reduce spurious differences between objects belonging to the same class through motion and thus reduce the likelihood of overfitting. Here we demonstrate a robot that achieves more robust categorization when it evolves to use proprioceptive sensors and is then trained to rely increasingly on vision, compared to a similar robot that is trained to categorize only with visual sensors. This work thus suggests that embodied methods may help scaffold the eventual achievement of robust visual classification.

Resource constrained sensor systems are an increasingly attractive option in a variety of environmental monitoring domains, due to continued improvements in sensor technology. However, sensors for the same measurement application can differ in terms of cost and accuracy, while fluctuations in environmental conditions can impact both application requirements and available energy. This raises the problem of automatically controlling heterogeneous sensor suites in resource constrained sensor system applications, in a manner that balances cost and accuracy of available sensors. We present a method that employs a hierarchy of model ensembles trained by genetic programming (GP): if model ensembles that poll low-cost sensors exhibit too much prediction uncertainty, they automatically transfer the burden of prediction to other GP-trained model ensembles that poll more expensive and accurate sensors. We show that, for increasingly challenging datasets, this hierarchical approach makes predictions with equivalent accuracy yet lower cost than a similar yet non-hierarchical method in which a single GP-generated model determines which sensors to poll at any given time. Our results thus show that a hierarchy of GP-trained ensembles can serve as a control algorithm for heterogeneous sensor suites in resource constrained sensor system applications that balances cost and accuracy.

An open question in ensemble-based active learning is how to choose one classifier type, or appropriate combinations of multiple classifier types, to construct ensembles for a given task. While existing approaches typically choose one classifier type, this paper presents a method that trains and adapts multiple instances of multiple classifier types toward an appropriate ensemble during active learning. The method is termed adaptive heterogeneous ensembles (henceforth referred to as AHE). Experimental evaluations show that AHE constructs heterogeneous ensembles that outperform homogeneous ensembles composed of any one of the classifier types, as well as bagging, boosting and the random subspace method with random sampling. We also show in this paper that the advantage of AHE over other methods is increased if (1) the overall size of the ensemble also adapts during learning; and (2) the target data set is composed of more than two class labels. Through analysis we show that the AHE outperforms other methods because it automatically discovers complementary classifiers: for each data instance in the data set, instances of the classifier type best suited for that data point vote together, while instances of the other, inappropriate classifier types disagree, thereby producing a correct overall majority vote.

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.

It has been shown that the collective action of non-experts can compete favorably with an individual expert or an optimization method on a given problem. However, the best method for organizing collective problem solving is still an open question. Using the domain of robotics, we examine whether cooperative search for design strategies is superior to individual search. We use a web-based robot simulation to determine whether groups of human users can leverage design intuition from others to focus search on relevant parts of a complex design space. We show that individuals that work cooperatively with the aid of a simple optimization algorithm are better able to improve the design of robot locomotion than if they were to work individually with the aid of the optimization algorithm. This result suggests that groups of designers may more effectively work in tandem with optimization algorithms than individuals working in isolation.

In biomimetic engineering, we may take inspiration from the products of biological evolution: we may instantiate biologically realistic neural architectures and algorithms in robots, or we may construct robots with morphologies that are found in nature. Alternatively, we may take inspiration from the process of evolution: we may evolve populations of robots in simulation and then manufacture physical versions of the most interesting or more capable robots that evolve. If we follow this latter approach and evolve both the neural and morphological subsystems of machines, we can perform controlled experiments that provide unique insight into how bodies and brains can work together to produce adaptive behavior, regardless of whether such bodies and brains are instantiated in a biological or technological substrate. In this paper, we review selected projects that use such methods to investigate the synergies and tradeoffs between neural architecture, morphology, action, and adaptive behavior.

Whether, when, how, and why increased complexity evolves in biological populations is a longstanding open question. In this work we combine a recently developed method for evolving virtual organisms with an information-theoretic metric of morphological complexity in order to investigate how the complexity of morphologies, which are evolved for locomotion, varies across different environments. We first demonstrate that selection for locomotion results in the evolution of organisms with morphologies that increase in complexity over evolutionary time beyond what would be expected due to random chance. This provides evidence that the increase in complexity observed is a result of a driven rather than a passive trend. In subsequent experiments we demonstrate that morphologies having greater complexity evolve in complex environments, when compared to a simple environment when a cost of complexity is imposed. This suggests that in some niches, evolution may act to complexify the body plans of organisms while in other niches selection favors simpler body plans.

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.

Symbolic regression (SR) is a well studied method in genetic programming (GP) for discovering free-form mathematical models from observed data. However, it has not been widely accepted as a standard data science tool. The reluctance is in part due to the hard to analyze random nature of GP and scalability issues. On the other hand, most popular deterministic regression algorithms were designed to generate linear models and therefore lack the flexibility of GP based SR (GP-SR). Our hypothesis is that hybridizing these two techniques will create a synergy between the GP-SR and deterministic approaches to machine learning, which might help bring the GP based techniques closer to the realm of big learning. In this paper, we show that a hybrid deterministic/GP-SR algorithm outperforms GP-SR alone and the state-of-the-art deterministic regression technique alone on a set of multivariate polynomial symbolic regression tasks as the system to be modeled becomes more multivariate.

Symbolic regression (SR) is an attractive modeling approach because it can capture and present, mathematically, relationships between variables of interest. However, given n variables to model, symbolic regression returns a flat list of n equations. As the number of state variables to be modeled scales, interpretation of such a list becomes difficult. Here we present a symbolic regression method that detects and captures hidden hierarchy in a given system. The method returns the equations in a hierarchical dependency graph, which increases the interpretability of the results. We demonstrate that two variations of this hierarchical modeling approach outperform non-hierarchical symbolic regression on a synthetic data suite.

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.

Generating models from large data sets-and determining which subsets of data to mine-is becoming increasingly automated. However, choosing what data to collect in the first place requires human intuition or experience, usually supplied by a domain expert. This paper describes a new approach to machine science which demonstrates for the first time that nondomain experts can collectively formulate features and provide values for those features such that they are predictive of some behavioral outcome of interest. This was accomplished by building a Web platform in which human groups interact to both respond to questions likely to help predict a behavioral outcome and pose new questions to their peers. This results in a dynamically growing online survey, but the result of this cooperative behavior also leads to models that can predict the user's outcomes based on their responses to the user-generated survey questions. Here, we describe two Web-based experiments that instantiate this approach: The first site led to models that can predict users' monthly electric energy consumption, and the other led to models that can predict users' body mass index. As exponential increases in content are often observed in successful online collaborative communities, the proposed methodology may, in the future, lead to similar exponential rises in discovery and insight into the causal factors of behavioral outcomes.

According to the principles of embodied cognition, intelligent behavior must arise out of the coupled dynamics of an agent's brain, body, and environment. This suggests that the morphological complexity of a robot should scale in relation to the complexity of its task environment. This idea is supported by recent work, which demonstrated that when evolving robot morphologies in simple and complex task environments more complex robot morphologies do tend to evolve in more complex task environments. Here this idea is extended to examining the mechanical complexity of evolved robots. Counter to intuition it is found that the mechanical complexity decreases in more complex task environments.

The principles of embodied cognition dictate that intelligent behavior must arise out of the coupled dynamics of an agent's brain, body, and environment. While the relationship between controllers and morphologies (brains and bodies) has been investigated, little is known about the interplay between morphological complexity and the complexity of a given task environment. It is hypothesized that the morphological complexity of a robot should increase commensurately with the complexity of its task environment. Here this hypothesis is tested by evolving robot morphologies in a simple environment and in more complex environments. More complex robots tend to evolve in the more complex environments lending support to this hypothesis. This suggests that gradually increasing the complexity of task environments may provide a principled approach to evolving more complex robots.

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.

This paper extends prior work using Compositional Pattern Producing Networks (CPPNs) as a generative encoding for the purpose of simultaneously evolving robot morphology and control. A method is presented for translating CPPNs into complete robots including their physical topologies, sensor placements, and embedded, closed-loop, neural network control policies. It is shown that this method can evolve robots for a given task. Additionally it is demonstrated how the performance of evolved robots can be significantly improved by allowing recurrent connections within the underlying CPPNs. The resulting robots are analyzed in the hopes of answering why these recurrent connections prove to be so beneficial in this domain. Several hypotheses are discussed, some of which are refuted from the available data while others will require further examination.

Scaffolding---initially simplifying the task environment of autonomous robots---has been shown to increase the probability of evolving robots capable of performing in more complex task environments. Recently, it has been shown that changes to the body of a robot may also scaffold the evolution of non trivial behavior. This raises the question of whether two different kinds of scaffolding (environmental and morphological) synergize with one another when combined. Here it is shown that, for legged robots evolved to perform phototaxis, synergy can be achieved, but only if morphological and environmental scaffolding are combined in a particular way: The robots must first undergo morphological scaffolding, followed by environmental scaffolding. This suggests that additional kinds of scaffolding may create additional synergies that lead to the evolution of increasingly complex robot behaviors.

In order to evolve large robot controllers for increasingly complex tasks, fully connected neural networks are not feasible. However, manually designing sparse neural connectivity is not intuitive, and thus should be placed under evolutionary control. Here I show how spontaneous structural modularity can arise in the connectivity of evolved robot controllers if the controllers are boolean networks, and are selected to converge on point attractors that correspond to successful robot behaviors.

In evolutionary algorithms, much time is spent evaluating inferior phenotypes that produce no offspring. A common heuristic to address this inefficiency is to stop evaluations early if they hold little promise of attaining high fitness. However, the form of this heuristic is typically dependent on the fitness function used, and there is a danger of prematurely stopping evaluation of a phenotype that may have recovered in the remainder of the evaluation period. Here a stopping method is introduced that gradually reduces fitness over the phenotype's evaluation, rather than accumulating fitness. This method is independent of the fitness function used, only stops those phenotypes that are guaranteed to become inferior to the current offspring-producing phenotypes, and realizes significant time savings across several evolutionary robotics tasks. It was found that for many tasks, time complexity was reduced from polynomial to sublinear time, and time savings increased with the number of training instances used to evaluate a phenotype as well as with task difficulty.

The majority of work in the field of evolutionary robotics concerns itself with evolving control strategies for human designed or bio-mimicked robot morphologies. However, there are reasons why co-evolving morphology along with control may provide a better path towards realizing intelligent agents. Towards this goal, a novel method for evolving three-dimensional physical structures using CPPN-NEAT is introduced which is capable of producing artifacts that capture the non-obvious yet close relationship between function and physical structure. Moreover, it is shown how more fit solutions can be achieved with less computational effort by using growth and environmental CPPN input parameters as well as incremental changes in resolution.

In the vast majority of robotics experiments in which a controller is automatically optimized to produce some desired behavior, the robot's body plan does not change over the optimization process. This paper demonstrates the counterintuitive result that by gradually changing a quadrupedal robot's body plan from a prone to a standing posture over the course of the optimization process, desired behavior is discovered more rapidly compared to a simpler set up in which the same robot begins and maintains a standing posture throughout the optimization process. This mechanism of body plan change is referred to as morphological scaffolding, as the robot's body in effect scaffolds the optimization process. Moreover, it was found that this benefit becomes more pronounced for more challenging behaviors, and that this benefit is obtained only if the body plan gradually changes over the optimization process and during the evaluation of a single controller.

The original mechanism by which evolutionary algorithms were to solve problems was to allow for the gradual discovery of sub-solutions to sub-problems, and the automated combination of these sub-solutions into larger solutions. This latter property is particularly challenging when recombination is performed on genomes encoded as trees, as crossover events tend to greatly alter the original genomes and therefore greatly reduce the chance of the crossover event being beneficial. A number of crossover operators designed for tree-based genetic encodings have been proposed, but most consider crossing genetic components based on their structural similarity. In this work we introduce a tree-based crossover operator that probabilistically crosses branches based on the behavioral similarity between the branches. It is shown that this method outperforms genetic programming without crossover, random crossover, and a deterministic form of the crossover operator in the symbolic regression domain.

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.

An ensemble is a set of learned models that make decisions collectively. Although an ensemble is usually more accurate than a single learner, existing ensemble methods often tend to construct unnecessarily large ensembles, which increases the memory consumption and computational cost. Ensemble pruning tackles this problem by selecting a subset of ensemble members to form subensembles that are subject to less resource consumption and response time with accuracy that is similar to or better than the original ensemble. In this paper, we analyze the accuracy/diversity trade-off and prove that classifiers that are more accurate and make more predictions in the minority group are more important for subensemble construction. Based on the gained insights, a heuristic metric that considers both accuracy and diversity is proposed to explicitly evaluate each individual classifier's contribution to the whole ensemble. By incorporating ensemble members in decreasing order of their contributions, subensembles are formed such that users can select the top $p$ percent of ensemble members, depending on their resource availability and tolerable waiting time, for predictions. Experimental results on 26 UCI data sets show that subensembles formed by the proposed EPIC (Ensemble Pruning via Individual Contribution ordering) algorithm outperform the original ensemble and a state-of-the-art ensemble pruning method, Orientation Ordering (OO).

Many approaches to active learning involve periodically training one classifier and choosing data points with the lowest confidence. An alternative approach is to periodically choose data instances that maximize disagreement among the label predictions across an ensemble of classifiers. Many classifiers with different underlying structures could fit this framework, but some ensembles are more suitable for some data sets than others. The question then arises as to how to find the most suitable ensemble for a given data set. In this work we introduce a method that begins with a heterogeneous ensemble composed of multiple instances of different classifier types, which we call adaptive informative sampling (AIS). The algorithm periodically adds data points to the training set, adapts the ratio of classifier types in the heterogeneous ensemble in favor of the better classifier type, and optimizes the classifiers in the ensemble using stochastic methods. Experimental results show that the proposed method performs consistently better than homogeneous ensembles. Comparison with random sampling and uncertainty sampling shows that the algorithm effectively draws informative data points for training.

Embodied artificial intelligence argues that the body and brain play equally important roles in the generation of adaptive behavior. An increasingly common approach therefore is to evolve an agent's morphology along with its control in the hope that evolution will find a good coupled system. In order for embodied artificial intelligence to gain credibility within the robotics and cognitive science communities, however, it is necessary to amass evidence not only for how to co-optimize morphology and control of adaptive machines, but why. This work provides two new lines of evidence for why this co-optimization is useful: Here we show that for an object manipulation task in which a simulated robot must accomplish one, two, or three objectives simultaneously, subjugating more aspects of the robot's morphology to selective pressure allows for the evolution of better robots as the number of objectives increases. In addition, for robots that successfully evolved to accomplish all of their objectives, those composed of evolved rather than fixed morphologies generalized better to previously unseen environmental conditions.

Automatically synthesizing behaviors for robots with articulated bodies poses a number of challenges beyond those encountered when generating behaviors for simpler agents. One such challenge is how to optimize a controller that can orchestrate dynamic motion of different parts of the body at different times. This paper presents an incremental shaping method that addresses this challenge: it trains a controller to both coordinate a robot's leg motions to achieve directed locomotion toward an object, and then coordinate gripper motion to achieve lifting once the object is reached. It is shown that success is dependent on the order in which these behaviors are learned, and that despite the fact that one robot can master these behaviors better than another with a different morphology, this learning order is invariant across the two robot morphologies investigated here. This suggests that aspects of the task environment, learning algorithm or the controller dictate learning order more than the choice of morphology.

A central tenet of embodied artificial intelligence is that intelligent behavior arises out of the coupled dynamics between an agent's body, brain and environment. It follows that the complexity of an agents's controller and morphology must match the complexity of a given task. However, more complex task environments require the agent to exhibit different behaviors, which raises the question as to how to distribute responsibility for these behaviors across the agents's controller and morphology. In this work a robot is trained to locomote and manipulate an object, but the assumption of functional specialization is relaxed: the robot has a segmented body plan in which the front segment may participate in locomotion and object manipulation, or it may specialize to only participate in object manipulation. In this way, selection pressure dictates the presence and degree of functional specialization rather than such specialization being enforced a priori. It is shown that for the given task, evolution tends to produce functionally specialized controllers, even though successful generalized controllers can also be evolved. Moreover, the robot's initial conditions and training order have little effect on the frequency of finding specialized controllers, while the inclusion of additional proprioceptive feedback increases this frequency.

Embodied cognition emphasizes that intelligent behavior results from the coupled dynamics between an agent's body, brain and environment. In response to this, several projects have jointly evolved robot morphology and control to realize desired behaviors. However, which aspects of a robot's morphology should be placed under evolutionary control remains an open question. Here it is shown that subjugating more of the robot's body plan to selection pressure may either slow or increase the rate of evolution, depending on the desired behavior.

We present a novel stereo vision modeling framework that generates approximate, yet physically-plausible representations of objects rather than creating accurate models that are computationally expensive to generate. Our approach to the modeling of target scenes is based on carefully selecting a small subset of the total pixels available for visual processing. To achieve this, we use the estimation-exploration algorithm (EEA) to create the visual models: a population of three-dimensional models is optimized against a growing set of training pixels, and periodically a new pixel that causes disagreement among the models is selected from the observed stereo images of the scene and added to the training set. We show here that using only 5 % of the available pixels, the algorithm can generate approximate models of compound objects in a scene. Our algorithm serves the dual goals of extracting the 3D structure and relative motion of objects of interest by modeling the target objects in terms of their physical parameters (e.g., position, orientation, shape, etc.), and tracking how these parameters vary with time. We support our claims with results from simulation as well from a real robot lifting a compound object.

Many approaches to active learning involve training one classifier by periodically choosing new data points about which the classifier has the least confidence, but designing a confidence measure without bias is nontrivial. An alternative approach is to train an ensemble of classifiers by periodically choosing data points that cause maximal disagreement among them. Many classifiers with different underlying structures could fit this framework, but some classifiers are more suitable for different data sets than others. The question then arises as to how to find the most suitable classifier for a given data set. In this work, an evolutionary algorithm is proposed to address this problem. The algorithm starts with a combination of artificial neural networks and decision trees, and iteratively adapts the ratio of the classifier types according to a replacement strategy. Experiments with synthetic and real data sets show that when the algorithm considers both fitness and classifier type for replacement, the population becomes saturated with accurate instantiations of the more suitable classifier type. This allows the algorithm to perform consistently well across data sets, without having to determine a priori a suitable classifier type.

One common approach to active learning is to iteratively train a single classifier by choosing data points based on its uncertainty, but it is nontrivial to design uncertainty measures unbiased by the choice of classifier. Query by committee suggests that given an ensemble of diverse but accurate classifiers, the most informative data points are those that cause maximal disagreement among the predictions of the ensemble members. However the method for finding ensembles appropriate to a given data set remains an open question. In this paper, the random subspace method is combined with active learning to create multiple instances of different classifier types, and an algorithm is introduced that adapts the ratio of different classifier types in the ensemble towards better overall accuracy. Here we show that the proposed algorithm outperforms C4.5 with uncertainty sampling, Naive Bayes with uncertainty sampling, bagging, boosting and the random subspace method with random sampling. To the best of our knowledge, our work is the first to adapt the ratio of classifiers in a heterogeneous ensemble for active learning.

One of the major obstacles to achieving robots capable of operating in real-world environments is enabling them to cope with a continuous stream of unanticipated situations. In previous work, it was demonstrated that a robot can autonomously generate self-models, and use those self-models to diagnose unanticipated morphological change such as damage. In this paper, it is shown that multiple physical quadrupedal robots with similar morphologies can share self-models in order to accelerate modeling. Further, it is demonstrated that quadrupedal robots which maintain separate self-modeling algorithms but swap self-models perform better than quadrupedal robots that rely on a shared self-modeling algorithm. This finding points the way toward more robust robot teams: a robot can diagnose and recover from unanticipated situations faster by drawing on the previous experiences of the other robots.

Probabilistic Robotics. Sebastian Thrun, Wolfram Burgard, and Dieter Fox. (2005, MIT Press.) 647 pages. It’s a wild world out there. The most striking pattern one can observe in the history of robotics (since its beginnings in the 1950s) is its staggering successes in completely revolutionizing heavy industry through automation, and its equally spectacular failure to produce robots that work alongside us in the home, or out of doors. Like the artificial life community, roboticists have struggled to develop ways to enable their creations to deal with the constantly changing demands of the real world. In the first attempts, robots were provided with internal models crafted for them by their creators, but this limited their usefulness: They slowly evaluated their options against these models, and became useless (or dangerous) if their models became inaccurate through environmental change. One of the very first autonomous robots used this approach: Shakey the Robot [1], developed in the late 1960s, could reason using internal models, but it shook and hesitated as it used them to plan actions. In the 1980s Rod Brooks of MIT fomented a rebellion in the field by stating that robots may not require models at all in order to exhibit useful behavior [2], and (along with others that followed) loosed upon the research community a series of scrambling, bounding, and otherwise fast-moving robot critters. The debate between classical robotics and behavior-based robotics continues today. With the release of Probabilistic Robotics, Sebastian Thrun and his coauthors have laid down another, equally large gauntlet. If the only constancy in life is change, then robots should be able to deal with the uncertainties around them by taking them into account when operating. Thrun et al. replace the complete (and therefore computationally intensive) internal models from classical robotics with statistical ones that honestly reflect the uncertainty out there in the world, from the point of view of a robot. With precision, elegance, and depth, the authors indicate the deep philosophical and methodological differences that distinguish deterministic and model-free robotics from probabilistic robotics. (It is interesting to note that Thrun is currently director of the artificial intelligence laboratory at Stanford University, which, coincidentally, is also the birthplace of Shakey and where Brooks received his Ph.D.) As the authors state at the outset of the book, uncertainty does not just surround the robot in the form of environmental noise, but exists within the robot as well. Any real-world robot can safely assume that there are gaps in its knowledge about the environment (is this a door I’m seeing? ), but also in regard to its sensors (how well did that last measurement actually indicate that the door is open? ), the effect of an action (did I actually close the door? ), and its local position within a larger environment (have I seen this door before? ). Chapter by chapter, the authors systematically reveal the challenges related to equipping a robot with the wherewithal to deal with increasing uncertainty, and along the way introduce algorithms designed to handle them. This book, however, is not for the faint of heart, as the mathematics required to model and contain this uncertainty may be daunting for some. This book serves well as a graduate textbook, and as a mandatory reference and handbook for those working in the field. That being said, the authors provide a very thorough treatment of the mathematics required in the first part of the book. For those who are not working directly in robotics, such as artificial life researchers, machine learning researchers, and biologists, these initial chapters alone are invaluable as an accessible introduction to probability theory. The structure of the book is excellent, as the mathematics is interspersed with examples provided at varying levels of detail, from simple ‘‘imagine a robot attempting to . . . ’’ scenarios, to visual

In previous work [7] a computational framework was demonstrated that employs evolutionary algorithms to automatically model a given system. This is accomplished by alternating the evolution of models with the evolutionary search for new training data. Theory predicts [23] that the best new training data is that which induces maximum disagreement across the current model set. Here it is demonstrated that in a robot application this is not the case, and alternative fitness functions are developed that seek other, better training data. Also, it is shown that although crossover successfully reduces the mean error of the model set, it compromises the ability of the framework to find new, informative training data. This has implications for how to create adaptive, self-modeling machines, and suggests how competitive processes in the brain underlie the generation of intelligent behavior.

In previous work [8] a computational framework was demonstrated that allows a mobile robot to autonomously evolve models its own body for the purposes of adaptive behavior generation or recovery from damage. Conceivably, robots working in tandem could share their experiences such that one robot, when faced with a situation already encountered by another robot, could draw on that experience and adapt more rapidly. A first demonstration of this is given here: multiple robots with the same or similar body plan, but acting independently, combine self-models such that they accelerate modeling. Two approaches are investigated: the robots feed their experiences back into a common modeling engine, or they maintain their own modeling engine but share their best self-models with each other. It was found that the latter approach achieves a significant improvement in modeling compared to a single robot and compared to the former approach. This finding has implications for how to design autonomous robots acting in concert to achieve large-scale tasks.

In previous papers we have described a co-evolutionary algorithm (EEA), the estimation-exploration algorithm, that infers the hidden inner structure of systems using minimal testing. In this paper we introduce the concept of 'managed challenge' to alleviate the problem of disengagement in this and other co-evol-utionary algorithms. A known problem in co-evolutionary dynamics occurs when one population systematically outperforms the other, resulting in a loss of selection pressure for both populations. In system identification (which deals with determining the inner structure of a system using only input/output data), multiple trials (a test that causes the system to produce some output) on the system to be identified must be performed. When such trials are costly, this disengagement results in wasted data that is not utilized by the evolutionary process. Here we propose that data from futile interactions should be stored during disengagement and automatically re-introduced later, when the population re-engages: we refer to this as the test bank. We demonstrate that the advantage of the test bank is two-fold: it allows for the discovery of more accurate models, and it reduces the amount of required training data for both parametric identification -- parameterizing inner structure -- and symbolic identification -- approximating inner structure using symbolic equations -- of nonlinear systems.

New robotics is an approach to robotics that, in contrast to traditional robotics, employs ideas and principles from biology. While in the traditional approach there are generally accepted methods (e. g., from control theory), designing agents in the new robotics approach is still largely considered an art. In recent years, we have been developing a set of heuristics, or design principles, that on the one hand capture theoretical insights about intelligent (adaptive) behavior, and on the other provide guidance in actually designing and building systems. In this article we provide an overview of all the principles but focus on the principles of ecological balance, which concerns the relation between environment, morphology, materials, and control, and sensory-motor coordination, which concerns self-generated sensory stimulation as the agent interacts with the environment and which is a key to the development of high-level intelligence. As we argue, artificial evolution together with morphogenesis is not only "nice to have" but is in fact a necessary tool for designing embodied agents.

This paper describes an active learning approach to the problem of grammatical inference, specifically the inference of deterministic finite automata (DFAs). We refer to the algorithm as the estimation-exploration algorithm (EEA). This approach differs from previous passive and active learning approaches to grammatical inference in that training data is actively proposed by the algorithm, rather than passively receiving training data from some external teacher. Here we show that this algorithm outperforms one version of the most powerful set of algorithms for grammatical inference, evidence driven state merging (EDSM), on randomly-generated DFAs. The performance increase is due to the fact that the EDSM algorithm only works well for DFAs with specific balances (percentage of positive labelings), while the EEA is more consistent over a wider range of balances. Based on this finding we propose a more general method for generating DFAs to be used in the development of future grammatical inference algorithms.

We present a coevolutionary algorithm for inferring the topology and parameters of a wide range of hidden nonlinear systems with a minimum of experimentation on the target system. The algorithm synthesizes an explicit model directly from the observed data produced by intelligently generated tests. The algorithm is composed of two coevolving populations. One population evolves candidate models that estimate the structure of the hidden system. The second population evolves informative tests that either extract new information from the hidden system or elicit desirable behavior from it. The fitness of candidate models is their ability to explain behavior of the target system observed in response to all tests carried out so far; the fitness of candidate tests is their ability to make the models disagree in their predictions. We demonstrate the generality of this estimation-exploration algorithm by applying it to four different problems-grammar induction, gene network inference, evolutionary robotics, and robot damage recovery-and discuss how it overcomes several of the pathologies commonly found in other coevolutionary algorithms. We show that the algorithm is able to successfully infer and/or manipulate highly nonlinear hidden systems using very few tests, and that the benefit of this approach increases as the hidden systems possess more degrees of freedom, or become more biased or unobservable. The algorithm provides a systematic method for posing synthesis or analysis tasks to a coevolutionary system.

Remote robotics applications, such as space exploration or operation in hazardous environments, would greatly benefit from automated recovery algorithms for unanticipated failure or damage. In this paper a two-stage evolutionary algorithm is introduced-which we call the estimation-exploration algorithm-that forwards this aim by first evolving a damage hypothesis after failure and then re-evolving a compensatory neural controller to restore functionality. The algorithm presupposes that a robot simulator is running continuously onboard the physical robot. In this paper, the 'physical' robot is also simulated, but in future work the algorithm will be applied to a real, physical robot. Although evolutionary algorithms require a large number of evaluations to produce a useful solution, the results reported here indicate that almost complete functionality can be restored after only three evaluations on the 'physical' robot, as opposed to over 3000 evaluations if the compensatory controller is evolved all on the 'physical' robot. Our algorithm also has the benefit of producing a diagnostic model of the failure.

We introduce a system that combines ontogenetic development and artificial evolution to automatically design robots in a physics-based, virtual environment. Through lesion experiments on the evolved agents, we demonstrate that the evolved genetic regulatory networks from successful evolutionary runs are more modular than those obtained from unsuccessful runs.

Stable bipedal locomotion has been achieved using coupled evolution of morphology and control of a 5-link biped robot in a physics-based simulation environment. The robot was controlled by a closed loop recurrent neural network controller. The goal was to study the effect of macroscopic, midrange and microscopic changes in mass distribution along the biped skeleton to ascertain whether optimal morphology and control pairs could be discovered. The sensor-motor coupling determined that small changes in morphology manifest themselves as large changes in the performance of the biped, which were exploited by the optimization process. In this way, mechanical design and controller optimization were reduced to a single process, and more mutually optimized designs resulted. This work points to alternative routes for efficient automated and manual biped optimization.