Finding
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.
Paper
Monte Carlo Tree Search: Long-term versus short-term planning
Citations: 11
Full text
Semantic ScholarAbstract
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.
Authors
Diego Perez Liebana, Philipp Rohlfshagen, S. Lucas
Journal
2012 IEEE Conference on Computational Intelligence and Games (CIG)