[SOLVED] PowerPoint Presentation

PowerPoint Presentation

Classical Planning
Optimal Planning with SAS+

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 more specifically how we can try a different approach to planning by exploring it as a satisfiability problem.

Classical Planning: Material Overview
Classical Planning: The fundamentals.

Improving Search
Heuristic Design (RPG/LAMA)
Dual Openlist Search

Optimal Planning
SAS+ Planning
Pattern Databases

Non-Forward Search
SAT Planning
POP Planning
HTN Planning

Planning Under Uncertainty

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Returning to our overview back at the introduction, weve now explored the first real subject of this segment of the module, which is different ways we can improve or speed up our search process.
Now, were going to take a look at ways to optimise the planning process, given many of the things that we now take for granted, as well as what we have covered in the last segment, is both helping and hindering us when it comes to solving planning problems.

Lets take a moment to go back to our fundamentals for a minute, specifically, how do we model a state for a planning problem

PDDL defines predicates for each domain

A proposition is predicate with parameter bindings:
{(at truck1 city1)},
{(holding robot ball1)} ,

A proposition is either true or false, at any given point;
One proposition exists for everything that could possibly be true.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

To-date everything weve seen in this class is built around a domain that defines information for all problems within that space.
When a PDDL domain is given a specific problem file, this creates a series of propositions, whereby we have a predicate with a particular parameter attached to it.
This could mean truck1 is in city1 or that the robot is holding ball1.

In each case, we create different propositions based on the available variables and the constraints of the PDDL.So if were using typing, then the truck could be in a location, we may have ten locations.We may also have more than one truck.So this in-turn effectively creates a Boolean proposition for any combination of these variables for that predicate that could possibly be true at any point in the problem.

But this has its drawbacks

Propositions in Blocksworld
Lets consider the propositions in a given state of BlocksWorld.

s(A-on-B) = T
s(A-on-C) = F
s(A-on-table) = F
s(B-on-A) = F
s(B-on-C) = F
s(B-on-table) = T
s(C-on-A) = F
s(C-on-B) = F
s(C-on-table) = T
s(A-clear) = T
s(B-clear) = F
s(C-clear) = T

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So lets consider what would happen if we were to enumerate all propositions for even something as simple as Blocksworld.
So here we have five propositions that are true:
B is on the table
C is on the table
A is clear
C is clear

But look at how many other facts were encapsulating here. There are seven more propositions that are false, bringing it to a total of 12.

With this in mind, how many unique possible combinations is there?

Propositions in Blocksworld
Lets consider the propositions in a given state of BlocksWorld.

s(A-on-B) = T
s(A-on-C) = F
s(A-on-table) = F
s(B-on-A) = F
s(B-on-C) = F
s(B-on-table) = T
s(C-on-A) = F
s(C-on-B) = F
s(C-on-table) = T
s(A-clear) = T
s(B-clear) = F
s(C-clear) = T
212 = 4096 states
(not all reachable)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Even a naive calculation of the number of states, 212 results in 4096 states.
This is a ridiculous number of possible states, and while not all of these states are reachable, it is evidence of exponential growth in the state space.
Given if were to add another block to the problem

Propositions in Blocksworld
Lets consider the propositions in a given state of BlocksWorld.

s(A-on-B) = T
s(A-on-C) = F
s(A-on-table) = F
s(B-on-A) = F
s(B-on-C) = F
s(B-on-table) = T
s(C-on-A) = F
s(C-on-B) = F
s(C-on-table) = T
s(A-clear) = T
s(B-clear) = F
s(C-clear) = T

S(A-on-D) = F
S(B-on-D) = F
S(C-on-D) = F
s(D-on-A) = F
s(D-on-B) = F
s(D-on-C) = F
s(D-on-table) = T
s(D-clear) = T
220 = 1,048,576 states
(not all reachable)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

By adding just one new block, the number of propositions increased by a further 8, given we model where D is atop, but also whether the existing blocks are on D and of course if D is clear.
This increases the number of unique combinations from 4096 to 1,048,576.
Now again, I have to stress not all of these are legal or valid combinations and the PDDL actions will ensure we only visit a subset of the total list, but this expresses the point Im trying to make here.
Ultimately, as problems begin to increase in complexity, the state spaces are exploding in scale accordingly.

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

As a result of having all of the possible information that could occur in a problem our state spaces are now increasingly large.One fact transitioning from true to false results in a completely new state.So if we have all of these propositions that could be true in certain situations, them the number of states that encompasses every unique combination of propositions is going to be massive.Even this example shown on the right hand side is but a small taste of how expansive these state spaces can become.

And to-date, what weve really looked at is how to find a way to steer our way through this nightmare.Either by using heuristics, which help direct us through the space, or weve had landmarks that point out good intermediate goals to try and complete.But as weve seen, even that has its problems.Then in the case of both the FF and Identidem planners, were using variations of Enforce Hill Climbing only how they handle local minima or plateaus is really what is changing, but in each case were now being much more aggressively searching the space often ignoring other opportunities.

