Contents of the page


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 command line we are going to use is the following, assuming your program is named AIs/exhaustive.py:

python pyrat.py --rat AIs/exhaustive.py -p 5 -x 15 -y 15 -d 0.5

It is now time to increase the number of pieces of cheese in the maze (-p option). Keep this number low in a first time, as the program we are going to write is quite complex.

Generating the metagraph

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 metagraph).

First, 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 metagraph to another one.

An easy way to perform an exhaustive search is to see it as a depth-first search, in which we want each vertex to be visited within each branch, rather than only once in the whole search. Here is an example of a recursive depth-first search algorithm:

# Recursive implementation of a depth-first search
def dfs (graph, initial_vertex) :
    
    # Nonlocal list of visited vertices
    visited_vertices = []
    
    def _dfs (current_vertex, current_length) :
        
        # Visiting a vertex
        print("Visiting", current_vertex, "at distance", current_length, "from start")
        
        # We stop when all vertices are visited
        nonlocal visited_vertices
        if len(visited_vertices) == len(graph) :
            print("Back")
            return
        
        # If there are still vertices to visit, we explore unexplored neighbors
        for neighbor in graph[current_vertex] :
            if neighbor not in visited_vertices :
                visited_vertices.append(neighbor)
                _dfs(neighbor, current_length + graph[current_vertex][neighbor])

        # If there are no unvisited neighbors left, the inner function will return,
        # which corresponds to coming back to the previously visited vertex
        print("Back")

    # Initial call
    _dfs(initial_vertex, 0)

In that code, you will notice the use of a nonlocal variable. You can see that as a global variable, from the point of view of inner functions (i.e., those defined within another function).

The advantage of this way of writing global variables is that they are reinitialized between two calls of function dfs, which avoids side-effects like global variables can have.

Now, adapt the DFS code above to obtain an exhaustive search.

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

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 metagraph, 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 AIs/exhaustive_backtracking.py. This would allow you to compare performance of the exhaustive search with or without this optimization.