What have we done?

We've, in a little bit more depth, explored a very important practical problem, which

has given us a heuristic that will, independent of the problem, give us relatively good heuristics

by computing a heuristic in a relaxed problem, H+.

The problem is that we have something that is still NP-hard.

We have to, size of the problem often, add something that is also size, that can get

big, depending on how many actions we have.

So there might be an exponentiality somewhere in there, and indeed you have all, you have

all the kind of problems you always have in there, even though it's a huge win.

You can actually, in the general, look for better general relaxations, and that's really

what's going on in planning.

But essentially, all state of the art planning systems have some kind of a delete relaxation

built into the system at a very central place.

These kind of relaxation things there have, in the last 10 years, actually been more successful

than things where you just take the planning problem, reformulate it as a SAT problem,

and then use a SAT solver.

So these kind of things are now better.

It's an active research area.

There's a lot of stuff that one can still do, but I would like to spend the last one

or two lectures talking about online planning, essentially.

Remember, we started out with our problem solving, with the distinction between online

problem solving and offline problem solving.

If you're in a completely deterministic and discrete and observable world, then you can

do what we've been doing here, namely, don't sense it all, plan things through, because

everything is deterministic and single agent and so on.

There's nothing that can get into your way, and then just leave your brain at home, execute

your plan.

But of course, we know that the world isn't like that.

Things can go wrong, and how we deal with that, I would like to spend a little bit of

time next week, and even much more time in the next semester.