First return, then explore.

Reinforcement learning promises to solve complex sequential-decision problems autonomously by specifying a high-level reward function only. However, reinforcement learning algorithms struggle when, as is often the case, simple and intuitive rewards provide sparse1 and deceptive2 feedback. Avoiding these pitfalls requires a thorough exploration of the environment, but creating algorithms that can do so remains one of the central challenges of the field. Here we hypothesize that the main impediment to effective exploration originates from algorithms forgetting how to reach previously visited states (detachment) and failing to first return to a state before exploring from it (derailment). We introduce Go-Explore, a family of algorithms that addresses these two challenges directly through the simple principles of explicitly 'remembering' promising states and returning to such states before intentionally exploring. Go-Explore solves all previously unsolved Atari games and surpasses the state of the art on all hard-exploration games1, with orders-of-magnitude improvements on the grand challenges of Montezuma's Revenge and Pitfall. We also demonstrate the practical potential of Go-Explore on a sparse-reward pick-and-place robotics task. Additionally, we show that adding a goal-conditioned policy can further improve Go-Explore's exploration efficiency and enable it to handle stochasticity throughout training. The substantial performance gains from Go-Explore suggest that the simple principles of remembering states, returning to them, and exploring from them are a powerful and general approach to exploration-an insight that may prove critical to the creation of truly intelligent learning agents.

The Surprising Creativity of Digital Evolution: A Collection of Anecdotes from the Evolutionary Computation and Artificial Life Research Communities.

Evolution provides a creative fount of complex and subtle adaptations that often surprise the scientists who discover them. However, the creativity of evolution is not limited to the natural world: Artificial organisms evolving in computational environments have also elicited surprise and wonder from the researchers studying them. The process of evolution is an algorithmic process that transcends the substrate in which it occurs. Indeed, many researchers in the field of digital evolution can provide examples of how their evolving algorithms and organisms have creatively subverted their expectations or intentions, exposed unrecognized bugs in their code, produced unexpectedly adaptations, or engaged in behaviors and outcomes, uncannily convergent with ones found in nature. Such stories routinely reveal surprise and creativity by evolution in these digital worlds, but they rarely fit into the standard scientific narrative. Instead they are often treated as mere obstacles to be overcome, rather than results that warrant study in their own right. Bugs are fixed, experiments are refocused, and one-off surprises are collapsed into a single data point. The stories themselves are traded among researchers through oral tradition, but that mode of information transmission is inefficient and prone to error and outright loss. Moreover, the fact that these stories tend to be shared only among practitioners means that many natural scientists do not realize how interesting and lifelike digital organisms are and how natural their evolution can be. To our knowledge, no collection of such anecdotes has been published before. This article is the crowd-sourced product of researchers in the fields of artificial life and evolutionary computation who have provided first-hand accounts of such cases. It thus serves as a written, fact-checked collection of scientifically important and even entertaining stories. In doing so we also present here substantial evidence that the existence and importance of evolutionary surprises extends beyond the natural world, and may indeed be a universal property of all complex evolving systems.

Why Open-Endedness Matters.

Rather than acting as a review or analysis of the field, this essay focuses squarely on the motivations for investigating open-endedness and the opportunities it opens up. It begins by contemplating the awesome accomplishments of evolution in nature and the profound implications if such a process could be ignited on a computer. Some of the milestones in our understanding so far are then discussed, finally closing by highlighting the grand challenge of formalizing open-endedness as a computational process that can be encoded as an algorithm. The main contribution is to articulate why open-endedness deserves a place alongside artificial intelligence as one of the great computational challenges, and opportunities, of our time.

Open-Ended Evolution and Open-Endedness: Editorial Introduction to the Open-Ended Evolution I Special Issue.

