PaperlayerView exact revision on arXiv

Source-linked AI summary

Evolution of Swarm Robotics Systems with Novelty Search

Jorge Gomes, Paulo Urbano, Anders Lyhne Christensen

arXiv:1304.3362v1cs.NE

TL;DR

Fitness-guided evolution can be misled by deceptive objectives, a concern for complex swarm robotics tasks. This paper applies novelty search with NEAT to simulated swarm controllers and compares it with fitness-based evolution. Novelty search performs well across the studied tasks, while hybrid variants guide exploration toward higher-fitness behavior without reducing solution diversity.

  • Problem

    Fitness-based evolution can be misled by deceptive objectives, while configuring evolution to synthesize adequate solutions efficiently is difficult for complex robotic tasks.

    Source: §1 · p. 2

  • Method

    The study applies novelty search with NEAT to neural controllers for swarm aggregation and charging-station sharing, using swarm-level behavior characterizations and testing hybrids with fitness-based evolution.

    Source: §1 · pp. 2–3, §5.1 · p. 25

  • Results

    Novelty search was unaffected by deception and outperformed fitness-based evolution in the deceptive resource-sharing task; across both tasks it bootstrapped evolution and found successful solutions with lower neural-network complexity.

    Source: §6 · p. 29

  • Takeaways & Limitations

    Novelty search is a promising alternative for evolving swarm controllers, and PMCNS and linear scalarization can guide exploration toward higher fitness while preserving solution diversity.

    Source: §6 · pp. 29–30

    Macroscopic behavior characterizations must use task-relevant components with manageable differences in how easily their behavior-space dimensions can be explored.

    Source: §6.1 · p. 30

Abstract

from arXiv · show

Novelty search is a recent artificial evolution technique that challenges traditional evolutionary approaches. In novelty search, solutions are rewarded based on their novelty, rather than their quality with respect to a predefined objective. The lack of a predefined objective precludes premature convergence caused by a deceptive fitness function. In this paper, we apply novelty search combined with NEAT to the evolution of neural controllers for homogeneous swarms of robots. Our empirical study is conducted in simulation, and we use a common swarm robotics task - aggregation, and a more challenging task - sharing of an energy recharging station. Our results show that novelty search is unaffected by deception, is notably effective in bootstrapping the evolution, can find solutions with lower complexity than fitness-based evolution, and can find a broad diversity of solutions for the same task. Even in non-deceptive setups, novelty search achieves solution qualities similar to those obtained in traditional fitness-based evolution. Our study also encompasses variants of novelty search that work in concert with fitness-based evolution to combine the exploratory character of novelty search with the exploitatory character of objective-based evolution. We show that these variants can further improve the performance of novelty search. Overall, our study shows that novelty search is a promising alternative for the evolution of controllers for robotic swarms.

1 Introduction

Designing swarm controllers by hand is difficult, and fitness-guided evolution can be misled by deceptive objectives. This study tests novelty search for swarm robotics, comparing it with fitness-based evolution across two tasks and exploring behavior characterizations and hybrid methods.

1 Introduction

  • Swarm dynamics make hand-design difficult, while fitness functions can misguide evolution toward local optima, especially as task or system complexity increases.Novelty search instead rewards behavioral difference from previously evaluated solutions, without a static objective.Source: §1 · p. 2
  • The paper positions novelty search as an alternative for evolving neural controllers in complex swarm systems, where deceptive fitness landscapes may arise.The study evaluates that application empirically across multiple swarm tasks.Source: §1 · p. 2
  • The study compares novelty search with fitness-based evolution on aggregation and the more challenging task of sharing a charging station through periodic, exclusive access.Its behavior characterizations capture macroscopic swarm behavior independently of swarm size; the resource-sharing study also tests whether whole-simulation summaries suffice.Source: §1 · p. 3
  • The paper also explores progressive minimal criteria novelty search and linear scalarization to combine novelty's exploration with fitness-based evolution's exploitation.These variants address the possibility that novelty search spends substantial effort in novel but unfruitful behavioral regions.Source: §1 · p. 3

2 Related Work

This section introduces swarm robotics and evolutionary robotics challenges, then presents novelty search, its variants, and NEAT. It contrasts behavior-based exploration with fitness guidance and describes how the methods combine in the study.

