Travelling SalesMan Problem using Monte Carlo Simulation

A project made by Mallis Dimitris for Democritus University of Thrace under the coarse Artificial Intelligent


The travelling Salesman project description is: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city ? The TSP problem is one of the most important problems of theoretical computer Sience and also NP-hard. In this project we solve this problem using Monte Carlo Tree Search.

Monte Carlo Tree Search (MCTS) is a method for making optimal decisions in artificial intelligence (AI) problems, typically move planning in combinatorial games. It combines the generality of random simulation with the precision of tree search.



Basic Algorithm

The basic MCTS algorithm is simple: a search tree is built, node by node, according to the outcomes of simulated playouts

A. Selection

Starting at root node R, recursively select optimal child nodes (explained below) until a leaf node L is reached.

B. Expansion

If L is a not a terminal node (i.e. it does not end the game) then create one or more child nodes and select one C.

C. Simulation

Run a simulated playout from C until a result is achieved.

D. Backpropagation

Update the current move sequence with the simulation result.



Node Selection


UCB

Node selection during tree descent is achieved by choosing the node that maximises the following quantity. In this project we used the Upper Confidence Bounds (UCB) formula.

      

The UCB formula balances betweetn exploitation of known rewards with and exploration of relatively unvisited nodes.The reward estimation is based on random simulations, and for this estimations to be aqurate nodes must be visited many times. MCTS is typically unreliable at the start of the tree search but converge to more reliable estimates given sufficient time and perfect estimates given infinite time.

One of the advantages of is that it does not require any strategic or tactical knowledge about the given domain. The algorithm can function effectively with no knowledge of a game apart from its legal moves and end conditions. This means that a MCTS can be used for many games with little modification, and makes MCTS a usefull algorithm for general game playing.

MCTS performs asymmetric tree growth that adapts to the topology of the search space. The algorithm visits more interesting nodes more often, and focusses its search time in more relevant parts of the tree.


TSP solution for 100 cities:


ScreenShot of the software created for the project:

This software gives to the user the ability to solve a TSP instance that he creates manually by placing markers on the map. The user can choose different values for the C coefficient and also different policies for child selection. It can also give a visual representation of the tree graph created in each step of the algorithm.


You can download the project source code in c# code here.

You can download the project the executable here.

You can download the documentation here.