Search code examples
algorithmartificial-intelligencegraph-algorithmstate-space

Why is the state space the power set of the grid's dimensions? (edX CS 188.1x Artificial Intelligence)

I'm self-learning with the edX course CS 188.1x Artificial Intelligence. Since the course concluded a year ago, it is in "archive mode" and there are no teaching staff to help with the questions. This also means I get no credit for finishing the course, so hopefully asking for help with a "homework" question here is okay.

In the first homework assignment the following question is asked:

Question 9: Hive Minds Lost at Night It is night and you control a single insect. You know the maze, but you do not know what square the insect will start in. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, the insect will be on the exit square, regardless of initial position. The insect executes the actions mindlessly and does not know whether its moves succeed: if it uses an action which would move it in a blocked direction, it will stay where it is. For example, in the maze below, moving right twice guarantees that the insect will be at the exit regardless of its starting position.

Sample maze

It then asks the size of the state space. The answer is given as 2^MN, where M and N are the horizontal and vertical dimensions of the maze. Why is the answer the power set of MN? In my mind, the bug can only be in one square at the beginning, and we only have one bug, so I know the number of start states is MN. But the number of start states != state space, and that is where I am confused.

FYI - the cost per move is 1, and the bug can only move 1 square left, right, up, or down at a time. The goal is to get to the X (goal square).

Solution

  • Okay - I think I got it.

    Set of all subsets (power set*) is exactly the right way to think about this. The state space is the set of all states.

    1) Definition of state:

    "A state contains all of the information necessary to predict the effects of an action and to determine if it is a goal state." (http://artint.info/html/ArtInt_48.html)

    The actions in this scenario are simple: left, right, up, down. They are the possible movements a bug could make.

    2) Definition of solution:

    Solutions are sequences of actions that lead to the goal test being passed.

    If we only permitted MN states, one for each possible starting position the bug was in, then we would have a state space that gave solutions that were valid only for discrete starting positions. But, the solution must be valid regardless of the initial state of the bug. This means the solution must work for scenarios in which the bug could occupy any of the MN available squares.

    In other words, the solutions must be valid for each and every subset (combination) of possible starting spaces, which yields the power set of MN, which is 2^MN.

    Why? Because solutions that are valid for a given start state may not be valid for all other start states. And the problem requires us to find solutions that are valid for all start states. This is also why the state space is much larger than MN even though in reality our bug only occupies 1 of the MN positions upon initialization. Just because a solution (sequence of moves) works when the bug starts at (1, 1) doesn't mean that solution (sequence of moves) will also work for the bug starting at (2, 1).

    Bonus Question: Why isn't the state space just 1, the full set where each of the MN squares 'has' a bug (and bugs are permitted to move on top of each other)?

    I was tempted to say that just because a sequence of moves gives a goal state when the bug can start at all of the MN possible positions, that doesn't mean that same sequence of moves gives a goal state when the bug starts at (3, 2) or at MN - 1 or MN - 2 etc. possible positions. But by definition it must (a solution over all starting points must be a solution over every finite subset of starting points).

    So I think the reason you evaluate starting states other than "all boxes have a bug" is because the solution generated by evaluating only that state may not be optimal. And in fact this interpretation is borne out by what the homework gives as admissible heuristics for this problem:

    The maximum of Manhattan distances to the goal from each possible location the insect could be in.

    OR

    The minimum of Manhattan distances to the goal from each possible location the insect could be in.

    The case where we just have one starting state with bugs on all the boxes (with the magic ability to be on top of each other) is the relaxed problem we use to define our heuristic. Again by definition of admissibility, since the heuristic must not overestimate the true (arc) cost of an action, and since arc cost is given by Manhattan distances, both the heuristics above are admissible. (The maximum case is admissible because each possible location for the bug is, in fact, possible - thus the max cost is possible).

    *If you don't know what power set means, all you need to know is that the power set is the set of all subsets of a given set. It is given by 2^(size of the set).

    In other words, if I have a set of three balls {red, blue, green} and I want to know how many different subsets I have, I can calculate it as follows. A subset either has the element in it (1), or it doesn't (0). So {0, 0, 1} would be the subset of only the green ball, {1, 1, 1} would be the subset of all the balls (yes, technically this is a subset) and {0, 0, 0} would be the subset of none of the balls (again, technically a subset). So we see that the number of all subsets is 2^3 = 8. Or in our problem, 2^MN.