You control K insects, each of which has a specific

target ending location X k$.$ No two insects may occupy

the same square. In each time step all insects move

simultaneously to a currently free square $($or stay in

place$)$; adjacent insects cannot swap in a single time

step.

a$)$ Can you provide a smallest state space

representation?

b$)$ What is the size of the above state space?

$3$

c$)$ Which of the following heuristics are admissible $($if any$)?$ Explain why.

A: Sum of Manhattan distances from each insect's location to its target location.

B: Sum of costs of optimal paths for each insect to its goal if it were acting alone in the

environment, unobstructed by the other insects.

C: Max of Manhattan distances from each insect's location to its target location.

D: Max of costs of optimal paths for each insect to its goal if it were acting alone in the

environment, unobstructed by the other insects.

E: Number of insects that have not yet reached their target location