Nature's spectacular inventiveness, reflected in the enormous diversity of form and function displayed by the biosphere, is a feature of life that distinguishes living most strongly from nonliving. It is, therefore, not surprising that this aspect of life should become a central focus of artificial life. We have known since Darwin that the diversity is produced dynamically, through the process of evolution; this has led life's creative productivity to be called Open-Ended Evolution (OEE) in the field. This article introduces the first of two special issues on current research on OEE and on the more general concept of open-endedness. Most of the papers presented in these special issues are elaborations of work presented at the Third Workshop on Open-Ended Evolution, held in Tokyo as part of the 2018 Conference on Artificial Life.

An Overview of Open-Ended Evolution: Editorial Introduction to the Open-Ended Evolution II Special Issue.

Nature's spectacular inventiveness, reflected in the enormous diversity of form and function displayed by the biosphere, is a feature of life that distinguishes living most strongly from nonliving. It is, therefore, not surprising that this aspect of life should become a central focus of artificial life. We have known since Darwin that the diversity is produced dynamically, through the process of evolution; this has led life's creative productivity to be called Open-Ended Evolution (OEE) in the field. This article introduces the second of two special issues on current research in OEE and provides an overview of the contents of both special issues. Most of the work was presented at a workshop on open-ended evolution that was held as a part of the 2018 Conference on Artificial Life in Tokyo, and much of it had antecedents in two previous workshops on open-ended evolution at artificial life conferences in Cancun and York. We present a simplified categorization of OEE and summarize progress in the field as represented by the articles in this special issue.

Effect of fish oil supplementation on graft patency and cardiovascular events among patients with new synthetic arteriovenous hemodialysis grafts: a randomized controlled trial.

CONTEXT: Synthetic arteriovenous grafts, an important option for hemodialysis vascular access, are prone to recurrent stenosis and thrombosis. Supplementation with fish oils has theoretical appeal for preventing these outcomes. OBJECTIVE: To determine the effect of fish oil on synthetic hemodialysis graft patency and cardiovascular events. DESIGN, SETTING, AND PARTICIPANTS: The Fish Oil Inhibition of Stenosis in Hemodialysis Grafts (FISH) study, a randomized, double-blind, controlled clinical trial conducted at 15 North American dialysis centers from November 2003 through December 2010 and enrolling 201 adults with stage 5 chronic kidney disease (50% women, 63% white, 53% with diabetes), with follow-up for 12 months after graft creation. INTERVENTIONS: Participants were randomly allocated to receive fish oil capsules (four 1-g capsules/d) or matching placebo on day 7 after graft creation. MAIN OUTCOME MEASURE: Proportion of participants experiencing graft thrombosis or radiological or surgical intervention during 12 months' follow-up. RESULTS: The risk of the primary outcome did not differ between fish oil and placebo recipients (48/99 [48%] vs 60/97 [62%], respectively; relative risk, 0.78 [95% CI, 0.60 to 1.03; P = .06]). However, the rate of graft failure was lower in the fish oil group (3.43 vs 5.95 per 1000 access-days; incidence rate ratio [IRR], 0.58 [95% CI, 0.44 to 0.75; P < .001]). In the fish oil group, there were half as many thromboses (1.71 vs 3.41 per 1000 access-days; IRR, 0.50 [95% CI, 0.35 to 0.72; P < .001]); fewer corrective interventions (2.89 vs 4.92 per 1000 access-days; IRR, 0.59 [95% CI, 0.44 to 0.78; P < .001]); improved cardiovascular event-free survival (hazard ratio, 0.43 [95% CI, 0.19 to 0.96; P = .04]); and lower mean systolic blood pressure (-3.61 vs 4.49 mm Hg; difference, -8.10 [95% CI, -15.4 to -0.85]; P = .01). CONCLUSIONS: Among patients with new hemodialysis grafts, daily fish oil ingestion did not decrease the proportion of grafts with loss of native patency within 12 months. Although fish oil improved some relevant secondary outcomes such as graft patency, rates of thrombosis, and interventions, other potential benefits on cardiovascular events require confirmation in future studies. TRIAL REGISTRATION: isrctn.org Identifier: ISRCTN15838383.

