estion 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 location. 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. estion 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 location. 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