1. Consider the following Maze Problem where the allowed moves are (Left, Right, Up, Down}. Initially all the cells are colorless except for the grey cells which are bottomless pits where you cannot go. When you step on a colorless cell it turns red. You are standing in cell S. Your objective is to color all accessible cells red. S S h=8 3 2. Consider the state-space graph in the following figure. S is the start node and G is the goal node. Find out the solution paths and costs returned by the following search algorithms. [1.5+1.5+2+2] h=2 B h=6 3 3 E h=1 Now answer the following: i. C h=2 3 ii. iii. h=2 What variables are required to represent a state of the problem? What is the size of the state space? What is the goal test? 3 [1] [1.5] [0.5] G h=0 i. UCS ii. Greedy BFS iii. A* Tree Search iv. A* Graph Search