Even though this is very simple, we can already do quite a lot. We can do single state problems,

which are the most basic form of problems, which means we have an environment that's fully

observable, deterministic, static and discrete. The discrete is very important, we only have

a countable number of states, makes your life much easier. But you can also relax some of

the conditions to make harder problem classes and essentially these multiple state problems

are these that are only partially observable, but we still have deterministic, static and

discrete problems. Essentially this means you wake up somewhere in Romania, they've kind

of taken away all the street signs, you don't know the language and you have to go to Bucharest.

It's much more difficult than actually knowing where you are. A solution here would be something

that would solve the problem no matter where you start out. Then we have contingency problems,

which is not something we will be able to solve with these algorithms, because one of

the parameters in this is that we know the state space. For contingency problems either

you have non-determinism, that's something you can deal with relatively easily. But if

you don't even have a state space, then you can't really run these three search algorithms

that we have started looking at. We've looked at single state problems in these examples

and seen that there's a relatively simple extension to multi-state problems. The price

to pay here is that instead of reasoning about single states, you have to reason about sets

of states and even if we have only eight states like in this thing here, we already have that

power set exponentially in the order of two to the eight states in the one level-up, which

state problem. Okay, so, yeah, so this problem of selecting the state space is

non-trivial. It's probably the, if you're using search algorithms, that's probably

the most important design decision you're going to take. You need to have, you know,

the initial state, you have to have a successor function or a successor relation and then we have

a goal test. And we've talked about this, you have the choice of what a state is and if you have many

states then you have a very fine description of the world or probably better formulated the other

way. If you have a very fine description of the world that gives you a lot of states and if you

have a very abstract description of the world then you have few states but your actions might

actually become more interesting. While if you basically have a state description that kind of

for going somewhere that is kind of down to the step level and just an action like going from

here to the bus station is actually complex, right, whereas in a more abstract state where you basically

say, well, I have a state saying at the university or at the Hörsalgebäude and at Tecfac bus station

and so on, then this action of going from Hörsalten to the bus station is just one step. But of course

if you're back in the real world you don't know whether to go out there or to go out there or

there's another door out there and so on, right. So the more coarse-grained you have the more

difficult it is to actually make the actions happen. So essentially what you do is really a

game of abstraction and concretization and if you find out that, oh yeah, maybe planning every step

gives me, well, I don't know, 300, 400 steps or so to the bus station which gives you a huge search

space already, then you abstract away saying, well, but maybe I'll just make two states and

one action between that. But then of course for somebody who is here and doesn't know how to get

to the bus station, this action might actually become impossible. And so here finding a good

abstraction is really the art in applying these things. Okay, we've looked at a couple of examples

which we're going to use from time to time. We've looked at the eight puzzle where the state space is

essentially nine tuples of numbers. Basically we have nine positions and we can say which ones,

which number is in which place and that gives a very natural set of actions. We've looked at the

vacuum cleaner example. We've looked at one example which is really outside our reach with

these algorithms because the state space is just much too big. It's essentially uncountable which

is essentially a seven or eight dimensional real vector space.