Question 1: Problem Formulation .... 25 pointsCooperative agents: An agent is trying to eat all the food in a maze that contains obstacles, but he now has the help of his friends! An agent cannot occupy a squarethat has an obstacle. There are initially k pieces of food (represented by dots), at positions (f1,...,fk). Thereare also n agents at positions (p1...,pn). Initially, all agents start at random locations in the maze. Consider a search problem in which all agents move simultaneously;that is, in each step each agent moves into some adjacent position (N, S, E, or W, or STOP). Note that any number of agents may occupy the same position

1. Give a search formulation to the problem of looking for both gold and diamondin a maze.

2. Knowing that you have M squares in the maze that do not have an obstacle. What is the maximum size of the state space.

3. What is the maximum branching factor.

4. For each of the following heuristics, indicate (yeso) whether or not it is ad-missible.

h1: The number of dots (representing food) remaining. [ True, False ].

h2(s)=0, where s is a state node. [ True, False ).

h3(s)=1, where s is a state node. [ True, False ].

Question 2: Uninformed Search .. 25 pointsConsider the maze shown in Figure 2, where square a is the initial position and Ois the goal position. The goal of our agent is to find a way from the initial position to the final position. The possible actions are move up, down, left and right to an adjacent square. The shaded squares are obstacles, and the cost of each action is 1, except for (d, h) which has cost 4, (i, k) which has cost 2 and (h, 0) which has cost 3. Assume that the actions are ordered according to their resulting state alphabetically.For example, the action (a, b) comes before (a,c).

1. Draw the search graph corresponding to this problem.

Give the: final search tree, final explored list (the order is important), final frontier list (the order is important: the leftmost node is the next oneto be explored, indicate the priority when applicable), solution found, cost of the solution, for each of each of the following algorithms: (a) Depth first search (DFS): graph search version.

(b) Recursive depth first search (DFS).

(c) Uniform cost search (UCS): graph search version.

1 2 3 4 1 b e 2 a f 3 d 4 | 5 | 0 0 k Figure 2: Maze 1 2 3 4 1 b e 2 a f 3 d 4 | 5 | 0 0 k Figure 2: Maze