# Determining minimal state representation for maze game

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}$$.

I don't get why the (a).i. uses (𝑥,𝑦) coordinates whereas (b).i. uses boolean list. I guess they can be used interchangeablly right?

No these cannot be used interchangeably. The situations really are different enough that completely different state representations are necessary.

In the case of (a) you know the current bug's location, and nothing else about the problem changes over time. So any state representation that captures a single bug's location is valid. The (x,y) coordinates are a natural choice given the framing of the question, but also you could enumerate all the possible grid positions for the bug, giving the same size of state space.

In case of (b) you do not know where either bug is, but you don't need to care about the difference between each bug to track it separately (this is becasue your goal state does not rely on the identity of either bug). Therefore the state representation has to capture where any bug could possibly be.

The proposed solution is simple, but you could also do it by tracking possible locations of each bug. That could work with $$17^2$$ $$(x_1,y_1,x_2,y_2)$$ tuples initialised to all possible position combinations that the two bugs start in. The state space in that case is large (it is not just $$17^2$$, but includes all valid reachable combinations of the combined $$17^2$$ $$(x_1,y_1,x_2,y_2)$$ tuples) and difficult to assess because many state combinations are not reachable. Also note this alternative proposal does differentiate between the bugs - you could potentially improve upon that by removing start states that simply swap between bug locations, although this is still not as efficient as the binary representation.

Technically the proposed solution for (b) also works the same for any number of bugs that are spread out in the maze and want to all be in the same location at the end.

• Didnt get 2nd last paragraph from "The state space in that case is large...". For single flea maze, representation $(x,y)$ will have $M\times N$ state space, while boolean list will have $2^{M\times N}$ state space. For two bug maze, representation $(x_1,y_1,x_2,y_2)$ will have $(M\times N)^2$ state space, while boolean list will have $2^{M\times N}$ state space. We prefer $(x,y)$ representation for single flea maze since $M\times N < 2^{M\times N}$. But for two bug maze, 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}$?
– Maha
Feb 25, 2021 at 12:03
• The two bug version does not have $(M \times N)^2$ state space, because you do not know where the bugs are. The state space has to cover all possible locations that the bugs could be at the same time. Hence the representation starts as $17^2$ instances of the tuple, covering all combinations of start positions - that is the representation of the single starting state. This is a key part of the problem. Feb 25, 2021 at 13:57
• Sorry, am unable to get how not knowing where the bugs are makes it not to have $(M\times N)^2$ space? Also, with $(x_1,y_1,x_2,y_2)$ representation, first bug is at $(x_1,y_1)$ and second bug is at $(x_2,y_2)$. Doesnt that cover all possible locations that the bugs could be at the same time?
– Maha
Feb 25, 2021 at 14:04
• @anir: The state represents your current knowledge, not a hypothetical position in a simulation that internally knows where the bugs are. If you don't know where the bugs are, and they could be anywhere, the state needs to represent that fact in a data structure somehow. The binary representation in the answer you posted does this efficiently. If you use (x,y) coordinates, then you need a way to represent which (x,y) vales are currently possible (my suggestion as an alternative here to help you understand). A single (x,y) position (or just two) is not useful to resolve the problem Feb 25, 2021 at 14:16
• It may help if you understand the solution to second problem. It will be something like W, W, W, W, S, S, E, E, E, S, S - if you can understand why that is a good solution, it may be another way to help you visualise how the binary representation works (and why a coordinate-based system is more complex) Feb 25, 2021 at 14:24