[SOLVED] CS PowerPoint Presentation

PowerPoint Presentation

Classical Planning
Non-Forward Search

Copyright By Assignmentchef assignmentchef

Introduction to HTN Planning
6CCS3AIP Artificial Intelligence Planning
Dr Tommy Thompson

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

Hello and welcome to this chapter of Classical Planning as we continue our exploration of non-forward search techniques.In this chapter were going to take a look at a rather different approach known as Hierarchical Task Network or HTN planning.

Recap: Non-Forward Search
Exploring planning techniques that deviate from the traditional forward-search approach.
Initial state, open list, closed list, heuristic etc.

Graphplan:
Generate plan graphs forward, then search backward.

SAT Planning
Planning as satisfiability

POP Planning
Partial orders on plan execution.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

To quicky recap, this segment of the module is built around the idea that our traditional method of moving through the search space as weve discussed throughout the classical planning phase of the module isnt the only way in which we can think about planning.

Weve taken a look at some slightly different approaches and how they try to resolve planning in their own ways, with the likes of Graphplan and PoP planning being something new and unique from what weve seen to-date.

In this chapter, were going to continue this trend, by introducing a different perspective on how to solve a planning problem, that leans much more heavily on some of the ideas of how we as humans try to solve problems.

Hierarchical Task Network (HTN) Planning
In real life, we seldom plan down to the minutiae of detail, we instead think more abstractly.
E.g. getting out of the house in the morning:
waking up, washed, dressed, breakfast etc.

In many planning problems, we as the designer may already have ideas about what good solutions might look like.

E.g. driving to packages to pick them up, driving to destinations to drop them off.

Basic Idea: What if we put this information directly into the domain?

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If you recall the chapter a while back on SAS+ planning, the core premise is that we are exploiting a key facet of human understanding in the planning approach, that we can quickly make intelligent assumptions about how facts can invariants of one another and that was something we had to work hard to encode in a planner.

This time around, were thinking about another facet of human behaviour, and thats about abstraction and decomposition of a task we give ourselves.
As humans we plan all of the time, we try to figure our way through a given day, identifying tasks were going to complete and in what order.But often, we dont really worry about the minutiae of the execution until we start to actually do it.

So say for example, you need to get out the house in the morning: you have a job or youre going to school or university and you know you have to get to your destination.Now we typically think of it as, getting up and getting out of the house in the morning.But you usually have a routine for doing that.In my case, I would

Wake up and get out of my bed.
Then head to the bathroom, grab a shower, brush my teeth, and grooming such as fixing my hair or shaving that I need to do.I may also need to go to the toilet.
Id head back to my bedroom to get dressed.
Then head to the kitchen and grab some breakfast: that could be some cereal, porridge, toast, a croissant and maybe fruit juice, tea or coffee.
Then put on my shoes, grab my bike and head out.

Now two things to address here:
First, how I handle my morning routine could be different from you.You might have the same actions in a different order, or you may omit some of these (hopefully you remember to get dressed though).
Secondly, as I described it, it became much more grounded and complex than the original description I wrote in the slide of wake up, wash, dress, breakfast.

So here when I complete this larger task of getting out the house, I already have a routine or pre-determined notion of how this should be done.So, can we embed that knowledge into a planning domain when we try to solve it?

Hierarchical Task Network (HTN) Planning
Reframe the planning problem:

Tasks to complete instead of goals to satisfy.
Tasks are little more abstract than a typical planning problem.

Methods to decompose tasks into subtasks.
Enables for gradual decompositions of complex task into smaller and more manageable tasks.
A subtask could be a single action, or another method in and of itself.

We enforce constraints of the problem in the method and actions.

Simplest version: Simple Task Network (STN) Planning

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So in HTN planning our aim is to reformulate a typical planning problem into a different format.
Instead of goals we seek to achieve, we have tasks we wish to complete and this is a much more high-level concept than our original goals.It might be more common to say travel from my house to the university as a task in HTN planning than to say (at university = true) for example.

In addition, we then use methods to express how a given task could be solved.These methods then decompose the original task into subtasks, which in turn can be solved either by transforming that task into a single concrete action, or the task is handled by another method, which further decomposes said task into more tasks.

We then can apply much broader sets of constraints on action execution.So for example, we not only have the actions that we can reduce a task to have the traditional preconditions and effects were used to seeing, the methods also have preconditions attached to them that dictate whether they are applicable.

In this chapter my focus is largely just to explain how HTN planning works as a concept rather than specific implementations of the planning process, but we can also talk about that briefly.In addition, in the material this actually covering a special case of HTN planning known as simple task network planning or STN planning.Given this is arguably the more commonly discussed and implemented version of the process.

HTN Planning: More Formally
HTN Planning Problem:
a state-variable planning domain.
a set of methods
the initial state of the problem
a list of tasks to complete

