Assignment 8

from IPython.display import Image Image(filename='ass8_1.png')

Image(filename='ass8_2_2.PNG')

Image(filename='Astar-1.jpg')

A*: length = 10, time = 3.2 ms, operations = 78

Breadth-First-Search: length = 10, time = 1.7 ms, operations = 134

Best-First-Search: length = 10, time = 2.1 ms, operations = 56

As we can see, the Breadth-First-Search algorithm explores a larger path and is thus less efficient, which can be explained by the fact that it does not use any heuristic to gather information on whether it is getting closer to the goal or not. It is blindly exploring the different possibilities. Then, even though A* is more informed than Best-FS, since it takes into account the distance already travelled, the latter is more efficient: Best-FS is less prone to exploring a lot of possibilities, which is an advantage here since the target is quite close to the start.

Image(filename='a_star.png')

Image(filename='bfs.png')

Image(filename='best.png')

Image(filename='bfs-comparison.png')

Breadth-FS: length = 11; operations = 47

Image(filename='bfscomp2.png')

Best-FS: length = 11; operations = 52

The Generic Search Problem satisfies all the conditions (different coordinates = different states, moving up/down/left/right = set of actions, manhattan distance shrinking = reward) but the one regarding probability. Indeed, in every state, all the costs are estimated and the selected path is the one that minimises the cost/maximises the reward. Thus, for a given start, there is only one optimal solution: the GSP is deterministic.

A solution to make the GSP a MDP would be to say that the probability distribution is such that the probability is always 1, giving full control to the decision maker.