One such insight concerns the importance of considering how diversity is *characterized* when applying QD algorithms. Specifically, some choices of characterization can make finding QD more difficult, which on sufficiently deceptive problems can translate into an inability to find the best solutions altogether. This apparent weakness presents a problem for researchers interested in finding QD with respect to a non-optimal characterization (i.e., one which inhibits finding the best-performing individuals) because standard practice suggests driving search with the same notion of diversity that you are ultimately interested in discovering (Trujillo et al., 2008, 2011; Lehman and Stanley, 2011b; Cully and Mouret, 2013; Szerlip and Stanley, 2013; Mouret and Clune, 2015). A solution to this problem is presented and then empirically validated in the form of new QD algorithms that drive search with multiple characterizations simultaneously. These new multi-characterization approaches, together with an increased understanding of the types of characterizations that are ideal for driving search effectively, enable the application of QD algorithms to various more difficult domains in the future.

Nature has discovered organisms both diverse and highly optimized within their own niches. This kind of divergent creative phenomenon differs from the typical convergent objective-driven process seen in search algorithms across machine learning, evolutionary computation (EC), and evolutionary robotics. By bringing QD now to the forefront of EC and providing a framework for understanding and comparing its available algorithms, the hope is that the field can progress more confidently from this initial foundation. In some cases (as later results will show), QD may even produce results beyond what an objective-driven process can accomplish, but it more broadly offers the chance to uncover a large swath of uniquely intriguing possibilities within a vast space and during just a single run.

### 2. BACKGROUND

This section begins with a review of historical precedent for the study of QD, followed by highlights of recent works in the area and the questions they raise.

### 2.1. Before QD

Early work in *multi-modal function optimization* [MMFO; Mahfoud (1995)] foreshadowed the later arrival of QD. The aim of MMFO is to discover multiple local optima within a search space, which naturally yields a diversity of solutions. However, its main difference from QD is that MMFO traditionally focuses on *genetic* diversity and tends to apply only to simple phenotypes, such as mathematical functions, where the genotype and phenotype are in effect the same (Mahfoud, 1995); QD reflects a later shift in interest toward *behavioral* diversity and is often applied in domains such as evolutionary robotics where the relationship between genome and behavior is complex. The main limitation of genetic diversity is that it is susceptible to genetic aliasing, which means that genomes that are different may nevertheless behave similarly. Such aliasing, which is amplified especially in the presence of indirect genotype to phenotype mappings (Hornby and Pollack, 2001, 2002; Bongard, 2002; Stanley and Miikkulainen, 2003; Stanley, 2007), is thus counterproductive to find various behaviors, as shown empirically by Trujillo et al. (2011).

Another subject of research related to QD is multi-objective optimization (MOO) (Deb et al., 2002). In MOO, the search algorithm aims to uncover the key trade-offs (called the Pareto front) among two or more objectives set by the user. Similar to QD, MOO returns a set of top candidates rather than a single winner, but MOO is still ultimately driven toward specific objectives (though more than one) and therefore intrinsically convergent. By contrast, QD is a genuine *divergent* form of search driven explicitly to move *away* in the search space from where it has visited before. The unique effect is thus to reveal a sampling of the spectrum of possible behaviors latent in a search space.

### 2.2. Early Divergent Search Algorithms

Interest in divergence in evolutionary algorithms was sparked initially by the surprising observation that some problems are solved more reliably by searching for novel behaviors than by searching for their objective (Lehman and Stanley, 2008, 2011a). This approach, called *novelty search*, revealed just how pervasive and costly deception can be in otherwise unremarkable domains. It also showed that searching divergently instead of convergently can sometimes sidestep deception to uncover desirable parts of

These initial studies were followed by a wave of interest in divergent search algorithms as researchers explored their potential for discovery and open-endedness (Risi et al., 2009, 2011; Soltoggio and Jones, 2009; Doucette and Heywood, 2010; Goldsby and Cheng, 2010; Graening et al., 2010; Krcah, 2010; Kistemaker and Whiteson, 2011; Woolley and Stanley, 2011; Gomes and Christensen, 2013; Gomes et al., 2013; Liapis et al., 2013a,b; Martinez et al., 2013; Morse et al., 2013; Naredo and Trujillo, 2013; Risi and Stanley, 2013). However, a clear missing ingredient from pure novelty or behavioral diversity techniques is a complementary notion of objective quality. The radical shift away from objectives toward divergence discards with it the ability to specify up front what is good and what is bad, and to have that notion influence the search. The loss of this convenient notion set the stage for its reemergence in QD algorithms.

### 2.3. Quality Diversity (QD) Algorithms

Early works on behavioral diversity (Mouret and Doncieux, 2009, 2012) and some more recent studies of combining novelty with objectives (Gomes et al., 2015) investigate the idea of hybridizing novelty with fitness. The means of such combination is usually through a multi-objective framework (Mouret and Doncieux, 2009, 2012), though a weighted combination is also possible (Gomes et al., 2015). However, in either case the notion of fitness (i.e., quality) is *global*, which means in effect that the component of the search pushing toward quality focuses its effort exclusively on the part of the search space where performance is dominant over all other areas of the search space. Thus, such approaches are not generally focused on QD. In an approach closer to QD, Trujillo et al. (2008, 2011) achieve multiple functional behaviors through behavioral speciation and fitness sharing. However, while this approach finds several locally optimal behaviors, it is still governed by global fitness because it preferentially explores higher-performing niches. A preferential push toward global quality in any approach reintroduces a strong convergent force into the search. While that may help in some cases if the aim is to discover a single near-global optimum or a handful of highperforming local optima, QD algorithms aim instead to explore the entire behavior space.

In particular, the hope in QD is to uncover as many diverse behavioral niches as possible, but where each niche is represented by a candidate of the highest possible quality for that niche. That way, the result is a kind of *illumination* of the best of all the diverse possibilities that exist (Mouret and Clune, 2015). The original QD algorithm of this type, called *novelty search with local competition* (NSLC), hybridizes novelty search with local fitness competitions only among individuals with similar behaviors, yielding a broad population of numerous simultaneous local competitions in diverse behavioral niches (Lehman and Stanley, 2011b). In its first demonstration, NSLC uncovered a collection of effective virtual creature morphologies and walking strategies in a single run, thereby demonstrating the unique benefits of QD (Lehman and Stanley, 2011b).

The potential to uncover a diverse collection of high-quality alternatives in a single run inspired further investigations and algorithms. For example, Szerlip and Stanley (2013) evolve diverse ambulating two-dimensional creatures made of sticks, also in a single run. Cully and Mouret (2013) evolve a collection of walking behaviors for hexapod robots that functions as a repertoire of skills for a robot. In a hint at the wide applicability of QD, Szerlip et al. (2015) evolve diverse low-level feature detectors for neural networks that are later aggregated into a combined classifier network. Revealing that QD encompasses more than a single algorithm, Mouret and Clune (2015) and Cully et al. (2015) introduce an alternate QD algorithm called *multi-dimensional archive of phenotypic elites* (MAP-Elites) that collects elite versions of diverse behavior within individual bins in a behavioral map. In yet another QD application, MAP-Elites collects diverse walking strategies for a robot that can be adapted in response to different kinds of damage (Cully et al., 2015). Other applications of MAP-Elites include generating sets of images for fooling deep networks (Nguyen et al., 2015a), and for exposing the space of concepts encoded inside a deep network as two-dimensional images (Nguyen et al., 2015b) and as three-dimensional models (Lehman et al., 2016).

