Urbano, Paulo, and Henrique Vaz. “Using Fitness as Minimal Criteria for Novelty Search in the Maze Navigation Domain.”
URL1 URL2
The problem of deception is one of the biggest challenges for evolutionary robotics. Some fitness functions suffer from deception because they prevent the objective from being reached misguiding the search process towards local optima and poor solutions. A lot of techniques were introduced to overcome deception, mainly through the promotion of genotypic diversity. Recently, a radically different and counter-intuitive open-ended evolutionary approach called Novelty Search, which rewards behavioral phenotype novelty, was proposed with very successful results. The main idea is, paradoxically, to find what we want without explicitly looking for it. But as novelty search is guided by behavior novelty alone, its reliability can be greatly affected when searching through vast and unconstrained behavior spaces: it may spend most of its time exploring irrelevant behaviors with respect to the goal. To address this problem, different techniques were proposed, mostly of them reintroducing the fitness function. One of them is Progressive Minimal Criteria Novelty Search (PMCNS), which demonstrated promising results on a swarm robotics task. In PMCNS, novelty search freely explores new regions of behavior space as long as the solutions meet a progressively stricter fitness criterion. We have empirically evaluated PMCNS in a maze navigation simulated task, using a deceptive maze and an unclosed variation of it, representing respectively very deceptive problems with and without a vast behavior search space. In both mazes a simulated robot controlled by an evolved neural network, using NEAT, had to find a goal zone. The performance of PMCNS was compared with two other methods that were designed to prune the space of relevant behaviors: Minimal Criteria Novelty Search (MCNS) and Linear Scalarization of novelty and fitness (LS). MCNS was tested with domain dependent minimal criteria and also with a fixed fitness threshold in order to see if the progression and adaptation of the minimal criteria was necessary. We have also tested the performance of pure Novelty Search and the standard fitness based search. The experiments results showed that the use of a fitness threshold as the minimal criteria for constraining novelty search is a promising technique, specially in the unclosed deceptive maze with a large behavior space.