Lab 1: Modeling classical planning domains

Read the lab introduction page before you start!
The introduction contains important information that is common to all labs.

Updates

Any updates or changes we make in the instructions for this lab during the course will be announced here.

Introduction

The aim of the first two labs is:

• To practice modelling planning problems using a formal language that can be understood by an automated planner, and
• To give a feeling for the capabilities and limitations of today's domain-independent planning technology.

You will do this by using a classical fragment of PDDL to model a logistics domain for UAVs (unmanned aerial vehicles, typically helicopters). This domain will initially be quite simple and will later be gradually extended, in this lab as well as future labs. You will test your PDDL domain specifications on a number of problem instances using a set of well-known classical planners developed by various research groups around the world.

Because we want to be able to test using a wide variety of planners, we will focus on the STRIPS level of expressivity in PDDL. In other words, we will not yet begin to use negative preconditions, negative goals, conditional effects, or similar extensions. Many planners do support some extensions, but few planners support exactly the same ones, and they often have limitations or bugs. To avoid trouble, use the STRIPS level of expressivity at least in the beginning. This will be sufficient for all the modeling tasks in labs 1-3. (Using :typing should be OK; it's changes to the permitted formula types that we want to avoid.)

Note that we are talking about avoiding negative preconditions and goals. Negative effects are always allowed and are in fact required for almost all ordinary planning problems.

Most likely, you will start working with this lab before we go through the different planning techniques that are used in current classical planners. If this is the case, detailed descriptions of certain planners may not make much sense. But don't worry: The main point of this lab is to understand how planning domains are modeled and how current planners perform.

Writing a Report

After you finish all parts of this lab, you will hand in the domain and problem files you generate, as well as a short(ish) report on your results as discussed in each exercise below. There is no minimum (or maximum) page count for this report, and you do not need to write a long introduction or be extremely formal. Simply write a clear and comprehensible report on the results we ask for. You can include (all or part of) the output from running certain planners if this is helpful in explaining your results. Any suggestions you may have for improving the lab or the instructions are also very welcome – we want your feedback!

The report can be handed in as a simple text file, a PDF document, or a Markdown document in your repository (no Word or OpenOffice documents, please).

Throughout the instructions, we will show what you need to include in the report.

Getting started

Before you start, make sure you have received an email with a link to a Gitlab project for your Webreg group. Navigate to the repository, clone it, and do all your developent within that repository. Don't forget to commit your changes and push them to Gitlab regularly.

Do not create your own Git repository for this course. You need to do your development in the repository we provide for you.

If you should happen to be unfamiliar with Git and Gitlab, there are introductions in Swedish (TDDE23) and also plenty of tutorials in English on the web. You can also ask the lab assistant if you are stuck.

Lab 1.1: Emergency Services Logistics, Initial Version

In the emergency services logistics domain, a number of persons at known locations have been injured. Your task is to deliver crates containing emergency supplies to each person.

The initial version of the domain will be as follows:

• Each injured person is at a specific location.
• Each crate is at a specific location and has a specific content such as food or medicine. Note that it might be tempting to introduce predicates such as (is-food-crate ?c) and (is-medicine-crate ?c) to model the contents of crates. But then the domain has to be changed if a new crate type is introduced (water, different types of medicine, ...). Instead you must deal with crate contents in a generic way, so that new contents can easily be introduced in the problem instance. That is, you should be able to ask the question "does crate X have content of type Y?".
• Each person either has or does not have a crate with a specific kind of content. That is, you must keep track of whether they have food or not, whether they have medicine or not, and so on.
• There can be more than one person at any given location, and therefore it isn't sufficient to keep track of where a crate is in order to know which people have been given crates! You must instead associate the crate with the actual person.
• Initially all crates are located at a single location that we may call the depot. There are no injured people at the depot.
• The goal should be that certain people have crates with certain contents. Some people might not need crates, some people might need both food and medicine, and so on. This means that you have to deliver some or all of the crates at the depot. Note that people don't care exactly which crate they get, so the goal should not be (for example) that person1 has crate5, merely that person1 has a crate of food.
• A single helicopter, initially located at the depot, is available to deliver crates. It can fly directly between arbitrary locations (there is no "roadmap" with specific connections that must be taken). Since we want to be able to expand this domain for multiple helicopters in the future, we use a separate type for helicopters, which currently happens to have a single member in all your problem instances.
• The helicopter can pick up a single crate, if it is at the same location as the crate. It can then fly to another location with the crate. Finally, it can deliver a crate to a specific person who is at the same location. Doing this will result in three distinct actions in a plan.

You should do the following:

1. Model the domain in the STRIPS level of PDDL, and manually construct two small problem instances: One with only a single person and a single crate, and one with two people and three crates.

   • Avoid using negative preconditions (and goals), which some planners do not handle correctly, or you may run into trouble later (but do use negative effects). Avoid other extensions as well. Further motivation: At the top of this page.
   • There is a PDDL mode for Emacs that can be of some help, and a Visual Studio Code plugin that can be of much more help (see instructions in the introduction).
   • Some planners are very picky about getting the syntax right and will crash in strange ways if you get it wrong. Remember that you should have spaces on both sides around " - ", as in "?c - crate". Writing "?c -crate" is not the same, because "-crate" can be interpreted as a valid identifier!

2. Make sure you have read the instructions about running planners.

3. Run the domain and problem instances through the FF planner and possibly the "parser" tool to ensure they are correctly specified. Make sure you get a reasonable plan from FF. (The reason we use FF here is that its parser is generally quite robust and gives reasonable error messages. It doesn't catch everything, though.)

4. Begin writing your report. For lab 1.1, please tell us whether you had any specific difficulties in modeling the problem domain or getting FF to generate a plan.

When you have done this and verified that the domain works properly, you may want to ask a lab assistant to take a look at your domain to verify that there isn't anything obviously wrong or inefficient in the model you developed. This can also be done by submitting a Gitlab issue in the question project.

If you skip this step completely, you may find later that you spend twice as much time as necessary on future labs because your model has a flaw or is unnecessarily complicated! (But of course you should continue working with the remaining tasks until you get an answer from the assistant.)

Lab 1.2: Early State Of The Art Planners

Now, as part of a small demonstration of how planning performance has changed over the years, we'll move a little bit backwards in time and use the planner IPP, Interference Progression Planner. This planner won the more expressive ADL track (but not the less expressive STRIPS track) of the 1998 International Planning Competition, and while it is thoroughly obsolete by now, some of the underlying ideas live on in Relaxed Planning Graph heuristics. These heuristics are still very useful and will be covered to some extent during the lectures.

You should do the following, and discuss your findings in the report. Make sure that you clearly show exactly what you did to get the results that you are reporting, preferably by specifying exact command lines used. Fuzzy specifications such as "the one with 8 crates" or "the first two problems" are less useful.

1. Run the two problems you created earlier through IPP according to the IPP instructions. How much time does this take? (Note that IPP has some special requirements for type specifications, which is noted in the IPP instructions linked above.)

2. Continue creating larger problems and running them through IPP. How large problems can IPP solve within a one-minute time limit? What happens when you increase the number of crates that are not necessary for the problem? What happens when you increase the number of people that need crates? Discuss your findings briefly in your report for lab 1.

   You generated the first couple of problem instances manually, in order to better understand what is needed. At this point, you may choose to continue in the same way, but we strongly recommend that you complete and extend a problem generator skeleton written in Python, available in your Git repository. This generator will become more and more useful in later labs, when it can for example help you generate correct and consistent distances between all pairs of locations.

   The skeleton is deliberately incomplete. This is necessary because providing a full problem generator would also lead you directly towards a particular formulation of the problem domain. The intention is instead that you come up with your own problem domain and then adapt the problem generation to your own model.

   To use the generator, you finish the implementation and then run:

       python3 ...../generate-new.py -u 1 -r 0 -l 50 -p 3 -c 101 -g 4 

   ...if you want (for example) 1 UAV, 50 locations, 3 people, 101 crates and 4 actual goals (crates that need to be delivered). This is just an example; begin with smaller problems!

   If the skeleton won't run, try doing "unset PYTHONHOME" first ("unsetenv PYTHONHOME" in some shells).

Lab 1.3: Newer Planners

At this point we'll return to "modern" days and consider a number of sequential satisficing (non-optimal) planners from the International Planning Competitions in 2011, 2014, and possibly 2018.

Here you should be aware of the competition rules for "sequential satisificing" planning, which reward the highest plan quality that a planner can reach within a time limit of 30 minutes. For this reason, many (but not all) of the planners continue working after the first solution is found, searching for the full 30 minutes in the hope of finding a better plan ("anytime" planning). Their output may even end with "No solution found" even though they found some solutions earlier; this really means "no better solution found within the time limit". The safest way of finding the solutions is therefore to look at the generated output files.

However, finding a strictly better plan than the first one can be much harder in many cases. Planners typically do not have any way of taking one solution and optimizing it "in place" by modifying parts. Instead, they "backtrack" and keep searching in new parts of the search space in the hope of finding something better. They may have admissible heuristics helping them prune branches where they definitely can't find a strictly better solution, but heuristics are not perfect. The planner often has to go pretty deep before it realizes that while this part of the search space probably contains plans that are pretty good... none of them can be strict improvements. When searching for the initial solution, finding a "pretty good" plan was enough.

And if there is no better plan than the other one, it can take an even longer time to determine this.

Note that some of the planners also generate a great deal of output inbetween plans, which means you may want to pipe the output through a tool such as "less" if you want to have a chance to see the plans that are generated. This is discussed in more detail in the planner instructions.

For this exercise we want you to use the following planners:

• lama-2011, a heuristic search planner based on landmarks; the winner of the sequential satisficing competition in 2011.
• madagascar-p (ipc-2011), based on satisfiability checking rather than heuristic forward-chaining search.
• One of the following planners: YAHSP3 (ipc-2014, with two variations: "first" only gives you the first plan that is found, while the other one continues to try to find better plans), Jasper (ipc-2014, can sometimes crash after finding the first plan), Arvand (ipc-2011) or forkuniform (ipc-2011). If you want to know more about these planners, you can read parts of the papers that describe them (links can be found in the planner instructions). Note that we don't expect you to know and understand the inner workings of the planners.

• At least one planner from ipc-2018. These planners were only recently installed, due to their reliance on the Singularity containerization system. They are less well tested than the other planners, but should still contribute to your understanding of current planner performance!

  This is new (2022), so don't hesitate to ask the lab assistant if you encounter any problems!

  To run one of the newer ipc-2018 planners:

  cd [folder where your pddl files are] singularity run -C -H "$(pwd)" /courses/TDDD48/planners/ipc2018/seq-sat/[name of planner image] domain.pddl problem.pddl myoutput

  For example, if you choose the freelunch-madagascar planner (use ls to see which planners exist in the specified folder):

  cd /home/liuid123/tddd48/repo/lab1/lab1.1 singularity run -C -H "$(pwd)" /courses/TDDD48/planners/ipc2018/seq-sat/freelunch-madagascar.img domain.pddl problem.pddl myoutput

  The "$(pwd)" is there because Singularity needs to mount a folder where it can read your domain and problem files, and this needs to be specified as an absolute path, so "." won't do.

  Note that planners can create temporary files in that directory. Please try to avoid adding those to your Git repo.

You should do the following:

1. Run the largest problem you created earlier through the selected planners according to the planner instructions. How much time does it take before the first solution is generated? Again, be aware that some planners keep trying to generate better solutions after the first one. (If you encounter problems, please talk to your lab assistant rather than spending hours trying to resolve them yourself.)
2. Continue creating larger problem instances and running them through the planners. How large problems can they solve within a one-minute time limit? (By "one minute" we mean approximately one minute: Don't stop with problems that only require 45 seconds, but you don't need to spend a lot of additional time on finding out what they can do in 5 minutes.)

The intention is for you to get a general idea of how much time a planner might take and how large problems it can solve. It is NOT important to have very precise measurements or to do a very deep analysis.

Lab 1.4 Theory: State Space and Branching Factor

In this part you will familiarise yourselves with the size of planning problems and why they grow quickly. This is done by calculating the size of a state space, by calculating the size of a restricted state space so that only those states that are reachable are considered, and by finding the highest branching factor possible. Solve all problems and include the answers in your report.

The intention behind this part of the lab is to make you think a bit more deeply about some aspects of planning problems, to gain a level understanding that will help you later and perhaps during the exam. Don't worry if you are uncertain about the answer; then you can hand in your best attempt and we'll have a discussion / provide some tips when we have

Related issues are discussed in the lecture discussing the state space and forward state space search. If you have not yet attended that lecture, you may choose to start working with Lab 2 first.

1. Consider a planning problem where the domain consists of of the following untyped predicates:

   ;; "Ordinary" predicates
   (at ?uav ?loc), (has-photo-of ?t), (photo-possible ?loc ?t),
   ;; Type predicates
   (uav ?uav), (location ?loc), (target ?t)
   

   Assume the problem instance contains the objects uav1, loc1, loc2, target1 and target2. How many states exist in the corresponding state space, including both "sensible" states and "meaningless" ones, and including all possible and "impossible" instantiations of type predicates? Note that we are not talking about states that are reachable from some other states; we are talking about all states in the state space.

2. Generalize your answer to the case where there are U UAVs, T targets and L locations (O=U+T+L objects in total).

3. Assume instead that the domain and problem instance are typed, with the obvious interpretation of names (?t can only have the values target1 and target2). For example, this means that (photo-possible loc1 uav1) cannot be true, because uav1 is not a target. We also remove the type predicates, retaining the following ones:

   (at ?uav ?loc), (has-photo-of ?t), (photo-possible ?loc ?t)
   

   How many states will exist in this case, first for the small problem instance and then in the general case with U UAVs, T targets and L locations? Motivate your answer!

4. Assume that the following operators exists:

   (action move
     :parameters (?uav ?from ?to)
     :precondition (and (uav ?uav) (location ?from) (location ?to)
                      (at ?uav ?from))
     :effect (and (not (at ?uav ?from)) (at ?uav ?to)))
   (action take-photo
     :parameters (?uav ?loc ?t)
     :precondition (and (uav ?uav) (location ?loc) (target ?t) (at ?uav ?loc)
                      (photo-possible ?loc ?t))
     :effect (has-photo-of ?t))
   

   The branching factor of a node n is the number of successors of n.

   When we do forward search in the state space, each successor to a node is created by applying an applicable action to the node (which is a state). Strictly speaking, more than one action could lead to the same successor – that could be the case for the take-photo action above, where the ?uav parameter is irrelevant when we compute the successor state. However, that will not be considered in this question. Instead, to simplify your task, we will consider how many unique actions might be applicable. This is then an upper bound on how many unique successors this might lead to, a value that we will not compute.

   Now suppose that we start in a physically meaningful state – for example, not a state where objects are in multiple locations at once or where (uav target1) is true. What is the highest possible number of unique applicable actions (action instances) in any node/state reachable from such a meaningful state, given the above mentioned operators and predicates, assuming that there are U UAVs, T targets and L locations (still T=U+T+L objects in total)? You may make "optimistic" assumptions about photo-possible(...) facts in order to maximize the total number of possible instances of take-photo. Motivate your answer.

   Example: In the blocks world you could say that "if all N blocks are on the table, then I have N different actions I could choose to perform". This would be the maximum for any reasonable state. If you could have a state where all blocks are on all blocks at the same time (which is a state, but not a "reasonable" state), then you could have N*N alternative unstack actions that would all be executable in the same state... but we're not interested in those "strange" states right now.

Finishing and handing in the results

When you have finished the lab, you need to hand in your results. For this lab, no demonstration is necessary. Instead:

• 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, Markdown file or 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.