4) [3p] Consider the problem of finding a path in the grid shown below from the positions to the position g. A piece can move on the grid horizontally or vertically, one square at a time. No step may be made into a forbidden shaded area. Each square is denoted by the xy coordinate. For example, sis 43 and g is 36. Consider the Manhattan distance as the heuristic. State and motivate any assumptions that you make. a) Write the paths stored and selected in the first five iterations of the A* algorithm, assuming that in the case of tie the algorithm prefers the path stored first. g 8 7 6 5 4 3 S 2 1 1 2 3 4 5 6 7 8