Q6 Hive Minds: Lonely Bug 6 Points Introduction 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. X 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. Q6.1 2 Points Which of the following is a minimal correct state space representation? O An integer (d) encoding the Manhattan distance to the hive. O A tuple ((x, y)) encoding the (x) and (y) coordinates of the insect. A tuple ((x, y, d)) encoding the insect's (x) and (y) coordinates as well as the Manhattan distance to the hive. O This cannot be represented as a search problem. Submit Q6.2 2 Points What is the size of the state space? O (MN) O ((MN)^2) O (2^{MN}) O (M^N) O (N^M) O (max(M, N)) Submit Q6.3 2 Points Which of the following heuristics are admissible (if any)? Manhattan distance from the insect's location to the hive. Euclidean distance from the insect's location to the hive. Number of steps taken by the insect. Submit