Birth defects among a cohort of infants born to HIV-infected women on antiretroviral medication.

OBJECTIVE: To determine rate of and risk factors for birth defects in infants born to HIV-infected women receiving nucleoside and protease inhibitor antiretroviral (ARV) therapy. METHODS: Birth defects were evaluated among infants on the Pediatric AIDS Clinical Trials Group 316 trial that studied addition of peripartum nevirapine to established ARV regimen for prevention of mother-to-child transmission. Maternal therapy was categorized by trimester of earliest exposure. Birth defects were coded using conventions of the Antiretroviral Pregnancy Registry. RESULTS: Birth defects were detected in 60/1414 (4.2%; 95% CI 3.3-5.4%) infants including 30/636 (4.7%; 95% CI 3.2-6.7%) with first trimester ARV exposure and 30/778 (3.9%; 95% CI 2.6-5.5%) with exposure only after the first trimester (P=0.51). Rates of classes of defects were similar between first trimester compared to later exposure groups except heart defects which occurred in 16 (2.5%; 95% CI 1.4-4.1%) with first trimester ARV exposure and in six (0.8%; 95% CI 0.3-1.7%) infants with later exposure (P=0.02). Exposure to ARV was not associated with specific types of heart defects. Two cases of cardiomyopathy were noted. CONCLUSION: ARV use in early pregnancy was not associated with an increased risk of birth defects overall. The possible association of ARV exposure with heart defects requires further surveillance.

Abandoning objectives: evolution through the search for novelty alone.

In evolutionary computation, the fitness function normally measures progress toward an objective in the search space, effectively acting as an objective function. Through deception, such objective functions may actually prevent the objective from being reached. While methods exist to mitigate deception, they leave the underlying pathology untreated: Objective functions themselves may actively misdirect search toward dead ends. This paper proposes an approach to circumventing deception that also yields a new perspective on open-ended evolution. Instead of either explicitly seeking an objective or modeling natural evolution to capture open-endedness, the idea is to simply search for behavioral novelty. Even in an objective-based problem, such novelty search ignores the objective. Because many points in the search space collapse to a single behavior, the search for novelty is often feasible. Furthermore, because there are only so many simple behaviors, the search for novelty leads to increasing complexity. By decoupling open-ended search from artificial life worlds, the search for novelty is applicable to real world problems. Counterintuitively, in the maze navigation and biped walking tasks in this paper, novelty search significantly outperforms objective-based search, suggesting the strange conclusion that some problems are best solved by methods that ignore the objective. The main lesson is the inherent limitation of the objective-based paradigm and the unexploited opportunity to guide search through other means.

Picbreeder: a case study in collaborative evolutionary exploration of design space.

For domains in which fitness is subjective or difficult to express formally, interactive evolutionary computation (IEC) is a natural choice. It is possible that a collaborative process combining feedback from multiple users can improve the quality and quantity of generated artifacts. Picbreeder, a large-scale online experiment in collaborative interactive evolution (CIE), explores this potential. Picbreeder is an online community in which users can evolve and share images, and most importantly, continue evolving others' images. Through this process of branching from other images, and through continually increasing image complexity made possible by the underlying neuroevolution of augmenting topologies (NEAT) algorithm, evolved images proliferate unlike in any other current IEC system. This paper discusses not only the strengths of the Picbreeder approach, but its challenges and shortcomings as well, in the hope that lessons learned will inform the design of future CIE systems.

Autonomous evolution of topographic regularities in artificial neural networks.

