[SOLVED] IJCAI95), pp. 1636

PowerPoint Presentation

Classical Planning
Landmarks for Planning

Copyright By Assignmentchef assignmentchef

6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Hello and welcome to this third chapter on classical planning.In this chapter were going to look at landmarks, a measure for understanding elements of a planning problem.Once we have established this, we can then begin to use landmarks in the next chapter as an alternative for domain-independent heuristics.

Domain Independent Heuristics
Building heuristics that can adapt to different domains/problems.

Not reliant on specific information about the problem.

We analyse aspects of the search and planning process to find potential heuristics.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

As discussed in the previous chapter on the RPG heuristic, we need to find heuristics on the fly, given we cannot anticipate that these heuristics will be in place when the designer comes up with the planning domain in the first place.

Relaxed Planning Graph Heuristic
Relaxed Planning Graph (RPG) heuristic creates a simple layered approach to exploring the state space.

Inspired by the GraphPlan system
GraphPlan covered later in this module.
For reference, see (Blum & Furst, 1995)

The relaxed solution plan
Where each Oi is the set of actions selected in parallel at time step i, and m is the number of the first fact layer containing all goals
h(s) := |Oi|
Blum, A. L., & Furst, M. L. (1995). Fast planning through planning graph analysis.
In Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI95), pp. 1636

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

One possible solution to this is, as discussed in the previous chapter, use of delete relaxations, meaning we ignore the delete effects of actions during execution.
This creates what is known as a relaxed problem and if we solve it optimally, it creates a useful heuristic for understanding how far away we are from the final destination.
And so this is but one way we can build a heuristic that improves out search process.

Landmarks: Constraint-Based Heuristics
Understanding and exploiting constraints that encapsulate facets of every possible solution of a problem.

Some of these constraints can be denoted as landmarks of the solution.
Landmarks must be true at some point in every plan generated.

Landmarks can be ordered to dictate the order in which they should be achieved.

We aim to discover landmarks and their ordering automatically from the problem.
Jrg Hoffmann, and.
Ordered landmarks in planning. JAIR 22, pp. 215278, 2004

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So the an alternative to using simple delete relaxation is to try and analyse the problem as it has been provided and from that establish constraints that would encapsulate facets of any valid solution to the problem.These constraints are what we call landmarks, information that must be true at some point in the final valid plan.And as well see this can include both facts as well as actions that can appear at some point.We can then order these landmarks to dictate the order in which they should be achieved.

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

There are three key facts were interested in for this chapter:
Fact landmarks which are simply variables that need to hold a specific value in at least one state in the final plans execution.
Action landmarks an action that must be applied in the solution.
Plus there are disjunctive action landmarks, which is a set of possible actions that can be applied in the solution, giving us a little more free reign.

Returning to our example from the previous chapter of Freecell Solitaire.Landmarks in Freecell could be the fact that the Ace cards appear on all the foundations, or the set of actions that move cards off a tableau and onto a foundation.There are many possible landmarks either facts or actions that will prove very useful at some point during the execution of the plan.

Landmarks Example

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

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So lets look at an example, of the logistics domain, where we have a package 0 and we want to get it from the starting location B and in the goal have it reach location E.
In order to do this, well need to use the truck and the plane p in order to get it there.

Landmarks Example

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

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Through analysis, we can actually generate numerous fact landmarks for this problem shown on the right.
We can see at the top that having both the package and the truck are good landmarks, given this allows us to then have the package on the truck.
Plus once we get the package and the plane to c, we can then get the package onto the plane and ultimately to the final destination.

How Do We Find Landmarks?
We also need to find good landmarks, given some will not be informative.
The set of all possible actions is technically a disjunctive action landmark.
Every variable that is true in the initial state is a fact landmark.

But finding landmarks can be as hard as planning itself (PSPACE-complete).

Can exploit the relaxed planning graph technique to generate landmarks.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So how do we find these landmarks?And perhaps more critically, how do we find good landmarks.Given many landmarks can be rather uninformative.Technically, every variable in the initial state is a fact landmark. But thats not at all useful, given you will satisfy all of these as soon as you start searching.

But the problem is that finding landmarks is just as hard as planning itself, sitting in PSPACE-complete complexity.

Why is it P-Space complete?Well its actually quite easy to prove even simplistically, given we know planning itself is PSPACE-complete.In order to prove an action or fact is a landmark, its the same as deciding if you can solve the problem without either the action itself or in the case of the fact the action that generates the fact.Meaning youre just planning again.

Finding Landmarks # 1: Deletion Relaxation w/ RPG
Delete Relaxation Landmarks

Iterating through all actions
Remove an action if it adds a fact to the planning problem.
Build the relaxed planning graph.
If the goal no longer appears in the RPG, then the action was a landmark of the problem.

It works, but has issues.
Slow to execute..

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The easiest way to generate landmarks, is to adopt the deletion relaxation once more.Try removing a specific valid action from the if it adds a fact to the problem, generate the relaxed planning graph from there and if the goal no longer appears in a future fact layer, then we know the action was a landmark to the problem.

Problem is this is slow to execute, given were trying each of these actions one at a time and then essentially attempting to just run a relaxed plan solution as normal.

