Lab 4: Hierarchical Task Network Planning
This page is obsolete.
Updates
Any updates or changes we make in the lab instructions during the course
will be announced here.
Introduction
In this lab, you will learn how to model domains for Hierarchical Task
Network (HTN) planners by creating an HTN-based variation of the Emergency
Services Logistics domain. Moreover, you will show your
understanding of HTN by completing the theoretical part consisting
of manually expanding tasks when given an initial task, methods and an
initial state.
The planner you will use
is JSHOP2, a Java
version of SHOP2: Simple Hierarchical Ordered Planner. It is based on
ordered task decomposition, a variation of HTN planning that involves
planning for tasks in the same order that they will later be executed
(similar to the procedures we discussed during the lectures). Therefore
we will revert to generating sequential plans.
Like the PFD procedure, JSHOP2 can interleave subtasks from
different methods. Thus, the methods themselves can be partially ordered,
though the final plan is totally ordered. However, guiding the planner
into interleaving subtasks in the way you prefer can be somewhat tricky.
Therefore you will only be required to use totally ordered tasks.
As usual, your domain specifications must be easily readable and
sufficiently commented, explaining the way you chose to implement the
required HTN methods. Note that if you try out one design and find out
that you have to make changes to make it work, then this is an excellent
opportunity for explaining why you made the change and why your new design
is better. If the lab assistants are not completely satisfied, they may
ask you to make additional changes.
Many of you will be working in pairs. Note again that
both participants must be able to answer questions about all of the
domains you define.
You may want to use
a shop mode for
Emacs. There is also a test version of an
error checker
for SHOP files that may give you useful information if SHOP can't parse your
files.
GUI and Command Line Implementations
JSHOP2 has a simple command line implementation that you use as follows:
/home/TDDD48/bin/jshop2-command domainFile problemFile
The JSHOP2 implementation also contains a GUI for plan exploration. This
GUI calls the planner indirectly and can be used as follows:
/home/TDDD48/bin/jshop2 domainFile problemFile
Note that if a plan cannot be found, for instance due to infinite recursion, it is not possible
to use the GUI. This limits its usefulness somewhat, but it can still
provide some guidance as to which plans are investigated and generated.
It is recommended that the domain file and the domain name (inside the
file) are the same since this enables the scripts to remove temporary
files. It is also mandatory that the problem name specified in the
problem definition file is problem. This is due to integration with
java. Preprocessing will create files domain.java, domain.txt and
problem-name.java. These java files are then compiled together with the
gui.java file that is fetched by the script. The gui needs to have a class
called "problem" to work with, hence this restriction. If you see the following:
javac: file not found: problem.java
Usage: javac
You need to change the name of the problem, as defined in the problem file, to "problem".
One bug in the GUI is that it sometimes "overwrites" some actions
when it tries to visualize backtracking. For example, you may get two actions
with index 14, and then only the last of these actions is shown when the GUI
displays the final plan. This is a bug in the GUI, not in the planner.
Resources
The following resources are available:
- The JSHOP2 documentation
- A set of example domains and problems. Note that
these are sometimes written for performance rather than readability
and may be considerably more complex than your own solutions will need to be.
However, they still serve to exemplify HTN domains in JSHOP2 and demonstrate
the syntax used.
- The above
mentioned error
checker for JSHOP2 files. The tool provides some warnings of
what might be misspellings. However, the warnings aren't
guaranteed to be correct.
Notes on the JSHOP2 Input Language
HTN planning involves different concepts than classical planning, such as
methods and tasks, and therefore JSHOP2 does not use PDDL. Though the
languages sometimes look similar, in particular because they are both
based on standard LISP syntax, they are not identical!
We refer to the JSHOP2 documentation for
complete information about the SHOP input language. Below we will discuss
some of the more important aspects of the language, but you will most
likely have to refer to the documentation as well! You may want to look
at some of the example domains and problems
while reading this section.
Don't start writing a problem definition yet. We will soon show what you
need to do for each exercise in this lab.
-
SHOP does not support typed objects. You will have to use type
predicates instead. Also, there is no explicit list of objects in the
problem definition. Objects are implicitly defined when you
specify initial states and tasks to perform.
-
As you already know, primitive tasks cannot be subdivided
further into subtasks. They are to HTN planners what operators are to
PDDL planners. In JSHOP2, primitive tasks are called operators
and defined as follows:
(:operator (!task-name ?arg1 ?arg2 ... )
precondition
deletelist
addlist
)
The name of an operator must begin with an exclamation mark, to
indicate clearly that it is primitive. The
precondition must be satisfied to execute the action, and can
contain conjunctions, disjunctions, quantification, and so on. The
result will be that all properties in the deletelist will be
removed and all properties in the addlist will be added
– unlike the PDDL syntax, where you write "(not x)" to delete
the property x.
-
Quantified and conditional add and delete effects can be used
in operators. For example, suppose the operator (!unload-all-from
?truck?loc) should unload all packages from the given truck
at the given location. This could be modeled approximately as
follows:
(:operator (!unload-all-from ?truck ?loc)
;; Precondition
(...precond...)
;; Delete effects
((forall (?p) (in ?p ?truck) (and (in ?p ?truck))))
;; Add effects
((forall (?p) (in ?p ?truck) (and (at ?p ?loc))))
)
The add effect states that for all ?p, if ?p is in the truck, then "(at ?p
?loc)" becomes true. The delete effect means that for all ?p, if ?p is in
the truck, then "(in ?p ?truck)" becomes false.
A "pure" unquantified conditional effect is modeled as "(forall nil (cond)
(add-or-delete))": Quantification over the empty list of variables.
-
In the lectures, we discussed how each non-primitive task can
be realized through multiple methods and that one explicitly
specifies which task a given method implements. For example,
a travel task could be implemented the
methods taxi-travel, foot-travel
and airplane-travel.1
JSHOP2 instead relies instead on naming: Tasks are never
declared, and methods that implement the same task are identified by
giving them the same name. In the example, there would be three
methods with the same name (for example travel) but with
different specifications. Whenever a travel task is needed,
the planner considers all methods with the given name.
-
Rather than each method having a single precondition and a single
expansion (list of new tasks), JSHOP2 allows methods to be written as
follows:
(:method (method-name ?arg1 ?arg2 ... )
preconditionlist_1
task-list_1
...
preconditionlist_n
task-list_n
)
When the planner attempts to apply this method to a task, it will test
conditions in sequential order. If preconditionlist_1 is true,
task-list_1 will be executed. If not, JSHOP2 will test whether the
next precondition list is satisfied, and so on. This results in an
"if/elseif/elseif" structure, providing a convenient "shortcut" where
multiple alternative expansions can be modeled using a single method.
Below is an example from the standard logistics domain (not emergency
services logistics). This method uses a truck to transport a package
between two locations in a single city. If the two locations are in
fact one location, then the task is already achieved and no subtasks
need to be performed. Otherwise, if loc-from is in a certain city and
the truck is in the same city, a sequence of four subtasks should be
performed. First, ensure that the truck is at loc-from (note that
truck-at is a task, not a proposition). Then, load the object into
the truck using the primitive task (operator) !load-truck. Make sure
that the truck is at loc-to, and then unload the object from the truck.
(:method (in-city-delivery ?truck ?obj ?loc-from ?loc-to)
((same ?loc-from ?loc-to))
()
((in-city ?loc-from ?city) (truck ?truck ?city))
((truck-at ?truck ?loc-from)
(!load-truck ?obj ?truck ?loc-from)
(truck-at ?truck ?loc-to)
(!unload-truck ?obj ?truck ?loc-to)))
Note that this method implementation follows a pattern where the first
condition tests whether the task is already achieved. This is a very
important pattern as it allows you to avoid unnecessary actions in
your plans. A method such as (truck-at truck loc) would use a similar
pattern to avoid adding a (!drive-truck truck loc) action if the truck
is already there.
-
We discussed during the lectures that a method can
have additional parameters that are not part of the task it
implements: The task move-topmost-container(pile1, pile2) has
a method called take-and-put(cont, crane, loc, pile1, pile2, c1,
c2) with five additional parameters. This way, the task only
specifies some of the parameters to use in the method, and the planner
must find good values for the other parameters.
Since JSHOP2 does not distinguish between methods and tasks, there is
no place to explicitly declare the "additional parameters". Instead,
as you can see in the example below, preconditions can simply
use free variables that are not part of the argument list:
(:operator (!put-down-carrier ?uav)
(and (at ?uav ?loc) (holding ?uav ?carr))
(and (holding ?uav ?carr))
(and (at ?carr ?loc) (empty ?uav))
)
This has essentially the same meaning as this, in the syntax used in the
book:
Task: put-down-carrier(uav)
Method: put-down-method(uav, loc, carr)
Precond: ...
Effects: ...
Be careful: If you accidentally misspell a variable, JSHOP2 will
believe you meant to implicitly create a new variable and will not
complain!
-
If the name of an operator task begins with two exclamation
marks, it is assumed to correspond to some operation done for
"internal bookkeeping" during the planning process but does not
correspond to a real action in the final plan. If you see such
operators in the examples, don't worry: You won't need them in your
solution.
-
In the example files, you may see that one can omit the "and"
keyword in expressions, writing conjunctions as simple lists.
That is, (and expr1 expr2) can be written simply (expr1
expr2). If these expressions are themselves parenthesized, as
in (and (at ?x ?loc) (holding ?y)), you get something that
looks like a list of lists: ((at ?x ?loc) (holding ?y)).
We recommend that you explicitly write "and" in conjunctions to avoid
confusion.
-
JSHOP2 supports ordered and unordered task lists. A
method such as in-city-delivery (above) would typically use an ordered
task list, which is the default if nothing else is specified: You have
to drive, load, drive, and unload in a specific order. Some methods
might be unordered. The "goal" (initial task list specified in the
problem file) can typically be unordered:
(:unordered (deliver-to person1) (deliver-to person2) ...)
However, we will not require you to use unordered task lists in
this lab, as guiding JSHOP2 to expand subtasks in the desired order
can be quite tricky.
-
It is possible to call functions from JSHOP2. There are built-in
functions for comparisons, including <, <=, =, >, >=,
!=, +, -, *, /, ^ and Member. A function call expression
is written as (call func ?arg1 ?arg2). For
instance, (call - ?c 1) will return the value ?c -
1. More information is available in
the JSHOP2 documentation under "call
terms".
-
An interesting extension (that you don't necessarily have to use) is
that JSHOP2 can sort action instances in order to try promising
branches of the search-tree first. For instance, (:sort-by ?dist
#'< (and (at ?here) (distance ?here ?there ?dist))) in a
precondition will try the different instantiations of ?here
and ?there in order of increasing ?dist.
DANGER! In contrast to PDDL planners, SHOP does not require
predicates, operators or constants to be explicitly declared before they are
used. This is sometimes useful, but also dangerous. For example, if you use
the predicate "(holding ?x)" but in one place misspell it "(holdng ?x)", there
will be no warning but you might never be able to solve the problem you
define. Similarly, if you misspell the name of a subtask in the decomposition
of a method, SHOP may simply conclude that there was no way of performing the
subtask rather than complaining that the subtask has not been defined.
Lab 4.1 Theory: Task expansion
In the theory part of the lab you have to expand two tasks. The
expansion should be done according to the Total Order Forward
Decomposition algorithm (please see the lecture slides for more
information). Describe at each expansion step
which task that you have expanded, their variable
bindings, which method you have used and how the current state
has changed. This can be done in multiple ways however we
recommend that you do so partly by drawing a tree structure like
in the lectures slides and add description when needed. Doing this task
with a pen and paper is a good preparation for the written exam.
The available methods for the tasks are:
Task: make-delivery(pkg)
method: make-delivery(pkg, from, to, carrier, vehicle)
precond: undelivered(pkg), destination(pkg, to),
delivery-speed(pkg, fast), at(vehicle, from), at(carrier, from),
holding(carrier, pkg)
subtasks: <enter-vehicle(carrier, vehicle, from), travel(vehicle, from, to),
leave-and-deliver(carrier, pkg, vehicle, to)>
Task: make-delivery(pkg)
method: make-delivery(pkg, from, to, carrier)
precond: undelivered(pkg), destination(pkg, to),
delivery-speed(pkg, slow), at(carrier, from),
holding(carrier, pkg)
subtasks: <walk(carrier, from, to), deliver(pkg, carrier, to)>
Task: leave-and-deliver(carrier, pkg, vehicle, to)
method: leave-and-deliver(carrier, pkg, vehicle, to)
precond: in(carrier, vehicle), holding(carrier, pkg),
destination(pkg, to), undelivered(pkg)
subtasks: <leave-vehicle(carrier, vehicle, to), deliver(pkg, carrier, to)>
The available primitive task are as follows:
Primitive-task: enter-vehicle(carrier, veh, loc)
precond: at(veh, loc), at(carrier, loc)
effect: ¬at(carrier, loc), in(carrier, veh)
Primitive-task: leave-vehicle(vehicle, carrier, loc)
precond: at(veh, loc), in(carrier, vehicle)
effect: ¬in(carrier, vehicle), at(carrier, loc)
Primitive-task: travel(vehicle, from, to)
precond: at(vehicle, from)
effect: ¬at(vehicle, from), at(vehicle, to)
Primitive-task: walk(carrier, from, to)
precond: at(carrier, from)
effect: ¬at(carrier, from), at(carrier, to)
Primitive-task: deliver(pkg, carrier, to)
precond: at(carrier, to), holding(carrier, pkg),
destination(pkg, to), undelivered(pkg)
effect: ¬holding(carrier, pkg), ¬undelivered(pkg)
Your assignment is to expand the two following tasks and using
their corresponding state and the given methods and primitive tasks.
- State:
undelivered(one-ring),
destination(one-ring, mount-doom),
delivery-speed(one-ring, slow),
at(hobbit, bag-end),
holding(hobbit, one-ring)
Task: <make-delivery(one-ring)>
- State:
undelivered(death-star-plans),
destination(death-star-plans, hidden-rebel-base),
delivery-speed(death-star-plans, fast),
at(farm-boy, desert-far-away),
holding(farm-boy,death-star-plans),
at(old-ship, desert-far-away)
Task: <make-delivery(death-star-plans)>
Lab 4.2: An HTN Version of the Emergency Services Logistics Domain
In the first part of the lab, you should create an HTN version of the
Emergency Services Logistics Domain corresponding to what you initially
did in Lab 1 (i.e. without carriers). This will involve:
-
Creating an initial problem file in the JSHOP2 syntax, containing among
other things an initial task list with the single task
"(deliver-all)".
-
Creating a domain definition file in the JSHOP2 syntax.
-
Creating a set of low-level JSHOP2 operators, probably
corresponding quite closely to the operators you had in your original
classical domain model.
-
Creating a set of JSHOP2 method specifications that can
incrementally decompose the top-level task (deliver-all) into primitive
tasks.
Some hints:
-
Don't try to do too much in each task. As in programming, you can often
benefit from breaking down each task into less complex subtasks in
several levels, and giving descriptive names at each level.
-
Remember that recursion can replace iteration (slide 10+ in 2012). For
instance, if you at some point want to deliver everything that is needed
at a specific location, you can break this down into an "initial"
delivery and a recursive call to deliver the rest.
-
Because the initial task does not state who needs what (like the goal
statement did in Lab 1.1), you instead need to introduce a predicate
such as (needs ?person ?cratetype) so that your methods will
know what needs to be done.
-
Your solution should be reasonable but does not necessarily have to
generate optimal plans.
When you are finished (or if you run into problems), ask a lab assistant
to take a brief look at your domain.
Lab 4.3: Carriers and Numeric Representations
In this part of the lab, you should extend the HTN-based domain with
support for carriers, similarly to what you did for classical domains.
The aim is to deliver a certain number of crates to injured people. Since
JSHOP2 supports numeric fluents and arithmetic functions, you can now
abstract away from modeling individual persons and crates, and instead
specify only how many crates of each type are needed at each
location. This means that the planner does not have to care about
exactly which crate of a certain type it decides to pick up and
delivered to a certain location, which reduces redundancy and decreases
the branching factor: Instead of having to choose among 100 crates to pick
up, the planner only has to choose among a few crate types.
Thus, there should be no person objects. A location
will implicitly correspond to an arbitrary number of people: A
single person needing a single crate of medicine, or dozens of people that
together require 30 boxes of food and 20 boxes of medicine. There should
also be no crate objects, as you will only specify the number of crates
present or required at any given location.
Given this model, you need predicates keeping track of how many crates of
each type you have in each location right now, as well as how many of each
type are required at that location in total. Similarly, you should
explicitly model the capacity of each carrier (which may be different for
different carriers) as well as the current number of crates (of each type)
on each carrier.
At the middle level, there might be a task such as "(deliver-to
location)", which would ensure that a sufficient number of crates of each
type is present at the specified location. Note that this, together with
the fact that we are using total-order forward decomposition, means that
we will never use a single carrier to deliver crates to two distinct
locations.
The following conditions must be satisfied:
- You only deliver with a carrier to a certain location if you have at
least two boxes left to deliver to that location.
- You only deliver "directly" (without a carrier) to a certain location
if there is a single box left to deliver to that location.
When you have verified that your methods generate correct plans, you must
define a considerably larger problem instance and use it for additional
testing. Then ask a lab assistant to take a brief look at your domain.
Report
Write a report where you answer the following questions as well as
the answers to the theory questions:
- Compare building the HTN domain to what you did previously in PDDL. Which
parts were easier, if any? Which parts were harder? Why?
- Is JHOP2 faster/slower than the competition planners from previous
labs, given your own particular formalization of the domain?
- How does the run time of JSHOP2 scale with larger problems?
Finishing and handing in the results
When you have finished the lab, you need to demonstrate and discuss the
results with your lab assistant.
After the demonstration and discussion, you should hand in your results:
-
Create a single ZIP file, named fffll111-fffll222-lab4.zip where
fffll111 and fffll222 are your liu-ids (assuming you are working in
pairs).
-
The ZIP file should contain in all domain files, problem files and
problem generators you have created or modified, clearly named. It
should also contain the report as a simple text file or as a PDF
document (no Word or OpenOffice documents, please).
-
Send the ZIP file by e-mail to Mikael
Nilsson.
Updates
Any updates or changes we make in the lab instructions during the course will be announced here.
Introduction
In this lab, you will learn how to model domains for Hierarchical Task Network (HTN) planners by creating an HTN-based variation of the Emergency Services Logistics domain. Moreover, you will show your understanding of HTN by completing the theoretical part consisting of manually expanding tasks when given an initial task, methods and an initial state.
The planner you will use is JSHOP2, a Java version of SHOP2: Simple Hierarchical Ordered Planner. It is based on ordered task decomposition, a variation of HTN planning that involves planning for tasks in the same order that they will later be executed (similar to the procedures we discussed during the lectures). Therefore we will revert to generating sequential plans.
Like the PFD procedure, JSHOP2 can interleave subtasks from different methods. Thus, the methods themselves can be partially ordered, though the final plan is totally ordered. However, guiding the planner into interleaving subtasks in the way you prefer can be somewhat tricky. Therefore you will only be required to use totally ordered tasks.
As usual, your domain specifications must be easily readable and sufficiently commented, explaining the way you chose to implement the required HTN methods. Note that if you try out one design and find out that you have to make changes to make it work, then this is an excellent opportunity for explaining why you made the change and why your new design is better. If the lab assistants are not completely satisfied, they may ask you to make additional changes.
Many of you will be working in pairs. Note again that both participants must be able to answer questions about all of the domains you define.
You may want to use a shop mode for Emacs. There is also a test version of an error checker for SHOP files that may give you useful information if SHOP can't parse your files.
GUI and Command Line Implementations
JSHOP2 has a simple command line implementation that you use as follows:
/home/TDDD48/bin/jshop2-command domainFile problemFile
The JSHOP2 implementation also contains a GUI for plan exploration. This GUI calls the planner indirectly and can be used as follows:
/home/TDDD48/bin/jshop2 domainFile problemFile
Note that if a plan cannot be found, for instance due to infinite recursion, it is not possible to use the GUI. This limits its usefulness somewhat, but it can still provide some guidance as to which plans are investigated and generated.
It is recommended that the domain file and the domain name (inside the file) are the same since this enables the scripts to remove temporary files. It is also mandatory that the problem name specified in the problem definition file is problem. This is due to integration with java. Preprocessing will create files domain.java, domain.txt and problem-name.java. These java files are then compiled together with the gui.java file that is fetched by the script. The gui needs to have a class called "problem" to work with, hence this restriction. If you see the following:
javac: file not found: problem.javaUsage: javac
You need to change the name of the problem, as defined in the problem file, to "problem".
One bug in the GUI is that it sometimes "overwrites" some actions when it tries to visualize backtracking. For example, you may get two actions with index 14, and then only the last of these actions is shown when the GUI displays the final plan. This is a bug in the GUI, not in the planner.
Resources
The following resources are available:
- The JSHOP2 documentation
- A set of example domains and problems. Note that these are sometimes written for performance rather than readability and may be considerably more complex than your own solutions will need to be. However, they still serve to exemplify HTN domains in JSHOP2 and demonstrate the syntax used.
- The above mentioned error checker for JSHOP2 files. The tool provides some warnings of what might be misspellings. However, the warnings aren't guaranteed to be correct.
Notes on the JSHOP2 Input Language
HTN planning involves different concepts than classical planning, such as methods and tasks, and therefore JSHOP2 does not use PDDL. Though the languages sometimes look similar, in particular because they are both based on standard LISP syntax, they are not identical!
We refer to the JSHOP2 documentation for complete information about the SHOP input language. Below we will discuss some of the more important aspects of the language, but you will most likely have to refer to the documentation as well! You may want to look at some of the example domains and problems while reading this section.
Don't start writing a problem definition yet. We will soon show what you need to do for each exercise in this lab.
-
SHOP does not support typed objects. You will have to use type predicates instead. Also, there is no explicit list of objects in the problem definition. Objects are implicitly defined when you specify initial states and tasks to perform.
-
As you already know, primitive tasks cannot be subdivided further into subtasks. They are to HTN planners what operators are to PDDL planners. In JSHOP2, primitive tasks are called operators and defined as follows:
(:operator (!task-name ?arg1 ?arg2 ... ) precondition deletelist addlist )
The name of an operator must begin with an exclamation mark, to indicate clearly that it is primitive. The precondition must be satisfied to execute the action, and can contain conjunctions, disjunctions, quantification, and so on. The result will be that all properties in the deletelist will be removed and all properties in the addlist will be added – unlike the PDDL syntax, where you write "(not x)" to delete the property x.
-
Quantified and conditional add and delete effects can be used in operators. For example, suppose the operator (!unload-all-from ?truck?loc) should unload all packages from the given truck at the given location. This could be modeled approximately as follows:
(:operator (!unload-all-from ?truck ?loc) ;; Precondition (...precond...) ;; Delete effects ((forall (?p) (in ?p ?truck) (and (in ?p ?truck)))) ;; Add effects ((forall (?p) (in ?p ?truck) (and (at ?p ?loc)))) )
The add effect states that for all ?p, if ?p is in the truck, then "(at ?p ?loc)" becomes true. The delete effect means that for all ?p, if ?p is in the truck, then "(in ?p ?truck)" becomes false.
A "pure" unquantified conditional effect is modeled as "(forall nil (cond) (add-or-delete))": Quantification over the empty list of variables.
-
In the lectures, we discussed how each non-primitive task can be realized through multiple methods and that one explicitly specifies which task a given method implements. For example, a travel task could be implemented the methods taxi-travel, foot-travel and airplane-travel.1
JSHOP2 instead relies instead on naming: Tasks are never declared, and methods that implement the same task are identified by giving them the same name. In the example, there would be three methods with the same name (for example travel) but with different specifications. Whenever a travel task is needed, the planner considers all methods with the given name.
-
Rather than each method having a single precondition and a single expansion (list of new tasks), JSHOP2 allows methods to be written as follows:
(:method (method-name ?arg1 ?arg2 ... ) preconditionlist_1 task-list_1 ... preconditionlist_n task-list_n )
When the planner attempts to apply this method to a task, it will test conditions in sequential order. If preconditionlist_1 is true, task-list_1 will be executed. If not, JSHOP2 will test whether the next precondition list is satisfied, and so on. This results in an "if/elseif/elseif" structure, providing a convenient "shortcut" where multiple alternative expansions can be modeled using a single method.
Below is an example from the standard logistics domain (not emergency services logistics). This method uses a truck to transport a package between two locations in a single city. If the two locations are in fact one location, then the task is already achieved and no subtasks need to be performed. Otherwise, if loc-from is in a certain city and the truck is in the same city, a sequence of four subtasks should be performed. First, ensure that the truck is at loc-from (note that truck-at is a task, not a proposition). Then, load the object into the truck using the primitive task (operator) !load-truck. Make sure that the truck is at loc-to, and then unload the object from the truck.
(:method (in-city-delivery ?truck ?obj ?loc-from ?loc-to) ((same ?loc-from ?loc-to)) () ((in-city ?loc-from ?city) (truck ?truck ?city)) ((truck-at ?truck ?loc-from) (!load-truck ?obj ?truck ?loc-from) (truck-at ?truck ?loc-to) (!unload-truck ?obj ?truck ?loc-to)))
Note that this method implementation follows a pattern where the first condition tests whether the task is already achieved. This is a very important pattern as it allows you to avoid unnecessary actions in your plans. A method such as (truck-at truck loc) would use a similar pattern to avoid adding a (!drive-truck truck loc) action if the truck is already there.
-
We discussed during the lectures that a method can have additional parameters that are not part of the task it implements: The task move-topmost-container(pile1, pile2) has a method called take-and-put(cont, crane, loc, pile1, pile2, c1, c2) with five additional parameters. This way, the task only specifies some of the parameters to use in the method, and the planner must find good values for the other parameters.
Since JSHOP2 does not distinguish between methods and tasks, there is no place to explicitly declare the "additional parameters". Instead, as you can see in the example below, preconditions can simply use free variables that are not part of the argument list:
(:operator (!put-down-carrier ?uav) (and (at ?uav ?loc) (holding ?uav ?carr)) (and (holding ?uav ?carr)) (and (at ?carr ?loc) (empty ?uav)) )
This has essentially the same meaning as this, in the syntax used in the book:
Task: put-down-carrier(uav) Method: put-down-method(uav, loc, carr) Precond: ... Effects: ...
Be careful: If you accidentally misspell a variable, JSHOP2 will believe you meant to implicitly create a new variable and will not complain!
-
If the name of an operator task begins with two exclamation marks, it is assumed to correspond to some operation done for "internal bookkeeping" during the planning process but does not correspond to a real action in the final plan. If you see such operators in the examples, don't worry: You won't need them in your solution.
-
In the example files, you may see that one can omit the "and" keyword in expressions, writing conjunctions as simple lists. That is, (and expr1 expr2) can be written simply (expr1 expr2). If these expressions are themselves parenthesized, as in (and (at ?x ?loc) (holding ?y)), you get something that looks like a list of lists: ((at ?x ?loc) (holding ?y)).
We recommend that you explicitly write "and" in conjunctions to avoid confusion.
-
JSHOP2 supports ordered and unordered task lists. A method such as in-city-delivery (above) would typically use an ordered task list, which is the default if nothing else is specified: You have to drive, load, drive, and unload in a specific order. Some methods might be unordered. The "goal" (initial task list specified in the problem file) can typically be unordered:
(:unordered (deliver-to person1) (deliver-to person2) ...)
However, we will not require you to use unordered task lists in this lab, as guiding JSHOP2 to expand subtasks in the desired order can be quite tricky.
-
It is possible to call functions from JSHOP2. There are built-in functions for comparisons, including <, <=, =, >, >=, !=, +, -, *, /, ^ and Member. A function call expression is written as (call func ?arg1 ?arg2). For instance, (call - ?c 1) will return the value ?c - 1. More information is available in the JSHOP2 documentation under "call terms".
-
An interesting extension (that you don't necessarily have to use) is that JSHOP2 can sort action instances in order to try promising branches of the search-tree first. For instance, (:sort-by ?dist #'< (and (at ?here) (distance ?here ?there ?dist))) in a precondition will try the different instantiations of ?here and ?there in order of increasing ?dist.
DANGER! In contrast to PDDL planners, SHOP does not require predicates, operators or constants to be explicitly declared before they are used. This is sometimes useful, but also dangerous. For example, if you use the predicate "(holding ?x)" but in one place misspell it "(holdng ?x)", there will be no warning but you might never be able to solve the problem you define. Similarly, if you misspell the name of a subtask in the decomposition of a method, SHOP may simply conclude that there was no way of performing the subtask rather than complaining that the subtask has not been defined.
Lab 4.1 Theory: Task expansion
In the theory part of the lab you have to expand two tasks. The expansion should be done according to the Total Order Forward Decomposition algorithm (please see the lecture slides for more information). Describe at each expansion step which task that you have expanded, their variable bindings, which method you have used and how the current state has changed. This can be done in multiple ways however we recommend that you do so partly by drawing a tree structure like in the lectures slides and add description when needed. Doing this task with a pen and paper is a good preparation for the written exam.
The available methods for the tasks are:
Task: make-delivery(pkg) method: make-delivery(pkg, from, to, carrier, vehicle) precond: undelivered(pkg), destination(pkg, to), delivery-speed(pkg, fast), at(vehicle, from), at(carrier, from), holding(carrier, pkg) subtasks: <enter-vehicle(carrier, vehicle, from), travel(vehicle, from, to), leave-and-deliver(carrier, pkg, vehicle, to)> Task: make-delivery(pkg) method: make-delivery(pkg, from, to, carrier) precond: undelivered(pkg), destination(pkg, to), delivery-speed(pkg, slow), at(carrier, from), holding(carrier, pkg) subtasks: <walk(carrier, from, to), deliver(pkg, carrier, to)> Task: leave-and-deliver(carrier, pkg, vehicle, to) method: leave-and-deliver(carrier, pkg, vehicle, to) precond: in(carrier, vehicle), holding(carrier, pkg), destination(pkg, to), undelivered(pkg) subtasks: <leave-vehicle(carrier, vehicle, to), deliver(pkg, carrier, to)>
The available primitive task are as follows:
Primitive-task: enter-vehicle(carrier, veh, loc) precond: at(veh, loc), at(carrier, loc) effect: ¬at(carrier, loc), in(carrier, veh) Primitive-task: leave-vehicle(vehicle, carrier, loc) precond: at(veh, loc), in(carrier, vehicle) effect: ¬in(carrier, vehicle), at(carrier, loc) Primitive-task: travel(vehicle, from, to) precond: at(vehicle, from) effect: ¬at(vehicle, from), at(vehicle, to) Primitive-task: walk(carrier, from, to) precond: at(carrier, from) effect: ¬at(carrier, from), at(carrier, to) Primitive-task: deliver(pkg, carrier, to) precond: at(carrier, to), holding(carrier, pkg), destination(pkg, to), undelivered(pkg) effect: ¬holding(carrier, pkg), ¬undelivered(pkg)
Your assignment is to expand the two following tasks and using their corresponding state and the given methods and primitive tasks.
- State:
undelivered(one-ring), destination(one-ring, mount-doom), delivery-speed(one-ring, slow), at(hobbit, bag-end), holding(hobbit, one-ring)
Task:<make-delivery(one-ring)>
- State:
undelivered(death-star-plans), destination(death-star-plans, hidden-rebel-base), delivery-speed(death-star-plans, fast), at(farm-boy, desert-far-away), holding(farm-boy,death-star-plans), at(old-ship, desert-far-away)
Task:<make-delivery(death-star-plans)>
Lab 4.2: An HTN Version of the Emergency Services Logistics Domain
In the first part of the lab, you should create an HTN version of the Emergency Services Logistics Domain corresponding to what you initially did in Lab 1 (i.e. without carriers). This will involve:
- Creating an initial problem file in the JSHOP2 syntax, containing among other things an initial task list with the single task "(deliver-all)".
- Creating a domain definition file in the JSHOP2 syntax.
- Creating a set of low-level JSHOP2 operators, probably corresponding quite closely to the operators you had in your original classical domain model.
- Creating a set of JSHOP2 method specifications that can incrementally decompose the top-level task (deliver-all) into primitive tasks.
Some hints:
- Don't try to do too much in each task. As in programming, you can often benefit from breaking down each task into less complex subtasks in several levels, and giving descriptive names at each level.
- Remember that recursion can replace iteration (slide 10+ in 2012). For instance, if you at some point want to deliver everything that is needed at a specific location, you can break this down into an "initial" delivery and a recursive call to deliver the rest.
- Because the initial task does not state who needs what (like the goal statement did in Lab 1.1), you instead need to introduce a predicate such as (needs ?person ?cratetype) so that your methods will know what needs to be done.
- Your solution should be reasonable but does not necessarily have to generate optimal plans.
When you are finished (or if you run into problems), ask a lab assistant to take a brief look at your domain.
Lab 4.3: Carriers and Numeric Representations
In this part of the lab, you should extend the HTN-based domain with support for carriers, similarly to what you did for classical domains.
The aim is to deliver a certain number of crates to injured people. Since JSHOP2 supports numeric fluents and arithmetic functions, you can now abstract away from modeling individual persons and crates, and instead specify only how many crates of each type are needed at each location. This means that the planner does not have to care about exactly which crate of a certain type it decides to pick up and delivered to a certain location, which reduces redundancy and decreases the branching factor: Instead of having to choose among 100 crates to pick up, the planner only has to choose among a few crate types.
Thus, there should be no person objects. A location will implicitly correspond to an arbitrary number of people: A single person needing a single crate of medicine, or dozens of people that together require 30 boxes of food and 20 boxes of medicine. There should also be no crate objects, as you will only specify the number of crates present or required at any given location.
Given this model, you need predicates keeping track of how many crates of each type you have in each location right now, as well as how many of each type are required at that location in total. Similarly, you should explicitly model the capacity of each carrier (which may be different for different carriers) as well as the current number of crates (of each type) on each carrier.
At the middle level, there might be a task such as "(deliver-to location)", which would ensure that a sufficient number of crates of each type is present at the specified location. Note that this, together with the fact that we are using total-order forward decomposition, means that we will never use a single carrier to deliver crates to two distinct locations.
The following conditions must be satisfied:
- You only deliver with a carrier to a certain location if you have at least two boxes left to deliver to that location.
- You only deliver "directly" (without a carrier) to a certain location if there is a single box left to deliver to that location.
When you have verified that your methods generate correct plans, you must define a considerably larger problem instance and use it for additional testing. Then ask a lab assistant to take a brief look at your domain.
Report
Write a report where you answer the following questions as well as the answers to the theory questions:
- Compare building the HTN domain to what you did previously in PDDL. Which parts were easier, if any? Which parts were harder? Why?
- Is JHOP2 faster/slower than the competition planners from previous labs, given your own particular formalization of the domain?
- How does the run time of JSHOP2 scale with larger problems?
Finishing and handing in the results
When you have finished the lab, you need to demonstrate and discuss the results with your lab assistant.
After the demonstration and discussion, you should hand in your results:
- Create a single ZIP file, named fffll111-fffll222-lab4.zip where fffll111 and fffll222 are your liu-ids (assuming you are working in pairs).
- The ZIP file should contain in all domain files, problem files and problem generators you have created or modified, clearly named. It should also contain the report as a simple text file or as a PDF document (no Word or OpenOffice documents, please).
- Send the ZIP file by e-mail to Mikael Nilsson.
Page responsible: Jonas Kvarnstr�m
Last updated: 2019-03-18