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

$($g$)$ How many illegal states are there? Give $4$ examples of illegal states.