Okay, welcome to the last AI-1 lecture.

The plan for today is to complete what we wanted to learn and then maybe have a couple

of questions. Talk about the exam or those kind of things. Yesterday we talked about agents,

model-based agents, which instead of having a world state, which they keep up to date with their

sensor model and their transition model, which has a single state. We were looking at agents and

search slash planning procedures that have to entertain the possibility of multiple states,

because we have either non-dominant actions or a partially observable world. In essence,

we can do everything we can do before. The only difference is that we have to talk about

sets of states as the belief states. We're kind of moving all the algorithms one level up. The

punishment for that is that the set of states is exponentially bigger. It's still finite though.

The gain of that is that at the belief state level, the actions are deterministic. If you

have this world, this belief state, then you bake all the non-determinism of the actions into the

transition model at the belief state, which means if you start with this belief state, you end up

with that belief state without any non-determinism. Same thing for partially observable. Your belief

state captures exactly what you know about the world, which might be nothing, then the belief

state is all the physical states, or you might know certain things, then it's a subset, but actually

we can observe what about the world we know, and that's the belief state. The other thing we've

been talking about, and this is kind of a summary of this, we can still do the same algorithms one

level up. We can see that factored and structured representations of the world, where we might have

descriptions that fit kind of the physical states in the blobs with one description, they might

actually fare better. If you want to think about it, you can always transfer that into a single

description of the belief state, so for instance the lower left-hand state, which is five or seven,

you can describe in state is five or state is seven, or state is prime and state greater

than four. That would be an alternative description of it. Here it doesn't really make sense because

all this stuff is longer, but think of a description of a belief model that has hundreds of states,

then a succinct description, if we can make it, might actually be useful. So the impact of going

to the belief level, the belief state algorithm level, might actually be smaller in planning,

in using logics or CSPs or something like that. That's kind of what I want you to keep in mind,

and I would like you to think of this, the things we're doing today, kind of as a preview for the

next semester. In the next semester you're going to concentrate on the inference algorithms. What

does the agent know or consider likely? Those are the things that kind of go on in all of these

algorithms in the background. If you have an agent that ultimately is going to work with Bayesian

networks or Bayesian decision diagrams or something like this, it's always embedded into,

say, a search algorithm or planning algorithm like this. In this planning algorithm we always

have the inference component. Maybe most prominently we talked about that in the CSP chapter, where we

actually looked at the interleaving of search and inference, and all of that goes on here as well,

if we're using logic-based or factored representation of the world. Okay, are there any questions about

belief states? I would like to go forward a bit on the algorithm side. We've always looked in all

of these algorithms, conditional planning and contingency planning and all of those kind of

things. We've looked at offline search or offline planning. The more uncertain our environment

becomes, the more the offline algorithms become unattractive, because you basically have to plan

for so many contingencies that your plans are going to be massive. At some point it's just better

to take your brain along and plan as you go along, as by the way most biological organisms that show

some kind of intelligence actually do. Again, online problem solving is actually especially

helpful in stochastic environments, because you would have to plan for many, but also in

dynamic environments. Very often, intelligence beings have to improvise. If somebody gets into

a traffic accident, they bleed profusely. We can't really have a plan for that, you have to improvise,

you have to plan as you go along, react to what you're seeing. Even more so if you have an unknown

environment, as we almost always do, then you also have to go along and do exploration. You have to

explore the environment and then you can make planning decisions, otherwise you just can't.