[SOLVED] PowerPoint Presentation

PowerPoint Presentation

Classical Planning
Pattern Databases

Copyright By Assignmentchef assignmentchef

6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Hello and welcome to this chapter on Optimal Planning and in this chapter were going to look at another means by which to help us improve our search process with what is known as pattern databases.

Recap: The Perils of Expressivity
By having such an expressive formalism, state spaces can begin to explode.

How do we circumvent this?
Use heuristics to guide the search?
Find landmarks to give us sub-goals to solve?
Use local search (see EHC)?

Often sacrificing completeness of search in an effort to find a solution quickly.
Hence Best-First Search fallback in EHC.

What if we instead sacrifice expressiveness for efficiency?

Image Credit: A hierarchical neuronal network for planningbehavior
PNAS November 25, 1997 94 (24) 13293-13298

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

In the previous chapter we discussed the perils of expressivity.This idea that as we introduce more variables to a problem, as well as predicates and actions that help us understand and transform information about that variable, it results in an exponential growth in the number of possible states.This is a real issue, given even something as simple as adding one new block to a blocksworld problem results in a massive increase in the number of possible states.

And so we began looking at the idea of how we can optimise the planning process, potentially by analysing elements of the problem and reformulating it.

Recap: SAS+ Planning
Optimising planning by analysing the problem.

SAS+ Planning re-encodes existing problem into new formulation.

Use of DTGs help us visualise assignment of variables to values during search/execution.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And this led to us taking a look specifically at SAS+ planning, which is a process whereby we take the original problem encoding and how we can revise it in such a way that it should help optimise the planning process.
This new encoding identifies the constraints that exist in a given problem given there are mutual exclusions on specific combinations of variables such that we can reduce the number of possible states that exist which in turn is very useful for optimising search.

So while SAS+ is all about reformulating the problem to make the state space smaller, in this chapter, were going to consider something a little different: what if we can analyse the problem to help us automatically generate a one more heuristics, such that it can guide us the search space more optimally.

Pattern Databases
Problem: Planning is hard and expensive.
We want to find a way to speed up our exploration of the search space.

Solution: Store solution costs for sub-problems within the search space.

Solution costs to sub-problems will provide an admissible heuristic to solve the actual problem.
Heuristic calculation becomes very fast (database lookup).

Searching backwards from the goal, record costs of states.
An expensive albeit one-time calculation.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

In this chapter, let us consider a rather different approach, known as pattern databases.
Given that we know planning is a PSPACE-complete problem, we are always looking for new ways to speed up the process.More specifically, we want to change how we explore the state space.
So pattern databases proposes a new idea: what if we can establish to cost of solutions to problems that are subsets of the current problem?
If we can calculate these subproblem heuristics, they will provide us with a very fast means to calculate during search of the main problem what the heuristic value is.
This is even more relevant when we consider that the solution cost to a sub-problem will be an admissible heuristic to solving the actual problem itself.
To do this we can search backs from the goal and record the costs of states as we do so.
This is going to be a very expensive process to run but, once weve done it one-time, we dont need to do it again and ideally, it should mean that the latter search process runs much faster.

Why Heuristics for Sub-Problems?

Image Credit: Graphplan and Advanced Heuristics
A. Tate and G. Wickler, AIPLAN, 2014

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

But why would solving sub-problems make for good heuristics?
Lets consider the 8-puzzle problem, whereby we have a group of tiles, numbered one through 8 and the idea is that we use the one available empty slot to slide one tile at a time.
Over time were going to solve this problem by moving the tiles around such that they are ordered 1 through 8 in sequence from top to bottom.

This isnt an easy problem to solve and if youre like me you would try to go about solving this by fixing parts of the problem gradually along the way.

Sub-Problems and Heuristics

Sub-Problem: Removing some complexity of the original problem.
Solution cost will be less than or equal to the optimal solution of the original.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If we were to ignore some of the tiles, it becomes an easier problem to solve.By removing numbers 5 through 8 and simply acknowledging them as any number, then we can calculate a solution that ensure 1-4 are in the correct position, but the rest of it doesnt really matter.Just so long as theyre down there.

By removing the numbers on the other tiles, we have actually established a sub-problem of the original problem.Were only interested in 1-4 being in the correct place.
Now if we were to calculate the solution to this problem, the actual cost of the solution in this case the number of moves made will be either less than or the equal to the number of moves required to achieve in the optimal solution in the original problem.In a similar way to delete relaxations, were creating a variation of the search space that is guaranteed to produce an easier problem to solve.

So ultimately, solving a sub-problem optimally will always produce an admissible heuristic to the original problem.

Partial specification of a given state.
Information is incomplete, abstraction of original state.

Target Pattern: partial specification of the goal state.

Establish a Pattern Database (PDB)
Set of all permutations of the target pattern.

