A robot placed at the "Start" position is being programmed to navigate the below maze to reach the nearest exit marked by numbers (in black color) which represents the prize money obtainable at the end of the search. The goal state expected is to get atleast 4 as the prize amount. Each of the Exit point and the intersections of the maze marked in blue represents the decision nodes for the robot to process its move, with the latter has stored heuristic value to reach the goal marked in square bracket. The heuristic value given can be assumed to be the fitness of the state. Gate LE E 131 1101 Wall K [0] Start [8] LE [1] M Note: All the paths are unidirectional ie., robot can move from node C to H but not vice versa A traversal between every pairs of nodes incurs a default traversal cost of value=1 To enable the actuator's setting, and additional path cost of (1,1,2,2) is added for every direction of move corresponding to (N,E,W,S). ie.From "F" to reach its nearest exit numbered "1", additional cost = 1+1+1+2 for NE+N+W Extra penalty of cost =3 is charged if the robot were to use the force to open the Gate (marked by red colored dashed lines) Use the above information on the cost attributing factor and the following algorithms to answer the corresponding questions: [4 + 4 + 6 = 14 Marks] For each of the following search strategies, indicate which goal state is reached (if any) and list, in order, all the states explored from Frontier/Open List. When all else is equal, nodes should be removed from Frontier in alphabetical order. a) Uniform Cost Search: I Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] b) Hill Climbing I Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] c) A* Search: I. Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] IV. Only with respect to the intersection node "A"check if the heuristic is admissible. Prove numerically with appropriate example. [2 Marks] A robot placed at the "Start" position is being programmed to navigate the below maze to reach the nearest exit marked by numbers (in black color) which represents the prize money obtainable at the end of the search. The goal state expected is to get atleast 4 as the prize amount. Each of the Exit point and the intersections of the maze marked in blue represents the decision nodes for the robot to process its move, with the latter has stored heuristic value to reach the goal marked in square bracket. The heuristic value given can be assumed to be the fitness of the state. Gate LE E 131 1101 Wall K [0] Start [8] LE [1] M Note: All the paths are unidirectional ie., robot can move from node C to H but not vice versa A traversal between every pairs of nodes incurs a default traversal cost of value=1 To enable the actuator's setting, and additional path cost of (1,1,2,2) is added for every direction of move corresponding to (N,E,W,S). ie.From "F" to reach its nearest exit numbered "1", additional cost = 1+1+1+2 for NE+N+W Extra penalty of cost =3 is charged if the robot were to use the force to open the Gate (marked by red colored dashed lines) Use the above information on the cost attributing factor and the following algorithms to answer the corresponding questions: [4 + 4 + 6 = 14 Marks] For each of the following search strategies, indicate which goal state is reached (if any) and list, in order, all the states explored from Frontier/Open List. When all else is equal, nodes should be removed from Frontier in alphabetical order. a) Uniform Cost Search: I Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] b) Hill Climbing I Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] c) A* Search: I. Prize money obtained & its immediate parent node: [1 Mark] II Total path cost of the solution: [1 Mark] III. Order of States explored from Frontier: [2 Marks] IV. Only with respect to the intersection node "A"check if the heuristic is admissible. Prove numerically with appropriate example. [2 Marks]