2.1 Swarm Robotics

  • Self-organization makes swarm systems useful for decentralized coordination, but manually deriving individual rules for a desired collective behavior is difficult and lacks a general method.Designers typically draw on biological examples or manual trial and error.Source: §2.1 · p. 4

2.2 Evolutionary Robotics

  • Evolutionary robotics can synthesize robotic systems through iterative evaluation, but deceptive fitness gradients and weak early selective pressure can stall evolution.Genotypic diversity and coevolution are among proposed responses, but fitness misdirection can persist and task decomposition may require substantial prior knowledge.Source: §2.2 · pp. 4–5

2.3 Novelty Search

  • Novelty search rewards behaviorally different solutions using an archive and a novelty metric based on average distance to k-nearest neighbors.Sparse regions receive higher scores, promoting behavioral diversity; characterizations that are too detailed or inadequate can respectively explore irrelevant regions or conflate distinct behaviors.Source: §2.3 · p. 6
  • Novelty search does not require a fitness gradient, but its behavior characterization still requires selecting task-relevant features.An excessively detailed characterization can enlarge the search space, while inadequate characterizations can conflate behaviors.Source: §2.3 · p. 6

2.4 Novelty Search Variants

  • Novelty-search variants combine exploration with fitness guidance; PMCNS progressively tightens fitness criteria, while linear scalarization combines novelty and fitness scores.MCNS requires domain-dependent criteria and can restrict search, motivating PMCNS's dynamic threshold; prior work also reports linear scalarization outperforming both pure novelty search and fitness-based evolution on a deceptive box-pushing task.Source: §2.4 · p. 7

2.5 NEAT

  • NEAT evolves neural-network weights and topology from small networks, using historical markings and speciation to protect structural innovations while networks complexify.NEAT maintains genotypic diversity, complementing novelty search's phenotypic diversity.Source: §2.5 · p. 8

3 Evolution of Aggregation Behaviours with Novelty Search

The aggregation experiments compare novelty search with fitness-based and random evolution on a task in which a dispersed swarm must form one cluster. The setup makes aggregation harder than earlier studies by limiting sensing and enlarging the arena.

3 Evolution of Aggregation Behaviours with Novelty Search

  • The aggregation task requires a dispersed swarm to form a single cluster, and experiments compare three behavior characterizations under novelty search with fitness-based and random-evolution baselines.Random evolution assigns individuals random fitness scores.Source: §3 · p. 8
  • Prior aggregation studies used directional sound sensing that let robots follow signals toward groups; earlier work also reported evolved behaviors converging to one behavioral class per run.Other prior work distinguished static compact clusters from loose, moving clusters.Source: §3 · pp. 8–9
  • Unlike earlier aggregation setups, these robots use no sound, have shorter sensing range, and operate in a larger arena.The changes mean robots can sense one another only at close range and may require different aggregation strategies.Source: §3 · p. 9

3.1 Experimental Setup

The experiments use simulated homogeneous swarms of seven robots in a bounded arena, with sensor-driven neural controllers. Controllers are evaluated across randomized initial conditions and repeated simulations.

3.1 Experimental Setup

  • Simulations use a 3 m square arena and a homogeneous swarm of seven e-puck-inspired robots, each 8 cm in diameter with a maximum speed of 12 cm/s.Robots have obstacle sensors with a 10 cm range and robot-detection sensors with a 25 cm range; a count sensor reports nearby robots relative to the desired cluster size.Source: §3.1 · p. 9
  • Each controller is evaluated 10 times with randomized robot positions and orientations, with initial placements at least 50 cm apart.Each simulation lasts 2,500 steps, or 250 seconds.Source: §3.1 · pp. 9–10
  • The best individual of each generation is post-evaluated in 100 simulations to obtain a more accurate fitness estimate.The implementation uses the Simbad 3D robot simulator and NEAT4J.Source: §3.1 · pp. 9–10

3.2 Configuration of the Evolutionary Algorithms

The evolutionary comparisons used NEAT-based fitness, random, and novelty search, with novelty characterized by sampled spatial relationships among robots. The study combined average-distance and cluster-count descriptors and evaluated controllers across repeated simulations.

