Research Repository

Monte-Carlo Tree Search for the Physical Travelling Salesman Problem

Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte-Carlo Tree Search for the Physical Travelling Salesman Problem. In: UNSPECIFIED, ? - ?.

Full text not available from this repository.


The significant success of MCTS in recent years, particularly in the game Go, has led to the application of MCTS to numerous other domains. In an ongoing effort to better understand the performance of MCTS in open-ended real-time video games, we apply MCTS to the Physical Travelling Salesman Problem (PTSP). We discuss different approaches to tailor MCTS to this particular problem domain and subsequently identify and attempt to overcome some of the apparent shortcomings. Results show that suitable heuristics can boost the performance of MCTS significantly in this domain. However, visualisations of the search indicate that MCTS is currently seeking solutions in a rather greedy manner, and coercing it to balance short term and long term constraints for the PTSP remains an open problem. © 2012 Springer-Verlag.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Additional Information: Published proceedings: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
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: Elements
Depositing User: Elements
Date Deposited: 19 Oct 2012 22:03
Last Modified: 15 Jan 2022 00:45

Actions (login required)

View Item View Item