Looking to nature as inspiration, for at least the past 25 years, researchers in the field of neuroevolution (NE) have developed evolutionary algorithms designed specifically to evolve artificial neural networks (ANNs). Yet the ANNs evolved through NE algorithms lack the distinctive characteristics of biological brains, perhaps explaining why NE is not yet a mainstream subject of neural computation. Motivated by this gap, this letter shows that when geometry is introduced to evolved ANNs through the hypercube-based neuroevolution of augmenting topologies algorithm, they begin to acquire characteristics that indeed are reminiscent of biological brains. That is, if the neurons in evolved ANNs are situated at locations in space (i.e., if they are given coordinates), then, as experiments in evolving checkers-playing ANNs in this letter show, topographic maps with symmetries and regularities can evolve spontaneously. The ability to evolve such maps is shown in this letter to provide an important advantage in generalization. In fact, the evolved maps are sufficiently informative that their analysis yields the novel insight that the geometry of the connectivity patterns of more general players is significantly smoother and more contiguous than less general ones. Thus, the results reveal a correlation between generality and smoothness in connectivity patterns. They also hint at the intriguing possibility that as NE matures as a field, its algorithms can evolve ANNs of increasing relevance to those who study neural computation in general.

Born to learn: The inspiration, progress, and future of evolved plastic artificial neural networks.

Biological neural networks are systems of extraordinary computational capabilities shaped by evolution, development, and lifelong learning. The interplay of these elements leads to the emergence of biological intelligence. Inspired by such intricate natural phenomena, Evolved Plastic Artificial Neural Networks (EPANNs) employ simulated evolution in-silico to breed plastic neural networks with the aim to autonomously design and create learning systems. EPANN experiments evolve networks that include both innate properties and the ability to change and learn in response to experiences in different environments and problem domains. EPANNs' aims include autonomously creating learning systems, bootstrapping learning from scratch, recovering performance in unseen conditions, testing the computational advantages of particular neural components, and deriving hypotheses on the emergence of biological learning. Thus, EPANNs may include a large variety of different neuron types and dynamics, network architectures, plasticity rules, and other factors. While EPANNs have seen considerable progress over the last two decades, current scientific and technological advances in artificial neural networks are setting the conditions for radically new approaches and results. Exploiting the increased availability of computational resources and of simulation environments, the often challenging task of hand-designing learning neural networks could be replaced by more autonomous and creative processes. This paper brings together a variety of inspiring ideas that define the field of EPANNs. The main methods and results are reviewed. Finally, new opportunities and possible developments are presented.

The Emergence of Canalization and Evolvability in an Open-Ended, Interactive Evolutionary System.

Many believe that an essential component for the discovery of the tremendous diversity in natural organisms was the evolution of evolvability, whereby evolution speeds up its ability to innovate by generating a more adaptive pool of offspring. One hypothesized mechanism for evolvability is developmental canalization, wherein certain dimensions of variation become more likely to be traversed and others are prevented from being explored (e.g., offspring tend to have similar-size legs, and mutations affect the length of both legs, not each leg individually). While ubiquitous in nature, canalization is rarely reported in computational simulations of evolution, which deprives us of in silico examples of canalization to study and raises the question of which conditions give rise to this form of evolvability. Answering this question would shed light on why such evolvability emerged naturally, and it could accelerate engineering efforts to harness evolution to solve important engineering challenges. In this article, we reveal a unique system in which canalization did emerge in computational evolution. We document that genomes entrench certain dimensions of variation that were frequently explored during their evolutionary history. The genetic representation of these organisms also evolved to be more modular and hierarchical than expected by chance, and we show that these organizational properties correlate with increased fitness. Interestingly, the type of computational evolutionary experiment that produced this evolvability was very different from traditional digital evolution in that there was no objective, suggesting that open-ended, divergent evolutionary processes may be necessary for the evolution of evolvability.

Baseline resistance to nucleoside reverse transcriptase inhibitors fails to predict virologic response to combination therapy in children (PACTG 338).

