Time for theory. Remember, there are two kinds of doing planning. One is

satisfying planning and the other one is optimal planning. And if you

think back at the elevator, satisfying planning as long as it's not too non-optimal

is probably sufficient. You don't have to prove to the CEO that there's no way

you could have served him earlier. The CEO would probably want to want to have an

apology if the planning algorithm was too dumb, but that's not really at the

top level. The CEO, what the CEO really is interested in, is to have a plan

how to get down to the lunch level and not see the banker who wants to have his

loan paid back and not in the elevator have to see the the cleaning lady and so

on, but only management level people up or something like this. That's

satisfying. It gets you where you want to be and you don't care that much about

optimality. Okay and that really gives rise to, in theory and it's a well

studied thing, to classes of problems. You remember we have the classes of

problems like P and NP and P space and all of those kind of things. And for

planning we introduce our own. So we have plan X which is really the question of

whether a plan exists given a domain and problem description. And then we have the

problem plan LEN which is the question is there a plan of length of a given

length. And you can imagine of course that plan X is easier than plan LEN.

If you can solve plan LEN then you can just basically take a huge number

like 20 gazillion or something like that and then that actually kind of

degenerates to plan X. And of course plan LEN in a way, especially if you give

yourself kind of an iterative deepening approach where you say oh yes we can do

it in a thousand steps, can we also do it in 500 steps? And then kind of do some

kind of an interval reducing scheme to find the optimal thing. So plan LEN

is optimal planning and plan X is satisfying planning. And then we can kind

of look at subclasses like poly plan LEN which is where you're

interested in whether you have polynomial plan lengths. Your plan is

optimal if it is as short as possible? Yes. Okay so we don't have any cost

function yet? Well we could, I mean you can map any, at the level of theory you

can map anything into anything. You can just basically say the length of a

plan is actually the length of time it takes or the length of dollars you have

to give or whatever. Okay so they're intermappable.

Plan LEN, so just looking at the length of plans and steps is the

easiest way of formulating it. And in theory we can just map everything into

it, but almost everything into everything which is the fun of the game.

Some things you can't map. Okay good. So we basically, we kind of, just like

we have for other arbitrary procedures where we are interested in

side ability and complexity, we kind of instantiate that to plans now. And then

we can do things like saying well plan X is P space heart. Remember P space is the

problem class of everything that can be decided in polynomial space. And when

you're a theoretician that is fun and when you're an AI person that gives you

an idea of what kind of algorithms you actually expect. And whenever you want to

say something is something hard then you have to recode the problem. Right? And P

space is something where it's about arbitrary computations so you always

just, you always just recode into a Turing machine because that's the

standard model. You could also recode into Scala but then it becomes more

difficult to count. So you just basically recode into Turing machines and you do

this essentially in looking at all the, at the things you have in your planning

problems and essentially everything has to be written to tape and you have to

have a couple of, and you, the other free variable is you have a couple of