Perez, Diego and Powley, Edward J and Whitehouse, Daniel and Rohlfshagen, Philipp and Samothrakis, Spyridon and Cowling, Peter I and Lucas, Simon M (2014) Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions. IEEE Transactions on Computational Intelligence and AI in Games, 6 (1). pp. 31-45. DOI https://doi.org/10.1109/tciaig.2013.2263884
Perez, Diego and Powley, Edward J and Whitehouse, Daniel and Rohlfshagen, Philipp and Samothrakis, Spyridon and Cowling, Peter I and Lucas, Simon M (2014) Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions. IEEE Transactions on Computational Intelligence and AI in Games, 6 (1). pp. 31-45. DOI https://doi.org/10.1109/tciaig.2013.2263884
Perez, Diego and Powley, Edward J and Whitehouse, Daniel and Rohlfshagen, Philipp and Samothrakis, Spyridon and Cowling, Peter I and Lucas, Simon M (2014) Solving the Physical Traveling Salesman Problem: Tree Search and Macro Actions. IEEE Transactions on Computational Intelligence and AI in Games, 6 (1). pp. 31-45. DOI https://doi.org/10.1109/tciaig.2013.2263884
Abstract
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 |
---|---|
Uncontrolled Keywords: | Computational and artificial intelligence; game search; Monte Carlo tree search; real-time games; reinforcement learning |
Subjects: | Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
Divisions: | Faculty of Science and Health Faculty of Science and Health > Computer Science and Electronic Engineering, School of |
SWORD Depositor: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 06 Aug 2013 09:07 |
Last Modified: | 04 Dec 2024 06:37 |
URI: | http://repository.essex.ac.uk/id/eprint/7250 |
Available files
Filename: PTSP-TCIAIG-AuthorFinal.pdf