Calculate pattern cost.
Compute distance to target pattern.
Minimum number of actions to achieve target pattern.

Target Pattern

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

What we have built is what is known as a pattern: a partial specification of a given state in the problem.And this is actually a representation of what we would call an abstraction of the state space.Which is a point I will be returning to in a few slides from now.But for the purposes of our Pattern Database, the PDB, what were looking for are target patterns: partial specifications of the goal state.We want to find all permutations of the target pattern, so different partial specifications of the goal.This could mean in this case we have one target pattern where only the number 1 is in the correct place and the rest are stars, or possibly every tile up to number 7 is correct, although to be fair that is pretty much the goal state at that point.

Once we have all the target patterns for our problem we then calculate the pattern cost: which is going to be the minimum number of actions to achieve the target pattern.

Now this all sounds fine in theory, but it introduces a bunch of problems for us:
How do we search through a state space where each state is only a partial specification?
How do you then compute the distance to the target pattern?

Now I already gave away some of the answer to this, were going to search the abstract state space.

Pattern Discovery
How are patterns discovered in a given problem?

We search the abstraction of the state space.

Search is achieved using breadth-first-search, moving backwards from the goal state.
Actions applied are the inverse of the original.

Pattern cost = search-tree depthfrom sgoal to sinit

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Before I explain the abstract state space, lets quickly cover the process of how were going to find patterns and establish their costs.

We will generate a target pattern think of it as a function and when we apply that to the state space it creates what is known as an abstraction of the state space.Its going to group states together such that the overall number of states is now smaller and faster to search through.And dont worry, well go through an example of this in a second.

We can then search through the abstract state space, by using breadth first search backwards from the goal state.Applying the actions in reverse, and once we reach the initial state, we can calculate how many actions are applied in the abstract state space and thats our pattern cost.One of the reasons we go backwards from the goal state, is that were actually going to have a much smaller search tree thanks to the abstraction.This isnt going to be obvious straight away, but were going to discuss how abstractions work next.

Abstractions
Pattern Discovery explores the abstract state space.

Our target patterns exist within the abstract state space.

We only care about specific values in any given state, so the number of unique states is now smaller.
We have already abstracted the state space, to only the values visible in the target pattern.

But how does this work and what does the abstract state space look like?

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So as mentioned already, these patterns exist with in the abstract state space, so what does that actually look like and how does it work?

If we again look at this pattern weve established, we are only interested in this specific combination where 1, 2, 3 and 4 are in these specific positions.
But this means there are numerous possible states in the original problem where numbers 5 through 8 are in the remaining cells.But the thing is were not really interested in that, were only interested in where numbers 1-4 are.

And the reason for this, is we have applied an abstraction function that strips away all but numbers 1-4 in the state.This pattern is an abstraction that actually represents several states, all with the same shared feature of 1-4 being in the correct positions.

Abstractions
Functionapplied on a state S, transforming it into abstract state S
Function (equivalence relation) helps to remove distinctions between states in abstract space.
Hence this may result in

Maps state space into a smaller state space.
In abstract state transition system, similar states are now indistinguishable.

Abstraction Heuristic: Heuristic estimate is cost-to-goal in the abstract transition system.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Abstraction works by applying a function alpha on a given state S that transforms it into an abstract state S.
This removes any distinctions between states and only focusses on the information that is similar.
Hence for any state that has 1-4 in the correct positions, when the abstraction function is applied to them, they all map to the same abstract state.

So our target pattern that we have here, is simply a visual representation of a state in the abstract state space, having applied the function that only cares about the positions of tiles 1, 2, 3 and 4.

Our target pattern cost, is then the abstraction heuristic, the estimate of the cost to the goal in the abstract transition system.

Abstractions (Example)

Image Credit: Latest Trends in Abstraction Heuristics for Classical Planning
M. Helmert, K. Seipp, S. Sievers, ICAPS, 2015

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So lets look at a smaller and easier to understand state space to get our heads around this.Here we have a simple driver log problem of two trucks and one package.
For the sake of cleanliness, the labels have been reduced to three letters, which correspond to the package, truck A and truck B.

The trucks can only be in two locations: location L and location R.
Meanwhile the package can be in locations L and R or it can be in trucks A and B.

So if we read this diagram from the left hand side, our initial state is that the package is in Location L and both trucks A and B are in location R.
Meanwhile the goal states on the far right highlighted in green, say that the package is in Location R.
And if we look across the graph, what we are seeing is all the different paths that can arise when the trucks drive over to L, put the package on them and drive over to R and then unload them.

So what if we tried to abstract this state space?Specifically, I want to run an abstraction where I am only interested in the location of the package?What happens to this state space?

Abstractions (Example)
Image Credit: Latest Trends in Abstraction Heuristics for Classical Planning
M. Helmert, K. Seipp, S. Sievers, ICAPS, 2015
= location of package 1

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

