HW9. Search heuristics and TSP optimization (31st of October, 23:59)
Virtual World and Search Heuristics
A virtual world can be represented as an image (e.g. Figure 1) where each pixel is either white (means vacant) or has a color. Colored pixels have special meaning, e.g. pink pixels belong to impenetrable obstacles. Also, each possible virtual world has a start pixel (A) and end pixel (B), that are defined by circles.
Goal: find the shortest path from pixel A to pixel B. The final path is measured as a sum of lengths of each step in the path. The length of a step is an Euclidean distance between its start and end pixels.
Rules: You need to avoid the obstacles (pink areas and no crossing the pink line!) and honoring the slow-down factors in the swamp and in the sea (by making Euclidean distance 2x and 4x times “longer” in those areas).
Things to consider before you start:
- What are the nodes?
- What are the edges? Given a node, where can you move to?
- What is the distance between any two nodes?
- How to represent the graph for traversal? You can either load in the image with some image library, such as PIL for Python and check colors of each pixel or code the objects by yourself (or some other way).
EX1. Getting started with pathfinding in the small virtual world. The first task is to implement Dijkstra algorithm to find the shortest path from A (blue) to B (red) on the following small scale world (250x250). Pink is a block, you can not go through it! Report the shortest distance from A to B and the time it took to run the algorithm. Visualize the final path and pixels that were visited by the algorithm at any time. Comment on your results.
To generate the image for the world use the following web tool. Set the world size to 250x250 at the top and use the following object instructons to get the small world:
circle 10 10 3 blue circle 240 240 3 red text "A" 15 20 20 black text "B" 225 235 20 black rectangle 0 50 150 60 pink rectangle 0 110 50 125 pink rectangle 70 110 250 125 pink rectangle 100 125 130 220 pink rectangle 160 150 180 250 pink
Figure 1: a small virtual block world for EX1 and EX2
After you’ve added objects (and path) to the world under Objects, you can click “Save as png” to save the image to your computer. This image can then be used as an input to your search algorithm.
In order to visualize the path using the webtool, save your algorithm’s output into a “.txt” file in the following format
X1 Y1 X2 Y2 X3 Y3 ….
Here, each pair of X and Y represents a pixel that is included into the final path from A to B (including A and B). For example, consider the following .txt file (URL). Select this file by clicking “Choose file” under “Path file” section in the web tool. You should get the following result:
Figure 2: an example path in the small virtual block world.
You can also use the web tool to highlight pixels that were visited by the algorithm. For this, store the visited pixels/nodes in a text file, in a similar to path file format:
X1 Y1 X2 Y2 …
For example, if your search algorithm visited every possible node (which is inefficient!) then you would get the following output, defined by the coverage file (URL):
Figure 3: an example visited area in the small virtual block world.
NB! “Save as png” does not save the visited pixels, therefore if you want to use the webtool for this, you need to separately screenshot it.)
EX2. Implement A* search algorithm on the small world (the same as above). Similarly to the previous exercise report: execution time and the shortest distance. Visualize the visited area and the final path. Comment on the differences between Dijkstra and A*!
EX3. Now let’s consider the bigger version of the virtual world (1000x1000), which is provided below (Figure 4). The goal is still the same - find the path from A (BLUE) to B (RED). But now with some additional obstacles: SWAMP and SEA. SWAMP in light green, is 2 times slower compared to usual. SEA in light blue and is 4 times slower than the usual (taking one step in a sea, is equal to taking 4 steps on normal land). Measure and report the search time and the shortest distance. Visualize the visited area and the final path. How sea and swamp affect the final trajectory?
Hint: make sure to use efficient data structures for keeping visited/discovered nodes, e.g. consider the priority queue for A*. Using inefficient data structures can end up your search running for a really long time!. Another way to speed up your search is by making steps longer. So, instead of considering every immediate nearest neighbor as a potential next step, consider only nodes that are 2-3 pixels away (or even 10-20 pixels).
Hint II: for the slower regions like the sea or swamp decide the distance or time spent on each step based on the slow-down in the location of the target pixel.
The instructions to build a bigger version of the virtual world are provided in the file and below (URL). Feel free to either ignore or remove the “text” lines. The world size is 1000x1000.
circle 500 920 8 blue circle 500 80 8 red circle 100 250 75 lightgreen circle 300 250 75 lightgreen circle 500 250 75 lightgreen circle 700 250 75 lightgreen circle 900 250 75 lightgreen rectangle 100 400 900 500 lightblue rectangle 0 400 100 500 lightgreen rectangle 900 400 1000 500 lightgreen rectangle 0 600 400 650 pink rectangle 600 600 1000 650 pink rectangle 200 700 800 750 pink line 200 100 800 100 2 pink line 200 100 200 0 2 pink line 1000 1000 700 800 7 pink line 750 950 600 700 7 pink text "A" 510 930 20 black text "B" 510 80 20 black
Figure 4: the bigger version of the virtual world (1000x1000) for EX3 and EX6.
Traveling Salesman Problem, Optimization
Take a look at the coordinates of hypothetical "cities" - TSP.zip. Our goal is to find the shortest route through all cities (solve the TSP). Assume that there exists a direct road between any pair of cities (Euclidean distance; two points p1=(100,100), p2=(103,104) will have distance (p1, p2)=5 ).
EX4: Run the Nearest Neighbour (NN) algorithm to generate a route through all cities starting from any node (e.g. from node 0). Your route should also end in this node. If distances tie, choose the first city. Report the shortest tour and time it took to complete it for cities of size 10, 20 and 100. Visualize resulting paths either using a webtool: https://abercus.github.io/tspvis/ or your own code.
To get a better feeling of the algorithm, feel free to try it also "on paper" for small size problems (e.g. 10 or 20-cities task). Implementation is preferred, of course, feeding to the next problems.
EX5: Implement an optimization method of your choice (e.g. simulated annealing, genetic algorithm, ant colony optimization, hill climbing, tabu search etc.) on provided cites. For the sake of acceptable performance, you may calculate all possible distances before running your algorithm (distances between each two cities). It is recommended to work on small size problems (10, 20 nodes) first. As usual - report resulting path, its length, and execution time. Comment on comparison with nearest neighbour result.
Hint: Many of the heuristic search algorithms described in the lecture, require the notion of "neighbourhood". Think of your current state as a sequence of cities, e.g. 1-2-3-4-5 (the resulting path). Then one way you can describe a neighbourhood of a certain sequence, is to try all possible swaps of two cities (or only sequential ones). Two possible example of a neighbour for 1-2-3-4-5 could then be 2-1-3-4-5, 1-3-2-4-5. Of course, you can describe neighbourhood in some other way as well, but you most likely don't want to consider every possible permutation as your neighbour! If you can generate the neighbours, then for example when implementing hill climb/simulated annealing/..., you would choose your next state to be the best result out of all the neighbours (the sequence with shortest total distance).
EX6 (Bonus up to 3p). This is a continuation to Virtual World. Experiment with the virtual world, add more different terrains (ice, lava, forest etc.), add surprising things (e.g. portals, magnets, black holes etc.). Also, you may try to improve visualization by perhaps doing it yourself. How your algorithm behaves? Can you tweak the algorithm to outperform standard A* in this specific setting? Try to show this advantage with some empirical results. The number of points granted for this exercise will depend on the number of things considered and on the level of their implementation.
EX7 (Bonus up to 3p). Prove Travelling Salesman Problem (TSP) on n cities is solvable in time O(4nnlog n) using only polynomial space.