This is the belief state space for the sensorless vacuum problem. So we started off here. We drew the circle around this belief state, so we don’t know anything about where we are. But the amazing thing is if we execute actions, we can gain knowledge about the world even without sensing. So let’s say we move right. Then we’ll know we’re in the right-hand location. Either we were in the left and we moved right and arrived there, or we were in the right to begin with and we bumped against the wall and stayed there. So now we end up in this state. We now know more about the world. We’re down to four possibilities rather than eight, even though we haven’t observed anything. And now, note something interesting, that in the real world, the operations of going left and going right are inverses of each other, but in the belief state world, going right and going left are not inverses. If we go right and then we go left, we don’t end up back where we were in a state of total uncertainty. Rather, going left takes us over here, where we still know we’re in one of four states rather than in one of eight states. Note that is possible to form a plan that reaches a goal without ever observing the world. Plans like that are called conformant plans. For example, if the goal is to be in a clean location, all we have to do is suck. So we go from one of these eight states to one of these four states, and in every one of those four, we’re in a clean location. We don’t know which of the four we’re in, but we know we’ve achieved the goal. It’s also possible to arrive at a completely known state. For example, we start here. We go left. We suck up the dirt there. We go right and suck up the dirt. Now we’re down to a belief state consisting of one single state, that is we know exactly where we are. Here’s a question for you. How do I get from the state where I know my current square is clean but know nothing else, to the belief state where I know that I’m in the right-hand-side location and that that location is clean? What I want you to do is click on the sequence of actions – left, right, or stuck – that will take us from that start to that goal.