Abstract
The Tartarus problem is a benchmark problem for non-Markovian decision making. In order to achieve high fitness, individuals must make efficient use of internal state. Finite-state machines are an ideal candidate for exploring the Tartarus problem, and there are several examples from previous work that use a finite-state approach. However, the input space of the Tartarus problem is quite large, so these approaches typically augment the internal states of the finite-state machine with methods to compress the large input space into one of lower dimension. Therefore, the behaviour of a finite-state machine representation that manipulates rules for every possible input is unknown. This paper explores a finite-state machine that manages all 6561 inputs of the Tartarus problem without requiring input space transformation. Far from being ineffective, the results suggest that the evolved FSMs are able to achieve a high level of fitness in a reasonable time frame. Through analysis of the turn-back behaviour of individuals, a simple heuristic is introduced into the representation that further improves fitness.