Image Credit: Lecture Slides for Automated Planning and Acting
Nau, D. 2016
= (S,A,)
s S, a A
(s,a) s

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

If we were to consider this more formally, then we would consider the HTN planning problem as 4-tuple, , M, s0 and T.

is our traditional state variable planning domain, like we have seen previously.This includes the set of all states, S, the set of all actions A and our state-transition function .. This will allow us to be in a given state, apply an action to the state using and discover what resulting state s emerges from that interaction.

Next up we have M, this is a set of methods that are designed to decompose tasks.As well see in a minute, the types of tasks we are dealing with can either be reduced to a single action inthat we can then execute, or it will translate that task into another type of task that could potentially be resolved by another method.

We have the initial state of the problem s0, much like weve seen before.

Lastly, we have the tasks we want to complete, this could be just one task which requires us to decompose it, or numerous tasks with some ordering to them that we wish to consider.

Hierarchical Task Network (HTN) Planning
HTN planning defines two types of tasks.
Primitive Tasks: Translate to single planning action.
Compound Tasks: Translate into a collection of one or more tasks.

Planning Process:
Recursively refine each task into subtasks.
Ensure tasks can then be grounded with literals.

Image Credit: Lecture Slides for Automated Planning and Acting
Nau, D. 2016

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The tasks themselves exist in one of two different forms, we have

Primitive Tasks: which are essentially a task formalism that the planner can translate into an action, provided the preconditions of the action can be satisfied by the current state.
Compound Tasks: these are tasks that we would require a method to be applied to.Provided the methods preconditions are satisfied we can then decompose the task into more tasks.

Compounds tasks are actually quite interesting in that they can be translated into one or more new tasks.
You might assume, that it would decompose into two or more tasks, but the method can be used to add additional constraints on an action that the original actions preconditions dont provide.

So say for example, we have an action to walk between two locations, and in our current state were in Holborn and the task is to travel to Kings Cross station in London.
Now there is no stopping us provided the action preconditions are satisfied that there is a path between the two from then applying the walk action.
We could have a method that decomposes the travel task to a travel-on-foot action, but it adds another precondition that states in this circumstance decomposing this task is invalid because the distance between these two locations is too far apart.Hence it may decompose the task to say, travel by the subway or using a taxi.

But of course, we will typically see that the compound tasks are reduced to multiple subtasks.And in this instance, these subtasks can either be primitive tasks or they can be new compound tasks.

But the critical part, is that only the primitive tasks actually change the state, because they translate directly into actions from the planning domain.

Hierarchical Task Network (HTN) Planning

Image Credit: Lecture Slides for Automated Planning and Acting
Nau, D. 2016

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So as you can see from this diagram, we start with the original task we were given to complete, and given this is a compound task the method is applied to find a valid permutation of possible tasks based on the current state.
This is then decomposed into two tasks and we approach them from left to right.So we visit the first task and as we decompose this into a primitive task, which translates into an action, which then results in the plan moving from s0 to s1, Meanwhile, we cant find an action that matches the task on the right, so we once again need to run a method to find a valid decomposition of this task, which in this case is two more primitive tasks, enabling for us to move from s1 to s2 and then finally s3

What this allows is for a top-down approach to behavioural design.If you think about how plans are usually constructed, its more of a bottom-up approach, whereby the individual actions are selected and the resulting plan emerges from the planner finding out that putting actions together in a specific sequence yields an intelligent response.We then have to go back and correct this as we realise the search is taking us down dead-ends, but ultimately its more focussed on individual actions being glued together in the correct sequence.

However, in this case, what were seeing is that the resulting plan is at the mercy of the task networks.By embedding specific constraints on how a particular task is executed, were expressing a total order over a subset of actions that will yield a resulting behaviour that is exactly what the designer intended.

So lets look at an example of a HTN domain and how this could work

HTN Example: Dockworker (DWR)
Task: Moving containers from one pallet in the yard to another.

Goal: Moving containers from original pallet X to destination Y, while preserving the order of the containers on the new pallet.

Image Credit: Lecture Slides for Automated Planning and Acting
Nau, D. 2016

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So lets consider the dockworker or DWR example, which is a fairly common example to see for HTN planning in textbooks and such is the dockworker or DWR domain.Now this domain is largely built around robots driving around and leaving containers on pallets that in locations, with the cranes responsible for picking up and moving objects around on the pallets at that location.A crane only has access to the pallets that are connected to it, so for example as we can see in this diagram, crane 1 can only move containers c11 and c12 and they can only be moved to locations p1a p1b and p1c.Because those are the three pallets attached to that location.

However, the task we have here is to move these containers from one pallet to another at each location, but to do so in such a way that preserves the original order.Hence as you can see in our initial state, in location 1 we have c11 atop c12 and theyre both sitting on p1a.However, the goal is not only for them to be on p1c, but also that they retain that order of c11 being on top and c12 being on the bottom.

