AI Search - State in the toy vacuum problem
&quot;State&quot; is the sum of all information that describes the current situation of the robot, and everything about that past that might be relevant.  I don't understand your diagram so I can't tell you what it is specifically in your particular example, but it appears that the state includes the current location of the vacuum and which locations currently have dirt.  So, you might have one variable that defines where the robot is located, one variable that indicates whether there is dirt in the left room, and one variable that indicates whether there is dirt in the right room.
In AI search, we often assume that we know the set of all possible states and all ways to transition between them.  We give that information as input to the search algorithm, and it finds a way to reach a desired state from where we currently are.