Geodesics, Non-linearities and the Archive of Novelty Search
The Novelty Search (NS) algorithm was proposed more than a decade ago.
However, the mechanisms behind its empirical success are still not well
formalized/understood. This short note focuses on the effects of the archive on
exploration. Experimental evidence from a few application domains suggests that
archive-based NS performs in general better than when Novelty is solely
computed with respect to the population. An argument that is often encountered
in the literature is that the archive prevents exploration from backtracking or
cycling, i.e. from revisiting previously encountered areas in the behavior
space. We argue that this is not a complete or accurate explanation as
backtracking - beside often being desirable - can actually be enabled by the
archive. Through low-dimensional/analytical examples, we show that a key effect
of the archive is that it counterbalances the exploration biases that result,
among other factors, from the use of inadequate behavior metrics and the
non-linearities of the behavior mapping. Our observations seem to hint that
attributing a more active role to the archive in sampling can be beneficial.