The behavioral space of the maze solver agent is defined by its trajectory through the maze while running the maze-solving simulation. An effective novelty score implementation needs to compute the sparseness at any point in such a behavioral space. Thus, any area with a denser cluster of visited points of behavior space is less novel, giving fewer rewards to the solver agent.
As mentioned in Chapter 1, Overview of Neuroevolution Methods, the most straightforward measure of sparseness at a point is the average distance from it to the k-nearest neighbors. The sparse areas have higher distance values, and the denser areas have lower distance values, correspondingly. The following formula gives the sparseness at point of the ...
