A.L.: Progressive minimal criteria novelty search

Abstract. We propose progressive minimal criteria novelty search (PM-CNS), which is an extension of minimal criteria novelty search. In PM-CNS, we combine the respective benefits of novelty search and fitness-based evolution by letting novelty search freely explore new regions of behaviour space as long as the solutions meet a progressively stricter fitness criterion. We evaluate the performance of our approach in the evolution of neurocontrollers for a swarm of robots in a coordination task where robots must share a single charging station. The robots can only survive by periodically recharging their batteries. We compare the performance of PMCNS with (i) minimal criteria novelty search, (ii) pure novelty search, (iii) pure fitness-based evolution, and (iv) with evolution-ary search based on a linear blend of novelty and fitness. Our results show that PMCNS outperforms all four approaches. Finally, we analyse how different parameter setting in PMCNS influence the exploration of the behaviour space