BACKGROUND: The association between baseline drug resistance mutations and subsequent increase in viral failure has not been established for HIV-infected children. We evaluated drug resistance mutations at 39 codon sites (21 protease inhibitor (PI) resistant codons and 18 nucleoside reverse transcriptase inhibitor (NRTI) resistant codons) for 92 clinically stable NRTI-experienced, PI-naive HIV-infected children 2 to 17 years of age who were initiating new therapy with ritonavir plus zidovudine (ZDV) and lamivudine or plus stavudine. The association between baseline drug resistance mutations and subsequent viral failure after 12 and 24 weeks of highly active antiretroviral therapy (HAART) was studied. RESULTS: There were few primary PI associated mutations in this PI-naïve population, but 84% had NRTI mutations--codons 215 (66%), 41 (42%), 67 (37%), 210 (33%) and 70 (32%). None of the specific baseline drug resistance mutations were associated with a higher rate of virologic failure after 12 or 24 weeks of HAART. Median week 12 viral load decreased as the total number of NRTI mutations at baseline increased (P = 0.006). Specifically, a higher level of baseline ZDV resistance mutation was associated with a decrease in viral failure after 12 weeks on a ZDV-containing HAART regimen (P = 0.017). CONCLUSION: No increase was seen in the rate of viral failure after HAART associated with the presence of resistance mutations at baseline. This paradoxical result may be due to adherence, replicative capacity, or ZDV hypersusceptibility to the new regimen.

WebAL Comes of Age: A Review of the First 21 Years of Artificial Life on the Web.

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.

Open-Ended Evolution: Perspectives from the OEE Workshop in York.

We describe the content and outcomes of the First Workshop on Open-Ended Evolution: Recent Progress and Future Milestones (OEE1), held during the ECAL 2015 conference at the University of York, UK, in July 2015. We briefly summarize the content of the workshop's talks, and identify the main themes that emerged from the open discussions. Two important conclusions from the discussions are: (1) the idea of pluralism about OEE-it seems clear that there is more than one interesting and important kind of OEE; and (2) the importance of distinguishing observable behavioral hallmarks of systems undergoing OEE from hypothesized underlying mechanisms that explain why a system exhibits those hallmarks. We summarize the different hallmarks and mechanisms discussed during the workshop, and list the specific systems that were highlighted with respect to particular hallmarks and mechanisms. We conclude by identifying some of the most important open research questions about OEE that are apparent in light of the discussions. The York workshop provides a foundation for a follow-up OEE2 workshop taking place at the ALIFE XV conference in Cancún, Mexico, in July 2016. Additional materials from the York workshop, including talk abstracts, presentation slides, and videos of each talk, are available at http://alife.org/ws/oee1 .

Switch from ritonavir to indinavir in combination therapy for HIV-1-infected children.

BACKGROUND: Protease inhibitors are an effective component of combination antiretroviral treatment for children infected with human immunodeficiency virus 1 (HIV-1), but tolerance or toxicity issues sometimes require an alternative therapeutic strategy. METHODS: HIV-1-infected children aged 2-17 years received combination therapy with either stavudine plus ritonavir or with zidovudine, lamivudine, and ritonavir as part of a randomized clinical trial. Twenty-one months after the start of the trial, ritonavir in capsule formulation became unavailable. The treatment regimen for 25 children was switched from ritonavir capsules to indinavir capsules (500 mg/m(2) every 8 h). The other study drugs remained unchanged. A matched-pairs analysis was performed to compare the results for these 25 children with the results for 25 matched children whose treatment regimen continued to include ritonavir (in liquid formulation). RESULTS: There were no significant differences in the percentage of children with an HIV-1 RNA load of

Growth of human immunodeficiency virus-infected children receiving highly active antiretroviral therapy.