So this is sort of an extreme example of problems such as the Towers of Hanoi and even blocksworld in that we have a limited number of locations to move objects around, but have a strict ordering on their final destination.

HTN Example: Dockworker (DWR)

Parameters:
The original location.
The destination location.

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

When we consider this as task, its pretty straight forward, we want to move one stack from its current location p, to a destination location q.
Over time, we can then begin to flesh out the ordering process through use of our HTN formalism.But for now, let us focus on how what our actions will look like.What are the most primitive actions we can execute here in this particular planning problem?

Dockworker: Actions
Take
Preconditions

Put
Preconditions

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

When we consider the actions we can execute, we have only two.Taking a container off of a pallet and putting it on another one.
This is all relatively straightforward, in that the both actions require the crane (denoted as k) and the pallets that the container is either being lifted from or put onto are related to the location.Hence the use of the belong and attached predicates.

The take action will then pick up a container and the crane will hold it.It will then also reassign the other container o as the top of that particular pile.Note that in this case, o can either be another container or the pallet itself, denoting that there are now no longer any containers atop that particular pallet.

Meanwhile, when we then attempt to put it down, in a manner similar to blocksworld and its ilk, we check whether the location is clear for us to put it where we intend to.All pretty straightforward and nothing weve never really seen before.

So if we were trying to solve this problem, we could in theory do this with a regular PDDL representation.We could move the containers around between locations and eventually reach the correct combination.However, there is a lot of bespoke information here about the nature of the problem that if we knew about it in advance would be really helpful.And this is where the HTN methods will come in handy, given they will permit us the ability to create compound tasks that allow us to deal with some of the specific issues were about to see here.

Dockworker: Methods
Recursive-Move(p,q,c,x)

Do-Nothing(p,q)
Subtasks (none).

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So we can start, by defining a method that explicitly solve the task of moving the stack of containers across from one pile to another.And the interesting part, is right here in the name recursive move.
If we take a look at this method a little more closely, it has preconditions that state we cannot run this task lest we know that container c is at the top of pile p and we can figure out which container that c is atop of, so we can thet set that as top afterwards.Plus we can see that it not only is designed to solve the move-stack task, but it does so using two subtasks: first we move the topmost container from the original pile and onto another, but also, we have the move-stack task emerge as a subtask.This ensures that we continue to work our way down the stack by applying the same method again.

This task is recursive because it is asking us to solve the original task after it does everything else it needs to do.But in order for a recursive task like this to work, it also needs a base case.A situation where we can ensure that the recursion stops.To address this, there is the Do-Nothing task.This task checks whether only the pallet is at the top of a given pile, which means that the pile is empty.In the event that the pile is empty, we can apply this method which will effectively stop the recursive-move task from continuing to run, given weve completed moving every object.

But of course, we now have another task here, the move-topmost-container which will move items between each pile.So lets take a look at that one.

Dockworker: Methods
Take-and-Put(c, k, l1, l2, p1, p2, x1, x2)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

So now we consider how the move-topmost-container task could be implemented.We have another method entitled take-and-put, which is rather self explanatory.In this instance, we are aiming to take the topmost item on a given pile and then move it to another one.The actual tasks are as expected, to execute both the take and put actions in that order.But what is interesting is that the preconditions of the method are essentially reinforcing that the grounding of variables for each task lines up in such a way that it is possible for these two actions to happen back to back.Hence we ensure that the two locations both use the same crane but also that we have the correct grounding of variables for each of these actions such that we dont have to wait until the preconditions fail before realising that this isnt valid.

Dockworker Example

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

And so if we consider how this will roll out, we can see that moving one stack from p1 to another location, will roll out in this fashion.
In this example, were moving a collection of three containers from one location to another.And this is how that would roll out for that one particular pile.

But this still doesnt solve the problem, given we can now move one pile of containers from one position to another, but when we do so, the ordering is now upside down.So how do we resolve this?

Dockworker: Methods
Move-Stack-Twice(p1, p2, p3)

FACULTY OF NATURAL & MATHEMATICAL SCIENCES
DEPARTMENT OF INFORMATICS

The solution, is to create another method that can solve the move-stack problem.In this case, we create a task that actually moves a stack twice, by running the move stack task twice but on a collection of three parameters.Our main locations we wish to move between and an intermediate. So if we were to consider the three pallets in location 1, p1a p2b and p1c, we would list them in this order, given we can then move the collection into an upside down configuration in the intermediary location, followed by then moving it back into the correct orientation in the final location.

So in essence, we can then solve the moving of one stack from a given location to another using the one task, which will then be decomposed into the recursive task, generating the take and put actions in the correct

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