Okay, let's start.

Yesterday we started looking at a second algorithm for planning.

It kind of has the central idea of the most influential systems currently,

which is just relying on essentially greedy search with heuristic.

And the trick here is in relaxed planning that at every step we map the current state into a state of the relaxed problem.

In our example with the delete relaxation, that was just the identity.

Then we optimally solve the planning problem in the simplified system.

Then we count the length of the plan and that gives us our heuristic for the upstairs planning, for the real world planning.

And we've seen in one example that this actually works well in restricting the search spaces in the real world search.

While being relatively easy, the optimal planning for the heuristic was relatively easy.

Mostly after a couple of seconds you had done it by hand and most of it was correct.

So in some way most of the current best algorithms take this idea.

That's probably going to change again. We never know what innovation is around the corner.

But that's kind of the best of breed general framework at the moment.

This can be extended. We've only looked at kind of non-optimal planning at the delete relaxation level.

Optimal planning there is actually NP-complete and it still pays off.

So there's a couple of kind of incremental tweaks and so on to this idea.

There are approximations to optimal planning which are still good enough while being polynomial.

So those kind of things happen and of course we can also use many of many other ideas that have been kind of successful in other places.

Landmarks is a typical example. If you want to plan a detailed way from here to Frankfurt Airport,

then you kind of make a detailed plan in isolation to the train station in Erlangen.

You know what to do. And then you kind of use Erlangen as a landmark.

And that makes the planning process much simpler.

Even though there might be a plan of catching a horse buggy to Nürnberg directly and so on.

That turns out better, but the plan space is much wider. So landmarks actually help you do things.

All of those can be somehow baked into this search process, but we're not going to look at that.

There are pruning and decomposition methods.

We've already seen the kind of duplicate pruning in greedy search in the example, which helped us very much.

But there are more advanced decomposition methods that we can use.

Okay, are there any questions so far?

The next thing I would like to start is a chapter which we call acting and planning and also searching in the real world.

We have so far been looking at the very simplest of environments.

You remember we classified environments when we started out.

Static versus dynamic, fully observable against partially observable and all of those things.

And of course I told you then and it should be clear to you by now, is that the real world is always the opposite choice of what we did in AI1.

But of course you have to do the easy stuff first.

I would like to give an outlook for the next semester where we're looking at all the other choices and develop the math to do it.

We kind of look at the first bits and pieces in the remaining three lectures here.

Right.

In the real world, things go wrong, which means actions aren't always deterministic.

And actions being deterministic, we've assumed all along in this semester, except in the beginning where we defined a search problem to have a successor relation.

And then the next slide where we kind of took a little bit of care to do that, we will look at this in a little bit more detail.

We're going to look at conditional planning and so on.

As we've seen, planning and search are largely the same.

So anything we say here in this chapter also applies to any other search technique, not only to planning.

Right. So you're driving along in your somewhat artistic car.

You have a flat tire.

What do you do?

So the situation really is we have a start node, which basically we have a situation where we have a car, we have a tire.

We assume that the spare is not flat, meaning it has air in it, that it is intact, and that is off, meaning not on one of the wheels.