Artificial Intelligence

2. The following figure shows a Pac-Man game. The Pac-Man (open mouth) should move to the positions of monsters and eat them. The black blocks in the figure is the areas where the Pac-Man can move, others not. Now you are required to program a shortest path from the current position of Pac-Man to the position of the monster in the right. ( Please use A* search method to solve this problem: 1) Design your Heuristic Function, and explain whether and why it is an admissible heuristic. [3 points] 2) According to your designed Heuristic Function, draw the search graph and label the value of heuristic function (h value), the value of evaluation function (f value), and the expansion order of nodes in the graph. [7 points] 2. The following figure shows a Pac-Man game. The Pac-Man (open mouth) should move to the positions of monsters and eat them. The black blocks in the figure is the areas where the Pac-Man can move, others not. Now you are required to program a shortest path from the current position of Pac-Man to the position of the monster in the right. ( Please use A* search method to solve this problem: 1) Design your Heuristic Function, and explain whether and why it is an admissible heuristic. [3 points] 2) According to your designed Heuristic Function, draw the search graph and label the value of heuristic function (h value), the value of evaluation function (f value), and the expansion order of nodes in the graph. [7 points]