Okay, let's start.

We're talking about planning and the new thing is that our actions have add and delete lists.

We're doing search at the description level, which means we have some kind of a logic for

describing the worlds we are in and then we do search.

Today we're going to go into the specifics of planning search algorithms and go through

a relatively detailed account of how relaxed heuristics, which we've learned in the beginning

about, actually perform in practice.

Yesterday we mainly looked at planning complexity and at a very concrete planning language,

this plan description language PDDL, which is essentially a language that uses some form

of first order logic written down in Lisp form with lots of brackets, which is a tradition

in AI where you can define both the domains.

The domains you basically specify the predicates you can use to describe the world and the

actions.

The actions have parameters, which is something you don't have in propositional logic.

Usually you have kind of family of actions, which is stack A on B, stack B on C and so

on and you want to write that as stack X on Y and then these can be instantiated and make

it easier to write down.

Things you have the preconditions and you have the effects and you have both positive

effects, that's the add list in strips, and negative effects, which is the delete list

in strips.

Pretty straightforward, something like that if you had gotten the task of writing down

a language, you'd probably come up with something very similar.

This is a domain description that basically tells you what the predicates and the actions

are and you can instantiate that with a problem description that tells you what the initial,

what the objects are that you're talking about, what the initial state is and the goal state.

If you have a domain description and a problem description, those two actually give you the

full idea of this and the domain description is slightly more reusable, therefore you put

it into its own file.

We looked at real world domain descriptions.

This is a domain description of this elevator example.

Actually it's a partial description, namely only the preconditions of one of the actions.

If you look at the actions here, we have parameters, we have preconditions, we have effects, only

the preconditions, which were kind of a short line here in a real system, actually become

a little bit bigger.

Any questions about such languages?

The upshot is really you can actually do whatever you want as long as you have one.

Yes, some languages are better than others, but the really important point is that you

have one that everybody uses, which makes your systems comparable.

Next thing we looked at yesterday was planning complexity.

Planning complexity is essentially looking at worst-cased scenarios for planning and

we had it before, we have satisfying planning and optimal planning and you would think that

optimal planning is much harder than satisfying planning.

Turns out that they're in the same complexity class, which means essentially up to the granularity

of measurement of exponential effects, which is really what you're going to get for PSPACE,

they're just as hard one as the other.

But then if you're accepting algorithms that are equal, if they have exponential factors

of difference, then you shouldn't be surprised that you put them into the same complexity

class.

In a way, complexity class gives us good estimates of how hard things are, but also it's a relatively

coarse-grained description.