Hide menu

Lab 4: Hierarchical Task Network Planning

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 (Partial-order Forward Decomposition) procedure in the book, 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 we will not require you to use partially 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. Alternatively, you can use a Lisp mode in Emacs or other editors to help you with indentation and highlighting comments. Unfortunately, neither of these modes are going to provide the kind of support you get in a VSCode PDDL mode.

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:

    /courses/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:

    /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 when trying to start the GUI, without any other errors preceding it (such as exceptions):

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. They still serve to exemplify HTN domains in JSHOP2 and demonstrate the syntax used, but you should mainly focus on the explanations given on this page.
  • 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, but beware: Many of them are rather complex, and your main source of information should probably be this page and the manual.

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 mention them in the specification of initial states and tasks to perform.

    Because SHOP implicitly defines objects when you mention them, you must be very careful not to misspell objects. If you mention heli1 and then helil, you will get two distinct objects, not a warning.
  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 
    	  )

    For example:

    (:operator (!load-truck ?obj ?truck ?loc)
    	  ((at ?truck ?loc) (at ?obj ?loc))
    	  ((at ?obj ?loc))
    	  ((in ?obj ?truck))
    	  )
    • 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.

    • All facts in the deletelist will be removed.

    • All facts in the addlist will be added.

  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.

    Suppose you want a plain conditional effect, without any quantification: If cond is true, then something should happen. There is no separate syntax for this; instead you quantify over the empty list of variables. The empty list is denoted by nil in Lisp, so you write "(forall nil (cond) (what-you-want-to-add-or-delete))".

  4. Quantification can also be used in preconditions: (forall (?p) (in ?p ?truck) (is ?p medicine)) would mean that for every ?p such that (in ?p truck) is true (where ?truck may be an operator parameter), the formula (is ?p medicine) is also true.

    If you want to check existence, use the fact that "exists t: phi(t)" is equivalent with "not forall t: not phi(t)".

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

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

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

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

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

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

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

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

Debug version of JSHOP

It's easy to run into problems when trying to debug what happens with JSHOP2 and where it is searching for plans.

Therefore, we've also compiled a slightly modified test/debug version where we have added some printouts to the source so that you can see more about how the search space is explored. Use it as follows:

    /courses/TDDD48/bin/jshop-test/jshop2-command domainFile problemFile |& less

When you run timing tests, use the "old" version without all the output!

The output can look like this, showing the TaskLists (similar to the lists of tasks shown in the simplified representation from the lecture), which tasks are being decomposed.

====================================================================================================
Main search level 0: Plan so far is:
Plan cost: 0.0

--------------------

Main search level 0: Global TaskList is ((deliver-all))
Main search level 0: Now trying to achieve TaskList ((deliver-all))
Main search level 0: Which subtasks could be expanded first?

Find potential first tasks, level 0, non-atomic task: [(deliver-all)]
Find potential first tasks, level 0: Task is ordered, checking subtasks
Find potential first tasks, level 1, atomic task: (deliver-all)
Find potential first tasks, level 1: Task is atomic, returning (deliver-all)

Main search level 0: Could be expanded first: One of [(deliver-all)]

Main search level 0: Expanded non-primitive task (deliver-all)
Main search level 0: Method params are [null, null, person1, food, loc1, crate1, uav1, null]
Main search level 0: Resulted in TaskList ((pickup-crate uav1 crate1) (be-at uav1 loc1) (!unload-crate uav1 crate1 VAR7 person1 food) (deliver-all))
Main search level 0: Recursing to expand more tasks
    

Some explanations:

  • The "main search level" is the depth in the DFS search tree used by SHOP. The "plan so far" is a list of actions actually added to the plan; right now it is empty. At the next step, SHOP may have added a new action to the plan, OR it might have expanded a method one step, which doesn't necessarily lead to actually adding an action.

  • The global task list is ((deliver-all)), containing one deliver-all task with no parameters. This is what the planner should now expand. Right now there is only one thing that can be expanded first, as you can see above, but sometimes the planner may have different alternatives.

  • Expanded non-primitive task (deliver-all) says that it expanded this task...

  • Method params are [null, null, person1, food, loc1, crate1, uav1, null] tells you the values of all method parameters. You can get nulls in the list because SHOP keeps track of all possible parameters and forgets about which ones were actually used by this particular method...

  • Resulted in TaskList ((pickup-crate uav1 crate1) (be-at uav1 loc1) (!unload-crate uav1 crate1 VAR7 person1 food) (deliver-all)) tells you the end result after deliver-all was replaced with new tasks. Here VAR7 is a parameter that isn't bound, which may or may not be a problem -- you are leaving it up to the next step to provide an actual value for the variable.

  • ...and so on...

