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 location. In the case of multiple insects adjacent insects cannot swap locations. 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 illustrations are given as examples; your answers should not assume a specific maze. Lonely Bug You control a single insect as shown in the maze above, 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 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 location. In the case of multiple insects adjacent insects cannot swap locations. 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 illustrations are given as examples; your answers should not assume a specific maze. Lonely Bug You control a single insect as shown in the maze above, 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
