Given these problems, there are a couple of problem types. We're going to call something

a single state problem in this general problem solving setting. If we have an observable

environment, some people are happy with just knowing the initial state, I think offline

planning. You can imagine traveling in Romania becomes much more difficult if you don't know

that you're an arad. You wake up with a total hangover and say, where am I? Well, I don't

know. I have to go to Bucharest. That makes it much more difficult. Deterministic, of

course, you can always reach the successor state, which in real world Romania is not

actually that likely. They have problems with their buses. Static and discrete. Those are

the simple ones. That's the ones we're going to look at. We are talking of a multiple state

problem. If the initial state is not or partial observable, which means hangover, where am

I? That actually means you might actually be in multiple states. That's where the name

comes from. You still have a deterministic, static, and discrete world. That's actually

what we made Romania to be by having these operators. Then you have contingency problems

where either the state space is unknown, which is a typical thing to have, or it's undeterministic

and so on. We're going to look at only single state problems and speculate, say, maybe about

multiple state problems. Let's make up a couple of more examples.

The vacuum cleaner world. We have eight states. We have a couple of actions. I've written

down the full set, the full story about this. If we're in this state and we go to the left,

because we were already in left, we stay in left so we don't leave the state. Going left

also doesn't change the dirt in our rooms. If I sock in the left room, then the left

room becomes clean. That gives me this. The only way I can leave this is by going right

and so on. This tells you the full story of states and actions in the vacuum cleaner world.

For a single state problem, you might start in... One, two, three, four, five. That doesn't

work. Let's call this one five. I don't know why, but... Oh yes, because one, two, three,

four, five. If we're in this situation here, then if we're in a single state problem, which

means I know that I'm here, I can formulate a plan or a solution by saying I need to go

right and I need to sock, which gets me into one of these two goal states. If we have a

multiple state problem, say the vacuum cleaner doesn't know where it is, so it starts in

one of those. We have eight states. It has no idea what to do. This here is a solution

why? Because if I start here and I go right, then I'm in one of those states. If I sock,

then I go to one where I'm still right, but it's clean. It could be nowhere. This one

or that one, and then I go left and then sock, and that actually brings me into state seven,

which is one of the goal states. Sometimes, very similar... Single state problems and

multiple state problems aren't that different. You have to have some notion of possibility

where I might be. We'll use that kind of perceived similarity to just basically say, oh, we're

going to stick to single state problems. You can always get to multiple state problems

by going from single states to sets of states. That makes the graph much bigger, but still

gives you the same kind of problem. Exponentially larger, but who cares? Contingency problems

are nastier. You all know Murphy's Law. If something can go wrong, it will. Say we invoke

Murphy's Law here, then sucking up the dirt may actually make a clean carpet dirty. What

do you do? You have a kind of a solution by saying sock, right sock, but it's not clear

that this actually gets you into the solution, but it has a good probability of doing so.

You don't do a lot of sucking, so the chances of making something dirty is small. There

is a better plan, which is sock, go right. If it's dirty, then sock, which needs a more

interesting plan language. This is actually not in our definition, except if you want

to put a new operation, if dirt, then sock, into your set of operations, which we didn't

have before. Those are general recipes what to do when you're not in a single state problem.

As you can imagine, there is a whole cottage industry of people trying to deal with these

things and get them right and those kind of things. That's all interesting and wonderful,

but not AI-1 material. You can think of those things yourself or read the papers. Good.