The Novelty Search method employs a novelty metric for tracking the uniqueness of the behavior of each new individual. That is, the novelty metric is a measure of how far the new organism is from the rest of the population in the behavior space. An effective novelty metric implementation should allow us to compute sparseness at any point of the behavior space. Any area with a denser cluster of visited points is less novel and produces less evolutionary rewards.
The most straightforward measure of sparseness at a point is an average distance to the k-nearest neighbors of that point in the behavior space. When this distance is high, the point of interest is in the sparse area. At the same time, the denser areas are marked by ...
