Practical activity

Presentation & objectives

In this activity, you will have to develop a solution to grab multiple pieces of cheese in a minimum number of actions. To do this, we will program an exhaustive search, and then complement it with backtracking.

If you want to go further, we advise you that you at least have a look at the part on solvers. You will discover interesting additional concepts.

Activity contents

1 — The exhaustive algorithm

1.1 — Get prepared

Before we start, let’s first create the files we need in the workspace:

• pyrat_workspace/players/Exhaustive.py – Duplicate the file TemplatePlayer.py, and rename it Exhaustive.py. Then, as in the previous session, rename the class to Exhaustive.

• pyrat_workspace/games/visualize_Exhaustive.ipynb – Create a file that will start a game with an Exhaustive player, in a maze with mud (argument mud_percentage), and 5 pieces of cheese (argument nb_cheese). Optionally, you can set a random_seed and a trace_length. You should draw inspiration from the other files in the games subdirectory you encountered in the previous session.

• pyrat_workspace/tests/tests_Exhaustive.ipynb – Drawing inspiration from the test_DFS.ipynb, test_BFS.ipynb and test_Dijkstra.ipynb files you encountered in the previous sessions, create a test_Exhaustive.ipynb file. This file will contain the unit tests you will develop to test the methods of your Exhaustive player.

1.2 — Program the exhaustive algorithm

In order to write an exhaustive algorithm (without backtracking), follow the same steps as last time, i.e.:

• Identify methods – You should first identify which methods you will need. Do not hesitate to come back to the articles you had to study for today. When identified, write their prototypes in your Exhaustive.py player file.

• Identify tests – Determine which tests you should perform to guarantee these methods work as expected.

• Program the methods – Then, write some code (tests and player) to make sure your methods work as expected, and pass the tests you designed.

The following video shows you an example of what you should observe:

Once you have a working program, try to increase the number of pieces of cheese. What is the maximum number of pieces of cheese you can reach in a decent amount of time?

1.3 — Add backtracking

1.3.1 — Improvements to the exhaustive search

We are now going to add a backtracking strategy to our exhaustive search. Let’s write two new players:

• Backtracking – Create a new player Backtracking.py (copy Exhaustive.py to use as a basis), and a game using it. Then, improve your exhaustive algorithm by integrating a backtracking strategy in it.

• SortedNeighbors – The number of branches explored by the exhaustive algorithm depends on the quality of the first found solutions. In order to exploit this, create a new player SortedNeighbors.py (copy Backtracking.py to use as a basis), and a game using it. Then, think of an order in which it would be interesting to explore vertices, and update your codes so that your search takes this into account.

Again, don’t forget about the tests!

1.3.2 — Evaluate your improvements

You now have three programs based on an exhaustive search. It would be interesting to evaluate if your improvements indeed accelerate resolution of the TSP, or if your extra computations are harmful to performance. To do so, here are two things you should do:

• Monitor time – Compare the needed time it takes to the various programs to solve the TSP. To do so, you can:

  • Plot the average time (over 100 games for instance) required to complete a game, as a function of the number of pieces of cheese in the maze.

  • For a fixed number of pieces of cheese, compute the distributions of needed times for each program. Then, use adapted statistical tests to evaluate whether distributions are significantly different.

  Information

  Make sure to run your experiments with a Python kernel that disables asserts, as this would be counted in execution time. To do so, here are two possible solutions:

  • Without VSCode:

    • Convert this .ipynb notebook into a .py file with command ipynb-py-convert <this_notebook.ipynb> <created_file.py> (you may have to install ipynb-py-convert with pip).
    • Run the new Python file with python3 -O <created_file.py>.

  • With VSCode:

    • Create a Jupyter kernel with the following command: python3 -m ipykernel install --user --name python-o --display-name "Python (no asserts)".
    • Modify the kernel file (in ~/.local/share/jupyter/kernels/python-o/kernel.json or %APPDATA%\jupyter\kernels\python-o\kernel.json) to add the -O option in the argv list.
    • Restart VSCode.

• Count branches – Compare the cut and remaining branches in your exploration. To do so, you can:

  • Adapt your code to count how many branches were cut when exploring. An interesting plot you could produce is the number of cut branches, as a function of their depth in the tree (i.e., the number of vertices in the path before cutting). Indeed, the earlier you cut a branch, the fewer complete branches you have to explore, and thus the faster the algorithm will complete.

  • Adapt your code to count how many complete branches were explored. An interesting plot you could produce is the number of complete branches explored of length at most $l$, as a function of length $l$.

  Using these indicators, how good is your sorting strategy in SortedNeighbors.py?

To go further

2 — Factorize codes

Drawing inspiration from the previous sessions, you can try to factorize your various exhaustive searches. Indeed, we asked you multiple times to copy the previous file to use as a basis. It probably results that you have multiple times the same function in these files, which is very problematic. Indeed, if you find an error in such function now, you would have to update multiple places in your codes. This is an useless overload of work, and you may insert new errors when doing so.

Here are two possible things you can do (choose your favorite):

• Library – You can create an external Python file (for instance called tsp_utils.py) and write your duplicated functions there. Then, update your players to import the functions you need from that file.

• Class – As proposed in the session on graph traversals, you can create here an abstract class TSPSolver (in an utils directory), that aggregates common methods to all exhaustive solvers. Then, write classes ExhaustiveTSPSolver, BacktrackingTSPSolver and SortedNeighborsTSPSolver that inherit from TSPSolver. Finally, create a player TSPPlayer.py that exploits the solver you want.

  Here is a small UML diagram that represents a possible factorization. Check session 2 for a guide on how to read it.

  

3 — The branch-and-bound algorithm

While backtracking is an optimization based on a DFS algorithm, the branch-and-bound algorithm relies on a BFS-like approach. This algorithm was presented to you in the optional section of an article you had to study for today.

Try to implement it in a new player called BranchAndBoundTSPSolver. How does it compare to your other players?

To go beyond

4 — Solvers

4.1 — Intuition of possible improvements

It may seem strange to you that we struggle finding the TSP solution in a graph with as few vertices as 10-15, when tools such as GPS, traject planners, etc. exist in real life. In practice, most of these tools rely on what we call “heuristics”, which find approximate (not exact) solutions. You will study such approaches for the next session.

However, there is still room for improvement with exact algorithms. Indeed, we can easily think of some simple improvements. For instance, it is probably a bad decision to go back and forth in the maze as follows:

Catching close pieces of cheese is obviously better than this approach. For instance, this permutation is definitely shorter (although not necessarily the best):

You can see this optimization as some sort of triangular inequality. Indeed, the meta-graph that represents the repartition of pieces of cheese in the maze is a distance matrix with particular properties. This property – and numerous others – are exploited by advanced tools called “solvers”.

4.2 — What is a solver?

A solver is a generic tool that – for a given problem – explores the space of solutions in an intelligent way. Indeed, solutions can be organized in an abstract space, and their proximity in that space indicates similarity between the solutions. You can see that as a graph of solutions, and solvers will explore this graph intelligently to find the optimal one.

We will not go in details on how solvers work, but here is a link on how to formalize it mathematically if you are curious.

4.3 — Let’s use a solver

Let’s try to use a solver to solve the TSP on a PyRat maze. In Python, you can for instance use the ORTools library.

To use it, you should define a distance matrix that models your problem. Then, adapt the example provided by ORTools to solve the TSP on a PyRat maze.

With this solution, you should be able to compute the solution to the TSP for a lot of pieces of cheese within the preprocessing time.