Figure $2$

Question $2[6$ pts$]$ Figure $2$ shows a robot navigation field, where the green square $($b$7)$ is the

robot, and red square $($d$2)$ is the goal. The shad squares $($such as $c2,d3$ etc.$)$ are obstacles. The

robot is not allowed to move in diagonal line. Nodes are coded using an alphabet letter followed

by a digit $($such as b$1,$ b$2$ etc.$).$ When two sibling nodes are inserted into fringe $($queue$),$ use

deque order to favor node with a lower alphabet and a lower digit. For example, if d$1$ and e$2$ are

sibling nodes, $d1$ will be dequeued first $($because $"$d$"$ has a lower alphabetic order than $"$e$").$ If e$1$

and e$2$ are sibling nodes, e$1$ will be dequeued first $($because $"1"$ has a lower digit than $"2").$ Node

expanded$/$visited does not need to be revisited.

Use Best First Search to find path from b$7$ to d$2.($Using Manhattan distance

as the heuristic function$)$

Report nodes in the fringe $($including their $f(N)$ values$)$ in the orders they

are included in the fringe. $0\mathrm{.}5pt$

Report the order of the nodes being expanded. $0\mathrm{.}5pt$

Report the final path from $b7$ to $d2.0\mathrm{.}5pt$

Best First Search