In this video nugget, I would like to cover the case where we search and or plan.

As you remember, those are essentially the same, but there was different levels of representation

with non-deterministic actions. We are mostly going to introduce this by example. So, what

we need here, since the actions are non-deterministic, we cannot really rely on the state we want

to reach by an action, actually, to be reached. For that reason, we need something that is

called conditional plans, which just basically have kind of conditional actions or steps.

What these conditional actions is they have a condition C, and basically they basically

allow you to choose between two subplans depending on whether the condition is quote unquote

true. And how do we know that it's true? Well, we see whether the knowledge about the world,

the knowledge base the agent keeps and updates, and the percepts together and tail C. We have

an inference entailment step here that may be non-trivial in planning, whereas in search,

it's usually very trivial. We just basically know whether certain states support certain

conditions. And then we have something of the way we are going to use this syntax if

C, then plan A, else plan B, phi or something like this.

So those are, if we allow these plans, then we say that these, we have conditional plans.

But if we also just limit the possible percepts to determining the current state, we're going

to speak of a contingency plan. The main thing we're going to see here is that for every,

so say we are in a state and a percept comes in, we basically, since we do not know in

advance which percept comes in, we need to have some plan for every possible percept.

Which is, well, we've seen something like this in game playing in the chapter, where

basically for every move the opponent makes, we have to have an answer. Or think in prologue

back chaining, basically for every premise, you can think of those as being the precondition

of achieving the head, we have to have some rule that matches every premise or satisfies

every premise. And that gives rise to a rather standard data structure or algorithm, which

we call and or tree search, which is kind of like backward chaining. And I would like

to go into this. I would like to use what we've called the erratic vacuum cleaner world.

So basically this has a variant of the suck action. So if we're in a dirty square, then

we have always cleaned the square, but sometimes also remove dirt from an adjacent square.

So we don't know what the outcome is, but the outcome might actually be better than

for dirty squares. If the square is clean, then we might just deposit dirt on the carpet.

So we're in this initial state, we've always been, right? And we have two possible actions.

We have a suck action and a go right action. We get to choose between those two. The agent

gets to choose. And then we have a, since the suck action here is non-deterministic,

we have two possible outcomes, which we have to determine by sensing. So we might be in,

remember when we suck in the dirty square, we might get into a situation, a goal situation

where we have a totally clean apartment, or we might be in a situation where there's still

dirt here. In this case, we can either suck, which gives us things we've seen before, either

this one or that one, one and five, or we can go right, in which case, which is deterministic.

So we have a, we only have one outcome, which is there's dirt here, we can suck. And since

we're in a dirty square, we end up in a goal state. If we were to go left, or in this case,

go right, there are lots of other states, which we don't even care about because we

found a goal. We found with depth first search, say, we found a goal. Actually, we found a,

we found goals on all the branches here. And the important thing here is we've found loops,

which we will see how we get to do them. But if we basically have goal, all goal leaves

and loop leaves, we're done. And now we can read off from this situation, a plan, we first

suck, then we have an, an and node, where depending on the state, in this case, we're

doing contingency planning. If we're in state five, then we go right and suck and go to

a, else we're already in a goal state, we do nothing. Okay, very simple. Okay, so what

we've seen here is an instance of what we call an and or tree. So these are important

data structure and arteries are important data structures for representing problems