Problem $1$

Consider the very simplified version of Pacman shown below. The game world is a $3$ X $3$ grid where each cell

is named by a letter from A to I. 'The Pacman agent is initially in cell A$,$ and wants to go to cell I. Pacman has a

heuristic function to estimate how close each cell is to the goal. Here are some more details:

On the top right corner of each cell, the heuristic cost is given $($this heuristic function was

calculated using the Manhattan distance from each cell to the goal$).$

From any cell, the agent can make horizontal $($left$/$right$)$ or vertical $($up$/$down$)$ moves to an

adjacent cell UNLESS the border between the two cells is marked by a thick line $($borders between

A & D and F & I$).$

The cost of an allowed move between two cells is $2($two$)$ EXCEPT for moves between two cells

separated by a fence marked with dashed lines $($borders between B & E and E & H$)$ for which the

move cost is $7($seven$).$

a$)$ Construct a search tree from this problem using the greedy best first search algorithm. On the

tree, each node should be marked with the value of the evaluation function in that node, and

each edge should be marked with its corresponding weight $($the cost of that action$).$

b$)$ Do the same as part $($a$),$ this time for A$*$ search.

$[$Note: Use alphabetical order to break any ties$]$