The next five questions share a common setup. You control one or more insects in a rectangular maze-like environment with dimensions M times N , as shown in the figure below. At each time step, an insect can either (a) move into an adjacent square if that square is currently free, or (b) stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is always in terms of time steps; all actions have cost 1 regardless of the number of insects moving or where they move. For each of the five questions, you should answer for a general instance of the problem, not simply for the example maps shown. Problems For this problem, you control a single insect as shown in the maze above, which must reach a designated target location X, also known as the hive. There are no other insects moving around.

3.2 What is the size of the state space? Explain. Choice 1 of 6: (MN) Choice 2 of 6: (MN) square Choice 3 of 6: 2 power MN Choice 4 of 6: M power N Choice 5 of 6: N power M Choice 6 of 6: max(M, N)

3.3 2 Points Which of the following heuristics are admissible (if any)? Explain. Choice 1 of 3: Manhattan distance from the insects location to the hive. Choice 2 of 3: Euclidean distance from the insects location to the hive. Choice 3 of 3: Number of steps taken by the insect.

E