Question $4$ Search

$($a$)$ Consider a problem with two possible actions: a and $b.$ The cost of $a$ is $2$ and the cost of $b$ is $1.$ The shallowest goal node can be at any level of the tree and the problem solution may involve a sequence of these actions. Is breadth$-$first search optimal to solve this problem, given this cost function? Justify your answer.

$[10$ marks$]$

$($b$)$ An agent must traverse a maze in order to find and collect a treasure. This task can be formulated as a search problem as in the following:

Initial state: the agent is in $A1.$

Goal test: the agent is in $E5($automatically collects the treasure$).$

Actions: move $(n,n^{\text{'}})$ moves the agent from state $n$ to a state $n^{\text{'}}$ that is to the left of$,$ or the right of$,$ or above or below state $n.$

Transition model: see figure below. States depicted in black, e$.$g$.,$ A$2,$ are considered obstacles and cannot be traversed by the agent.

Path cost: each action has cost $1.$

Generate the $A^{**}$ tree until the goal node is found.

The heuristic to be used is the following:

$h(n)=d_M(n,n_{\text{g}\text{o}\text{a}\text{l}})={\displaystyle \underset{i=1}{\overset{3}{}}}|p_i-q_i|,$

where $d_M(n,n_{\text{g}\text{o}\text{a}\text{l}})$ represents the Manhattan distance between node $n$ and the goal node $n_{\text{g}\text{o}\text{a}\text{l}}.$ When comparing the first coordinate of each state, assume the following values for each of the possible letters in the grid: $A=1,B=2,C=3,D=4$ and $E=5.$ Order of expansion: if $f(n)$ produces the same lowest value for two nodes, expand the nodes in alphanumerical order $($e$.$g$.,A2$ expanded before $B1).$ Additionally, if $g(n)$ also produces the same lowest value for two nodes, keep the the node that has been added last into the frontier. Recall that the evaluation function $f(n)=g(n)+h(n)$ is the sum of the cost to reach node $n$ and the heuristic calculated at node $n.$

Write down the following:

Search tree produced by $A^{**},$ indicating the $f(n),g(n)$ and $h(n)$ values of each node $n$; which nodes are in the frontier when the algorithm terminates; and which nodes have been pruned as a result of the above instructions.

The solution retrieved by $A^{**}$ and its cost.

The sequence of nodes visited by $A^{**}$ in the order they are visited. Note: you can identify a node through its state, e$.$g$.,A1$ or $B1.$