I am having trouble understanding the following statement.

I have understood why in a sensorless/conformant problem, if there exists a solution (a sequence of actions) for a belief state $b$, then it is also a solution for any $b'$ that is a subset $b$.

Next claim is what is confusing me.

Then in a standard graph search, we can save time by pruning some branches from the search tree.

Example from the Sensorless Vacuum World problem in Russel Norvig.

When we have a successor $\{1,3,5,7\}$ generated during graph search, we do not add it to the frontier if we have already expanded the belief state $\{5, 7\}$ which is a subset.

I thought those cases are totally unrelated since each belief state may encode a different path from the start state. If $\{5, 7\}$ does give us a solution, we have no guarantee it will work for $\{1, 3, 5, 7\}$. It's also possible $\{1, 3, 5, 7\}$ can lead to a solution through a different path.

I must be missing something.. can someone please explain?


1 Answer 1


'different path from the start state': The sensorless vacuum world is by definition a 'single-state problem', that is, all variables in the world are incorporated into a single state variable. In that case, history doesn't matter. If we are in state 5 by one path, the world is exactly as it would be if we had got there by another path.

For an example of something else represented as a single-state problem, consider chess: you might say history matters because whether you can castle, depends on whether the king has moved, not just the current board position. Okay so if we represent chess as a single-state problem, then the state would encode not only the current board position but also other relevant variables like whether the king has moved.

Subsets: if we know how to get to {5,7}, we don't need to be interested in {1,3,5,7}. Getting to {5,7} gives us all the same information plus more besides.

  • $\begingroup$ If we are at $\{1, 3, 5, 7\}$ and through some seq of actions, we can get to a goal state of $\{1\}$ without going through $\{5, 7\}$ on the way. As for $\{5, 7\}$, we may find out, after a few expansions, that doesn't get us to goal state. What may be more concerning is that we could have generated $\{5, 7\}$ through some state that was not $\{1, 3, 5, 7\}$ in the first place. I'm concerned that if we prune away the search tree branch that is rooted at $\{1, 3, 5, 7\}$ because there is a state that is a subset of this, we are pruning away a path to what may be the only solution in this case. $\endgroup$
    – namesake22
    Jan 29, 2019 at 15:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.