BACKGROUND: Weight and height growth of HIV-infected children tends to lag behind that of uninfected children of similar age. Previous reports of the effect of highly active antiretroviral therapy (HAART) on the growth of HIV-infected children have been contradictory. METHODS: Age- and gender-adjusted height and weight z scores were studied for 192 HIV-infected children, 4 months to 17 years of age, who had been treated with antiretroviral therapy for at least 16 weeks. These children, in clinically and immunologically stable condition, were enrolled into one of 4 HAART regimens and evaluated for 96 weeks. RESULTS: At baseline, these HIV-infected children were significantly shorter than uninfected children (mean z score, -0.57; 95% confidence interval, -0.73 to -0.41; P < 0.001). Children with greater viral loads at baseline were significantly shorter and lighter than children with smaller viral loads (both P < 0.001). Administration of HAART led to an increase in mean weight z scores to normal values (mean z score increase, from -0.16 to >0) by week 48 and an increase in mean height z scores of 72% toward normal values (mean z score increase, from -0.57 to -0.16) by week 96. Younger children gained height more rapidly (P < 0.001), and children with greater baseline viral loads gained weight more rapidly (P < 0.001). There was no evidence of differential height or weight changes in 48 weeks between children with different degrees of virologic control. CONCLUSIONS: HAART improved the average weight gain of HIV-infected children from subnormal to normal after 1 year and improved average height growth to nearly normal after 2 years.

Investigating Biological Assumptions through Radical Reimplementation.

An important goal in both artificial life and biology is uncovering the most general principles underlying life, which might catalyze both our understanding of life and engineering lifelike machines. While many such general principles have been hypothesized, conclusively testing them is difficult because life on Earth provides only a singular example from which to infer. To circumvent this limitation, this article formalizes an approach called radical reimplementation. The idea is to investigate an abstract biological hypothesis by intentionally reimplementing its main principles to diverge maximally from existing natural examples. If the reimplementation successfully exhibits properties resembling biology, it may support the underlying hypothesis better than an alternative example inspired more directly by nature. The approach thereby provides a principled alternative to a common tradition of defending and minimizing deviations from nature in artificial life. This work reviews examples that can be interpreted through the lens of radical reimplementation to yield potential insights into biology despite having purposely unnatural experimental setups. In this way, radical reimplementation can help renew the relevance of computational systems for investigating biological theory and can act as a practical philosophical tool to help separate the fundamental features of terrestrial biology from the epiphenomenal.

Altruists Proliferate Even at a Selective Disadvantage within Their Own Niche.

The evolutionary origin of altruism is a long-standing puzzle. Numerous explanations have been proposed, most prominently based on inclusive fitness or group selection. One possibility that has not yet been considered is that new niches will be created disproportionately often when altruism appears, perhaps by chance, causing altruists to be over-represented in such new niches. This effect is a novel variant of group selection in which altruistic groups benefit by discovering unoccupied niches instead of by competing for the limited resources within a single niche. Both an analytical population genetics model and computational simulations support that altruism systematically arises due to this side effect of increased carrying capacity even when it is strongly selected against within any given niche. In fact, even when selection is very strongly negative and altruism does not develop in most populations, it can still be expected to be observed in a consistent fraction of species. The ecological structure provided by niches thereby may be sufficient for altruists to proliferate even if they are always at a disadvantage within each niche considered individually.

Indirectly Encoding Running and Jumping Sodarace Creatures for Artificial Life.

This article presents a lightweight platform for evolving two-dimensional artificial creatures. The aim of providing such a platform is to reduce the barrier to entry for researchers interested in evolving creatures for artificial life experiments. In effect the novel platform, which is inspired by the Sodarace construction set, makes it easy to set up creative scenarios that test the abilities of Sodarace-like creatures made of masses and springs. In this way it allows the researcher to focus on evolutionary algorithms and dynamics. The new indirectly encoded Sodarace (IESoR) system introduced in this article extends the original Sodarace by enabling the evolution of significantly more complex and regular creature morphologies. These morphologies are themselves encoded by compositional pattern-producing networks (CPPNs), an indirect encoding previously shown effective at encoding regularities and symmetries in structure. The capability of this lightweight system to facilitate research in artificial life is then demonstrated through both walking and jumping domains, in which IESoR discovers a wide breadth of strategies through novelty search with local competition.