Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte Carlo Tree Search: Long-term versus short-term planning. In: 2012 IEEE Conference on Computational Intelligence and Games (CIG), 2012-09-11 - 2012-09-14.
Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte Carlo Tree Search: Long-term versus short-term planning. In: 2012 IEEE Conference on Computational Intelligence and Games (CIG), 2012-09-11 - 2012-09-14.
Perez, Diego and Rohlfshagen, Philipp and Lucas, Simon M (2012) Monte Carlo Tree Search: Long-term versus short-term planning. In: 2012 IEEE Conference on Computational Intelligence and Games (CIG), 2012-09-11 - 2012-09-14.
Abstract
In this paper we investigate the use of Monte Carlo Tree Search (MCTS) on the Physical Travelling Salesman Problem (PTSP), a real-time game where the player navigates a ship across a map full of obstacles in order to visit a series of waypoints as quickly as possible. In particular, we assess the algorithm's ability to plan ahead and subsequently solve the two major constituents of the PTSP: the order of waypoints (long-term planning) and driving the ship (short-term planning). We show that MCTS can provide better results when these problems are treated separately: the optimal order of cities is found using Branch & Bound and the ship is navigated to collect the waypoints using MCTS. We also demonstrate that the physics of the PTSP game impose a challenge regarding the optimal order of cities and propose a solution that obtains better results than following the TSP route of minimum Euclidean distance. © 2012 IEEE.
Item Type: | Conference or Workshop Item (Paper) |
---|---|
Additional Information: | Published proceedings: 2012 IEEE Conference on Computational Intelligence and Games, CIG 2012 |
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:58 |
Last Modified: | 05 Dec 2024 21:45 |
URI: | http://repository.essex.ac.uk/id/eprint/4127 |