Automated Map Generation for the Physical Travelling Salesman Problem

This paper presents a method for generating complex problems that allow multiple non-obvious solutions for the Physical Travelling Salesman Problem (PTSP). PTSP is a single-player game adaptation of the classical Travelling Salesman Problem that makes use of a simple physics model: the player has to visit a number of waypoints as quickly as possible by navigating a ship in real time across an obstacle-filled two-dimensional map. The difficulty of this game depends on the distribution of waypoints and obstacles across the two-dimensional plane. Due to the physics of the game, the shortest route is not necessarily the fastest, as the ship’s momentum makes it difficult to turn sharply at speed. This paper proposes an evolutionary approach to obtaining maps where the optimal solution is not immediately obvious. In particular, any optimal route for these maps should differ distinctively from (a) the optimal distance-based TSP route and (b) the route that cor-responds to always approaching the nearest waypoint first. To achieve this, the evolutionary algorithm CMA-ES is employed, where maps, indirectly represented as vectors of real numbers, are evolved to differentiate maximally between a game-playing agent that follows two or more different routes. The results presented in this paper show that CMA-ES is able to generate maps that fulfil the desired conditions