This is not necessarily intuitive, but it should still help you see where it is recursing infinitely if this happens, and a bit about what parameters are used in the recursion. In particular, you might focus on the task lists:

    /courses/TDDD48/bin/jshop-test/jshop2-command domainFile problemFile |& grep "Global TaskList" | less

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) and should show what happens in the planner, step by step. To show what happens, there are a couple of alternatives:

  • Illustrate each step using full hierarchical diagrams as shown in many of the slides.

  • Illustrate each step using a linear left-to-right "task list" with actions, a current state, and a tail of unexpanded non-primitive tasks. This was also used as a "simplified" representation in the slides and it is closer to what is actually used in the TFD algorithm.

Regardless of which method is used, the following must be clear from your description:

  • Which task was expanded in a given step

  • Which method / operator was used, including all actual parameters

  • What the task was expanded to (new action / new subtasks)

  • What the "current" state is, and where in the hierarchy or task list it is actually valid (after a certain action / ...)

Doing this is also a good way of ensuring that you understand the algorithm better, which may be needed for the 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 tasks 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 using their corresponding current states and the given methods and primitive tasks.

  • Current 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)>
  • Current 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)", without parameters.

    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. This will be initialized in the initial state.

    The general form of a problem file is as follows (where "problem" and "domain" on the first line could in theory be your own names, but in practice there are addvantages to leaving them as they are):

    	(defproblem problem domain 
    	;; Initial state
    	((at x y) (has z w) (raining) ...)
    	;; Initial task list
    	((do this) (do that) (do something else))
    	)
          
  • Creating a domain definition file in the JSHOP2 syntax. The general form of a domain definition file is:

    	(defdomain domain
    	(
    	;; Declarations...
    	(:operator ...)
    	(:method ...)
    	)
    	)
          

    Do not call the file domain.txt or something else ending in .txt. Then SHOP may overwrite your file!

  • 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 that deliver crates to exactly those people who need them.

The solutions generated should be reasonable but does not necessarily have to be optimal.

Hints

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. Your task is essentially "while there are packages, deliver the next package". Remember that recursion can replace iteration. For instance, to deliver "all crates that are needed", you can break this down into an "initial" delivery and a recursive call to deliver the rest.

  3. Remember that SHOP methods work like "if-elseif". This may be quite useful in terminating your recursion.

  4. Remember how you modeled the number of crates on a carrier in lab 2. You might have used atoms such as (crates-on-carrier carrier1 num0) to represent that there are zero crates on carrier1, and every time you changed the number of crates, you needed to add and delete instances of crates-on-carrier. You can now keep track of the number of crates of a particular type at a particular location in a very similar way. However, since SHOP supports actual numbers, you can use 0 instead of a manually defined value called n0, and you can use call functions instead of manually defined predicates such as next in order to do addition, subtraction and so on.

Troubleshooting: Error messages

  1. "Expecting RP..." means "expecting right parenthesis". Similarly, LP is left parenthesis.

    Also, the parser is not smart enough to suggest all possible alternatives for what you could write in a particular location. "Expecting RP" could mean that the parser has looked for a left parenthesis starting a new atom, didn't find one, and then thought that a right parenthesis was the only remaining option.

  2. If you get a StackOverflowError for complex problems where you expect long plans, but not for smaller ones, try changing -Xss2048K to -Xss16384K in the jshop2-command you are using (the standard or tracing/debugging version). This has already been done for the version available on the university computers. Running ulimit -s unlimited in the shell where you run jshop2-command could also be useful.

    If you get a StackOverflowError even for small problem instances, you probably have a case of infinite recursion. Go to the next section.

    Note: When you get a StackOverflowError, it will be followed by a long stack trace. Unless you scroll up (far!), you might only see something like this:

    	...
    	at JSHOP2.JSHOP2.findPlanHelper(JSHOP2.java:325)
    	at JSHOP2.JSHOP2.findPlanHelper(JSHOP2.java:325)
    	at JSHOP2.JSHOP2.findPlanHelper(JSHOP2.java:259)
    	at JSHOP2.JSHOP2.findPlanHelper(JSHOP2.java:259)
    	at JSHOP2.JSHOP2.findPlanHelper(JSHOP2.java:325)
          

