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: | Computer Science, Information & General Works Technology > Digital Works > Digital Games |
Courses by Department: | The Games Academy |
Depositing User: | Edward Powley |
Date Deposited: | 23 Jun 2017 10:57 |
Last Modified: | 08 Aug 2024 09:27 |
URI: | https://repository.falmouth.ac.uk/id/eprint/2259 |
Actions
View Item (login required) |