Finding Landmarks #2: Backchaining
Treat each goal (B) as a landmark, for each goal:
Take intersection of preconditions of all actions that achieve goal (A)
If numerous actions share A and achieve B, A is also a landmark;
A is also ordered before (must be achieved before) the goal.

Repeat for all landmarks found.

Can do a bit better (find more landmarks) by looking whether A is needed to achieve B for the first time (build RPG without A, see if B appears).
e.g. suppose there is another location F joined to E, we can drive from F->E to achieve the goal but not unless we already went through E
Ordered Landmarks in Planning.
J. Hoffmann, J. Porteous, S. Creswell JAIR, Volume 22, pages 215-278.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

An alternative to this is to use a principle known as backchaining.

In this instance we treat every goal as a Landmark and then analyse how these goals are satisfied.Then find the actions that satisfy that goal, and what preconditions they all share.If we have 3 actions that all have the same precondition A that generates that goal landmark B, then we know that the precondition A is a landmark.

Perhaps even more critically, we also know that these new landmarks are ordered before the goal landmark.

This can be further optimised by also looking to see whether A is needed to achieve B the first time it occurs.By running RPG without A and see whether B appears.

Finding Landmarks #3: RPG Propogation
Actions (numbers) take union over preconditions labels (all are necessary).
Facts (letters) take intersection of achievers labels (at least one is necessary).

Landmark extraction via planning graph propagation.
Zhu, L., & Givan, R. ICAPS 2003 Doctoral Consortium.(Example Sylvia Richter)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The third alternative is to use the RPG approach and pay attention to what facts hold true during the execution of a plan.
This propagation, whereby we take the union of preconditions of actions that achieve specific facts, helps us to establish what facts could be landmarks for the problem.

If we consider this example A is the only fact holding true in the initial fact layer, and as we roll out all valid actions 1, 2 and 3, we now have more facts, b, c and d.

This creates a situation where we have threw parallel conjunctions of facts: (a,b), (a,c) and (a,d).

But as we generate the next set of actions, we see that action 5 requires c and d as preconditions.Hence we now have the a,c,d as the landmark facts in this instance.
As this rolls out across all actions, we see the different effects of actions as add effects are implemented, resulting in different fact unions being established.

RPG Propagation: Extracting Landmarks
Finds all causal delete relaxed landmarks in polynomial time

Build the RPG not just until the goals appear but until all goals appear and we reach a layer with identical labels to the previous one (labels stop changing).

The landmarks are the labels on the goal nodes in final layer.

Possible first achievers of B are achievers that do not have B in their label.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We simply repeat this process until the goals appear and once they have, we keep generating new action/fact layers until the labels no longer change.At which point, we can then grab the goals in the final layer and check to see what fact layer unions are attached to them and voila, we have our fact landmarks, generated within polynomial time.

Landmark Orderings
It can be useful to know the order in which landmarks must be achieved.
Several types of sound ordering:
Necessary Ordering A n B : A is always true one step before B;
Greedy-necessary Ordering, A gn B: A is true one step before B is true for the first time;
Natural Ordering A B: A is true some time before B.
A n B A gn B A B

And unsound orderings (used in heuristics):
Reasonable Ordering A r B: if B was achieved before A then the plan should delete B to achieve A and reachieve B after (or at the same time as A).
Obedient Reasonable Ordering A or B: if B was achieved before A then any plan that obeys reasonable orderings must delete B to achieve A and reachieve B after (or at the same time as A).

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

As well as finding the landmarks, it can also be useful if possible to discover the ordering of landmarks, given having the landmarks will be useful in search, but we need to know when they should appear.

We can typically separate our landmarks into sound and unsound orderings, in sound orderings we know that A achieves B, but we just dont know exactly when.Hence we can have necessary ordering, where A is always true one step before B, greedy necessary which is similar to necessary ordering, but this only applies the first time B comes true, rather than every time.Natural ordering A is true, at some point?Before B is.

Further to that we have unsound orderings, where we have special conditions on the orderings of landmarks.Hence there is reasonable ordering, where if B was achieved before A, so the plan has to delete B to then achieve A and then reachieve B possibly on the same time point.
And lastly obedient reasonable ordering, which enforces a reasonable ordering.

Landmark Orderings
A B if A forms part of the label for B in the final layer
A gn B if A is precondition for all possible first achievers of B (achievers not labelled with B).

Landmark extraction via planning graph propagation
Zhu, L., & Givan, R. ICAPS 2003 Doctoral Consortium.(Example Sylvia Richter)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So given what we have already seen in this RPG rollout, we can then determine what the landmark orderings are in this instance.
Hence we can establish that label a has a natural ordering over e, f and g, given it occurs at some point, prior to their appearance.
Meanwhile for f, both c and d are have greedy necessary ordering over f, given they both occur in the preceding fact layer for the first time, while f also appears for the first time.

Classical Planning
Landmarks for Planning
6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

As we wrap up this chapter, we now have an understanding of what landmarks are and how they can be found, and in the next chapter, we will then explore how we can use them as part of search.

/docProps/thumbnail.jpeg

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