Exercise $3(42$ points$).$ Consider a vacuum world as follows. We have a $\backslash (2\backslash$times $2\backslash )$ grid with cells $\backslash (\backslash \{(0,0),(0,1),(1,0),(1,1)\backslash \}\backslash ).$ The agent can move one step in any direction $($U$)$p or $($D$)$own with cost $1,($L$)$eft or $($R$)$ight with cost $2$; or $($S$)$uck dirt with cost $10.$ Any of the cells may or may not have dirt. A goal state has no dirt in any cell.

$1.(4$ points$)$ Draw the state$-$space graph as in fig. $3\mathrm{.}2.$ How many states are there?

$2.(2$ points$)$ For this problem, what is better: tree search or graph search? Explain.

$3.$ Let the initial state be: agent at $\backslash ((0,0)\backslash )$; dirt only at $\backslash ((1,0)\backslash ).$ For each of the following search algorithms, run it showing your work $($the relevant data structures, path costs and parent $($predecessor$)$ in the path$).$ Draw the final search tree, give the path found to the goal and its cost. When needed to break ties in picking actions, use this order: $\backslash (\backslash$mathrm$\{$S$\},\backslash$mathrm$\{$U$\},\backslash$mathrm$\{$D$\},\backslash$mathrm$\{$L$\},\backslash$mathrm$\{$R$\}\backslash )$; also, if the lowest value of the evaluation function $\backslash ($ f$($n$)\backslash )$ in a priority queue is achieved by multiple states, pop the oldest one $($i$.$e$.,$ the one that entered the queue first$).$

$($a$)(4$ points$)$ BFS$.$

$($b$)(4$ points$)$ DFS$.$

$($c$)(4$ points$)$ UCS.

$4.(12$ points$)$ Let the initial state be: agent at $\backslash ((0,0)\backslash )$; dirt only at $\backslash ((0,0)\backslash )$ and $\backslash ((1,1)\backslash ).$ Repeat as in the previous point.

$5.(6$ points$)$ Repeat point $3$ but now assuming the actions U and D are not allowed.

$6.(6$ points$)$ Repeat point $4$ but now assuming the actions U and D are not allowed.