3.2 Configuration of the Evolutionary Algorithms

  • All algorithms used NEAT settings of 25% crossover, 10% mutation, population 200, recurrent links, and 250 generations.Fitness-based and random evolution used the default NEAT4J implementation; random evolution assigned random fitness scores.Source: §3.2 · p. 10
  • Novelty search used k = 15 nearest neighbours and stochastic archive additions with a 2% probability.Its implementation followed the description and parameters in Lehman and Stanley (2011a), with archive probability suggested by Lehman and Stanley (2010b).Source: §3.2 · p. 10
  • Behaviour characterisations sampled spatial inter-robot relationships every 5 seconds, tracking average distance to the swarm centre of mass or robot-cluster count.Robots were in the same cluster when separated by less than their 25 cm sensor range.Source: §3.2 · p. 10
  • The combined bcmcl descriptor concatenated bcm and bcl, whose components contributed approximately equally to novelty.Descriptors had lengths 50 for bcm and bcl and 100 for bcmcl; each controller’s final vector was the element-wise mean across 10 simulations.Source: §3.2 · pp. 10–11

3.3 Performance Comparison

In aggregation, novelty search with bcmcl reached highest fitness scores comparable to fitness-based evolution, despite the task’s non-deceptive fitness function. Novelty variants also outperformed fitness-based evolution early in the search.

3.3 Performance Comparison

  • Novelty search with bcmcl achieved highest fitness scores not significantly different from fitness-based evolution, while bcl scores were significantly lower.The study describes aggregation as non-deceptive because fitness-based evolution typically converged to the most effective strategy, yet novelty search attained comparable scores.Source: §3.3 · pp. 11–12, Figure 1 · p. 12
  • From around generations 5–40, all novelty search variants achieved significantly higher fitness scores than fitness-based evolution (p-value < 0.01).Fitness trajectories show the average highest fitness found so far across 30 independent runs per method.Source: §3.3 · p. 11, Figure 1 · p. 12
  • Novelty search could consistently find relatively high-scoring solutions across all three behaviour characterisations.Novelty search does not follow a fitness gradient, so its best solutions were not necessarily found in the final generation.Source: §3.3 · p. 11

3.4 Behavioural Diversity

The behavioural-diversity analysis shows that novelty search explores more broadly than fitness-based evolution, which is biased by its fitness gradient. Different behaviour characterisations produce different behaviours, while combining them can modestly improve fitness without harming search effectiveness.

3.4.1 Centre of mass behaviour characterisation

  • Novelty search explored behaviour regions more uniformly than fitness-based evolution, which avoided behaviours where average distance to the centre of mass rises.The maps show explored regions, with regions c to g marking higher fitness scores.Source: §3.4.1 · pp. 12–13, Figure 2 · p. 13
  • Fitness-based evolution spends time at a local maximum without aggregation dynamics, while novelty search explores aggregation and dispersion behaviours and can discover better solutions faster.The average initial distance to the centre of mass lies in the middle of the spectrum, so novel behaviours can include either aggregation or dispersion.Source: §3.4.1 · p. 14
  • Novelty search with bcm often evolved wall-exploiting aggregation behaviours, including robots that form loose central clusters or clusters near walls.Fitness-based evolution’s fitness gradient disfavors wall navigation, although wall-following can provide a stepping stone to aggregation.Source: §3.4.1 · pp. 14–15

3.4.2 Number of clusters behaviour characterisation

  • Novelty search with bcl produced flocking behaviours distinct from bcm, while conflation can cause distinct observable behaviours to be treated as non-novel and disappear.With bcm, clustering degree is irrelevant to the characterization; with bcl, distances between robots and clusters are irrelevant.Source: §3.4.2 · pp. 15–16, Figure 5 · p. 16

3.4.3 Combined behaviour characterisation

  • p-value < 0.05: novelty search with bcmcl achieved marginally higher fitness than bcm and bcl, and combining the related characterisations reduced conflation without harming search effectiveness.The combined characterization considers both average distance to the centre of mass and number of clusters; those measures are related because many clusters imply a scattered swarm and higher average distance.Source: §3.4.3 · pp. 16–17

3.5 Neural Network Complexity

At the same fitness levels, novelty search found less complex neural networks than fitness-based evolution, with the difference especially pronounced at lower fitness levels.

