That gives us the heuristic.

Here's my improved picture again, where we now have actually Plan X plus as the problem

class for the heuristic.

And the important thing here is that Plan X plus is something easy.

Easy for any domain.

And the important thing here is also, and there's engineering decisions here, whether

we do kind of optimizing or satisfying planning here.

This algorithm, which solves Plan X, gives us one.

There might be better ones that give you shorter plans though.

There you could have domain dependent things like having a couple of preconditions or leaving

out preconditions or so.

Of course, if you want to convince your parents and their tracking company to use your heuristic

rather than the standard heuristic, you would have to redo this kind of a proof that it

actually does what it's supposed to do and find an algorithm that kind of deals with

your better heuristic.

Doable and maybe even worth it, but I want to stick to the general case here for the

course.

So the question is, do we want to optimize at the relaxed level or not?

If you want to have admissibility for the heuristic, then you need to have optimized

plans.

You must be.

So if you think about it, you have somewhere the optimal heuristic.

You want to have this here.

You compute this heuristic.

Now if you give yourself too much leeway and allow too bad plans, then you can just inadvertently

do something like this and then admissibility would be lost.

So if you insist on admissibility so you can actually guarantee optimal plans for your

unrelaxed problem, then you have to basically look at plan land plus.

And here we get something, but we also pay something.

We have to do optimizing planning at the lower level.

But we can convince ourselves that H plus, the heuristic you get by shortest plans at

the relaxed level, that this is admissible, which is exactly what we want, and now we

can A star or 3D away.

Which we're now going to do.

So same situation, we start out with AC, we go down to the relaxed problem, we get a heuristic

value of 5, which is nicer than 2, not 1 at this case, but we still drive from A to B

because that's still in the unrelaxed situation the only thing we can do.

Good.

So back to the next step, what's the relaxed problem?

And now you can see that this is one plan, and it's actually a good plan because we still

have to drive from B to C, we load in C, we drive from C to D, we unload in D, and we

have to drive back here.

And since we're not deleting stuff, we can drive back in directly.

Because at that point, if we drive back to A, then since we're deleting nothing, the

truck is still in A and B, which allows us to drive to C.

Okay, so we have another value of 5, and we explore going to C, at the relaxed problem,

we still have a level of 5, right?

Why?

Because we always have to drive back from C to A, nothing is changing in this initial

state.