Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte-Carlo Tree Search for the Physical Travelling Salesman Problem. In: UNSPECIFIED, ? - ?.
Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte-Carlo Tree Search for the Physical Travelling Salesman Problem. In: UNSPECIFIED, ? - ?.
Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte-Carlo Tree Search for the Physical Travelling Salesman Problem. In: UNSPECIFIED, ? - ?.
Abstract
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: | Unnamed user with email elements@essex.ac.uk |
Depositing User: | Unnamed user with email elements@essex.ac.uk |
Date Deposited: | 19 Oct 2012 22:03 |
Last Modified: | 16 May 2024 17:10 |
URI: | http://repository.essex.ac.uk/id/eprint/4118 |