Description of the Lab

In this Lab, we increase the difficulty once more by introducing multiple pieces of cheese in the maze.

The goal of the Lab is to program an exhaustive search of possible paths that go through all pieces of cheese, in order to find the solution to the traveling salesman problem. Then, we improve this exhaustive search using an optimization called backtracking.

The traveling salesman problem

Set up the environment

Let’s create a new PyRat program. To do so, please copy template.py into a new file tsp_1.py.

Now, let’s setup the maze configuration a bit. Here, we are going to work with a single character, in a 15×11 maze, with some mud and multiple pieces of cheese. As before, we will show the trace so that we can check afterward if the character indeed took the shortest path.

#################################################################################################################
###################################################### GO ! #####################################################
#################################################################################################################

if __name__ == "__main__":

    # Map the functions to the character
    players = [{"name": "TSP 1", "preprocessing_function": preprocessing, "turn_function": turn}]

    # Customize the game elements
    config = {"maze_width": 15,
              "maze_height": 11,
              "mud_percentage": 40.0,
              "nb_cheese": 8,
              "trace_length": 1000}

    # Start the game
    game = PyRat(players, **config)
    stats = game.start()

    # Show statistics
    print(stats)

#################################################################################################################
#################################################################################################################

Generate the meta-graph

As studied in the Episode, the traveling salesman problem requires a complete graph to work. We are going to build such a graph, that abstracts some locations in the maze (we call it the meta-graph).

You should write a function that returns a complete graph, in which vertices represent the locations of the pieces of cheese and the starting position, and of which edges are weighted by the lengths of the shortest paths connecting these vertices.

Note: You should also store these shortest paths somewhere in order to move in the maze from a vertex of the meta-graph to another one.

def graph_to_metagraph ( graph:    Union[numpy.ndarray, Dict[int, Dict[int, int]]],
                         vertices: List[int]
                       ) ->        Tuple[numpy.ndarray, Dict[int, Dict[int, Union[None, int]]]]:

    """
        Function to build a complete graph out of locations of interest in a given graph.
        In:
            * graph:    Graph containing the vertices of interest.
            * vertices: Vertices to use in the complete graph.
        Out:
            * complete_graph: Complete graph of the vertices of interest.
            * routing_tables: Dictionary of routing tables obtained by traversals used to build the complete graph.
    """
    
    # TODO: Fill here

Help: You probably have understood already that building the meta-graph requires the use of Dijkstra’s algorithm. However, if you are still struggling with it, you can still progress on the TSP by changing the maze parameters to remove the mud. In that case, you should be able to build the meta-graph using the BFS algorithm instead.

Now, we are going to write a function that iterates over all possible orders of pieces of cheese to find the one associated to the shortest path.

An easy way to perform an exhaustive search is to see it as an adaptation of a depth-first search algorithm. While a DFS explores the graph until each vertex is visited once and for all (which corresponds to a single permutation of all vertices of the meta-graph), an exhaustive search wants each vertex to be visited once within each possible branch of the solutions tree. Here is a possible implementation of a recursive depth-first search algorithm to use as a basis for your exhaustive search.

def dfs_recursive ( source: int,
                    graph:  Union[numpy.ndarray, Dict[int, Dict[int, int]]]
                  ) ->      Tuple[Dict[int, int], Dict[int, Union[None, int]]]:

    """
        This is a recursive implementation of the DFS.
        At each call, we check if we are done with the traversal, and then we explore unexplored neighbors.
        This implementation stops when the spanning tree is done, i.e. when all vertices have been explored once.
        In:
            * source: Vertex from which to start the traversal.
            * graph:  Graph on which to perform the traversal.
        Out:
            * distances_to_explored_vertices: Dictionary where keys are explored vertices and associated values are the lengths of the paths to reach them.
            * routing_table:                  Routing table to allow reconstructing the paths obtained by the traversal.
    """
    
    # We will fill these variables during the traversal
    routing_table = {source: None}
    distances_to_explored_vertices = {source: 0}
    
    # Internal implementation of the recursive DFS
    def _dfs_recursive (current_vertex, parent_vertex, current_length):

        # Access the variables defined outside the function
        nonlocal routing_table, distances_to_explored_vertices

        # Visit the vertex
        print("Visiting", current_vertex, "at distance", current_length, "from start along the explored path")
        routing_table[current_vertex] = parent_vertex
        distances_to_explored_vertices[current_vertex] = current_length

        # We stop when all vertices are visited
        if len(distances_to_explored_vertices) == len(graph) :
            print("Spanning tree done, all vertices have been explored once using DFS")
            return
        
        # If there are still vertices to visit, we explore unexplored neighbors
        for neighbor in graph[current_vertex] :
            if neighbor not in distances_to_explored_vertices :
                _dfs_recursive(neighbor, current_vertex, current_length + graph[current_vertex][neighbor])
    
    # Perform the traversal
    _dfs_recursive(source, None, 0)
    return distances_to_explored_vertices, routing_table

You can now draw inspiration from the code above to develop your TSP exhaustive search:

def tsp ( complete_graph: numpy.ndarray,
          source:         int
        ) ->              Tuple[List[int], int]:

    """
        Function to solve the TSP using an exhaustive search.
        In:
            * complete_graph: Complete graph of the vertices of interest.
            * source:         Vertex used to start the search.
        Out:
            * best_route:  Best route found in the search.
            * best_length: Length of the best route found.
    """
    
    # TODO: Fill here

Help: Alternatively, if you struggle to much with recursive algorithms, you can have a look at the itertools library (doc here) to generate all permutations of pieces of cheese. However, this implementation does not allow you to integrate the backtracking optimization, so do this only if you really have trouble with the proposed implementation.

Once the result of the traveling salesman problem is obtained, write a function to transform the solution path (into the meta-graph) into a sequence of locations within the maze.

def expand_route ( route_in_complete_graph: List[int],
                   routing_tables:          Dict[int, Dict[int, Union[None, int]]],
                   cell_names:              List[int]
                 ) ->                       List[int]:

    """
        Returns the route in the original graph corresponding to a route in the complete graph.
        In:
            * route_in_complete_graph: List of locations in the complete graph.
            * routing_tables:          Routing tables obtained when building the complete graph.
            * cell_names:              List of cells in the graph that were used to build the complete graph.
        Out:
            * route: Route in the original graph corresponding to the given one.
    """

    # TODO: Fill here

Then, use the code you designed in previous labs to transform this list into a list of moves to apply, and get all pieces of cheese in a minimum number of moves.

Implement a backtracking strategy

At this point, you should have a program which checks all possible permutations of vertices in the meta-graph, finds the one leading to the shortest path, and then converts this permutation into moves.

Now, you should improve this by implementing a backtracking strategy, that will abort exploration of a branch if it is already longer than the current best.

It would be interesting to work on a different file now, and create a program called tsp_2.py. This would allow you to compare performance of the exhaustive search with or without this optimization.

Explore the vertices in a better order

Remember from the course that if you explore vertices in a good order, then you may cut more branches than when exploring them in a random order.

One more improvement you can make is therefore to sort the neighbors in increasing distance to the current vertex of the search. Do this in a third file named tsp_3.py.

Test!

As usual, you should write the unit tests of your functions to get confidence on their correction.

Then, why not comparing if the improvements from tsp_2.py and tsp_3.pyaccelerate the required time to find the best route?

Super advanced?

You’re already done and you want to code more? Why not trying to find the solution to the TSP, in a tsp_4.py file, using a solver? Such tools will explore the space of possible solutions more intelligently than with an exhaustive search, exploiting things like triangular inequality, etc.

Here is a library you can use to achieve that: OR-Tools.