The geometry of Tartarus fitness cases

Abstract

Tartarus is a standard AI task for grid robots in which boxes must be moved to the walls of a virtual world. There are 320, 320 fitness cases for the standard Tartarus task of which 297, 040 are valid according to the original statement of the problem. This paper studies different schemes for allocating fitness trials for Tartarus using an agent-based metric on the fitness cases to aid in the design process. This agent-based metric is a tool that permits exploration of the geometry of the space of fitness cases. The information gained from this exploration demonstrates why a scheme designed to yield a superior set of training cases in fact yielded an inferior one. The information gained also suggests a new scheme for allocating fitness trials that decreases the number of trials required to achieve a given fitness of the best agent. This scheme achieves similar fitness to a standard evolutionary algorithm using fewer fitness cases. The space of fitness cases for Tartarus is found, relative to the agent-based metric, to form a hollow sphere with a non-uniform distribution of the fitness cases within the space. The tools developed in this study include a generalizable technique for placing an agent-based metric space structure on the fitness cases of any problem that has multiple fitness cases. This metric space structure can be used to better understand the distribution of fitness cases and so design more effective evolutionary algorithms.