# Search on Conformant Problem: solution for subset of a belief state

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?

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.
• 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. – namesake22 Jan 29 at 15:28