I came across this question set. It asks following question:
Let’s revisit our bug friends from assignment 2. To recap, you control one or more insects in a rectangular maze-like environment with dimensions M × N , as shown in the figures below. At each time step, an insect can move North, East, South, or West (but not diagonally) into an adjacent square if that square is currently free, or the insect may stay in its current location. Squares may be blocked by walls (as denoted by the black squares), but the map is known.
For the following questions, you should answer for a general instance of the problem, not simply for the example maps shown.(a) You now control a single flea as shown in the maze above, which must reach a designated target location X. However, in addition to moving along the maze as usual, your flea can jump on top of the walls. When on a wall, the flea can walk along the top of the wall as it would when in the maze. It can also jump off of the wall, back into the maze. Jumping onto the wall has a cost of 2, while all other actions (including jumping back into the maze) have a cost of 1. Note that the flea can only jump onto walls that are in adjacent squares (either north, south, west, or east of the flea).
i. Give a minimal state representation for the above search problem.
Sol. The location of the flea as an (x, y) coordinate.
ii. Give the size of the state space for this search problem.
Sol. M ∗ N(b) You now control a pair of long lost bug friends. You know the maze, but you do not have any information about which square each bug starts in. You want to help the bugs reunite. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, both bugs will be on the same square, regardless of their initial positions. Any square will do, as the bugs have no goal in mind other than to see each other once again. Both bugs execute the actions mindlessly and do not know whether their moves succeed; if they use an action which would move them in a blocked direction, they will stay where they are. Unlike the flea in the previous question, bugs cannot jump onto walls. Both bugs can move in each time step. Every time step that passes has a cost of one.
i. Give a minimal state representation for the above search problem.
Sol. A list of boolean variables, one for each position in the maze, indicating whether the position could contain a bug. You don’t keep track of each bug separately because you don’t know where each one starts; therefore, you need the same set of actions for each bug to ensure that they meet.
ii. Give the size of the state space for this search problem.
Sol. $2^{MN}$
I don't get why the (a).i. uses $(x,y)$ coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right? And correspondingly the answers to ii will change.
Update
I now understand following:
For single flea maze, the representation $(x,y)$ will have $M\times N$ state space, whereas boolean list will have $2^{M\times N}$ state space. For two bug maze, the representation $(x_1,y_1,x_2,y_2)$ will have $(M\times N)^2$ state space, whereas boolean list will have $2^{M\times N}$ state space. I am able to understand, we prefer $(x,y)$ representation for single flea maze since $M\times N < 2^{M\times N}$. But for two bug maze, I am not able to understand why we prefer boolean list representation (and not $(x_1,y_1,x_2,y_2)$ representation), since $(M\times N)^2<2^{M\times N}$.