3.5 Neural Network Complexity

  • Novelty search found significantly less complex neural networks than fitness-based evolution at the same fitness levels, especially at lower fitness levels.Complexity is the sum of neurons and connections; the comparison uses the least complex solution above each fitness threshold, averaged across runs.Source: §3.5 · p. 17, Table 2 · p. 17

4 Evolution of Resource Sharing Behaviours with Novelty Search

The resource-sharing task requires five homogeneous robots to coordinate access to a single charging station so all can survive. The experiments compare novelty search with fitness-based evolution using two whole-simulation behavior characterisations.

4.1 Experimental Setup

  • Five robots must find and share a single-robot charging station in a 3 m by 3 m arena; each controller is tested from randomized starts.Robots have obstacle, robot, and charging-station sensors, plus recharge-state and energy sensors; each simulation lasts 2,500 steps.Source: §4 · p. 18, §4.1 · pp. 18–19, Figure 6 · p. 18

4.2 Configuration of the Evolutionary Algorithms

  • Evolutionary runs continued through generation 400 because resource sharing was more challenging than aggregation.Randomly generating a solution with at least one survivor in any of 10 trials was empirically estimated at approximately 1%.Source: §4.2 · p. 19
  • The fitness function combines end-of-simulation survivors with average robot energy, whose term distinguishes solutions with equal survivor counts.The authors included average energy to provide a fitness gradient when the initial population is unlikely to contain solutions with a surviving robot.Source: §4.2 · p. 19
  • The simple characterisation, bsimple, uses normalized survivor count and average energy among alive robots as its two behavior features.Resource-sharing characterisations summarize each simulation, rather than sampling spatial relationships over time as in the aggregation task.Source: §4.2 · p. 19
  • The extra characterisation, bextra, extends bsimple with normalized average speed and average distance to the charging station.These additional features are not directly related to the fitness function.Source: §4.2 · p. 20

4.3 Performance Comparison

In the resource-sharing task, novelty search with bsimple achieved stronger fitness results than fitness-based evolution, while bextra performed less well. The section also contrasts the behavior patterns and exploration trade-offs associated with these methods.

4.3 Performance Comparison

  • Novelty search with bsimple significantly outperformed fitness-based evolution (p-value < 0.01) and consistently neared maximum fitness by generation 400; bextra scored significantly lower (p-value < 0.01).At generation 400, NS-extra and fitness-based evolution did not appear stable and might improve with more generations.Source: Figure 7 · p. 20, §4.3 · p. 21

4.4 Behavioural Diversity

  • High-scoring solutions from all methods first searched for the station, then coordinated access using charge-and-go-away, charge-and-surround, or charge-and-wait behaviors.Figure 8 shows robot trajectories for the highest-scoring solutions.Source: §4.4 · p. 21, Figure 8 · p. 22

4.4.1 Fitness-based evolution

  • Fitness-based evolution failed to find viable solutions in 10/30 runs, with local maxima including one robot monopolizing the station or robots conserving energy while remaining nearly static.These patterns could take many generations to escape, or evolution might not escape at all.Source: §4.4.1 · pp. 21–22

4.4.2 Simple behaviour characterisation

  • Novelty search with bsimple explored greater behavioral diversity than fitness-based evolution, including distinct energy-threshold variations that can look similar in trajectory inspection.Figure 9 maps individuals by average energy and survivor count; darker zones indicate more individuals.Source: §4.4.2 · p. 22, Figure 9 · p. 23

4.4.3 Extra behaviour characterisation

  • With bextra, novelty search explored varied average energy, movement, and station distance, but rarely explored behaviors with many survivors.Only one mapped region included behaviors in which the whole swarm often survived, and it was among the least explored; the larger, less-correlated behavior space helps explain the lower performance.Source: Figure 10 · p. 23, §4.4.3 · p. 23
  • The fitness-aligned bsimple characterisation improved high-fitness search but conflated behaviors differing in speed, making charge-and-wait less common than with bextra.The authors advise against including behavior dimensions that novelty search may explore at the expense of dimensions more crucial to the task.Source: §4.4.3 · p. 24

4.5 Neural Network Complexity

For resource sharing, novelty search with bsimple found significantly less complex neural networks than fitness-based evolution at fitness levels above 0.2.

