Research Repository

Solving the physical traveling salesman problem: Tree search and macro actions

Perez, D and Powley, EJ and Whitehouse, D and Rohlfshagen, P and Samothrakis, S and Cowling, PI and Lucas, SM (2014) 'Solving the physical traveling salesman problem: Tree search and macro actions.' IEEE Transactions on Computational Intelligence and AI in Games, 6 (1). 31 - 45. ISSN 1943-068X

PTSP-TCIAIG-AuthorFinal.pdf - Accepted Version

Download (1MB) | Preview


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 2-D maze full of obstacles. The game, the Physical Traveling 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 analyzed, 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. © 2009-2012 IEEE.

Item Type: Article
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health > Computer Science and Electronic Engineering, School of
Depositing User: Jim Jamieson
Date Deposited: 06 Aug 2013 09:07
Last Modified: 23 Jan 2019 02:15

Actions (login required)

View Item View Item