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

Perez, Diego, Powley, Edward ORCID: https://orcid.org/0000-0002-7317-7304, 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

Preview

Text Perez_TCIAIG_master.pdf Download (601kB) | Preview

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:	Computing & Data Science Computing & Data Science > Game Design
Courses by Department:	The Games Academy
Depositing User:	Edward Powley
Date Deposited:	23 Jun 2017 10:57
Last Modified:	18 Nov 2024 14:25
URI:	https://repository.falmouth.ac.uk/id/eprint/2259

View Record (staff only)