Question 1 Consider the simplified Pac-Man problem shown in the figure below, which is given as a 55 grid environment. In this version of the game, the Pac-Man starts in the center of the grid, with 4 food items in the grid corners. The goal is to eat the 4 food items while avoiding the ghost. An illegal state is one where both the Pac-Man and the Monster are in the same loeation. For simplicity, we assume that at each time step, the ghost moves first then the Pac-Man. Each agent can move one grid horizontally or vertically at each time step. (a) Represent this problem as a search problem (for the Pac-Man) and choose a representation from the problem's states. Each state should be represented as a tuple. Note: if a certain attribute is not important when representing a certain state(s). you can use X to indicate 'not important'. (b) Write down the initial state (as shown in the image). (c) Write down the goal state. (d) What are the possible actions for the Pac-Man? (e) Draw 2 levels ( 2 steps) of the state space for this problem showing all possible states. Assume that the ghost is idle during these steps. (f) Draw 1 level (1 Pac-Man step) of the state space for this problem showing all possible states. Assume that the ghost takes a moving step before the Pac-Man. For the Pac-Man problem given in Question 1. design an admissible heuristic that gives a value for each state. You can completely ignore the existence of the ghost