Question 2 Hive Minds You control one or more insects in a rectangular maze-like environment. At each time step, an insect can move into an adjacent square if that square is currently free, or the insect may stay in its current lo cation. In the case of multiple insects adjacent insects cannot swap lo cations Squares may be blocked by walls. There are N non-wall squares. 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 following scenarios, precisely but compactly define the state space and give its size. Then, give a non-trivial admissible heuristic for the problem and the maximum branching factor. Your answers should follow the format in the example case below. Full credit requires a minimal state space (i.e. do not include extra information) and a reasonable non- trivial heuristic. The heuristic must be admissible, but you are not required to prove admissibility. The illustrations are given as examples; your answers should not assume a speciiic maze. Example [Lonely Bugl: You control a single insect as indicated in the maze shown in Figure 2, which must reach a designated target location X. There are no other insects moving around. State space description: A tuple (x, y) encoding the x and y coordinates of the insect. State space size: N Heuristic: The Manhattan distance from the insect's location to the target. Maximum branching factor: 5 Figure 2: Lonely Bug Maze. a) Swarm Movement: You control K insects, one blue and K - 1 red. There are K target locations. In each time step all insects move si insect can go to any target location. An example is shown in Figure 3. Fill the missing information below. multancously (or some may stay in place). Each State space description: State space size: Heuristic: Maximum branching factor: Figure 3: Swarm Movement Using K Bugs. b) Patrolling Guards: You again control a single insect, but there are G spiders patrolling knowa paths as shown in Figure 4. Specifically at time t each guard g will be at position (6sd(0), Ya(t)) (in general, guard movements need not be a function of a guard's current location, but you may assume that the tuple of guard positions follows a known pattern that repeats with period T and two guards cannot be in the same cell at the same time). Similarly to question a), your insect cannot take an action which moves it into either a guard's current location or the location a guard is about to occupy. State space description: State space size: Heuristic: Maximum branching factor: Figure 4: Patrolling Guards Maze