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:
The JSHOP2 implementation also contains a GUI for plan exploration. This
GUI calls the planner indirectly and can be used as follows:
/courses/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
use -help for a list of possible options
Fel: Kan inte hitta eller kan inte ladda huvudklassen problem
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.
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:
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:
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:
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.
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:
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:
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.
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 your results.
Since we are working at a distance, this will initially involve:
Making sure that your domain files are sufficiently commented, in order
to explain how you have chosen to model the domain.
Making sure that your report covers the issues discussed above.
Your assistant may ask you questions or ask for a Zoom meeting in case additional information is required.
You should then hand in your results:
Make sure everything is checked in and pushed to the Gitlab project you
were assigned: All domain files, problem files and problem generators
you have created or modified, clearly named, as well as the report as a
simple text file or as a PDF document. Do not use your "own" Gitlab
projects for this.
Then add a submission in
the hand-in
issue tracker. There is no need to generate zip files; simply
provide a link to your repo.