Now in each of these cases, were sacrificing the completeness of the search: we may use inadmissible heuristics that prevent us from ever visiting a state, landmarks prune areas of the state space given were focussed on reaching them and as weve seen this can also cause problems plus enforced hill climbing is aggressively pushing through the search space to find an answer.And in that, were having to rely on Best-First search in the event we reach a dead end.

But in this session, were going to consider something different: what if instead of using this original encoding to define our search space, we change the expressivity of the problem to help reduce it.

Invariants
When humans reason about planning tasks, we implicitly make use of obvious properties and relationships between propositions.
E.g. A block cant be atop another block and on the table.
E.g. A truck cant be in two places at once.

Despite this, we still need to ensure PDDL captures this knowledge (add + delete effects).

Invariants: logical formulas that are true in all reachable states.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So lets look at it from a different angle and employ a more human tactic. One thing that is immediately obvious to us as humans is that a lot of the propositions relate to one another in certain ways.We generally dont think about it, because its super obvious to us. The simple idea that you cant be in two places at once, which is critical to our ability to think through some sort of logistics problem, isnt something that is going to be obvious to the planner.

Hence for example, when we create an action in PDDL that moves an object from one place to another, we have to use the add and delete effects to express this very succinctly.That if we are say moving A to B, now that I am at B, I am most certainly no longer at A.But if I dont express this in the PDDL, we run risk of creating a new possible state where both of those facts are true.Giving us even more states to explore, but are also incorrect which is of course how the RPG heuristic is able to solve problems more effectively, because we remove the additional information that were no longer at that destination.

So what if we tried to express this obvious information in a way that is useful to us in a planner? We can capture this knowledge in what are known as Invariants: a formula that has to be true in any reachable state of the problem.So if we have two locations, say the university and our home and we have two propositions stating were at the university or at home, we write an invariant that states there is no way that any valid reachable state of the problem can say that Im at the university and at home at the same time.

Finding Invariants
Theoretically, testing whether an invariant is valid is as hard as planning itself.

But, if we can find invariants and encode it in a way a planner can understand, we could potentially reduce the state space.

Even finding obviousinvariants could drastically improve our performance in solving the planning task.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Now much like what we saw with finding good heuristics and landmarks, proving whether a function over a set of propositions is in fact an invariant is again a PSPACE-Complete problem.
Why is this?Well again were trying to now prove that specific facts do not change in the solving of a problem, which in turn requires us to then try and solve the problem.So once again, were hoping we can try and get the answers we need within polynomial time.

But if we can find even the most obvious and simplest of invariants that emerge within a particular problem and then encode it somehow into the planning system it could drastically improve the overall performance, given we could prune the state space down to a slightly more manageable size.

So lets talk about how we could express the state more succinctly

Mutual Exclusion
Mutual Exclusion (mutex): an invariant over a set of propositions that states only can be true at any point in time.

is a mutex

This can also extend to sets of propositions, which are mutex if every subset of two is mutex.

Lets look at some examples

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

One of the most commonly used invariants that we will see today but also in later sessions in this module is a mutual exclusion or mutex relationship.
This is an invariant over a set of propositions where only proposition can be true at any given point of time.Hence if we return to my example from earlier, being at the university and being at home is a mutex.Because only one of those two propositions will be true in any given state.

Now this can extend out to sets of literals, and we can express that any subset is also going to be mutex.
To help give this some clarification, lets take a closer look at the blocksworld example again and how we could go about expressing that through mutexes.

Mutual Exclusive: Example

BlocksWorld Invariant:

andare mutex.

Because every pair in this set are mutex.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

A simple example is an invariant that states block C is not on block A or is not on block B, meaning that C-on-A and C-on-B cannot hold true at the same time.
This mutex sufficiently describes the phenomena that C cannot be on two different blocks at the same time, but it doesnt express that C can also be on the table, but we can use mutexes arranged from sets of literals to help us encapsulate these broader relationships.

So, if we consider a set of literals, A-on-B, C-on-B and B-clear.This set is also mutually exclusive.Why?Because every possible pairing in this set is also mutex.

Mutual Exclusive: Example
BlocksWorld Invariant:

andare mutex.

Because every pair in this set are mutex.

This makes sense
Its impossible for both A and C to be on B at the same time. And for B to be clear when something is atop it.

How does this impact state space size?

{AonB, ConB}
{AonB, Bclear}
{ConB, Bclear}

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If we enumerate all of the unique subsets, we have three combinations:

A is on B and C is on B
A is on B and B is clear
C is on B and B is clear.

