$7$:$09$

Notes

CAP$6635\_2024\_$Final

Done

$\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 d$1$ and e$2$ are sibling nodes, $d1$ will be dequeued first $($because $"d"$ has a lower alphabetic order than $"$e$").$ If al and a$2$ 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 $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. $1pt$

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

Best First Search

$\backslash$table$[[$Fringe: $f(N)=h(N),$Node visited$/$expanded$],[,],[,],[,],[,],[,]]$

$\backslash$table$[[,],[,],[,],[,],[,],[,],[,],[,],[,]]$