Exercise $4(31$ points$).$ Consider an infinite $2$D grid where the initial state is the origin $(0,0),$ the goal state is

$($u$,$v$)$inZ$^(2)$ and the only possible actions are Up$,$ Down, Left, Right $($picked in that order when needed to break ties$),$

each with a cost of $1.$ As in the previous exercise, break ties in the priority queue by popping the oldest state.

$1.(1$ point$)$ What is the branching factor b $?$ Explain.

$2.(3$ points$)$ How many distinct states are there at depth i$>0?$ Explain.

$3.(4$ points$)$ How many nodes $($at most$)$ will BFS expand if using tree search? And if using graph search?

$4.$ Run each of the following algorithms for a goal $($u$,$v$)=(2,1),$ giving for each the sequence of states as they are

explored $($either as a list or by marking it on the grid$),$ and the cost of the path found:

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

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

$5.(3$ points$)$ Consider h$\_(2)($x$,$y$)=($u$-$x$)^(2)+($v$-$y$)^(2)$ at a state $($x$,$y$).$ Is this an admissible heuristic? Explain.

$6.(6$ points$)$ Run A$^(*)$ using as heuristic h$\_(2)$ for a goal $($u$,$v$)=(2,1).$ How many nodes does A$^(*)$ expand? Give the cost

for the path found. Is it optimal?

$7.(6$ points$)$ Repeat the previous two points for the function h$\_(1)($x$,$y$)=|$u$-$x$|+|$v$-$y$|.$