In each case, the pair of propositions is also mutex.Its impossible for C to be on B and A to be on B at the same time.
Plus if either A or C are on B, its impossible for B to be clear, because, yknow, theres something sittingon top of it.

So, if we were to consider these mutex relationships, how does we begin to encode this in a more succinct way?

Finite-Domain State Variables
We can use these literals to reframe a problem using Finite-Domain State Variables

We create a variableand a domainthat expresses the range of possible values that can be assigned to .

We can then create Finite Domain States that express a state of a planning problem as an assignment to all variables in the state

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So, given we have these relationships, we can begin to encode this information in a different way for a planning problem.This approach, known as finite-domain state variables, sounds quite complicated, but once we see it in an example it will make a lot more sense.

In essence, we are going to create variables that we assign, much like before, but this time we express the range of possible values that can be assigned to them.By having this domain, we can reduce the possible assignments and keep the overall state space much tighter.

Ultimately, one state is then an assign of all variables in the state to a value within their respective domains.

Finite-Domain State Variables
We can use these literals to reframe a problem using Finite-Domain State Variables

We create a variableand a domainthat expresses the range of possible values that can be assigned to .

We can then create Finite Domain States that express a state of a planning problem as an assignment to all variables in the state

E.g.below-abelow-a

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

A simple example of this would be to have a variable that encapsulates what block is underneath block A.
The domain for this variable, would then be either the block B or C, or nothing, theres no block underneath it.
This encoding allows us to say either B-on-A, C-on-A or A-on-table, but instead of three different propositions that we need to ensure dont contradict one another, we now have one variable that expresses all of this information really succinctly and prevents the mutex situations from occurring.

Blocksworld using Finite-Domain Representation
Lets revisit BlocksWorld, but this time using propositions and Finite-Domain State Variables.

below-a: {b, c, table} = b
below-b: {a, c, table} = table
below-c: {a, b, table} = table

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So what if we were to try and encode the same BlocksWorld encoding, but this time, we can encapsulate the information in a different way.
Lets try and use these finite domain state variabls, which express what block can be underneath another block.Now there are some issues here, given that we do not successfully encapsulate whether the blocks are clear to put anything atop them, but lets just consider for a moment how big this state space is.

Blocksworld using Finite-Domain Representation
Lets revisit BlocksWorld, but this time using Finite-Domain State Variables.

below-a: {b, c, table} = b
below-b: {a, c, table} = table
below-c: {a, b, table} = table
33 = 27 states

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If we return to our nave calculations from before, there are only 27 possible combinations here. This already a massive improvement.Were removing so much complexity from the state space by capturing all of the critical information about the problem in a way that is much more computationally tractable to explore.

But as I mentioned, this isnt complete: given this does not successfully encapsulate whether a block is clear or not.Now, we could infer this by checking each relation to see if for a given block X, the variable assigned in one of these relations is X.That would tell us it is beneath something else.But still, this doesnt help accurately model the state, so lets try adding a different formalism to the problem that will capture this information.

Blocksworld using Finite-Domain Representation
Lets revisit BlocksWorld, but this time using Finite-Domain State Variables.

above-a: {b, c, nothing} = nothing
above-b: {a, c, nothing} = a
above-c: {a, b, nothing} = nothing
63 = 216 states
below-a: {b, c, table} = b
below-b: {a, c, table} = table
below-c: {a, b, table} = table

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If we establish a different encoding, where we also model all of the blocks that are above A, B and C, we have successfully encapsulated all the information about the state that we needed.
So in this case, above-a, encodes the mutex of {B-on-A, C-on-A and A-clear).
And as a result, while we have increased the total number of unique configurations from 27 to 216, this is significantly less than the original 4096 states we calculated earlier.

But also, it is worth mentioning that there are relationships that exist between the below and above variables here as well.Given for example, below-a and above-a shouldnt have the same value.Given that would mean that a block is in two different places at the same time which is of course an invalid state.But also, if below-a is assigned to B, then above-b should be assigned to a.

So even having reduced this state space to this level, there are further constraints that could be applied to this problem space.

But for now, this is a good start.We have successfully encapsulated a lot of obvious information

Finite-Domain Formula
Given the Finite-Domain Representation (FDR) encoding, this is valuable because we can translate it back to the normal propositions, but safely encapsulating the mutex relationships we have discovered.

above-a below-b

Corresponds to
A-clearB-on-C

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And what makes this useful, is that we can we can effectively translate any Finite-Domain State back into the propositions mentioned earlier.
We can create Finite Domain Formulae, whereby we can now express rules or constraints we wish to have over a given problem space, but do so in a way that can later be reduced to their atomic propositions that we saw earlier.

For anyone who has previously studied our Introduction to Artificial Intelligence class, youll perhaps have noted that a lot of this shares similarities with constraint satisfaction problems or CSPs, whereby we impose rules and constraints on the variables in

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