By applying the abstraction to only consider the location of the package, we abstract the entire state space into four states.
We can see the groups are predicated on whether the package (which again in the state is the symbol to the far left) is either L, A, B or R.

Hence now the transitions in the abstract state space, are either to the same abstract state or to another abstract state.Hence in this case, our target pattern is the abstract state on the right hand, which is to have the package at location R.But its actually an abstract state comprised of four different state.

And with this, we can search back and count that its only two actions required to get us from the abstract state which represents the initial state to the goal.
Hence our heuristic value is only two in this case.

Abstractions (Example #2)

Image Credit: Planning and Optimisation: Abstractions
M. Helmert, T. Keller, 2019

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So if we consider a similar example, where the state space is ever so slightly different, given in this instance there are two packages and only one truck.
Hence in the initial state, package 1 and package 2 are in state L, while the truck I is in location R.And this time we want both packages over in location R.
This time were going to abstract the problem space in different ways, and we see how that impacts the abstract state space.

Abstractions (Example #2)
Image Credit: Planning and Optimisation: Abstractions
M. Helmert, T. Keller, 2019

= location of package 1

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Here we have applied the abstraction function that is only interested in where the first package is, hence you can see we have the three abstract states.
In the first abstract state, the package is still at location L.In the middle case, the package is in the truck and the right hand side, which is all of the states that the first package is in location R.

This is a nice abstraction to visualise and help us understand the problem, given we have a collection of states that satisfy the goal of the first package being in location R.This more accurately reflects a target patterns influence on the state space, given here we have a significant number of states that arent actual goal states to the problem but if we had a target pattern that only considers the location of the first package, then this would accurately reflect it.Once again, we have a heuristic value of 2.

Abstractions (Example #2)
Image Credit: Planning and Optimisation: Abstractions
M. Helmert, T. Keller, 2019

= location of package 2

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Then we apply a different abstraction function, whereby we are only interested in the location of package 2.We see a similar albeit different effect, given now the abstractions break up the state space in different ways.
Once again were going to have a heuristic value of 2, but this time how we explore and break down that state space is going to be slightly different.

Planning with Pattern Databases
Create a set of all state propositions in mutex groups
These are the variables were interested in.

Construct abstract problem space(s).

Construct Pattern Database

Run planning process from initial state.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So given we now have an understanding of how pattern databases works, how do we actually plan using them?

We do this by relying on a SAS+ encoding of the problem, we generate a set of propositions mutually exclusive groups.
After that were going to start constructing the functions that help us generate the abstract spaces.
This is of course a quite difficult process in and of itself, and we can do this by splitting up goals into sets and then alternate between different combinations of goals.

We then use breadth forward search from the goal state to search for solutions in the abstract state spaces and construct our pattern database.And of course thanks to the abstractions the state spaces are exponentially smaller and easier to maintain.

So to wrap up, lets look at a quick example of how we might do this

Pattern Database Planning for BlocksWorld
Initial State

(ontable d)

Goal State

(pick-up a)

P = (clear a), (ontable a), (handempty);
A = (holding a); and
D = (ontable a), (clear a), (handempty)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We have a simple blocksworld problem where we have four blocks, and in the initial state we have
And d on the table

In the goal state we want
A on the table
And we just dont care about B.

So we would try to solve this, by first generating the mutexes in the state propositions

SAS+ Encoding for BlocksWorld
G1 = {(on c a), (on d a), (on b a), (clear a), (holding a)},
G2 = {(on a c), (on d c), (on b c), (clear c), (holding c)},
G3 = {(on a d), (on c d), (on b d), (clear d), (holding d)},
G4 = {(on a b), (on c b), (on d b), (clear b), (holding b)},
G5 = {(ontable a), true},
G6 = {(ontable c), true},
G7 = {(ontable d), true},
G8 = {(ontable b), true}, and
G9 = {(handempty), true},

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

We generate our mutex groups by using the SAS+ encoding of the problem space which of course we discussed in the previous chapter.
We now have this collection of sets of mutex relations and were going to use these as the basis for our particular abstract state space searches.

SAS+ Encoding for BlocksWorld
G1 = {(on c a), (on d a), (on b a), (clear a), (holding a)},
G2 = {(on a c), (on d c), (on b c), (clear c), (holding c)},
G3 = {(on a d), (on c d), (on b d), (clear d), (holding d)},
G4 = {(on a b), (on c b), (on d b), (clear b), (holding b)},
G5 = {(ontable a), true},
G6 = {(ontable c), true},
G7 = {(ontable d), true},
G8 = {(ontable b), true}, and
G9 = {(handempty), true},

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Next we split them into groups, even doing something as simple as alternating between odd and even sets is actually enough to work with.

PDB(EVENOUT

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