  Behavior domination is proposed as a tool for understanding and harnessing
the power of evolutionary systems to discover and exploit useful stepping
stones. Novelty search has shown promise in overcoming deception by collecting
diverse stepping stones, and several algorithms have been proposed that combine
novelty with a more traditional fitness measure to refocus search and help
novelty search scale to more complex domains. However, combinations of novelty
and fitness do not necessarily preserve the stepping stone discovery that
novelty search affords. In several existing methods, competition between
solutions can lead to an unintended loss of diversity. Behavior domination
defines a class of algorithms that avoid this problem, while inheriting
theoretical guarantees from multiobjective optimization. Several existing
algorithms are shown to be in this class, and a new algorithm is introduced
based on fast non-dominated sorting. Experimental results show that this
algorithm outperforms existing approaches in domains that contain useful
stepping stones, and its advantage is sustained with scale. The conclusion is
that behavior domination can help illuminate the complex dynamics of
behavior-driven search, and can thus lead to the design of more scalable and
robust algorithms.
