Robotics and Biology Laboratory

Entropy as an Organizing Principle for Selection in Evolutionary Robotics

People

Paulo Urbano

Joel Lehman

Oliver Brock

Thesis Description

In evolutionary computation, a goal-based objective function is typically unable to include the local challenges on the way towards its fulfillment and tends to to cause the search to converge prematurely. Therefore, this work proposes to use objectives that are defined by different aspects of an individuals interaction with the environment and a selection procedure able to reallocate search efforts in order to avoid convergence. The objectives, curiosity, novelty and evolvability, differ in the time-scale they operate over and the amount of information they include about the problem structure. The common theme of these objectives is their tendency to increase the diversity of behaviors, which is assumed can act as general-purpose utility value. The goal is to combine the benefits of the objectives by optimizing subsets of them simultaneously with a multi-objective EA. Entropy is used as unifying framework for modelling the objectives and determining which of their values are considered desirable. Using entropy for the latter part relies on the fact that degenerate behaviors are more pervasive in search spaces than functional ones. Thus, selecting for high-entropy values implicitly treats the frequency with which a behavior occurs as a heuristic of its interestingness, reallocating search efforts towards diversity. The performance of the different objectives and selection methods are evaluated by solving deceptive navigation tasks. Verified on a more challenging biped locomotion experiment, the new finding of this work is that entropy selection is as good or better than optimization. Concerning the individual objectives, these work’s results support previous findings that novelty is a very good indicator for selection and additionally show that it can be efficiently modelled with entropy. The method of modelling novelty with entropy is shown to be applicable to many, possibly higher dimensional and less informative behavioral characterizations simultaneously without a decrease in conceptual simplicity and computational efficiency, indicating how future research could explore more complex behavior spaces and problems.
Concerning the evolvability objective, which describes the capacity to produce diversity and generalization, this work investigates how it can be estimated from the many individuals discarded during search, in order to avoid the many extra evaluations necessary to calculate it precisely. Also, this work proposes how an elitist-multiobjective EAs could interpret evolvability as adaptive variation without referring to a specific task. Taken together, the negative results of both evolvability-estimations indicate that different behaviors might have different potentials for evolvability and should therefore not be compared on it globally.

Publications

Link to Thesis