Hello, welcome to this little lecture on partial order planning.

So remember that we talked about the Sussman anomaly, which is really a very simple blocks

world problem, which shows that planning is non-trivial.

Say we have three blocks, we have C on A and B is on the table, and we want to reach a

goal where A is on B is on C. So, of course, simple planners just split this into two subgoals,

namely A being on B and B being on C, which is the goal.

And that brings them into problem because if you want to realize A on B, that's very

simple.

You just unstack C by putting it onto the table and just move A onto the B. Now, so

far so easy.

But now if you want to actually get to the goal, say you have to move both A and B onto

C, but you can only move one block at a time.

So you kind of destroy the subgoal of on A, B.

Dually, if you first try to solve the subgoal on B, C by moving B onto C, very simple, you

end up with this kind of a big stack.

But again, if you want to have the goal, you have to destroy the subgoal here.

So indeed, planning is non-trivial.

And I want to show you briefly a version of planning, partial order planning it's called,

that can solve this very well.

It's called partial order planning, and we start with the notion of a partially order

plan, which is very simple.

Instead of having fully ordered plans where we commit about the order of steps totally,

we just think of them as being partially ordered.

So some steps might be unordered.

So what is a partially ordered plan?

It's a plan.

It has a start and a finish step, and those steps are actually actions that, actions with

a description of their pre and post conditions, of their effects.

And we just add the start step, which just basically has the initial state description

as its effect and a finish step, which has the goal description as its precondition.

And then, and I'm going to show you a little example here, we have a partially ordered

plan for shopping for bananas, milk, and cordless drill.

You have the start, and as a post commission, just starting the plan actually initializes

the state with being at home, knowing that the hardware store sells a drill, that the

supermarket sells milk and bananas.

And we have duly the finish line, which has all the, that has the goal state as the preconditions,

the idea being that you can finish the plan if you've achieved all of those.

So and then we have causal links between steps, between actions, that basically gives you

an effect if you have P as an effect of the one and a precondition of the other, then

you can basically achieve P by going from S to T.

You may also have temporal orderings between pairs of steps, that's something we're going

to get to.

So and you basically want to use these causal links to achieve preconditions, and open conditions

are those that are not achieved yet, so that are not causally linked.

We call a partially ordered plan complete if every precondition is achieved.

And the, so we have an achieved precondition if it's an effect of an earlier step, and

nothing that can kind of get in between that undoes it.

All of this might be a little bit confusing.

We're going to have a nice notation for this, which I'm going to introduce next.

So the idea is that we take strips actions and have a nice notation for them.