$\backslash$table$[[$a$1,$a$2,$a$3,$a$5],[$b$1,$b$2,$b$3,$b$4],[$c$1,$c$2,$c$3,$c$4],[$d$1,$d$2,$d$3,$d$4],[$e$1,$e$2,$e$3,$e$4]]$

Figure $1$

Question $1[4$ pts$]$: Figure $1$ shows a robot navigation field, where the green square $($c$4)$ is the robot, and red square $($d$1)$ is the goal. The shade squares $($such as b$2,$ c$2,$ 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 a$1,$ 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 $d1$ and $e2$ are sibling nodes, $d1$ will be dequeued first $($because $"$d$"$ has a lower alphabetic order than $"$e$").$ If al and $a2$ are sibling nodes, a$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 c$4$ to d$1($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{.}5$ pt$]$

$,,$Report the order of the nodes being expanded. $[1$ pt$]$

$,,$Report the final path from $c4$ to $d1.[0\mathrm{.}5$ pt$]$

$,$Use A$*$ to find path from $c4$ to $d1($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. $[1$ pt$]$

$,,$Report the final path from $c4$ to $d1.[0\mathrm{.}5$ pt$]$