PowerPoint Presentation
Classical Planning
Pattern Databases
Copyright By PowCoder代写加微信 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 planning behavior
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 DTG’s 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, we’re 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 we’ve done it one-time, we don’t 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?
Let’s 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 we’re 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 isn’t an easy problem to solve and – if you’re 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 doesn’t really matter.Just so long as they’re down there.
By removing the numbers on the other tiles, we have actually established a sub-problem of the original problem.We’re 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, we’re 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 we’re 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, we’re 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, let’s quickly cover the process of how we’re 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.It’s going to group states together such that the overall number of states is now smaller and faster to search through.And don’t worry, we’ll 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 that’s our pattern cost.One of the reasons we go backwards from the goal state, is that we’re actually going to have a much smaller search tree thanks to the abstraction.This isn’t going to be obvious straight away, but we’re 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 we’ve 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 we’re not really interested in that, we’re 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 let’s 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 it’s actually an abstract state comprised of four different state.
And with this, we can search back and count that it’s 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 we’re 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 pattern’s influence on the state space, given here we have a significant number of states that aren’t 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 we’re 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 we’re 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 we’re 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, let’s 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 don’t 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 we’re 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]
Reviews
There are no reviews yet.