The quickly expanding set of applications of QD motivates the need for a systematic study of its best practices, which is the aim in this paper. For that purpose, a key concept in any QD algorithm is the *behavior characterization* (BC). The BC is usually a vector that describes the chronology of actions taken by an individual during its evaluation but can also describe other salient aspects of an individual's behavior or phenotype. This vector is then used to compute its novelty compared with other individuals (or its location in the behavior map in MAP-Elites), thereby driving the diversity component of QD. An important property of the BC is its *alignment* with the notion of quality, which refers to the *degree to which finding novelty tends also to lead to higher fitness*. For example, in a maze, if the BC is based on the final position reached, then it is highly aligned because eventually an agent that continues to find new final positions will find the endpoint of the maze. While BC alignment can be difficult to measure *a priori* (just as the shape of fitness landscapes are not known *a priori* for any challenging problems of interest), a BC's degree of alignment can be anticipated by considering two key properties of highly aligned BCs: (1) each behavior is associated with only a narrow range of fitness values (e.g., a robot's final position in a maze is associated with exactly one fitness value) and (2) the maximum possible fitness in adjacent regions of behavior space correlates (e.g., nearby positions in a maze generally have similar fitness).

By contrast, interestingly, most published QD applications involve finding diversity with respect to an *unaligned* BC because usually the notion of diversity that we find interesting is not intrinsically aligned with quality (Lehman and Stanley, 2011b; Cully and Mouret, 2013; Szerlip and Stanley, 2013; Mouret and Clune, 2015). For example, seeking creatures of different morphologies or with different numbers of legs does not naturally lead to higherquality walking, yet we are nevertheless interested in finding such creatures. So far, QD has succeeded even despite a lack of such alignment, leaning heavily on the quality component of the algorithm to push otherwise unaligned notions of diversity toward good performance. For example, a previous study of QD that is precedent for the present paper finds that unaligned BCs often lead to a slower discovery of passable solutions (Pugh et al., 2015).

The key question raised by this previous study is whether QD algorithms with unaligned BCs ultimately stop working entirely when the domain is sufficiently hard. The maze used to test unaligned BCs in Pugh et al. (2015) is relatively simple and easy to solve; what would happen with much more complex mazes? This paper takes this next step with mazes of a scale beyond mazes in previous studies of QD and examines the effect on finding QD with respect to unaligned BCs in these new mazes. Not only does this study reveal how QD holds up in more complex domains but it also surveys new strategies for mitigating the effects of BC misalignment (which is usually the most desirable and intuitive way to setup QD). Such insight is not only critical to the future of QD as a nascent field but also important for the general progress of machine learning outside of conventional convergent closed problems, where the potential might be open-ended and the aim to collect broad possibilities rather than to converge to a final answer.

### 3. DOMAINS

In the experiments described in this paper, simulated wheeled robots navigate mazes of varying complexity. To aid in their navigation, they are equipped with six rangefinder sensors (five of which are evenly distributed across the front half of the robot, and one pointing backwards) and four pie-slice sensors that indicate both the relative direction and distance to the goal. These sensors serve as inputs to an evolved neural controller with only a single continuous output that controls the degree to which the robot turns left or right (the robot always moves forward at a constant speed). The task is to evolve neural controllers that successfully guide the robot to a goal at the end of the maze.

Successfully navigating a maze can be challenging because it requires learning a complex mapping between sensors and effectors. In part, because sources of deception (and thus difficulty) are often visually apparent (e.g., dead ends), maze navigation has become a canonical domain for evolutionary robotics experiments [e.g., Lehman and Stanley (2011a) and Velez and Clune (2014)]. Another benefit of maze domains is that they tend to be computationally inexpensive, allowing many more evaluations than more intensive physics-based simulations. For this reason, maze domains are ideal for studying evolutionary dynamics over long timescales – an endeavor that would be impossible in a more computationally expensive domain.

In this study, three mazes of varying difficulty assess the efficacy of QD algorithms that will be described in the next section. In an important departure from mazes designed as an optimization problem [e.g., the HardMaze domain in Lehman and Stanley (2011a)], where there is often only a single "correct" path, the mazes here are intentionally designed with *multiple* viable paths to reach the goal. This unusual maze design makes it possible to investigate evolution's potential for finding QD. Thus, the task in this study is not simply to find an agent that reaches the goal, but to find all of the different ways of driving through the maze (including those who do not necessarily reach the goal at all).

An important feature of all three mazes is the *deceptive trap* – areas of the maze that appear to be close to the goal (in terms of Euclidean distance) but, because of the presence of obstructions, do not actually offer a short drivable path to the goal. These traps, often in the form of an easily accessible corridor that terminates at a dead end before reaching the goal, represent local optima in the search space, and serve to deceive algorithms that simply follow a gradient of increasing fitness (Lehman and Stanley, 2011a). Thus, mazes containing such traps serve as a metaphor for complex domains in general, where successfully finding solutions requires a clever search algorithm aimed at innovation rather than straightforward optimization.

The first maze, introduced by Pugh et al. (2015) as the "QD-maze" but called the **small maze** (**Figure 1**) in this article, provides an initial example of this multi-path maze design. In this maze, individuals must escape from a single deceptive trap surrounding the start point after which the maze opens up, allowing various possible strategies for reaching the goal. Importantly, agents are given a considerable amount of time to allow for the expression of complicated and roundabout strategies (such as crossing back and forth across the map several times before driving to the goal). The ideal QD algorithm would eventually find *all* strategies for driving around the maze, including those that do not end up reaching the goal.

Of course, the most interesting real-world problems are often complex and challenging, and if maze navigation domains are to serve as proxies for such problems then they too should display non-trivial complexity. For this reason, two additional *gauntlet* mazes are introduced. While each maintains the important design principle of multiple viable paths to the goal, these mazes are intentionally made more difficult by (1) adding several larger and more pronounced deceptive traps, (2) setting strict maximum

FIGURE 1 | Small maze. Individuals start at the yellow circle (top) and must navigate to the goal point, marked with a blue circle (bottom). The relative openness and lenient time constraint allow a range of different techniques for reaching the goal.

evaluation times such that individuals cannot wander down a deceptive trap and then subsequently reach the goal point, and (3) placing the goal point at the end of a series of chained sub-mazes that are each approximately as hard as the small maze and the original HardMaze from Lehman and Stanley (2011a). Navigating to the end of the **asymmetric gauntlet** (**Figure 2**) and **symmetric gauntlet** (**Figure 3**) thus requires evolving complicated behavioral strategies and overcoming significant levels of deception. In this way, these mazes test both the ability to overcome multiple successive deceptive traps *and* cover the space of possible solutions in the same run. Parameter settings for each maze domain are presented in **Table 1**, which describes differences in maze size, time constraints, and agent sensor radius.

### 4. ALGORITHMS

This section describes each of the various algorithms considered in this study, beginning with those featured by Pugh et al. (2015). Because the pursuit of quality diversity has only recently become a subject of persistent research interest, there are only two main QD algorithms currently represented in the literature: NSLC (Lehman and Stanley, 2011b) and MAP-Elites (Cully et al., 2015; Mouret and Clune, 2015). To provide a broader perspective on the untapped algorithmic potential in this developing field, this study additionally features several novel variants of these core algorithms including some proposed improvements to MAP-Elites, which is mechanically very simple and thus particularly amenable to modification. Importantly, several other new variants

FIGURE 2 | Asymmetric gauntlet. Individuals start at the bottom point and must navigate to the goal at the top of the maze. Because of the variation between maze legs, reaching the goal is easier by some routes than others. The presence of multiple paths through the maze increases the various potential driving strategies that can reach the goal.

specifically serve to address the problem of finding QD when the desired notion of diversity is unaligned with quality (and thus potentially incapable of finding the best solutions).

All of the following algorithm descriptions are partial in that they describe only selection and population maintenance mechanics for an underlying evolutionary algorithm. Algorithms new to this paper or otherwise not well represented in the literature are described with pseudocode in Appendix A. With the exception of Fitness (Section 4.1.1), which is implemented generationally (the entire population is replaced on every tick), all other algorithms are implemented as steady state (only a small portion of the population is replaced at a time). In particular, batches of 32 genomes are evaluated at a time to facilitate a modest amount of parallelism without substantially disrupting the composition of the population between batches.

FIGURE 3 | Symmetric gauntlet. Individuals start at the point at the bottom and must navigate to the goal at the top of the maze. Each leg of the maze is an approximate mirror image of the neighboring legs (thus, all paths through the maze are similarly difficult to achieve). The presence of multiple legs allows various different driving strategies to be successful.

#### TABLE 1 | Maze-specific parameters.

*Reflecting differences in design and difficulty, some parameters vary between mazes.*

### 4.1. Controls

While not themselves QD algorithms, both of the following two controls are included in the study to establish the importance of specialized approaches that simultaneously balance drives toward behavioral diversity and locally increasing quality. The controls thus, respectively, exemplify searching with quality pressure alone and with diversity pressure alone.

### 4.1.1. [Fitness] Neuroevolution of Augmenting Topologies

The first control, which includes only a quality component, represents a traditional objective-oriented optimization approach and is implemented as standard generational NEAT (NeuroEvolution of Augmenting Topologies) (Stanley and Miikkulainen, 2002) with a population size of 500. Agents are rewarded according to the Euclidean distance between their final position and the goal point (this heuristic also underlies the quality component of all of the QD algorithms throughout this paper). NEAT includes a sophisticated speciation and fitness-sharing mechanism for maintaining genetic diversity across the population. However, as the canonical HardMaze experiments (Lehman and Stanley, 2008, 2011a) reveal, genetic diversity is often not enough to overcome the problem of deception on difficult maze-navigation tasks, which instead favor rewarding *behavioral* diversity (a critical component of QD algorithms).

### 4.1.2. [NS] Novelty Search

The *novelty search* (NS) (Lehman and Stanley, 2008, 2011a) algorithm represents the other extreme: searching only for behavioral diversity with no fixed objective at all (i.e., NS has no "quality component"). Novelty search works by rewarding *novelty* instead of fitness, where novelty measures how different an individual's behavior is from those who have been seen before. More formally, novelty is calculated by summing the distances to the *k*-nearest behaviors (in this paper, *k* = 20) from a set composed of the current population and an *archive* of past behaviors. The distance between two behaviors is simply the Euclidean distance between those behaviors when represented as a vector of numbers (which is the origin of the term *behavior characterization* or BC). While there exist several different strategies for managing the archive (Gomes et al., 2015), preliminary experiments indicated that an effective strategy is to add all individuals to an archive with a maximum size that is enforced by deleting those with the lowest novelty (the novelty of all archive members is recomputed before each deletion). In this study, NS has a population size of 500 and a maximum archive size of 2,500.

### 4.2. Quality Diversity Algorithms

Each of the following algorithms features both of the essential components of QD: pressure to discover more behavioral niches and a tendency toward increasing performance in niches that have already been discovered.

### 4.2.1. [NSLC] Novelty Search with Local Competition

Perhaps, the first true QD algorithm, *novelty search with local competition* (NSLC) (Lehman and Stanley, 2011b) combines the diversifying power of NS with a localized fitness pressure called *local competition* (LC), calculated as the proportion of an individual's k-nearest (*k* = 20) behavior neighbors that have a lower-fitness score. LC allows a quality-based reward to be assigned within behavioral neighborhoods without asserting that some neighborhoods are better than others. In NSLC, novelty and LC are combined by Pareto ranking following the practice of the NSGA-II multi-objective optimization algorithm (Deb et al., 2002).

### 4.2.2. [ME] Multi-Dimensional Archive of Phenotypic Elites

An alternative approach to QD is an algorithm called *Multidimensional Archive of Phenotypic Elites* (MAP-Elites or ME) (Cully et al., 2015; Mouret and Clune, 2015). The key difference in MAP-Elites is that niches are explicitly defined rather than passively emergent from a system of local competition; the behavior space is divided into a number of discrete behavior bins (often called a "grid" and created by discretizing each dimension of the BC) where each bin remembers the single fittest individual ever mapped to that bin. The set of filled bins constitutes the active population and evolution proceeds by selecting a bin at random (with equal probability) to produce an offspring, which is then mapped to a bin corresponding to its behavior where it may be either saved or discarded depending on whether its fitness is higher or lower than the current elite occupant. Because selection is uniform, the hope is to acquire diversity passively by virtue of the observation that more bins will tend to fill over time and, once filled, they will not be forgotten.

### 4.2.3. [MENOV] MAP-Elites **+** Novelty

Unlike NS and NSLC, the original formulation of MAP-Elites does not preferentially explore under-represented behaviors, potentially causing it to lag in its discovery of new types of behaviors. Conveniently, it is easy to augment MAP-Elites with a stronger focus on diversity by simply making selection proportional to novelty. In this variant, called *MAP-Elites* + *Novelty* (MENOV), whenever offspring are generated, they are also added to an archive of past behaviors (with a maximum size of 2,500, managed in the same way as in NS) that enables calculating a novelty score for all members in the MAP-Elites grid.

### 4.2.4. [MEPGD] MAP-Elites **+** Passive Genetic Diversity

The strict elitism at each bin in the original MAP-Elites formulation may eventually cause evolution to stagnate if all stepping stones to higher fitness require first making strides through lower-fitness space. Furthermore, genetic diversity is intrinsically limited when only a single individual is saved in each bin. Addressing both of these potential pitfalls without introducing any additional overhead, a new variant called *MAP-Elites* + *Passive Genetic Diversity* (MEPGD) saves two individuals in each bin instead of one.3 Individuals with a lower fitness than the current elite still have a

<sup>3</sup>The number of extra slots per bin can conceivably be expanded to any number, where all slots except the first are governed by random replacement.

30% chance of being saved in the second slot, regardless of their fitness, thus allowing MEPGD to explore the potential of some lineages that would have otherwise been discarded. Importantly, these extra slots coincide with the set of MAP-Elites bins, which guarantees that they are behaviorally diverse.

### 4.3. Multi-BC Quality Diversity Algorithms

As discussed in Section 2.3, BCs that are strongly aligned with quality encourage the discovery of better behaviors simply by finding different behaviors, effectively bypassing the problem of deception that causes optimization-oriented search processes to become trapped in local optima. However, no such advantage exists for *unaligned* BCs, which often represent the most interesting and desirable types of diversity in practice. Worryingly, Pugh et al. (2015) find that such unaligned BCs actually negatively impact the performance of QD algorithms, which on sufficiently hard problems may translate into an outright failure to find the best-performing solutions. This observation raises the important question of how QD practitioners can find unaligned diversity without losing the ability to circumvent deception offered by aligned BCs.

This section offers a promising answer in the form of *driving search with multiple BCs simultaneously*. To explore this idea, the following algorithms represent various options for adapting QD to support more than one BC.

### 4.3.1. [NS–NS] Multi-BC Novelty Search

Novelty search can be extended to support multiple BCs simultaneously by calculating a separate novelty score for each BC and then combining these scores in a multi-objective formulation [via NSGA-II of Deb et al. (2002)]. Each BC maintains its own independent archive against which individuals are evaluated to determine their novelty score for that BC. There is only a single population where the breeding potential for each member is decided by a Pareto ranking according to the various novelty scores. Although NS is not itself a QD algorithm because it lacks a mechanism for discovered behaviors to increase in quality, when extended to include multiple BCs, NS–NS can conceivably achieve some success if one BC serves to find diversity while another promotes increasing quality (e.g., an unaligned BC paired with an aligned BC). Note that even such a pairing does not quite embody the spirit of QD because any tendency toward increasing quality that emerges from an aligned BC is not explicitly *local*.

### 4.3.2. [NS–NSLC] Multi-BC Novelty Search with Local Competition

The idea of NS–NS can then be expanded to include a drive toward locally increasing quality by adding a LC objective (in the same way as NSLC) where behavioral neighbors are decided by the unaligned BC that expresses the notion of diversity that the user is ultimately interested in collecting. The resulting NS–NSLC algorithm therefore includes three distinct objectives (combined via NSGA-II): (1) a quality-aligned novelty score to facilitate overcoming deception, (2) an unaligned novelty score for discovering new behaviors of interest, and (3) an unaligned LC score to promote competition within niches of similar behaviors.

### 4.3.3. [ME–ME] Multi-BC MAP-Elites

In an effort to maintain its characteristic simplicity, MAP-Elites is extended to support multiple BCs by maintaining a separate grid for each BC (with similar maximum sizes). On each iteration of ME–ME, an equal amount of parents are selected from each grid, and their resulting offspring are mapped to *both* grids (where the decisions to save or discard them are performed independently, e.g., between two grids, a single offspring may be saved in one, both, or neither).

## 4.3.4. [MENOV–MENOV] Multi-BC

### MAP-Elites **+** Novelty

Finally, MENOV is extended to MENOV–MENOV similarly to ME–ME except where each grid also maintains its own novelty archive and selection within each grid is proportional to novelty.

### 5. EXPERIMENTS

The behavior characterization (BC) determines the form of pressure that ultimately drives the diversity component of the search and thus must be selected carefully to complement the evolutionary algorithm. The experiments in this article explore two BCs that are each highly aligned or highly misaligned with the notion of quality (i.e., how close an agent is to arriving at the goal): **EndpointBC**, which is simply a two-dimensional vector containing the *x* and *y* coordinates of an individual's location at the end of its trial, and **DirectionBC**, a five-dimensional vector with entries indicating whether the individual was most frequently facing north (0.125), east (0.375), south (0.625), or west (0.875) for each fifth of its evaluation time. On the one hand, EndpointBC is thus highly aligned with the goal of navigating to the goal point because the continual discovery of new endpoints will eventually lead to finding the goal point. On the other hand, DirectionBC is largely orthogonal to quality because the direction a robot faces at a particular time step does not fully determine whether it solves the maze (more importantly, it is possible to visit all of the behaviors in the DirectionBC space without ever reaching the goal).

Consistent with the observation that the goal of QD applications in practice is often to find diversity with respect to an unaligned BC, the assumption in this study is that the goal is to find QD with respect to DirectionBC. Therefore, exploring how different approaches to QD interact with each of EndpointBC and DirectionBC makes it possible to address several important questions:

solutions to deceptive mazes (Lehman and Stanley, 2008). However, it is unknown whether it is similarly effective at finding QD when diversity is measured on a separate unaligned metric. The hypothesis is that algorithms driven by EndpointBC should do well in terms of progress toward the goal, but may not necessarily result in high diversity with respect to DirectionBC.

3. Finally, can multiple BCs successfully be *combined* to compensate for the shortcomings of highly aligned BCs (lower diversity) and unaligned BCs (lower performance)?

Each of the algorithms from Section 4 is implemented with some combination of DirectionBC and EndpointBC for a total of fifteen treatments, enumerated in **Table 2**. Each treatment is run 20 times on the small maze, symmetric gauntlet, and asymmetric gauntlet for a total of 900 runs (300 per maze). Small maze runs ended after 250,000 evaluations and gauntlet runs ended after 1,000,000 evaluations (in each case, more than enough time for all algorithms to reach a performance plateau). Networks are evolved with a modified version of SharpNEAT 1.0 (Green, 2003) with mutation parameters validated by Pugh et al. (2015): 60% mutate connection, 10% add connection, and 0.5% add neuron. Networks are feedforward and restricted to asexual reproduction; other settings follow SharpNEAT 1.0 defaults. Maze-specific parameter settings are presented in **Table 1**.

In traditional maze navigation domains, an appropriate metric would be whether or not a robot was eventually able to navigate to the goal. However, this metric does not speak to an algorithm's propensity for discovering diversity in a search space. For this reason, Pugh et al. (2015) introduces a new QD metric [which is also similar to the "global reliability" metric in Mouret and Clune (2015)] that reflects both the quality and diversity of individuals found by evolution (including solutions and non-solutions). Diversity in this metric, called the *QD-score*, is measured with respect to a BC. In the experiments reported in this article, DirectionBC always characterizes diversity for the purpose of computing the QD-score *regardless of the behavior characterization driving search*. This approach reflects the usual idea that the desire is to see a wide diversity of solutions at the end of a run with respect to a BC that is not necessarily directly aligned with solving the problem.

To quantify how much of the space is explored by an algorithm for the QD-score, the entire behavior space is first discretized into

*Algorithms in different columns differ by the BC that drives search. Conventional QD algorithms are tested with each of DirectionBC and EndpointBC driving search (denoted by the subscripts d and e, respectively), while a new class of multi-BC QD algorithms drives search with both DirectionBC and EndpointBC simultaneously.*

a collection of *t* bins4 {*N*1, …, *Nt*} as in the MAP-Elites algorithm described in the previous section. Each bin corresponds to a unique combination of features from the individual's BC (in this case, DirectionBC) and represents a niche in the behavior space. Diversity is then quantified as the number of bins filled over the course of an evolutionary run. By *summing the highest fitness values found in each grid bin*, where *Qi* represents the highest fitness achieved in bin *Ni*, it becomes possible to simultaneously quantify both quality and diversity as

$$\text{QD-score} = \sum\_{i=1}^{\ell} Q\_i.$$

This DirectionBC-based QD-score5 is the primary metric in all mazes. Note that for the purpose of calculating QD-score, fitness is defined in a way that reflects the shortest drivable path between an agent ending location and the goal, respecting that agents cannot drive through walls. This special QD-score fitness is calculated by a breadth-first flood fill from the goal point, assigning fitness to locations in the maze that decreases linearly at each layer of the flood fill. Importantly, this fitness value, which draws a perfect non-deceptive gradient over the maze, is not available to any algorithms to drive search but merely appears during *post hoc* analysis to give an accurate accounting for how close each collected behavior is to solving the maze.

Due to the overwhelming historical focus on optimization and the recent realization that behavioral diversity can itself be a powerful tool for optimization (Lehman and Stanley, 2008; Mouret and Doncieux, 2009, 2012), this study includes an additional performance metric for the two gauntlets6 that captures the spirit of this more conventional search paradigm: the *total maze progress* metric measures how close a run is to solving all four legs of the maze. More precisely, total maze progress is the sum of four progress measures (one per leg) where progress for each leg increases linearly as endpoints are discovered further along their solution path (calculated by means of the flood fill distance to the goal point). If *Ei* is the set of all flood fill fitness scores associated with endpoints discovered inside leg *i* then total maze progress can be quantified as

$$\text{total made progress} = \sum\_{i=1}^{4} \max E\_i.$$

A maximum score is achieved by solving all four legs. Total maze progress therefore addresses the important question of how well-suited QD algorithms are to the task of optimizing toward a series of predefined targets.7

<sup>4</sup> In this study, *t* = 1024 when discretizing the DirectionBC behavior space.

<sup>5</sup>The original small maze results from Pugh et al. (2015) instead always measure diversity with respect to the BC that drives search and thus do not explore the idea of driving search with BCs other than those which characterize the dimensions of interest.

<sup>6</sup>No such metric is defined for the small maze because all treatments consistently and quickly find solutions and thus it does not represent a challenging optimization problem.

<sup>7</sup>Total maze progress is related to the interests of multimodal optimization, where the goal is often to find all of the global optima in a fitness landscape without regard to the behaviors or phenotypes that get there.

#### Pugh et al. Quality Diversity: A New Frontier

### 6. RESULTS

In all of the figures presented in this section, treatments are color coded according to which BC drives search: DirectionBC (subscript *d*) is drawn in blue, EndpointBC (subscript *e*) in yellow, multi-BC in green, and Fitness (which is not driven by any BC) in gray. For each treatment, results represent an average over 20 runs; error bars represent the SEM and can be interpreted to infer which differences are statistically significant when *p* values are not explicitly provided. In all reported cases, statistical significance is determined by an unpaired two-tailed Student's *t*-test.8

### 6.1. Total Maze Progress

The total maze progress achieved by each treatment after all evaluations is depicted in **Figure 4** (asymmetric gauntlet) and **Figure 5** (symmetric gauntlet). A maximum possible score of 400 corresponds to solving all four legs in the same run, although such scores are not observed in practice. Unlike in the small maze, where all treatments consistently find solutions in every run, many gauntlet runs (particularly those of Fitness or DirectionBC-driven treatments) do not find solutions at all, reflecting the increased difficulty in the gauntlet mazes. Of the two gauntlet mazes surveyed by this metric, higher scores are obtained by all treatments on the asymmetric gauntlet, indicating that the asymmetric gauntlet is comparatively easier to solve, thus establishing a continuum of difficulty between the three maze domains featured in this study: small maze (easiest), asymmetric gauntlet (harder), and symmetric gauntlet (hardest).

While in both gauntlets the performance of Fitness is subpar as expected [it is known to struggle with deception in maze

<sup>8</sup>The simple Student's *t*-test is chosen intentionally to avoid Type II errors, which are more likely when adjusting for multiple comparisons. As such, the results here are intended to highlight potential differences between treatments, not to establish a definitive ranking.

domains; Lehman and Stanley (2008)], a perhaps more surprising result is that all DirectionBC-driven treatments perform significantly worse than Fitness in terms of ability to find solutions (*p* < 0.05) to both the asymmetric gauntlet (**Figure 4**) and the symmetric gauntlet (**Figure 5**). Indeed, of these treatments on the symmetric gauntlet, only MEPGD*d* finds any solutions at all (two solutions found across all 20 runs).

On the other hand, all approaches that include an aligned BC (EndpointBC) always perform significantly better than Fitness (*p* < 0.001). Of those treatments that include EndpointBC, single-BC approaches tend to perform better (with respect to solving the maze) than multi-BC approaches that also include DirectionBC (**Figures 4** and **5**). This phenomenon is especially apparent on the harder symmetric gauntlet (**Figure 5**), where NSLC*e* and NS*e* perform significantly better than the multi-BC variants (*p* < 0.05). Of particular interest is that specialized QD algorithms such as NSLC*e* are competitive with the currently accepted method for overcoming deception on maze tasks: NS*<sup>e</sup>* (Lehman and Stanley, 2008, 2011a). On the symmetric gauntlet (**Figure 5**), there is some evidence that NSLC*e* may actually be *better* than NS*e*, although the evidence is not strong enough to establish statistical significance (*p* = 0.093).

Of the successful MAP-Elites variants (those driven by EndpointBC), MEPGD*e* performs significantly better than the core ME*e* on both gauntlets (**Figures 4** and **5**), while MENOV*e* in neither case is significantly different than ME*e*.

### 6.2. QD-*Score*

The final QD-score achieved by each treatment after all evaluations is depicted in **Figure 6** (small maze), **Figure 7** (asymmetric gauntlet), and **Figure 8** (symmetric gauntlet).

### 6.2.1. Small Maze

Reflecting its lack of challenging complexity, the best treatments on the small maze (**Figure 6**) consistently achieve near the

maximum possible QD-score of 1,024,000, which corresponds to finding a maze solution (score = 1000) in each of the 1,024 bins. On this relatively simple task, QD-score is dominated by the multi-BC QD approaches (ME*e*ME*d*, MENOV*e*MENOV*d*, NS*e*NSLC*d*) and by NSLC*d*. EndpointBC-driven approaches perform poorly in comparison, though not as poorly as Fitness and NS*d*.

Of interest is the comparatively large variance on the MAP-Elites variants (when driven by DirectionBC) versus their NS-based counterparts (**Figure 6**). In particular, the most extreme such variance, on ME*d*, is caused by three outliers. While most runs of ME*d* score between 950 K and 1000 K, the outlier runs obtain scores of 791 K, 680 K, and 421 K. In each of these runs, the grid is completely filled (representing maximum diversity), but many bins contain low-quality behaviors (mostly representing agents that exclusively drive around inside the main deceptive trap). Thus, the higher variance observed by ME*d* here is indicative of MAP-Elites sometimes becoming stuck in local optima.

#### 6.2.2. Gauntlet Mazes

Because of the strict time constraints on the gauntlet mazes, many types of behaviors (i.e., bins in the QD grid) can never represent full solutions even in theory; thus, the maximum possible QD-score on the gauntlet mazes is lower than on the small maze and also difficult to achieve in practice. This limitation is reflected by the comparatively lower scores observed in both the asymmetric gauntlet (**Figure 7**) and the symmetric gauntlet (**Figure 8**).

While DirectionBC-driven QD achieves the highest scores on the small maze (**Figure 6**), this trend is reversed as domain difficulty increases. On the asymmetric gauntlet, treatments driven by EndpointBC perform similarly to those driven by DirectionBC (**Figure 7**). On the comparatively more difficult symmetric gauntlet, the trend is completely reversed, with EndpointBC-driven

FIGURE 7 | Final QD-score (asymmetric gauntlet). The QD-score achieved by each of fifteen treatments (Table 2) after 1,000,000 evaluations on the asymmetric gauntlet is shown (averaged over 20 runs). Bars are color coded according to which BC drives search (see section 6) and error bars represent SE. In all cases, QD-score is measured with respect to DirectionBC.

approaches performing significantly better than those who are driven only by DirectionBC (**Figure 8**).

Consistently with the small maze, in each of the gauntlets, QD-score is dominated by the best multi-BC treatments. Specifically, in all three mazes, NS*e*NSLC*d* is consistently among the best-performing treatments (**Figures 6**–**8**). On the asymmetric gauntlet (**Figure 7**), its lead is unmatched, while on the symmetric gauntlet it is tied with NSLC*e* (**Figure 8**; the difference between NSLC*e* and NS*e*NSLC*d* is not statistically significant, *p* = 0.163).

Pugh et al. Quality Diversity: A New Frontier

However, it turns out that even though their final QD-scores are similar on the symmetric gauntlet, NSLC*e* and NS*e*NSLC*d* do exhibit different learning curves. To highlight this difference on the symmetric gauntlet, it is instructive to graph the development of QD-score over the course of evolution. **Figure 9** depicts the QD-score over time for the best-performing method from each of the three classes in **Table 2**: EndpointBC, DirectionBC, and multi-BC. The general trend displayed by each treatment is representative of the other treatments in its respective class, e.g., DirectionBC-driven treatments tend to increase quickly and then plateau at a low score. On the other hand, NSLC*e* increases relatively slowly before ultimately reaching a much higher score. Combining the best of both of these options, NS*e*NSLC*d* quickly reaches high scores (**Figure 9**). Thus, overall the hybrid NS*e*NSLC*<sup>d</sup>* proves a competitive choice for maximizing QD-score on all the variant mazes.

### 7. DISCUSSION

Within the wide-ranging field of EC, two distinct types of research goals are relevant in the context of this investigation. The first and historically most dominant focus of EC is the task of optimization: harnessing the powerful natural mechanism of "survival of the fittest" to reach some predefined target (or series of targets). It is this goal that lies at the heart of the vast majority of EC literature, thereby seemingly aligning the ambitions of EC with the broader practice of machine learning, where optimization is treated as the essence of learning itself. However, having only recently begun to garner attention, the second type of research goal is less familiar, though it offers promising new opportunities for discovery and advancement uniquely accessible to EC. This goal, called *quality diversity*, represents a fundamental departure from optimization because instead the idea is to explore all of what is possible rather than to find only the best option. While the primary intention of this paper is to promote the theory and practice of QD, the results of this study have implications relevant to both paradigms.

The recent realization that pursuing behavioral diversity can help to overcome deception (Lehman and Stanley, 2008, 2011a;

Mouret and Doncieux, 2009, 2012) has offered a source of hope to solving the problem of deception that permeates almost every optimization space of interest. However, deception does not exclusively affect optimization and not all notions of "behavioral diversity" are equally capable of thwarting it. As this study reveals, simply focusing on QD does not make evolution immune to the problem of deception because the quality-seeking *component* of QD algorithms can itself fall victim to it. In this study, which features maze tasks of varying difficulty, QD algorithms following the compass of an unaligned BC are incrementally less able to find QD as the level of deception increases from one maze to another (**Figures 6**–**8**). Further highlighting the problem of deception even in QD, surprisingly, as maze difficulty increases, it actually becomes more effective to drive search with an aligned BC even when you are collecting unaligned QD (**Figure 8**). The primary lesson is that searching for diversity with respect to an unaligned BC does not circumvent the problem of deception (doing so is mostly orthogonal to overcoming deception, similar to the shortcomings of pursuing *genetic* diversity). However, for QD practitioners, the magic bullet cannot be to simply drive search with some other, better-suited BC because that only leaves the diversity of interest to be collected *coincidentally*. Instead, this study offers the promising new idea of driving search with multiple BCs simultaneously. The so-called multi-BC algorithms (such as NS–NSLC) allow search to be driven both by the desired notion of diversity and a separate BC that is well equipped to circumvent deception, thus unlocking the best parts of the search space for discovery.

An alternative approach not tested in this study is to simply concatenate both an aligned and unaligned BC into a single BC with more dimensions. In considering this option, it is important to note that the behavior space grows *exponentially* with the size of the BC. Thus, such an approach generally cannot be applied with MAP-Elites because the number of bins would also grow exponentially until the grid no longer resembles a reasonably sized population. While concatenating multiple BCs into a single monolithic BC is still tractable with NS-based algorithms, the resulting vast behavior space may present an additional challenge over the multi-BC approaches tested here.

Following the lesson originally presented by Lehman and Stanley (2008), this study reconfirms that a powerful strategy for finding solutions to a difficult maze is to abandon the objective entirely and simply search for behavioral diversity (e.g., NS*e* in **Figures 4** and **5**). This conclusion itself has implications outside of maze solving that apply more generally to all of optimization. However, an important observation is that not just any type of behavioral diversity is successful. Indeed, with regard to being able to solve difficult mazes, searching for diversity with respect to an unaligned BC (such as DirectionBC) does even worse than purely objective search (**Figure 5**). The more general lesson is that *BCs that are aligned with the notion of quality* (such as EndpointBC in this study) are the key ingredient to overcoming deception on difficult problems. Furthermore, this study offers the additional insight that QD algorithms themselves offer a means for "the objective-less search for behavioral diversity" (i.e., novelty search) to be rectified with their missing objective in a way that allows search to respect the ultimate goal (e.g., solving the maze) without re-introducing the problem of deception. Specifically, NSLC*e* in this paper demonstrates that it can optimize in the presence of strong deception at least as well as regular novelty search (**Figure 4**) and, in fact, might even be better (**Figure 5**). This result suggests that while the ultimate goals of QD are distinct from optimization, advancements in QD can themselves directly benefit optimization.

As a relatively new approach to QD, MAP-Elites remains a largely unexplored paradigm at the time of this writing. The core MAP-Elites algorithm offers the significant appeal of a very simple algorithm (requiring in effect only a few lines of code) that powerfully distills the essence of QD. Because it is relatively new, its performance in this study serves to confirm that it is largely impacted by BCs similarly to NS-based methods (suggesting some general principles for QD across different algorithms), but of course much room remains for MAP-Elites in particular to be improved. MENOV and MEPGD in this study both suggest that the core ME algorithm can be fruitfully augmented in part to overcome any restrictive effects of its strict elitism. Some ideas not tested here include MEPGDNOV (combining genetic diversity with novelty) and MEPGD–MEPGD (ME with genetic diversity and multiple BCs). The genetic diversity component might also benefit from expansion to more than one diversity candidate per bin.

An important question raised by the results is how to decide whether a particular domain is hard (therefore likely requiring more than one BC) and in such cases whether the chosen aligned BC is sufficiently aligned to overcome the threat of deception. One way to decide whether it may be necessary to include multiple BCs is simply to run a pure fitness-based (objective-driven) search. If such a search consistently finds solutions in multiple runs then the domain can be considered sufficiently easy that multiple BCs may be unnecessary. On the other hand, if the domain proves too difficult for fitness, then it is important to make sure that the aligned BC is, in fact, sufficiently aligned to complement the unaligned BC. One way to test for alignment is to try running simple NS only with the candidate aligned BC. If the alignment is effective, such a search should at least do better than fitness-based search, which would then validate that the BC in question can complement an unaligned BC in a multi-BC hybrid.

Interestingly, while the results support that in sufficiently easy domains a more naive single-BC approach with an unaligned BC may work to collect QD, it does not appear harmful in any case to take the safer multi-BC approach even then. Thus, even though it has been customary so far in the QD-related literature to rely on a single unaligned BC (Lehman and Stanley, 2011b; Cully and Mouret, 2013; Szerlip and Stanley, 2013; Mouret and Clune, 2015), it may be possible to revisit some of the domains of the past with multiple BCs and achieve even better performance.

More broadly, the multi-BC approach and our new understanding of the implications of alignment can help us in the

### REFERENCES

future to achieve significantly more impressive results with QD than seen in the past. Even domains that might have seemed inexplicably out of reach might now become accessible through the application of multiple BCs. Thus, because QD represents a promising direction exclusive to evolutionary techniques, it is in the interest not just of those working in QD, but EC and evolutionary robotics as a whole to seek out and propose such future domains. The potential for such ideas is foreshadowed by QD results already published in the diverse domains of morphology evolution (Lehman and Stanley, 2011b; Szerlip and Stanley, 2013; Mouret and Clune, 2015), robot control and adaptation (Cully and Mouret, 2013; Cully et al., 2015; Mouret and Clune, 2015), image generation (Nguyen et al., 2015a,b), and three-dimensional object evolution (Lehman et al., 2016). With increasing interest in the field, these domains may be just the beginning for QD.

### 8. CONCLUSION

In an attempt to unify and investigate the emerging field of quality diversity (QD), this paper compared various QD algorithm variants and controls in three different maze domains, two of a higher level of complexity than previously seen in such maze-based studies. By pushing the mazes to a higher level of complexity than seen in QD before, the study was able to expose conditions under which QD effectively breaks down. It turns out that driving the diversity component of QD algorithms exclusively by a BC unaligned with quality (which is heretofore common practice) performs relatively poorly under such difficult conditions. However, on a positive note, methods that hybridize more than one BC (one aligned and one unaligned) tend to perform well at the same time as finding the kind of diversity desired, suggesting a promising path forward for QD in the future as it is applied in increasingly ambitious domains.

### AUTHOR CONTRIBUTIONS

JP helped conceive the work and led experimental design, implementation, and writing. LS helped conceive the work and contributed to experimental design, implementation, and writing. KS provided vision and oversight, helped conceive the work, and contributed to experimental design and writing.

### FUNDING

This work was supported by the National Science Foundation under grant no. IIS-1421925. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Bedau, M. (2008). "The arrow of complexity hypothesis (abstract)," in *Proceedings of the Eleventh International Conference on Artificial Life (Alife XI)*, eds S.

Bäck, T., Hammel, U., and Schwefel, H.-P. (1997). Evolutionary computation: comments on the history and current state. *IEEE Trans. Evol. Comput.* 1, 3–17. doi:10.1109/4235.585888

Bullock, J. Noble, R. Watson, and M. Bedau (Cambridge, MA: MIT Press), 750. Bishop, C. M. (2006). *Pattern Recognition and Machine Learning*, Vol. 1. New York, NY: Springer.

*and Evolutionary Computation. GECCO '11, Dublin* (New York, NY: ACM), 965–972.

*of the 17th Annual Conference on Genetic and Evolutionary Computation (GECCO '15)* (New York, NY: ACM).

Nolfi, S., and Floreano, D. (2000). *Evolutionary Robotics*. Cambridge: MIT Press.

**Conflict of Interest Statement:** The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

*Copyright © 2016 Pugh, Soros and Stanley. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.*

### APPENDIX

### Algorithm Descriptions

This section provides pseudocode for selected algorithms (particularly studies that were not published previously). Some algorithms represent trivial modifications to existing algorithms, in which case only the modifications are shown. In all cases, *g* represents an individual genome, *B* represents a batch of genomes (batch size: *bsize*), *R* represents the novelty archive (maximum archive size: *rmax*), and *P* represents the population or the MAP-Elites grid (population size: *psize*). Following NEAT (Stanley and Miikkulainen, 2002), genomes are initialized with minimal complexity; additional neurons and connections are added later through mutations.

#### Algorithm 1 | MAP-Elites + Novelty (MENOV)

#### Algorithm 2 | MAP-Elites + Passive Genetic Diversity (MEPGD)

#### Algorithm 3 | Multi-BC Novelty Search with Local Competition (NS-NSLC)

34: end loop

#### Algorithm 4 | Multi-BC Novelty Search (NS-NS)

NS-NS works exactly the same as NS-NSLC, except the LC objective is removed. Modifications to Algorithm 3:

#### Algorithm 5 | Multi-BC MAP-Elites + Novelty (MENOV-MENOV)

<sup>33:</sup> end while

#### Algorithm 6 | Multi-BC MAP-Elites (ME-ME)

ME-ME works similarly to MENOV-MENOV, except selection is uniform rather than proportional to novelty scores (thus there is no need for novelty archives *R*1 and *R*2). Modifications to Algorithm 5:

# On the critical role of Divergent selection in evolvability

#### *Joel Lehman1 \*, Bryan Wilder2 and Kenneth O. Stanley3*

*1Center for Computer Games Research, IT University of Copenhagen, Copenhagen, Denmark, 2Department of Computer Science, University of Southern California, Los Angeles, CA, USA, 3Department of EECS, University of Central Florida, Orlando, FL, USA*

An ambitious goal in evolutionary robotics (ER) is to evolve increasingly complex robotic behaviors with minimal human design effort. Reaching this goal requires evolutionary algorithms that can *unlock* from genetic encodings their latent potential for evolvability. One issue clouding this goal is conceptual confusion about evolvability that often obscures important or desirable aspects of evolvability. The danger from such confusion is that it may establish unrealistic goals for evolvability that prove unproductive in practice. An important issue separate from conceptual confusion is the common misalignment between selection and evolvability in ER. While more expressive encodings can represent higher-level adaptations (e.g. sexual reproduction or developmental systems) that increase long-term evolutionary potential (i.e. evolvability), realizing such potential requires gradients of fitness and evolvability to align. In other words, selection is often a critical factor limiting increasing evolvability. Thus, drawing from a series of recent papers, this article seeks to both (1) clarify and focus the ways in which the term evolvability is used within artificial evolution and (2) argue for the importance of one type of selection, i.e. divergent selection, for enabling evolvability. The main argument is that there is a fundamental connection between divergent selection and evolvability (on both the individual and population level) that does not hold for typical goal-oriented selection. The conclusion is that selection pressure plays a critical role in realizing the potential for evolvability and that divergent selection in particular provides a principled mechanism for encouraging evolvability in artificial evolution.

### *Edited by:*

*Stephane Doncieux, Pierre-and-Marie-Curie University, France*

#### *Reviewed by:*

*Jean-Baptiste Mouret, French Institute for Research in Computer Science and Automation, France Anders Lyhne Christensen, University Institute of Lisbon (ISCTE-IUL), Portugal*

#### *\*Correspondence:*

*Joel Lehman<EMAIL_ADDRESS>
#### *Specialty section:*

*This article was submitted to Evolutionary Robotics, a section of the journal Frontiers in Robotics and AI*

*Received: 30 March 2016 Accepted: 08 July 2016 Published: 02 August 2016*

#### *Citation:*

*Lehman J, Wilder B and Stanley KO (2016) On the Critical Role of Divergent Selection in Evolvability. Front. Robot. AI 3:45. doi: 10.3389/frobt.2016.00045*

Keywords: evolutionary robotics, evolvability, divergent selection, encodings, evolution of complexity

### 1. INTRODUCTION

Natural evolution is an unguided process that has produced organisms with functionalities far exceeding the products of current human engineering. Although biological evolution is well studied, the abstract mechanisms through which cascades of increasingly complex functionalities evolve are not deeply understood. Supporting this claim, artificial evolutionary processes so far cannot reproduce biological levels of behavioral complexity.

This problem is well known within the evolutionary robotics (ER) community, given its aim to create complex robotic behaviors through algorithmic evolution. Note that while this paper focuses on ER, the insights likely generalize to many applications of evolutionary algorithms (EAs) beyond the black box setting (Doncieux and Mouret, 2014); for this reason, the term EA assumes domains in which observable *behavior* results from an evaluation. While ER's aims are ambitious, in practice evolved behaviors have remained simple relative to biological organisms, and ER does not compete commercially with mainstream robotics approaches. Thus, it is natural to seek the cause of the qualitative gulf between natural organisms and ER's current products. One hypothesis is that *evolvability*, i.e. the speed of evolutionary innovation, stagnates in ER systems, whereas in biological evolution, second-order mechanisms (e.g. sexual reproduction or developmental systems) often evolve that *accelerate* innovation.

Accordingly, this paper argues that an important limiting factor in ER is bounded evolvability, which manifests on different structural levels. First, there are limits to the evolvability *possible* to attain within particular ER models, because the search space does not *contain* certain possibilities. For example, most encodings do not enable an organism to influence how its offspring are generated, even if such influence could increase evolvability. Second, there are limits *in practice* to what levels of evolvability will be attained, given how the chosen environment, form of selection pressure, and encoding interact. In particular, because the gradients of task performance and evolvability often fail to align conveniently, selection may prune hereditary pathways that lead to increased evolvability. This paper focuses on this latter factor, because while there exist many interesting proposals for more expressive encodings (Spector and Robinson, 2002; Risi et al., 2010; Lehman and Stanley, 2011b), in practice realizing their potential for evolvability remains difficult (Edmonds, 2001; Spector and Robinson, 2002; Clune et al., 2008). The position taken here is that this challenge largely results from applying selection pressure uncorrelated with evolvability.

A further issue is that the term evolvability is defined across ER studies in disjoint and conflicting ways, which conflates distinct concepts. The result is confusion over what challenges evolvability poses for ER and even over what outcomes are most desirable or possible. One particular source of confusion addressed here concerns the level of organization (e.g. the level of the individual or the population) in which it is most important to consider and encourage evolvability.

To address such confusion, this paper aggregates from an ongoing research agenda (Lehman and Stanley, 2011b; Wilder and Stanley, 2015) one coherent vision of evolvability. Rather than focus on an *individual's* hereditary potential to achieve particular goals, the idea is to encourage the *population's* hereditary potential for creative divergence. The argument is that this conception of evolvability is more realistic and productive than alternative visions, and that it aligns well with researchers' expectations of ER and intuitions about natural evolution's creativity.

Viewing evolvability from this perspective of accelerating creativity has consequences for algorithm design. In particular, this paper argues that *divergent* selection, i.e. selection that encourages simultaneous exploration of diverse solutions, aligns systematically with this type of evolvability; in contrast, more traditional *objective-based* selection, i.e. selection for improving objective performance, has no such consistent alignment. Thus, to create more prolific ER algorithms may require increasing the potential for evolvability in encodings, focusing on populationlevel evolvability instead of on individual-level evolvability, and guiding search through divergent selection.

## 2. EVOLVABILITY IN EVOLUTIONARY ROBOTICS

Because evolutionary computation (EC) as a whole struggles with evolvability (Wagner and Altenberg, 1996; Reisinger et al., 2005; Hu and Banzhaf, 2010), the subfield of ER naturally confronts the same issue (Lehman and Stanley, 2011b; Tarapore and Mouret, 2015). A distracting complication when discussing or quantifying evolvability is the lack of consensus on evolvability's definition across biology (Pigliucci, 2008), EC in general (Altenberg, 1994; Reisinger et al., 2005), or ER in particular (Lehman and Stanley, 2011b; Tarapore and Mouret, 2015).

Overall, evolvability definitions largely can be divided into two main families. One focuses on the ability to respond to particular adaptive challenges (Reisinger et al., 2005; Pigliucci, 2008; Clune et al., 2013), while the other focuses more generally on future creative potential, i.e. the variety of phenotypes reachable from an individual or population (Wagner and Altenberg, 1996; Dichtel-Danjoy and Félix, 2004; Lehman and Stanley, 2011b). Encompassing these narrower viewpoints, a larger-scale conception of evolvability is the ability to create major phenotypic, behavioral, or morphological breakthroughs (Pigliucci, 2008), e.g. the *de novo* evolution of a developmental system. A unifying point is that this kind of large-scale evolvability is evident in natural evolution and is what researchers ultimately aspire to recreate. The hope is that studying and learning how to encourage lower levels of evolvability may aid this latter pursuit.

Such plurality of definitions is not inherently problematic; evolvability as an overarching concept may simply take on different meanings when considered across different functional goals (e.g. whether privileging adaptation to a specific target or potential for founding new niches through creative divergence) or levels of organization (e.g. whether considered over individuals, populations, or species) (Pigliucci, 2008). Thus, rather than absolute truth, the choice of evolvability definition may instead reflect the aims of a particular research agenda. That is, if one hopes to create an ER algorithm that directly solves any ambitious problem through optimization, the most fitting characterization of evolvability may be one aligned with increasing the value of a static fitness function. Yet when adopting a particular definition and devising a measure of it for ER, it is important that the resulting measure still respects what is ultimately *realistic* or *possible*. The measure can then identify limitations in current algorithms and highlight possible improvements, in service of a particular research agenda.

However, some overarching aims of ER may be more realistic than others. For example, while the optimization-based abstraction of evolution has long dominated ER (Lehman and Stanley, 2010), growing evidence suggests that such an approach is misaligned with how ambitious objectives are actually achieved (Doncieux and Mouret, 2014; Stanley and Lehman, 2015) and does not scale in practice (Lehman and Stanley, 2011c; Lehman et al., 2013; Nguyen et al., 2015). Thus, viewing evolvability through the lens of optimization (i.e. evolvability as the potential for solving particular adaptive challenges) may draw focus to desirable but ultimately unrealistic goals, like the design of an algorithm that can successfully optimize toward any arbitrarily complex robotic behavior. So while defining evolvability this way is valid, it may not fruitfully steer ER research.

In contrast, this paper instead frames evolvability by considering ER's most ambitious *creative* goals (i.e. evolvability as future creative potential) where creativity is defined here as the ability to create novel functionally complex artifacts. The argument is that framing evolvability this way draws focus to more realistic goals, because it better reflects how complex behaviors evolve in practice. That is, evolution does not craft highly complex functionalities because such behaviors are an explicit engineering objective, but instead cobbles them together through opportunistic tinkering (Jacob, 1977). Indeed, according to one mainstream biological opinion, complexity in biological evolution results from exploratory *diffusion* through the space of complexity rather than from any pervasive selective advantage that such complexity provides (Miconi, 2008; McShea and Brandon, 2010; Gould, 2011; Stanley and Lehman, 2015). In this view, complex behavior emerges as evolution creatively expands through a growing space of ecological niches (Kauffman, 2000; Schluter, 2000; Kelly, 2010), driven by opportunistic exaptation (Gould and Vrba, 1982) or ecological pressures toward diversity such as competitive exclusion (Hardin, 1960). Empirically, this understanding is supported by studies showing that complex functionalities fail to evolve without the scaffolding of functionally simpler niches (Lenski et al., 2003; Arthur and Polak, 2004), that bacteria colonies tend naturally to generate and maintain vast phenotypic diversity (Saint-Ruf et al., 2014), and that biodiversity begets further biodiversity (Jousset et al., 2016). Furthermore, viewing evolution as an open-ended creative process aligns with a similar understanding of cultural processes such as technological growth (Arthur, 2009; Kelly, 2010; Stanley and Lehman, 2015). Thus, if evolution's productivity largely derives from its capacity to diverge creatively, then *accelerating* such capacity is a logical aim for ER. This paper accordingly argues for measuring and encouraging evolvability as the potential for creative divergence, while acknowledging that other views may better fit alternative research agendas.

One representative such measure of divergent potential is to quantify the phenotypic variability of an individual (Dichtel-Danjoy and Félix, 2004; Pigliucci, 2008), i.e. the phenotypic diversity accessible within an individual's mutational neighborhood. This measure is used in practice (Lehman and Stanley, 2011b) and captures an important facet of an *individual's* potential for creative divergence. However, as explored in the next section, such individual-level focus neglects the greater possibilities enabled by considering the population as a whole (Wilder and Stanley, 2015).

### 3. EVOLVABILITY OF POPULATIONS AND INDIVIDUALS

When evolvability is measured and encouraged in ER, most often it is considered a property of an *individual* (Clune et al., 2013; Lehman and Stanley, 2013; Velez and Clune, 2014), often *aggregated* across the population by taking the mean or maximum value. However, simple aggregations obscure important properties unique to the population level, such as to what extent the population contains a *complementary* diversity of evolvable individuals. An alternative approach is to consider evolvability explicitly as a property of a *population* (Wilder and Stanley, 2015). For example, one such measure is the diversity of phenotypes accessible within the mutational neighborhood of all individuals in the population.

Both conceptions are logically consistent, but they imply different goals for ER. That is, benchmarking methods by their production of individual-level evolvability sets the implicit goal of producing *maximally* evolvable individuals. Even if individual evolvability is aggregated over the population by considering mean or maximum evolvability, both common aggregations can be maximized by a population converged to a *single* maximally evolvable individual. In contrast, benchmarking on populationlevel evolvability stresses the need for maximally evolvable populations, which may result from a diversity of individuals with complementary and specialized evolutionary potentials.

The fundamental problem with guiding ER by individual-level evolvability stems from the logical conclusion of its maximization. For evolvability measures focused on adapting to new goals, maximization requires an individual that can very quickly evolve to achieve any possible goal. For evolvability measures focused on creative potential, maximization requires an individual who can quickly lead to any possible phenotype. While such outcomes are certainly desirable, neither of these extreme visions are realistic nor do they reflect intuitions about terrestrial evolvability.

To highlight the benefits of population-level evolvability for ER, consider two controllers for a biped robot, one that locomotes with a one-legged hop and the other that uses both legs to achieve a smooth walking gait. To achieve their distinct gaits, both controllers contain specialized knowledge and thus are only *locally* evolvable, e.g. mutating the hopping controller yields many hopping gait variations, while mutating the walking controller likewise generates many variations of walking. Through the lens of individual-level evolvability, if both controllers had equivalent *quantities* of evolvability, there is no preference to preserve both in a population. In contrast, population-level evolvability recognizes the greater span of evolutionary potential when the hopper and the walker are both viable leaping-off points (see **Figure 1**).

In this way, population-level evolvability may be a more principled guiding light for ER than individual-level evolvability. As a result, increased focus on population-level evolvability may have implications for improving the design and creativity of ER algorithms and may illuminate promising research trajectories. In this spirit, the next section argues that divergent selection is an important algorithmic feature for cultivating such populationlevel evolvability.

### 4. DIVERGENT SELECTION AND EVOLVABILITY

One necessary condition for the evolution of evolvability is that selection must encourage (or at minimum, not oppose) trajectories through the search space leading to evolvable genotypes. Even if highly evolvable individuals exist within the search space, they are unlikely to be discovered if selection and evolvability are completely decorrelated. Just as degeneracy is over-represented relative to functionality within complex search spaces (i.e. a mutation more often causes catastrophe than novel functionality), there is

no reason to expect an arbitrary genome to be highly evolvable. Thus it is important to explore the relationship between different forms of selection pressure and evolvability. Note that a similar argument related to the evolution of complexity is provided by Miconi (2008).

The dominant form of selection pressure in ER is *objectivebased* fitness: a heuristic measure of progress to some fixed objective. Search driven to optimize such a measure often *converges*, because as the population's fitness rises the set of admissible improvements shrinks. This objective-based perspective derives from abstracting natural evolution as an optimization process (Lehman and Stanley, 2011a), i.e. from considering optimization as the key ingredient that enables impressive evolutionary products.

One might intuitively assume that evolvability will naturally increase with objective-based selection, because increased evolvability will hitchhike as a byproduct of selecting the adaptations such evolvability enables. That is, an evolvable individual will be more likely than an unevolvable one to produce useful adaptions (i.e. increases in fitness); therefore, evolvability will consistently be favored as a result of selecting high-fitness individuals. However, this intuition does not hold up to closer scrutiny or empirical studies (Lehman and Stanley, 2011b).

First, there is no necessary logical connection between narrowly increasing fitness and long-term potential. For example, in ER there may be many genomes with varying evolvability that express the same high-fitness behavior (e.g. a low-evolvability memorized list of motor commands vs. a higher evolvability generic wall following policy); yet short-term fitness optimization cannot *distinguish* between them. For more evolvable lineages to reliably distinguish themselves requires competition between sufficiently *different* lineages with differing potentials. Yet maintaining such diversity is in direct tension with objectivebased selection's tendency to converge. As a result, in most EAs an adaptation quickly propagates throughout the population, regardless if other reachable adaptations hold greater future potential.

A second more fundamental problem results from *deception*, i.e. the tendency in objective-based search for short-term fitness increases to themselves *anticorrelate* with long-term potential; such deception seems to increase in frequency and severity as problems scale in complexity (Zaera et al., 1996; Ficici and Pollack, 1998; Lehman and Stanley, 2011c; Stanley and Lehman, 2015). When objective-based fitness is itself a broken compass, then even if lineage-level selection could lead to evolutionary acceleration, the end effect would only be faster discovery of an ultimately unsatisfactory local optimum.

An alternative to objective-driven search is to explicitly abstract evolution as a creative process, reflecting that a key characteristic of biological evolution is its *divergent* accumulation of novelty. Practical examples of such selection in EAs are given by novelty search (Lehman and Stanley, 2011a), behavioral diversity (Mouret and Doncieux, 2012), and MAP-Elites (Mouret and Clune, 2015). In such algorithms, novelty or divergence is directly selected for, serving as a proxy for important creative processes in biology that are overlooked when evolution is treated only as an optimizer, e.g. negative frequency-dependent selection (Endler and Greenwood, 1988) and adaptive radiation (Schluter, 2000).

In contrast to objective-driven search, a consistent relationship often holds between divergent selection and evolvability (Lehman and Stanley, 2011b, 2013; Lehman and Miikkulainen, 2015; Wilder and Stanley, 2015; Mengistu et al., 2016). Importantly, unlike with *static* measures of progress, measures of divergence are *relative* to the current and past states of the search process. As a result, seeking divergence is self-defeating in a way that pursuing a fixed goal is not (see **Figure 2**). When objectivedriven search is stuck within a local optimum, a high-fitness individual retains such fitness indefinitely; selection in such cases is *antagonistic* to evolvability, because phenotypic deviations are overwhelmingly unlikely to be adaptive. However, with divergent

selection, a lineage must continually innovate to remain novel. Thus there is consistent pressure to diverge, meaning mechanisms that enhance the ability to diverge can hitchhike along with the divergences they enable. Furthermore, because divergent algorithms like novelty search and MAP-Elites are designed to simultaneously maintain many distinct lineages (Lehman et al., 2012; Gomes et al., 2015; Nguyen et al., 2015), evolvable lineages can therefore distinguish themselves by consistently producing novelty. In this way, divergent selection systematically aligns with evolvability. Note that the choice of how to *measure divergence* will significantly impact the evolvability generated by a divergent EA, similarly to how such choice significantly impacts algorithmic performance (Mouret and Doncieux, 2012; Doncieux and Mouret, 2013); how to best align behavioral distance metrics with evolvability without relying on human domain expertise remains an open research question.

Importantly, this argument gracefully extends to the population level. Because divergence is the primary selection criteria, individuals are directly incentivized to diversify and spread over the space of possible phenotypes. The product is thus a diverse set of leaping-off points that enable a significant base level of population-level evolvability. At the same time, by the argument above, lineages are indirectly rewarded to consistently produce diversity, which encourages individual evolvability that is fit to an individual's local phenotypic neighborhood. In this way, divergent selection encourages a population of individuals with complementary evolvabilities, resulting in a much wider range of reachable phenotypes than that would result from considering any single individual.

Beyond theoretical arguments, empirical studies have demonstrated that divergent search often results in higher evolvability than objective-based search (Lehman and Stanley, 2011b, 2013; Lehman and Miikkulainen, 2015; Wilder and Stanley, 2015; Mengistu et al., 2016). Other studies have highlighted that objective-based search often cannot fully exploit features that enable greater *potential* for evolvability, e.g. allowing individuals to control aspects of mutation (Clune et al., 2008; Lehman and Stanley, 2011b) or of reproduction (Spector and Robinson, 2002). One important caveat for interpreting these results is that nearly all such studies focus on individual-level evolvability (Wilder and Stanley, 2015), meaning that further studies focusing on population-level evolvability are needed to validate the theory. But, taken as a whole, evidence is accumulating that divergent selection is a critical ingredient for encouraging evolvability in ER.

## 5. CONCLUSION

This paper addressed two connected aspects of ER: (1) what is a coherent vision that realistically relates evolvability to the goals of ER, and (2) what algorithmic considerations align with achieving that vision. The idea is that it is both realistic and desirable to create divergent EAs that indirectly optimize population-level evolvability, formalized as the potential for a population to realize phenotypic variety. Such an approach agrees with intuitions about and understanding of natural evolution, and respects limitations about what ultimately is algorithmically possible.

While divergent search methods seem more aligned with evolvability than convergent search, a vast gulf still remains between the dynamics of such algorithms and those of natural evolution. One hope is that an explicit focus on population-level evolvability may lead to algorithmic improvements that enhance evolvability. However, a more fundamental problem is that existing measures of divergence in EAs are relatively simplistic and do not enable the seemingly endless and interesting innovation observed in natural evolution. Interesting proposals for more sophisticated divergent selection pressure are beginning to emerge (Liapis et al., 2013; Nguyen et al., 2015; Pugh et al., 2015), and are an important direction for future research.

### AUTHOR CONTRIBUTIONS

JL, BW, and KS, each contributed to the conception and writing of this article.

### REFERENCES

Gould, S. J. (2011). *Full House*. Cambridge, MA: Harvard University Press.

Kelly, K. (2010). *What Technology Wants*. London: Penguin.

### FUNDING

This work was supported by the National Science Foundation under grant no. IIS-1421925. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Zaera, N., Cliff, D., and Bruten, J. (1996). "(Not) evolving collective behaviours in synthetic fish," in *From Animals to Animats 4: Proceedings of the Fourth International Conference on Simulation of Adaptive Behavior* (Cambridge, MA: MIT Press Bradford Books).

**Conflict of Interest Statement:** The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

*Copyright © 2016 Lehman, Wilder and Stanley. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.*

# Behavioral specialization in embodied evolutionary robotics: Why so Difficult?

*Jean-Marc Montanier1 \*, Simon Carrignon1 and Nicolas Bredeche2*

*1Computer Application in Science and Engineering (CASE), Barcelona Supercomputing Center, Barcelona, Spain, 2CNRS, Institute of Intelligent Systems and Robotics (ISIR), Sorbonne Universités, UPMC Univ. Paris 06, Paris, France*

Embodied evolutionary robotics is an on-line distributed learning method used in collective robotics where robots are facing open environments. This paper focuses on learning behavioral specialization, as defined by robots being able to demonstrate different kind of behaviors at the same time (e.g., division of labor). Using a foraging task with two resources available in limited quantities, we show that behavioral specialization is unlikely to evolve in the general case, unless very specific conditions are met regarding interactions between robots (a very sparse communication network is required) and the expected outcome of specialization (specialization into groups of similar sizes is easier to achieve). We also show that the population size (the larger the better) as well as the selection scheme used (favoring exploration over exploitation) both play important – though not always mandatory – roles. This research sheds light on why existing embodied evolution algorithms are limited with respect to learning efficient division of labor in the general case, i.e., where it is not possible to guess before deployment if behavioral specialization is required or not, and gives directions to overcome current limitations.

#### *Edited by:*

*John Howard Long, Vassar College, USA*

#### *Reviewed by:*

*Eliseo Ferrante, Université Libre de Bruxelles, Belgium Eduardo J. Izquierdo, Indiana University, USA*

#### *\*Correspondence:*

*Jean-Marc Montanier<EMAIL_ADDRESS>
#### *Specialty section:*

*This article was submitted to Evolutionary Robotics, a section of the journal Frontiers in Robotics and AI*

*Received: 30 March 2016 Accepted: 17 June 2016 Published: 04 July 2016*

#### *Citation:*

*Montanier J-M, Carrignon S and Bredeche N (2016) Behavioral Specialization in Embodied Evolutionary Robotics: Why So Difficult? Front. Robot. AI 3:38. doi: 10.3389/frobt.2016.00038*

Keywords: embodied evolution, evolutionary robotics, behavioral specialization, division of labor, distributed online learning, collective behavior

### 1. INTRODUCTION

Embodied evolutionary robotics (EER) is defined as the design of on-line distributed evolutionary algorithms to be implemented in a population of robots with limited computation and local communication capabilities (Watson et al., 2002; Eiben et al., 2010). These algorithms can be deployed in *a priori* unknown and open environments, and aim at optimizing on-the-fly the individual's and (ideally) the group's performance with respect to a pre-defined objective. EER takes its root in Evolutionary Robotics (Nolfi and Floreano, 2000; Doncieux et al., 2015), but is also related to evolutionary swarm robotics (Trianni et al., 2008), as it is sometimes (though not always) concerned with the automated design of control architecture for large, swarm-like, population of robots.

In recent years, the on-line nature of such algorithms was shown to be very robust when conducting experiments with real robots (Watson et al., 2002; Prieto et al., 2010; Bredeche et al., 2012; Trueba et al., 2013): compared with more classic evolutionary robotics setup, the emphasis in EER is on the design of robust algorithms (i.e., design *while* already deployed) rather than on producing robust solutions (i.e., design *then* deploy) (Doncieux et al., 2015; Silva et al., 2016). However, the complexity of the tasks to be achieved has been quite limited so far, either resulting with each individual maximizing its own benefit [e.g., phototaxis (Watson et al., 2002), foraging, exploration, etc.] or in a limited level of cooperation among individuals who all display the same typical behavior [e.g., energy sharing (Montanier and Bredeche, 2011)].

To go further, evolving more complex organizations such as division of labor is clearly part of the research agenda. However, in the context of embodied evolution, the amount few works have tackled the evolution of populations where individuals can split in two (or more) sub-groups with specific roles. In this paper, we are interested in the evolution of specialized behaviors as a key milestone toward tackling more complex problems in collective robotics.

Classic (as in *off-line*) evolutionary robotics has already been used as a tool to explore important issues such as the nature of self-organized regulation mechanisms (Waibel et al., 2006; Duarte et al., 2011, 2012a,b; Lichocki et al., 2012; Ferrante et al., 2015), the benefits of communication (Trianni et al., 2007; Goldsby et al., 2010), the importance of coordination (Bernard et al., 2016b), and the trade-off between evolving polymorphic and monomorphic populations (Waibel et al., 2009; Bernard et al., 2015, 2016a; Tuci and Rabérin, 2015). However, embodied evolutionary robotics poses a problem on its own as mating and reproduction are performed *in situ*, meaning that *how* and *where* interactions between individuals are performed actually influence the course of evolution.

So far, the embodied evolution of specialized behaviors has been studied in two contexts: whether sub-tasks are geographically separated or not. First, some works considered the evolution of specialized behaviors in structured environments, where separate regions call for specific skills [e.g., cleaning tasks requiring two different methods (Prieto et al., 2010), increasing reproductive success with either phototaxis or photophobis behaviors (Bredeche et al., 2012; Bredeche, 2014)]. In this context, geographical separation plays an important role as subpopulations can evolve without interacting with one another due to the limitation in terms of communication range, therefore favoring the acquisition and conservation of different skills.

Second, other works have considered whether specialized behaviors could be acquired without geographical separation. It has been shown that specialized foraging behaviors can co-exist in a population of individuals (Haasdijk et al., 2014): faced with two resources available in limited quantity, the population evolves into two sub-groups, each specialized to forage one particular type of resource. However, this work showed that balancing between the two resources is challenging and could only be achieved by introducing a market mechanism explicitly favoring the smallest sub-group.

Possibly the most advanced work on this topic is presented by Trueba et al. (2013). The authors conducted an in-depth empirical study of behavioral specialization within the same geographic location. The authors showed that very specific values for the frequency of replacement and a carefully tuned recombination operator (with low rate) could be used to enforce behavioral specialization in a population of foraging individuals. However, validation in a realistic robotic setup remains to be done as the problem used in this study was greatly simplified: each robot's genome contains a single-gene that can take only three possible values, each value accounting for predefined behaviors.

In light of the limited results obtained so far, we address the following question in this paper: in the absence of geographical separation, **what challenges are posed by the evolution of behavioral specialization in embodied evolutionary robotics?** Specifically, we aim at identifying the limiting constraints in the evolution of behavioral specialization, including a more general formulation of the limiting factors with respect to both setups studied so far that is with or without geographical separation.

Indeed, the challenge of evolving specialization without geographical separation in embodied robotics echoes with concerns in biological speciation, where the lack of reproductive isolation is known to be a major obstacle with respect to genotypic divergence (Coyne and Orr, 1998; Gavrilets, 2003; Nosil, 2012). In this paper, we explore how reproductive isolation (whether by geographical separation or any other means) can favor the emergence of specialization, and what are the other relevant mechanisms at play. In particular, we also explore how selection and population size may impact the evolution of specialized behavior.

In the following, we perform an experimental study using different flavors of embodied evolutionary algorithms in two variations of a task with autonomous virtual robots: a foraging task *with* and *without* geographical separation. Furthermore, an abstract model is presented and used to identify the conditions required for behavioral specialization to occur in the general case, i.e., without referring to any specific evolutionary mechanisms to artificially enforce specialization, such as dedicated evolutionary operators or environment-induced phenotypic plasticity.

### 2. METHOD

### 2.1. A Foraging Task with Mutually Exclusive Resources

In order to study the evolution of behavioral specialization, we devised two experimental setups where foraging resources are required to survive. In both cases, two resources are available, and located in a particular location. These locations may change through time, requiring the agents to move accordingly. In order to successfully get energy from a particular resource, one agent must be on top of the resource location *and* must be able to *synthesize* this particular resource into energy, which requires a particular genetic trait.

Both experimental setups are defined as a circular arena without obstacles. Resources *R*0 and *R*1 are set at a specific location, which initial locations may differ with respect to the environment considered (cf. **Figure 1**), and which regularly moves from one location to another through a total of 8 possible locations. In the first environment (termed *collocateEnv*), the two resources are located in the same area and will move to a similar new area on a regular basis. In the second environment (termed *seperateEnv*), the two resources are located on the opposite side to one another, and will also move on a regular basis, always remaining far from one another. In both environments, resource's locations will move counter-clockwise.

The ability for an agent to synthesize energy from one resource is defined by one specific gene, termed *gskill*. It is defined in (−1.0, +1.0), and conditions the amount energy that can be *automatically* extracted from one resource when located in its area. The energy synthesis function, *Fsynth*, is shown in **Figure 2**. It illustrates that the function is designed so that an agent can get energy from *one* resource *only* (in addition to being located in the right area).

In order to account for the evolution of specialization, we introduce an additional constraint regarding the *carrying capacity* of the resources. Each resource area provides a limited amount of energy available at each time step, which is set so that only half the population can feed from a particular resource. Access to a resource is set according to a *first-come, first-served* basis: if an agent gets access to a resource, it may extract from it until it leaves the area (or until the resource area is relocated). As a result, the optimal survival strategy for the population of agents is to specialize half the agents on one resource (both in terms of tracking and synthesizing capability) and the other half on the other resource.

The fitness function for robot *x* at time *t* is defined as *fitness x t f x i t t w <sup>i</sup>* ( ) , = ( ) <sup>=</sup> − ∑ where *fi*(.) is computed at time step *<sup>i</sup>* depending on the energy synthesis function *Fsynth* with the value of *gskill* as parameter *and* the availability of resources at this particular location. A sliding window of size *w* is used in order to get a reliable estimation of the agent performance throughout its lifetime, and no genome (nor fitness value) is broadcasted during the first *w* iterations. Whether the value of *gskill* is negative or positive conditions the resource to be harvested (*gskill* <0 vs. *gskill* >1, means that resource *Ro* vs. *R*1, will be harvested), and, *if the target resource is available at this location*, the exact value of *gskill* determines the amount of energy to be harvested thanks to the *Fsynth* function.

In this setup, *resource availability* is true if the robot is located close enough to the resource *and* if the resource has not yet reached its carrying capacity.

### 2.2. Algorithms

The control function for all agents is a perceptron without hidden layer and an hyperbolic tangent activation function, which maps sensory inputs (12 proximity sensors, ground detectors, energy level, angle and distance to energy sources, and a bias node) to motor outputs (left and right motor speed). All sensory and motor values are normalized in (−1, +1). This results in a total of 38 weights to evolve. The control architecture is illustrated in Supplementary Material 1.

For the sake of simplicity, we devised a simple implementation of embodied evolution, which we term *vanillaEE*. As with other embodied evolution algorithm, it is assumed that each agent is able to receive genomes and current fitness values from agents within a pre-defined range, as well as to send its own genome and current fitness value to these nearby agents. After a pre-defined duration, which corresponds to the time allowed for evaluation, one of the genomes received previously is selected, and mutated, to produce a new genome, which will be used to provide the parameters for the control function in the next evaluation period.

The pseudo-code for this algorithm is described as Algorithm 1. It starts with a randomly initialized genome, whose parameters are used to set up the neural network controller. At each time step, the agent moves according to its controller outputs and broadcasts its current genome (and possibly its current fitness). Reciprocally, it may receive incoming genome from other neighboring agents [lines 13–16 of the algorithm – the *ListeningQueue* is filled by a subroutine (not shown here) and *getListeningQueueContent*(.) (line 13) is a non-blocking call]. At the end of the evaluation time, the current genome is deleted and replaced, if available, by a genome build from the list of genomes previously received [the *select(.)* and *applyVariation(.)* functions]. Once this new genome's parameters are used to set up the new controller, the list of genomes is emptied. Being a template algorithm, the *vanillaEE* algorithm may yield many variations depending on the particular implementations of the functions used (see below).

It is important to note that selection pressure in embodied evolution acts at two levels: first, pure performance with relation to a task can be evaluated by a fitness function and used to select a particular genome; second, an agent can also boost the chance for survival of its own genome by spreading more copies of this genome than other agents do, especially if a stochastic selection operator is used.

In the following, we use two different variations over the canonical vanillaEE algorithm, instantiating a particular selection scheme for each:

the mEDEA algorithm does not implement the *select* operator (cf. line 20) nor the *computeFitness()* function call (cf. line 10), and does not broadcast a fitness value (cf. line 11) nor receives fitness values with incoming genomes (cf. line 13).

For both algorithms, genome initialization is performed by randomly picking weight values in (−1.0, +1.0), and the variation operator is defined as a gaussian mutation with σ= 0.1. Evaluation time (or *lifetime*) for one genome is set to 600 iterations.

#### ALGORITHM 1 | The VanillaEE algorithm.

#### 6: end if

#### 12: end if

### 3. RESULTS

We devised a total of four setups testing all possible combinations of algorithms (mEDEA, VanillaEE-elitist) and environments (*collocateEnv*, *separateEnv*). For each setup, 50 independent runs are performed, each using the parameters described in **Table 1**. Experiments are implemented in the Roborobo 2*D* simulation tool (Bredeche et al., 2013) with 200 robotic agents.1

### 3.1. Evolution of Specialization

For each environment, two algorithms are tested: mEDEA (with *random* selection) and VanillaEE-elitist (with *elitist* selection). For each setup combining an algorithm and an environment,

<sup>1</sup>Code for all experiments in this Section and the next: http://pages.isir.upmc. fr/~bredeche/Experiments/Frontiers2016/

we classify each of the 50 independent runs depending on their outcomes: (1) all individuals display a similar harvesting pattern wrt. the resource harvested ("*one group*"), (2) two patterns are observed ("*two groups*"), and (3) individuals fail to harvest any resources as the population is extinct ("*extinct*"). For the first two outcomes, classification is made possible by looking at the values of *gskill* in the population, i.e., whether there is *one* or *two* clusters of values. As an example, **Figure 3** shows all *gskill* values in the population for two typical runs over time.

Results are shown in **Table 2**. For both algorithms, specialization fails to evolve in the *collocateEnv* environment, with the *elitist* algorithm also failing partly to even evolve any viable behaviors (two-third of the runs go extinct). The outcome is different in the *seperateEnv* environment as the mEDEA algorithm is actually able to evolve specialization in half of the runs, a result that is not observed with the VanillaEE-elitist algorithm. A statistical

#### TABLE 1 | Parameters used.

test (Pearson's χ<sup>2</sup> -squared) confirms the obvious: strategies used in each environment with the random selection scheme produce significantly different results (*p-value* <0.01).

**Figures 4A,B** compare the outcome of runs using mEDEA algorithm in the *seperateEnv* environment. As expected, runs where two sub-groups evolve also display the highest survival rate, as specialization is the only way for the whole population to survive due to limited available amount of each resource. Results are identical with the VanillaEE-elitist algorithm.

Results show that adding a fitness function (VanillaEEelitist) not only hinders the survival rate but also almost completely shuts down the possibility to evolve specialization. This sheds a negative light on the use of an explicit selection pressure defined through a fitness function over simply considering environmental selection pressure, as with the mEDEA algorithm. However, we can hypothesize that performing selection solely based on task-dependant fitness values does not leave much room for exploration of survival strategies.

### 3.2. Investigating the Trade-off between Exploration and Exploitation

In order to explore the impact of using a fitness function, we posit that there is a trade-off between exploration, which in this case balance toward environmental selection pressure, and exploitation, i.e., selection pressure provided by using a fitness function. We introduce the VanillaEE-tournament-*k* algorithm, similar to what has been proposed by Fernandez Pérez et al. (2015): this algorithm uses a tournament selection of size *k* to regulate the trade-off between the *exploitation* of a fitness function and the *exploration* of solutions allowing the survival of robots. Tournament selection selects the best genome out of *k* randomly picked genomes among those received during the last

evaluation session. Tournament sizes used are *k* = 5 and *k* = 20. Large tournament sizes tends to converge toward elitism selection (favoring exploitation) while small tournament sizes tends to favor exploration. It should be noted that the mEDEA algorithm is identical to a VanillaEE-tournament algorithm with *k* = 1, as using such a value implies random selection.

We design 4 new setups, testing all possibilities between the two tournament sizes and the two environments (*collocateEnv*, *separateEnv*). For each setup 50 independent runs are performed and classified as before. Results shown in **Tables 3** and **4** reveal that as the pressure toward exploitation increases, (a) the number of runs with extinctions also increases (in both setups) and (b) the number of runs where two specialized groups evolve decreases, at least when resources are seperated. A χ<sup>2</sup> statistical test is used for significance.

The smaller the tournament's size, the closer the results are to the results obtained with random selection. Reciprocally, larger size of tournament size produce results close to results obtained with the elitist selection scheme. We conclude that increasing the pressure toward the exploitation of genomes with higher fitnesses leads to sub-optimal solutions. While this mechanism allows us to mitigate the pressure from task-driven fitness function, the pressure from the environment keeps a strong influence, and the question remains open as to why specialization is (nearly) impossible when resources are *not* spatially separated.

TABLE 2 | Classification of the outcome of runs using random selection (i.e., the mEDEA algorithm) and elitist selection.

*Classes are determined using the value of the skill's gene. Fifty runs per experiment. Population size is 200 robots.*

### 3.3. Discussion

As expected from Trueba et al. (2013), we show that when resources are collocated, it is very difficult to evolve specialization. While Trueba et al. (2013) was successful at finding a very precise set of parameter values to achieve specialization, this was done under very specific conditions: either an abstract model or a toy problem (a genome with one parameter that can take one among three possible values). Our results confirm that in the general case, evolving specialization is challenging at the least, and unlikely if resources are collocated.

Similarly, and in accordance with Prieto et al. (2010), Bredeche et al. (2012), and Bredeche (2014), we show that geographical

*Classes are determined using the value of the skill's gene. Fifty runs per experiment. Population size is 200 robots. Random and elitist selection methods are copied from Table 2 for clarity.*

TABLE 4 | Classification of the outcome of runs where resources are collocated.

*Classes are determined using the value of the skill's gene. Fifty runs per experiment. Population size is 200 robots. Random and elitist selection methods are copied from Table 2 for clarity.*

FIGURE 4 | Number of active robots (mean, min and max from the 50 runs) in the *separateEnv* where (A) only one group is evolved (i.e., one cluster of values for the *gskill* gene) and (B) two groups are evolved (i.e., two clusters of values). The maximum number of active robots is 200.

separation promotes the evolution of specialization. However, specialization is not always evolved here (at best 36% of the runs for the best setting), while it was always the case in previously cited works. This is actually not a surprise as we face a more challenging set-up: we consider *extinction*, that is, the possibly to engage in evolutionary dead-ends. As a consequence, not only it is risky for the population to switch from one equilibrium (e.g., foraging without specialization) to another (e.g., foraging the two resources) but also historical contingencies can lead to early extinction, if foraging is not evolved in the very first generations.

From the results we obtained so far, we now question the current claim stating that one needs either geographical separation and/or very specific evolutionary operators as a necessary condition. In fact, bipolar crossover (Prieto et al., 2010), high replacement frequency (Trueba et al., 2013), low recombination rate (Trueba et al., 2013), market mechanism (Haasdijk et al., 2014), and geographical separation (Bredeche et al., 2012; Bredeche, 2014) can all be seen as coming from the same origin: a mean to achieve reproductive isolation.

Therefore, we posit this new hypothesis: **reproductive isolation is a key factor in the evolution of specialization**, whether the population is geographically dispersed or not. In order to investigate this assumption, we explore in the next Section an abstract model to study the impact of reproductive isolation independently from how it is implemented in practical, i.e., through geographical separation *or any other means*, and reveal the critical conditions for evolving specialization.

### 4. ANALYSIS

In order to identify the necessary conditions required to evolve specialization, we introduce an abstract model to perform computationally intensive experiments. In this model, each agent is located on a node within a graph, and each node hosts one agent only. Edges between two nodes indicate that genetic material is exchanged by the agents. Each agent lives for four iterations, has a battery that consumes one unit per iteration, and forage from resources *R*0 or *R*1 depending on the value of its *gskill* gene (as before, a value close to zero means no foraging), just as in the setup used in the previous Section (except that a genome contains now a single *gskill* gene). As before, each resource enables the survival of one half of the population, meaning that specialization into two groups is mandatory for the whole population to survive. We do not consider extinction: an agent, which runs short of energy is deactivated for 4–14 iterations (random), then listen to its neighbors during 4 iterations, and is finally reactivated using one of the received (and mutated) genome.

For each run, we randomly generate graphs, fixing only the number of nodes and the average number of edges for each node.

FIGURE 5 | The number of agents alive at the end of a simulation for different densities, different tournament sizes (from 1 to 50), and population sizes (100 and 500). Each violon plots is built from the result of 160 independent runs.

The number of edges acts as a proxy for the study of reproductive isolation. In order to do so, we have devised a method, which generates random connex graphs with a desired *density* of edges between nodes. The minimal density is 2 *<sup>n</sup>* (i.e., a ring), with *n* the number of agents and the maximal density is 1.0 (i.e., a complete graph). Supplementary Material 2 provides a formal definition of density, and Supplementary Material 3 provides the pseudo-code for the graph generation algorithm.

This simplified model corresponds to the *collocateEnv* environment used earlier, where all agents may access any of the two resources at all time, but with interactions between agents being determined by the selected density. In this Section, we first explore what are the critical parameters and parameter values that makes specialization possible (Subsection 4.1). Then, we investigate whether the non-homogeneous availability of resources impacts (or not) the possibility to evolve specialization (Subsection 4.2).

### 4.1. Interaction between Reproductive Isolation, Population Size, and Selection Pressure

We identify three candidate hypotheses that, if true, may lead to the evolution of specialization:

**Figure 5** shows the results obtained with different tournament sizes (*k*= 1, 2, 3, 5, 10, 50), population size (100 and 500) and densities (starting from the minimal density wrt. population size). For each parameter sets, 160 independent runs are conducted (i.e., a total of 5760 runs). Results are compiled from the data of the last generation for each run and shown as violin plots to capture the details of possibly non-uniform distributions (i.e., full histograms, rather than box-plots).

All three hypotheses are validated, though their importance varies. Lower densities *always* lead to specialization, whatever the population size or the selection pressure. A large population size favors specialization, and selection favoring exploitation (i.e., larger tournament sizes) turns to be detrimental as density increases. Actually, the lack of detrimental effect of large tournament sizes when density is low can be explained that for the lowest densities considered, tournament sizes is quickly far superior to the actual number of neighbors (e.g., for the lowest densities, the number of neighbors for one node is 2) – in other words, tournament sizes with *k* > 2 do not impact further the outcome of selection for such low densities.

As a conclusion to our original question, reproductive isolation is a key factor for evolving specialization, with a larger population size and a selection scheme favoring exploration rather than exploitation as secondary factors. Results from this Section also shed light on the negative results obtained in Section 3: the failure of all algorithms to achieve specialization in the *collocateEnv* environment is explained by the lack of restrictions on mating opportunities (all individuals are mixed together).

### 4.2. Deleterious Effects of Non-Homogeneous Resources Availability

So far, we have considered situations where both resources provide the same *quantity* of energy. We now depart from our initial question to consider the possible impact of resources being available in different amounts. We use the same setup as in the previous Subsection, with only *k* = 1 as tournament size (i.e., the mEDEA algorithm), and consider two environments [termed *S*(75,25) and *S*(90,10)] with different resource distributions: one where *R*0 (vs. *R*1) provides 75% (vs. 25%) of the amount of energy required to sustain the whole population, and another where *R*<sup>0</sup> (vs. *R*1) provides 90% (vs. 10%) of the amount of energy.

Results are shown in **Figure 6**, compiled from 160 runs for each set of parameters (i.e., a total of 3200 runs). Specialization can be observed whenever a run displays more active agents that can be sustained with one resource only (cf. the *red* lines in the graphs, which mark the maximum level of sustainability by foraging only the largest resource). When the distribution of

FIGURE 7 | The level of specialization (at the end of evolution) within populations depending on the number of active agents. Results are similar to Figure 6 but display the average specialization level observed in runs, rather than the number of runs. For each cell (i.e., rectangle covering a small interval in the number of active agents), the level of specialization is calculated as the distance between the ideal distribution over the two resources and the observed distribution (averaged over all runs considered in this cell). Blue means no specialization (i.e., only one resource foraged); red means specialization (i.e., population is split in two groups, each with an optimal size wrt. resources availability). A detailed explanation of how specialization is computed can be found in Supplementary Material 4. Note that the two cells colored red which are below the threshold line in the upper-left graph are due to successful specialization but only within a sub-part of the population (i.e., some agents carry a *gskill* value around zero). It is important to keep in mind that cells may correspond to very different number of runs: this Figure provides *complementary information* to what is shown in Figure 6.

resources follows a 75/25 distribution, more than half of the runs with a population of 100 ends up with specialization, as well as *all* runs with a population of 500. Specialization is confirmed by looking at the middle column of **Figure 7**, which displays the same results as the previous, but over-emphasizes on the (possibly different) values of *gskill* rather than the number of runs. The distribution of the *gskill* gene values show that all runs that display a survival success to be high above the threshold (the red lines in the graphs) are explained by the occurrence of two groups of individuals, one specialized to forage *R*0 and the other to forage *R*1.

Results are different when resources follow a 90/10 distribution, as **Figure 6** displays a survival rate around the threshold for runs with a population size of 100 and slightly above for most runs with a population size of 500. A Wilcoxon rank-sum test confirms that using a population of 500 yields significantly better results than a population of 100. Again, **Figure 7** provides a more precise analysis. Runs with a population of 100 almost never display specialization while runs with a population of 500 and a high survival rate are always displaying specialization (the top red boxes in the bottom-right graph).

Heterogeneous distributions of resources do have a negative effect on the ability to evolve specialization, though it can be mitigated – to a limited extent – by increasing the population size. This poses yet another challenge about ensuring the evolution of specialization even with a small population and unbalanced distribution of resources availability.

### 5. CONCLUSION AND PERSPECTIVES

In this paper, we explored why evolving behavior specialization remains an important challenge in embodied evolutionary robotics. We defined a foraging task where two resources are available in limited quantity to identify the critical parameters at work in the evolution of specialization. We implemented this task in both a pseudo-realistic robotic simulation and an abstract graph-based model.

The take-home messages from this work are threefold. First, reproductive isolation is mandatory for the evolution of specialization, whether such isolation is due to geographic constraints or particular mating strategies. This may open ways toward defining new mechanisms and/or operators to reduce the amount of mating interactions between individuals, such as preferential choice.

Second, larger population sizes also help, leading toward an important remark: a significant amount of works in embodied evolutionary robotics are concerned with small populations (approximately 10 robots), and face problems that are possibly unique to such population sizes. To some extent, embodied evolution with either small or large populations may well be to two different classes of problems, each with their own issues, and we ought to be cautious not to generalize conclusions obtained with larger populations to smaller populations, and reciprocally.

Third, a selection method should leave room to exploration, to be understood as performing a trade-off between environment-driven selection versus task-driven fitness function selection. The benefit of such a trade-off has already been explored elsewhere (Haasdijk et al., 2014), but mechanisms favoring exploration explicitly could also be explored [e.g., applying novelty measures for evolutionary swarm robotics (Gomes et al., 2013)]. Here lies an important aspect of embodied evolution: mating is evolved as a strategy, and is not given for free as an algorithmic feature as would be the case with a more classic evolutionary algorithm.

As for future works, a natural extension of this work is to consider the evolution of specialization into more than two subgroups, as well as to consider behaviors that are substantially different. So far, we have considered specialization as being the product of few skills (ability to forage one resource, and possibly to track its location), which may imply a limited distance in the genotypic space between the two genetic codes. Things may be very different if two (or more) behaviors exist in very different locations of the search space: except for very specific historical contingencies or dedicated operators it might be very difficult to co-evolve both behaviors simultaneously.

Another extension of this work is to consider setups where both generalists and specialists can evolve. Even if a population of generalists may provide a suboptimal solution, it is not clear that specialists could still evolve, even when the conditions discussed throughout this paper are met. Finally, it is also not clear what would be the respective advantages and drawbacks to achieving behavioral specialization through evolutionary adaptation (as explored here) versus lifetime adaptation (e.g., learning or memory mechanisms).

### AUTHOR CONTRIBUTIONS

Conceived and designed the experiments: J-MM, SC, and NB. Analysed the data: J-MM, SC, and NB. Performed the experiments: J-MM and SC. Coordinated the writing: NB.

### ACKNOWLEDGMENTS

This work is supported by the European Unions Horizon 2020 research and innovation programme under grant agreement No 640891, and the ERC Advanced Grant EPNet (340828). Part of the experiments presented in this paper were carried out using the Grid'5000 experimental testbed, being developed under the INRIA ALADDIN development action with support from CNRS, RENATER, and several Universities as well as other funding bodies (see https://www.grid5000.fr). The other parts of the simulations have been done in the supercomputer MareNostrum at Barcelona Supercomputing Center – Centro Nacional de Supercomputacion (The Spanish National Supercomputing Center).

### SUPPLEMENTARY MATERIAL

The Supplementary Material for this article can be found online at http://journal.frontiersin.org/article/10.3389/frobt.2016.00038

### REFERENCES

**Conflict of Interest Statement:** The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

*Copyright © 2016 Montanier, Carrignon and Bredeche. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY). The use, distribution or reproduction in other forums is permitted, provided the original author(s) or licensor are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.*

# **Morphological Modularity Can Enable the Evolution of Robot Behavior to Scale Linearly with the Number of Environmental Features**

*Collin K. Cappelle<sup>1</sup> \*, Anton Bernatskiy <sup>1</sup> , Kenneth Livingston<sup>2</sup> , Nicholas Livingston<sup>3</sup> and Josh Bongard<sup>1</sup>*

*<sup>1</sup> Department of Computer Science, University of Vermont, Burlington, VT, USA, <sup>2</sup> Department of Cognitive Science, Vassar College, Poughkeepsie, NY, USA, <sup>3</sup> Robotics Laboratory, Vassar College, Poughkeepsie, NY, USA*

In evolutionary robotics, populations of robots are typically trained in simulation before one or more of them are instantiated as physical robots. However, in order to evolve robust behavior, each robot must be evaluated in multiple environments. If an environment is characterized by *f* free parameters, each of which can take one of *n<sup>p</sup>* features, each robot must be evaluated in all *n f <sup>p</sup>* environments to ensure robustness. Here, we show that if the robots are constrained to have modular morphologies and controllers, they only need to be evaluated in *n<sup>p</sup>* environments to reach the same level of robustness. This becomes possible because the robots evolve such that each module of the morphology allows the controller to independently recognize a familiar percept in the environment, and each percept corresponds to one of the environmental free parameters. When exposed to a new environment, the robot perceives it as a novel combination of familiar percepts which it can solve without requiring further training. A non-modular morphology and controller however perceives the same environment as a completely novel environment, requiring further training. This acceleration in evolvability – the rate of the evolution of adaptive and robust behavior – suggests that evolutionary robotics may become a scalable approach for automatically creating complex autonomous machines, if the evolution of neural and morphological modularity is taken into account.

**Keywords: evolutionary robotics, modularity, evolvability, evolutionary algorithms, embodied cognition**

### **1. INTRODUCTION**