HW11. Search Heuristics, Optimization (26th of Nov, 23.59)
EX1. Let's play games in the virtual block world. Your task is to find the shortest path (measured in Euclidean distance between start and end pixel of each step or unit time spent per step) from A to B using A* algorithm or alternative heuristics. You need to avoid the obstacles (pink areas and no crossing the pink line!) and honouring the slow-down factors in the swamp and in the sea (2x and 4x slower respectively; or making Euclidean distance “longer” in those areas). Define the graph and roads based on exact pixels (in integer spaces - the image is 1000x1000 pixels). To vary the step length and choose a step length using Euclidean distance defining a circle radius and deciding how many points on the circle. E.g. 4, 6, 12, 24 … points divided equally around the 360°. Making longer steps should allow to search faster(?). Measure the time, calculate the distance and visualise the path-finding based on long (about 20-30 pixels) and short (2-3 pixels) steps.
Hint: 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. You may also want to first fix the grid of all possible pixels the search could in theory cover, not all 1000x1000.
SWOG code (see https://biit.cs.ut.ee/SWOG/index.cgi and paste it in the box at bottom of the page) and coordinates for this image are: pixel_world.txt
EX2. Visualize the solution - by coloring the actual shortest path in BLACK and the search front areas you have ever visited by some lighter color scheme. By varying the color of the lighter areas according to time you may get much better visualisation. See for example: https://bost.ocks.org/mike/algorithms/ the use of colors towards the end. (Hint: be gentle with SWOG server - it may not handle overly large files very well).
EX3. Experiment with various small modifications to standard A* algorithm that would reduce the global area searched. E.g. observe, when does search try to move into “wrong direction” and how to enforce the path that still tries to reach the goal.
EX4. Implement and play with the Ant Colony Optimisation strategy for finding shortest paths through the virtual block world with the complex terrain as described above. Note that each ant would become an instance that can only be in one single place at any time and move around from there. Use a global unit time so that ants would travel one step in one unit (or spend several time units in slowdown areas). Describe the choices you had to make and which parameters seemed to work the best.
EX5. Observe the dynamic behavior of ACO optimisation. Measure the speed (as in a unit time of counting steps) by which the ants will carry the food over the time. Experiment with the amount of food in target B and placing some random amounts in new locations. How fast the ants would “re-wire” their optimal behavior?
EX6 (3 Bonus). Try to propose as good a solution based on graph search for the block worlds as possible, by exploring various scenarios and showing your algorithm. Try to avoid exploring too broad areas. The goal is to outbeat A* by a clear margin and demonstrate that convincingly (e.g. finding some landmarks, sticking to promising paths and not searching backwards unless really needed, etc).. What happens if you give up the idea of the optimal solution? Compare the actual distances and the time it took to calculate them. I.e. the area explored by such shortest path finder.
Feel free to also change the block world to make some other interesting educational versions of the same task - original field + visualization. Add areas; change slow-down factors, or change the physics of moving.