(10 marks) Consider the maze shown below, where the successors of a cell are the cells directly to the east, west, north and south of the cell, except that you are not allowed to pass through the thick wall indicated by the double line. For example, the successors of cell I are H and N (and not D or J). Trace the operation of A* search applied to the problem of getting from cell R to cell G. The heuristic function is just the Manhattan distance, ignoring the existence of the wall. The heuristic values for each node are summarized for you in the table to the right. • Draw the search tree, starting from cell R. Beside each node in your tree, indicate the f, g and h scores for the node (in the format g(n)th(n) = f(n)). Assume that the cost of each move is 1. • To the side of your search tree, provide a list of the order in which paths are expanded. Show the contents of the frontier after each node is expanded. To make it easier to keep track of what you are doing, include both the f value and h value as subscripts when you write a path in your priority queue. For example, WXY Z11,7 would indicate that WXY Z is a path such that f(WXYZ) = 11 and h(Z) = 7. •If two or more paths are tied for the lowest f value, give priority to the one with minimum h value. Use alphabetical order if there is still a tie. • For this question, you can avoid generating states that have already been expanded. For example, you should not consider going west from cell I to cell H if you had already expanded cell H in an earlier step. • Also, when inserting a path onto the priority queue, if a path to the same state is already on the queue, just keep the copy with the lower f value. A B с DE FG HIJ KIL M N 0 S T WXY la b P Q R U V | cell A B с D E F G H I J K L M h(cell) cell N 0 2 1 2 3 4 1 0 1 2 3 2 1 2 P Q R S T U V BED W X Y What is the solution path returned by the algorithm, and what is its path cost? h(cell) 3 4 3 2 3 4 5 4 3 4 5 6

Fig: 1