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 Breadth First Search to find path from b$7$ to d$2.$

Report nodes in the fringe 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{.}5$ pt$]$

Breadth First Search