Solving the Physical Travelling Salesman Problem: tree search and macro-actions

Perez, Diego, Powley, Edward ORCID logoORCID:, Whitehouse, Daniel, Rohlfshagen, Philipp, Samothrakis, Spyridon, Cowling, Peter I and Lucas, Simon M (2014) Solving the Physical Travelling Salesman Problem: tree search and macro-actions. IEEE Transactions on Computational Intelligence and AI in Games, 6 (1). pp. 31-45. ISSN 1943-068X

[thumbnail of Perez_TCIAIG_master.pdf]

Download (601kB) | Preview
Official URL:

Abstract / Summary

This paper presents a number of approaches for solving a real-time game consisting of a ship that must visit a number of waypoints scattered around a two-dimensional maze full of obstacles. The game, the Physical Travelling Salesman Problem (PTSP), which featured in two IEEE conference competitions during 2012, provides a good balance between long-term planning (finding the optimal sequence of waypoints to visit), and short-term planning (driving the ship in the maze). This paper focuses on the algorithm that won both PTSP Competitions: it takes advantage of the physics of the game to calculate the optimal order of waypoints, and it employs Monte Carlo Tree Search (MCTS) to drive the ship. The algorithm uses repetitions of actions (macro-actions) to reduce the search space for navigation. Variations of this algorithm are presented and analysed, in order to understand the strength of each one of its constituents and to comprehend what makes such an approach the best controller found so far for the PTSP.

Item Type: Article
Identification Number: 10.1109/TCIAIG.2013.2263884
ISSN: 1943-068X
Subjects: Computer Science, Information & General Works
Technology > Digital Works > Digital Games
Courses by Department: The Games Academy > Computing for Games
Depositing User: Edward Powley
Date Deposited: 23 Jun 2017 10:57
Last Modified: 23 Nov 2023 13:46


View Item View Item (login required)