Hide menu

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
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.

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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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!

  7. 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.

  8. 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.

  9. 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.

  10. 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".

  11. 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:

  1. 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.
  2. 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.
  3. 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.
  4. 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:

  1. Compare building the HTN domain to what you did previously in PDDL. Which parts were easier, if any? Which parts were harder? Why?
  2. Is JHOP2 faster/slower than the competition planners from previous labs, given your own particular formalization of the domain?
  3. 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