[SOLVED] CS IPC 2008 Winner Satisfycing Track)

PowerPoint Presentation

Classical Planning
Searching with Landmarks

Copyright By Assignmentchef assignmentchef

6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Hello and welcome to this fourth chapter on classical planning.In this chapter were going to look at how to use landmarks as a basis for guiding search as an alternative for domain-independent heuristics.

Fact Landmark
A variable takes a particular value in at least one state.

Action Landmark
An action must be applied in the solution.

Disjunction Action Landmark
One of a set of possible actions must be applied.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

In the previous chapter we discussed landmarks, constraint-driven heuristics that is designed to encapsulate useful pieces of information that must occur in any plan.
Landmarks can encapsulate facts that must be true at some point during the plan, actions that must be applied during the planning process either individually or in a set.

Landmarks Example

Examples c/o
Landmarks in Heuristic-Search Planning
ICAPS Tutorial, 2010

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And its critical that we find good landmarks for a given problem.Since many basic things about the problem such as the suite of all valid actions and even the initial state can be considered landmarks, we need to find useful landmarks and we discussed different techniques such as

Making Landmarks Useful
So we can establish landmarks, but how can we use them?

Provided we generate the landmarks (and their orderings) in a pre-processing phase prior to planning we can then use them during search in different ways

Landmarks as Planning Subgoals
Landmarks as Heuristic Estimates
Admissible Landmark Heuristics

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So given that weve established how to find landmarks in our planning domains, what do we then do with them?
Ideally we have processed the problem prior to the planning phase beginning and as such we can use them as well as any landmark graphs weve established throughout the planning process.

There are three ways in which we can really exploit landmarks, as subgoals for planning, as heuristic estimates or as admissible landmark heuristics.
In this chapter were going to cover the first two, but there will be additional resources on KEATS available for reading up on this in more detail.

Landmarks as Subgoals
Simple approach: plan to one set of landmarks, repeat until all landmarks satisfied.

Given some landmarks and a (partial) ordering on them.
Set the goal to (a disjunction over) the first landmark (s), according to the landmark graph, find a plan;
Now update the initial state, plan to the next landmark(s) etc

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So using landmarks as subgoals is actually pretty straight forward.We plan to each set of landmarks and repeat until all landmarks are satisfied.
Provided we have the landmarks and a partial ordering of when they occur, we set the current goal to be a disjunction of the first landmarks on the graph.
We then plan towards it and once satisfied, plan to the next landmark.

Lets take a look at an example.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So we are returning to this logistics domains and in this instance we have two goals: the first is one of the earliest landmarks, that the package is in the truck.
But we also have the plane being at location C as a main benchmark.But were going to now plan towards solving one of them.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We put the package in the truck, satisfying the landmark and adding a new action to our partial plan.
Now we have a new landmark to achieve, which is to have the truck at C, which we now happens some time before the package is at C.Hence its ordered first.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We drive the truck and now the landmark has shifted to the package being at C but also that plane landmark is still waiting for us.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We unload the package, and now we only have one landmark goal, which is to get the plan to C, which we will focus on next.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The plan flies across and now the goal is the landmark of the package being in the plane.

Planning Between Landmarks
Examples c/o

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We have now satisfied all but one landmark and that will require two more actions flying p to E and then unloading o to E.But this is a very easy plan to formulate form this point.

So that was a very nice and easy example, given the landmarks inadvertedly kinda solved the problem for us.So what happens when we have a slightly more complicated and awkward problem?

That was a good one, consider another

Goal: (on A B) (on B C)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Lets take a look at the: a well-known situation in Blocksworld.This is a good example to explore, given each goal if tackled in isolation will impede the other one.Either the planner will put B on C and A cant be moved, or it puts A on B and forgets it still needs to put B on C.How does this work with landmarks?

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So we have our initial state, we then have our landmarks, which have been generated back from the goal.So our subgoals are for A to be clear and holding B, given clearing A will allow it to be held, while holding B allows us to put it on C.

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We satisfy holding B and now the two subgoals is A is clear or B on C

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And it satisfies the easiest one, meaning we are once again succumbing to the issues of the susman anomaly.Weve satisfied a subgoal, but created more work for ourselves.

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And if we then clear A by unstacking B and C, the subgoal is still hold A

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Which leads to A on B being the goal and

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Weve done it again.But we still havent satisfied the other subgoal.

That was a good one, consider another

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Meaning we still need to plan from that point again, which isnt ideal at all.

The Good and The Bad
Faster planning as the planner needs to explore the search space to a lower depth.

Can lead to poor-quality plans, sometimes landmarks need to be undone and achieved again if tackled in the wrong order.

