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 c$2,$ d$3$ 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, d$1$ 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 Depth First Search to find path from b$7$ to d$2.$

o Report nodes in the fringe in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

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

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

DFS

Fringe: Node visited$/$expanded

$$ Use Breadth First Search to find path from b$7$ to d$2.$

o Report nodes in the fringe in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

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

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

BFS

Fringe: Node visited$/$expanded

$$ Use Best First Search to find path from b$7$ to d$2.($Using Manhattan distance as the heuristic function$)$

o Report nodes in the fringe $($including their f$($N$)$ values$)$ in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

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

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

Best First Search

Fringe: f$($N$)=$h$($N$)$ Node visited$/$expanded

$$ Use A$*$ to find path from b$7$ to d$2.($Using Manhattan distance as the heuristic function$).$

o Report nodes in the fringe $($including their f$($N$)$ values$)$ in the orders they are included in the fringe. $[0\mathrm{.}5$ pt$]$

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

o Report the final path from b$7$ to d$2.[0\mathrm{.}5$ pt$]$

A$*$ Search

Fringe: f$($N$)=$g$($N$)+$h$($N$)$ Node visited$/$expanded