What I want to do today is I want to wrap up planning with a little foray into the real

world and what that means for planning algorithms. Essentially foray into a world where things can

go wrong and what we can do in this case and that's going to be a preview in a way for next

semester where we'll do reasoning and AI with uncertainty. The second half will be kind of

wrap up, kind of remember what all of what we did. I saw that we have more than 500 slides which

actually have more than a thousand actually frames and so we covered quite a lot and I will try to

kind of bind together again. Okay so last week we talked about how to do planning. Remember planning

is really only problem-solving just like in the beginning but at the inference level, the description

level which has its good things namely lots less states but it also has bad things namely that we

have to take care of what is sometimes called the frame problem. Namely if you do an action it has

effects but the most important thing is that most things in the world around you aren't affected by

the action. If I fall over, lie under the table, you'll still be sitting there. The way we deal

with that in planning is that we explicitly mark for every action the things that changes and

everything that's not changed by these actions, updates and down dates of the state, everything

that's not affected by these updates and down dates doesn't change. Gets us a little trick

actually that gets us around stating everything that stays the same. Since lots of stuff stays

the same it's better actually to say what no longer is the same and that's the idea of planning

operators. And of course like any other innovation we're doing this means we have to reconsider all

the algorithms. Some things we can just carry over and some things we have to do extra tricks

on and we've seen how that works with the strips or PDDL planning and the thing we looked at last

week was how to actually get heuristics going and here the idea was the same we had in black box

space state problem solving, namely to relax the problem. And we looked at two relaxations. One is

to get rid of preconditions which is kind of if you think of getting rid of the map, you can drive

everywhere which makes the problem very simple. Gives a good heuristic by the way. But in planning

you want to kind of do that irrespective of the problem. And the idea there is we have a problem

class, we can't compute the perfect heuristic for that, but we can relax the problem class to a

simpler problem class for which we can compute the perfect heuristic. And then the idea is to use the

perfect heuristic for the simpler problem as an approximative heuristic for the stronger problem.

And under very wide conditions this is going to lead to admissible heuristics which is good for

social algorithms. And this idea we've played through in very much detail for two heuristics

on a very simple example. We have this logistics example, we have a truck, we have a packet,

we have four cities and what we want to do is we want to get the packet from C to D and have the

truck in A afterwards. Which is something that's easy to write down, it's a very small problem,

it's just chosen to be big enough that it's not completely trivial and small enough that I can

still get it on one slide so that you can still see something. We looked at this only adds relaxation

which means we drop the preconditions, we drop the deletes and that makes everything very easy. I use

this as a way to kind of set up the whole example and the important idea here is that we have

heuristic exact search at the unrelaxed layer and we need to have that to get an exact plan. We're

not interested in the approximative relaxed plan, we're only interested in the length of the

approximate plan. To use that as a heuristic, we're planning in the relaxed problem and we're

throwing away the plans, very important to know. Well we're not throwing them away directly,

we're just counting how long they are so that we have a heuristic well. And that's what we're

doing, we're always alternating between the real problem and the relaxed problem and we do planning

in the relaxed problem only to get at the length of the plan. We're not interested in the solutions

of the relaxed problem because it's not the real world, you can do things there that you can't in

the real world so we want to have real-world plans and these aren't. You can't solve the problem by

just driving from B to A and unloading in D. Would be nice, impossible, so it has no worth other than

an estimate of how long it takes. And we use that estimate to actually steer the plan generation

through the search space at the real level, which is something we did. And here you can see the

search unfolding and you can see even though we do have a heuristic, the value is almost always