0
$\begingroup$

I have been reading about AI search, specifically the toy vacuum cleaner problem and I would like to code an example of this but I am finding the description of the state hard to get my head around.

The problem states that the AI needs to be able to move between squares, either left or right and if there is dirt in the square it can clean it (suck).

enter image description here

Is the state something you are supposed to hard code in advance in AI search? This seems unlikely due to the possible number of potential states for a larger problem, so I am not sure how I can represent the state in a problem like this, or any other really.

In the vacuum problem the states are 'dirt left', 'dirt right' and 'vacuum position' and an action such as 'move left', 'move right' or 'suck' will leave the problem in a new state but how do you represent these changes?

Would state be an object with boolean properties for the dirt and an int value for the vacuum position of either 0 or 1 depending on which array element it is looking at?

In the context of a map program trying to get to somewhere I do understand the state might be In(New York) but I what I am struggling with is how I would represent something like that in code, or perhaps a maze where the current state might be the x, y coordinate of the square the agent is currently in, again would an object be the right thing to use to model state?

$\endgroup$
2
  • $\begingroup$ Perhaps you could edit the question to define the "toy vacuum cleaner problem". I'm not sure there is any "supposed to"; there might be many ways to approach the problem, and some might be more effective than others. Is there some context behind the question? Is it based on something you're reading in a textbook or elsewhere, for instance? $\endgroup$
    – D.W.
    Jan 19 '21 at 23:49
  • $\begingroup$ I have added the diagram from the book "AI: A modern approach", and some text that hopefully demonstrates what the problem is, it is very simple and I am stuck on the state and transitioning between states. $\endgroup$
    – pac234
    Jan 20 '21 at 6:43
0
$\begingroup$

"State" 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.

$\endgroup$
4
  • $\begingroup$ So does that mean normally you would need to code all the possible states? When I think about a game of chess or even the 8 puzzle listed in the book that sounds unfeasible? Is someone really going to code all the potential states into an application? $\endgroup$
    – pac234
    Jan 20 '21 at 7:45
  • $\begingroup$ The diagram is show the 8 potential states and they are numbered 1-8 which is why I am unsure if they are 'discovered' dynamically, or whether they would be pre coded, as an example in the diagram, if we are in state 1 and apply the suck action then it transitions to state 3 where the vacuum is still in the same space physically but the dirt is now gone. $\endgroup$
    – pac234
    Jan 20 '21 at 7:47
  • $\begingroup$ @pac234, it depends; both are seen in practice. Sometimes they are all encoded in advance, sometimes they are discovered on the fly. In AI it is probably more common to discover them on the fly. No one would write each one down by hand, one at a time; instead they would write code that can represent all possibilities. $\endgroup$
    – D.W.
    Jan 20 '21 at 9:48
  • $\begingroup$ Thanks for the answers it was really helpful as I have now managed to create something that solves the vacuum problem, I opted to dynamically derive the state based on the currently supplied state and the action that the agent is going to perform. $\endgroup$
    – pac234
    Jan 20 '21 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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