Troubleshooting: Other Problems

  1. You should probably try some of the later tips first... but if they don't help, try the GUI or the debug version of JSHOP, and see where it stops / fails / backtracks or (using the trace version) what it does before the stack overflows. If you just want to see generic information about sequence of task lists being checked, filter the output:

    jshop2-test/jshop2-command domain problem |& grep "Global TaskList"

    Or:

    ... |& grep "Global TaskList " | sed -e "s/(\\+/(/g" -e "s/)\\+/)/g" 

    The "sed" commands remove duplicate parentheses, making task lists easier to read.

  2. Always try to minimize the problem size before debugging. Also try changing the initial task list to test your "sub-methods" and your actual operators rather than going directly for deliver-all. Can you fly the UAV to a location? Can you load a single crate of a hard-coded type onto a specific carrier? And so on. This can help you pinpoint the problem.

  3. Remember that the "addlist" and "deletelist" are lists of atoms, which are also lists. An addlist can't be simply (at ?uav ?dest); you have to say ((at ?uav ?dest)). If you miss this, you can get "expecting RP".

  4. The expression (call ...) is not a formula (which is true or false); it is a kind of term, something that returns a value (similar to a variable such as ?loc or a value such as uav1, which are also different types of terms).

    This means you can't add or delete a call expression; you can only use it where a value is expected. For example, it can be a parameter to a predicate, inside an atomic formula that is part of a precondition, an addlist, or a deletelist.

  5. Check if you misspelled something somewhere, or missed a question mark for a variable. SHOP is very sensitive to this as it doesn't require you to declare symbols before using them.

    Check the *.txt file generated by SHOP (often "domain.txt"). It has three sections listing all constants (constant symbols such as predicate names and names of values), methods (compound tasks), and operators (primitive tasks) that are implicitly declared in the domain file. Do you see anything that seems off?

    Use the error checker, which can find certain problems related to misspellings (but not everything).

  6. Be aware that negated literals do not bind variables. You must provide bindings before the negation; for example, you can say ((person ?person) (content ?content) (not (needs ?person ?content))), but it won't work if you just say (not (needs ?person ?content)).

  7. Remember that SHOP methods work like "if-elseif". This may be quite useful in terminating your recursion.

    You should also consider what this means in combination with the use of free variables. Suppose you have a method that starts like this:

    (:method (deliver-foo)
      ;; precond1
      ((person ?person) (content ?content) (not (needs ?person ?content)))
      ;; subtasks1
      ...
    
      ;; precond2
      ...
      ;; subtasks2
      ...
    )

    Notice that ?person and ?content are free variables, not occurring in the method parameters. The planner then essentially begins with the following:

    satisfied = False
    
    for each binding of ?person and ?content that satisfies precond1:
        satisfied = True
    
        # Let's check if expanding deliver-foo to subtasks1 actually works
        if subtasks1 can be successfully expanded:
            return a SOLUTION!
    
    if satisfied:
        # We didn't actually find a *solution* above.
        # But since we found bindings that satisfied precond1,
        # we still shouldn't try with preconds2/subtasks2.
        # Let's give up instead.
        return
    
    # We never managed to find bindings that satisfied precond1,
    # so try the second expansion with precond2 and subtasks2 instead
    
    for all bindings that satisfy precond2:
        satisfied = True
        if subtasks2 can be successfully expanded:
            return a SOLUTION!

    In other words, the planner does check all possible variable bindings that might satisfy precond1, and keeps iterating if the first variable binding didn't result in a solution. But then, if there was a variable binding that satisfied precond1, it will not try the second expansion at all.

  8. If the tracing/debugging version (or the GUI) shows parameters such as VAR1, VAR2 and so on, then this means that you are calling a method or an operator with an unbound variable. This can turn out to work well, but it can also lead to trouble in some situations. You may want to add additional preconditions to the method that called the subtask, ensuring that the variable (which may in your domain file be called ?loc or ?carrier or something else) is properly bound.

    For example, if you have a location type predicate, simply saying (location ?loc) in the precondition will ensure that the variable has a proper value before a subtask is called with this variable as a parameter. You may also want to add other constraints such as (at ?uav ?loc) that would further constrain the possible values of ?loc, but of course such constraints have to be adapted to whatever is actually required in the method you are defining.

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 of a particular type that are 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. (Delivering to multiple locations from one carrier is certainly possible, but requires some additional bookkeeping and modeling that is outside the scope of this lab.)

The following conditions must be satisfied, which may require adding further predicates specifying how many crates in total (for all content types) are required at any given location:

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

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. How does the run time of JSHOP2 scale with larger problems? Please test this with larger problems that require at least a minute to run using a modified problem generator. Include actual timing and plan length results for different problem sizes in your report!

    Note 1: Depending on your domain, 1 minute might be too much. If you can reach 20,000 actions, you do not necessarily have to go any further. You definitely need to reach 10,000 actions in a minute.

    Note 2: This may lead to StackOverflowError; see the error message section above.

    Note 3: Are you getting significantly less than 10,000 actions in a single minute? If so, your domain is probably written in a way that doesn't provide enough guidance to JSHOP2. As there is no other guidance than what you provide, JSHOP2 is highly sensitive to your precise formulation, and not providing sufficient guidance will cause the planner to search (depth first!) through a vast number of alternatives before it finds a path that actually leads towards a goal. In this case, please use the debug version of JSHOP2 to try to find out what is happening, possibly with the help of the lab assistant.

  3. Is JSHOP2 faster/slower than the competition planners from previous labs, given your own particular PDDL and HTN formalizations of the domain? How much?

Finishing and handing in the results

When you have finished the lab, you need to hand in your results. Since we are working at a distance, you should:

  • Make sure that your domain files are sufficiently commented, in order to explain how you have chosen to model the domain.
  • Make sure that your report covers the issues discussed above.
  • 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.

Your assistant may ask you questions or ask for a Zoom meeting in case additional information is required. Alternatively, your hand-in may be approved without a demonstration.


Page responsible: Jonas Kvarnstr�m
Last updated: 2023-04-18