Exercise $3(42$ points$).$ Consider a vacuum world as follows. We have a $2$xx$2$ grid with cells $\{(0,0),(0,1),(1,0),(1,1)\}.$ 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 $(0,0)$; dirt only at $(1,0).$ 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: S$,$U$,$D$,$L$,$R; also, if the lowest value of the evaluation function f$($n$)$ 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 $(0,0)$; dirt only at $(0,0)$ and $(1,1).$ 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.

FOR QUESTION $3-6,$ PLEASE DRAW OUT THE FINAL SEARCH TREES ALONG WITH THE PATHS TO THE GOAL AND ITS COSTS. DO NOT VERBALLY EXPLAIN THE PROCESS, THAT DOES NOT ANSWER THE QUESTION! Figure $3\mathrm{.}2$ The state$-$space graph for the two$-$cell vacuum world. There are $8$ states and three actions for each state: $\backslash (\backslash$mathrm$\{$L$\}=\backslash )$ Left, $\backslash (\backslash$mathrm$\{$R$\}=\backslash )$ Right, $\backslash (\backslash$mathrm$\{$S$\}=\backslash )$ Suck.