Adaptive Evolution of Finite State Machines for the Tartarus Problem

Abstract

Genetic algorithms can be used to evolve finite state machines for problems that require a large number of states and transitions. Tartarus problem is such a problem in which the purpose is to push the boxes towards the walls of a six by six grid using a bulldozer that can only sense its 8-neighbourhood. The bulldozer can rotate left, right, or move forward, each taking a single move out of its initial 80 moves. The result is scored by the number of boxes that are against a wall when the bulldozer is out of moves. Several approaches have been proposed, with genetic algorithms being the most common. We are proposing a representation of the problem using varying number of states and adaptive modification of the mutation parameter to decrease the probability of the population getting stuck at a local minima. Our results show improvement over the application of the genetic algorithm without parameter modification and dependency on the number states and the size of the population. © 2019 IEEE.