Incomplete in problems with dead ends.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So as weve seen in just these two examples, there are benefits and drawbacks.

On one hand,planning can be very fast, given the planner has a lot less work to do, since the landmarks solve so many elements of the problem for us.

But, it can also lead to much longer plans, because as we saw in Blocksworld, we can solve one landmark, and then give ourselves more work as we have to undo it.And thats largely to do with whether they were actually in the wrong order.Although in the case of the Sussman anomaly, thats kind of the point, given neither of them should really be tackled independently.

Landmarks as Heuristics
Number of landmarks still to be achieved is a heuristic estimate.

LM-Count: A path-dependent heuristic.
We cant tell which landmarks have been achieved just from whats true in the state.

Adopted by LAMA (winner of the IPC 2008 Winner Satisfycing Track)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So an alternative to this approach, is to use the number of outstanding landmarks as a heuristic.
Given as we saw earlier with solving landmarks as subgoals, as we complete each of them we are moving closer to the final goal.
This is adopted by LAMA, which won the 2008 Satisfycing Track of the International Planning competition, and it has some interesting benefits and drawbacks.
So lets take a closer look at the heuristic.

Path-Dependent Heuristic
Consider the situation shown here
Did we achieve the Holding B landmark?

Achieved landmarks are a function of the path taken, not an observation of the state.

Hence LM-Count is an inadmissible heuristic.
One action can achieve more than one landmark.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

LM-Count, which is heuristic used in LAMA, is what is known as a path-dependent heuristic.
Unlike the heuristics we have used to date, LM-Count cannot be derived solely from looking at the state and calculating the value.
If we consider this example from blocksworld, can we tell whether weve achieved the holding B landmark?

I mean, you could argue it is not true, given the block isnt being held.But of course the plan is going to continue to evolve over time, and the landmark is just one fact that has to hold true at some point during the plan.
So in this case, the heuristic becomes path-dependent, because is no longer a function of the observed state but instead the path that we took in order to reach it.

But this does create a problem in that LM-Count is inadmissible, given one action could satisfy more than one landmark.Hence it can inflate the perceived value of a state as distance to the goal, despite the fact that as weve seen in the blocksworld examples this can actually push us much further away from the goal than our current state.

Computing LM-Count
H(s,p) = (L Accepted (s,p)) U ReqAgain(s,p)
For state s, path p

L: set of all landmarks discovered for the problem;

Accepted (s,p): Accepted landmarks:
Landmark is accepted if its true in s and all its predecessors in the landmark graph are accepted.

ReqAgain(s,p): Landmarks that weve seen but know we need to see again. L is required again if:
Landmarks is false and it is a goal;
Landmarks is false in s and is a greedy-necessary predecessor of landmark m (must be true the step before m), which is not accepted.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The equation for computing LM-Count is provided above for a given state s on path p through the search space.

We grab the union of incomplete landmarks with the set of all landmarks that are required again by the problem.
The former is achieved by looking at how many landmarks are true in the state and their predecessors are satisfied in the landmark graph.
Hence it ignores landmarks that have been achieved prior to others that are ordered before it.

However, the Required Again landmarks acknowledges two key issues: first any landmarks that are goals, hence ensuring we dont tick them off prematurely.
But also any landmark whose predecessors are not accepted, meaning we need to satisfy this again after satisfying those that precede it.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So the real trick here, is that this helps us tackle the Sussman anomaly.
Given if we have created the situation where we immediately attempted to tackle the on-B-C goal like before, it would actually be denoted as a false goal.Hence we need to satisfy it again and from this position, achieving these landmarks is much more achievable than before and the search can be better directed.

Admissible Landmark Heuristics
Many of the most successful modern heuristics for optimal planning are landmark based.

Not covered here but if youre interested this tutorial is a good start:

And also covers what weve seen here on landmarks and LAMAs Heuristic.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So were going to wrap up at this point, but its worth acknowledging that a lot of research into heuristics for optimal planning is based around landmarks, hence it is something that is worth having a grasp of as you explore the subject in this module.

We didnt take time to look at admissible landmark heuristics, given this is beyond the scope of what we wanted to cover.
However, you can check out the landmarks tutorial from the 2010 ICAPS which goes into this and the topics covered here in much more detail.

Classical Planning
Searching with Landmarks
6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Thanks for watching this chapter on searching with landmarks.In the next chapter, were going to consider the use of multiple heuristics at the same time when searching for solutions and how that can be adopted.

/docProps/thumbnail.jpeg

CS: assignmentchef QQ: 1823890830 Email: [email protected]