A$1$: A $2$D grid map is given below. You are required to plan path from start $\text{'}S\text{'}$ to goal $\text{'}G\text{'}.$Map Start $($origin$)$

$\backslash$table$[[(0,0),1,2,3,,4],[6,,,5,,],[,9,10,11,12,13],[14,,15,,16,],[,17,18,19,G,20]]$

Grids in black color are obstacles $($non$-$empty grids$).$ Empty grids are numbered for convenience.

Starting point of the map also indicated. Subsequent grids can be addressed by their $x$ and $y$

coordinates.

Represent the map as a tree structure with $\text{'}S\text{'}$ being root $($also write costs$).$ Assume the

robot can only take four possible actions $($if allowed by map$)$ from any given grid i$.$e$.$ left,

right, up$,$ and down.

For Dijkstra and A$*,$ the cost of moving from node to adjacent allowed node is $1$ unit.

On paper, run Breadth first, Depth first, Dijkstra, and A$*$ to plan path from $\text{'}$S$\text{'}$ to $\text{'}$G$\text{'}.$

Answer following two questions for each algorithm:

o How many nodes $($grids$)$ have been explored by each algorithm before it hit the

goal.

$0$ What is the path generated by the each algorithm. You can indicate the path by

node numbers e$.$g$.$ S $-->5-->7...$

o Make a table enlisting above results for all algorithms.Man Start $($orioin$)$

Note: For A$*,$ you can use your own heuristic. Make a suitable choice of heuristics, and clearly

explain what is your heuristic function and why are you using it$.$

Map Start $($origin$)$

$\backslash$table$[[(0,0),1,2,3,,4],[6,,,5,,],[,9,10,11,12,13],[14,,15,,16,],[,17,18,19,G,20]]$

PLEASE DO IT ASAP