$[1\mathrm{.}25$ pts$]$ Figure $5$ shows a robot navigation field, where the red square $($d$2)$ is the robot,

and green square $($d$4)$ 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. Please use $A^{**}$ search to find the path from $d2$

to $4($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. $($Using table format showing below. Please add rows if

needed$)[0\mathrm{.}5]$

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

Report the final path from d$2$ to d$4.[0\mathrm{.}25]$