4.5 Neural Network Complexity

  • Above fitness 0.2, novelty search with bsimple evolved significantly lower-complexity networks than fitness-based evolution (Mann–Whitney U test, p-value < 0.05).Initial networks had complexity 107, comprising 29 neurons and 78 links.Source: §4.5 · p. 24

5 Combining Novelty and Fitness

Because novelty search can explore novel but low-fitness regions, this section tests two ways of combining it with fitness-based evolution in resource sharing. Both methods improve on pure novelty search with bextra while retaining broad behavioural coverage.

5 Combining Novelty and Fitness

  • The study combines novelty and fitness because novelty search can miss high-fitness regions, while fitness-based evolution exploits existing high-fitness solutions.It compares PMCNS and linear scalarization against both pure novelty search and fitness-based evolution on resource sharing.Source: §5 · pp. 24–25

5.1 Progressive Minimal Criteria Novelty Search

  • PMCNS uses a progressively rising fitness threshold as a minimal criterion, narrowing exploration without requiring fixed domain-dependent criteria.The criterion starts at the theoretical minimum, uses a population fitness percentile, and only increases; P sets its stringency and S smooths adaptation.Source: §5.1 · pp. 25–26

5.2 Linear Scalarization of Novelty and Fitness Scores

  • Linear scalarization combines normalized novelty and fitness scores, with ρ setting their relative weight.The experimenter specifies ρ, typically through trial and error.Source: §5.2 · p. 26

5.3 Experimental Setup

  • Experiments reused the resource-sharing setup and tested both bsimple and bextra; PMCNS used P = 0.50 and S = 0.25, while scalarization used ρ = 0.75.That scalarization setting assigns 75% weight to novelty and 25% to fitness; the behaviour characterisations differ in dimensionality.Source: §5.3 · p. 26, §5.4 · p. 27

5.4 Results

  • p-value < 0.01: with bextra, PMCNS and linear scalarization outperform pure novelty search; with bsimple, they achieve similar fitness scores.The comparison covers both novelty-search variants and fitness-based evolution in the resource-sharing task.Source: Figure 11 · p. 27, §5.4 · p. 27
  • PMCNS and linear scalarization focus exploration more on high-fitness behaviours while retaining the broad behaviour range found by pure novelty search.The methods explore low-fitness behaviours less and high-fitness behaviours more; the accompanying maps show behaviour-space occupancy for bsimple and bextra.Source: Figure 12 · p. 28, Figure 13 · p. 28, §5.4 · p. 28

6 Conclusions

Across aggregation and resource sharing, novelty search matched fitness-based evolution on the non-deceptive task and outperformed it on the deceptive one. The conclusions also identify characterization design as a condition for effective search and discuss future directions for combining novelty with fitness.

6 Conclusions

  • In aggregation, novelty search achieved fitness scores similar to fitness-based evolution; in deceptive resource sharing, it was unaffected by deception and performed significantly better.The authors also report that novelty search found high-fitness behaviours early and successful solutions with lower neural-network complexity in both tasks.Source: §6 · p. 29
  • The study’s behaviour characterisations were swarm-size independent, but combined features were effective only when task-relevant.Search can spend effort in unfruitful regions when easier-to-explore dimensions are unrelated to the task.Source: §6 · p. 29
  • Novelty search with PMCNS or linear scalarization guided exploration toward higher-fitness behaviours without reducing the broad diversity of solutions.These variants were studied because novelty search may miss high-fitness solutions when behaviour-space dimensions are unrelated or weakly related to the objective.Source: §6 · p. 29
  • The authors conclude novelty search is a promising swarm-controller alternative, citing diverse successful self-organised behaviours, less-pronounced bootstrapping issues, and less-complex networks.They note these properties in contrast with fitness-based evolution.Source: §6 · pp. 29–30

6.1 Future work

  • Macroscopic characterisations need task-relevant components with dimensions that are not too unequal in ease of exploration, criteria that may be difficult to ensure.The authors are studying manual or automatic component weights to encourage exploration of important dimensions.Source: §6.1 · p. 30
  • Future directions include dynamic scalarization weights to shift exploration versus exploitation and generic novelty measures for swarm robotics.Generic measures may create vast behaviour spaces only weakly related to the objective.Source: §6.1 · p. 30
Loading 1304.3362v1…