Hide menu

Lab 1: Modeling classical planning domains

No changes are planned for 2021.

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 UAV logistics domain that will initially be quite simple and later be gradually extended, in this lab as well as future labs. You will then 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.

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.
  • Each person either has or does not have a crate with a specific 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!
  • 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.

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

  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 should ask a lab assistant (during a scheduled lab) to take a look at your domain to verify that the model you developed appears reasonable. You can do this during a lab session in Teams, or you can send in a Gitlab issue in the question project.

Don't miss this step, or 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! (Of course you may continue working if no lab assistant is available right now, but make sure you ask as soon as possible.)

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 is based on GraphPlan, which will be discussed during the lectures, and won the more expressive ADL track (but not the less expressive STRIPS track) of the 1998 International Planning Competition.

You should do the following, and discuss your findings in the report:

  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 or to use and extend a problem generator skeleton written in Python. To use this generator, you download it, place it together with your domains and problem instances for lab 1.2, and call:

        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). If the skeleton won't run, try doing "unsetenv PYTHONHOME" first ("unset PYTHONHOME" if you use the Bash shell).

    The intention is that we provide a partial implementation that you can finish according to your particular domain model, so initially part of the generator is missing and needs to be filled in.

Lab 1.3: Current State of the Art Planners

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

Here you should be aware of the competition rules, 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 do not terminate when the first plan is found, but continue searching for the full 30 minutes in the hope of finding a better plan ("anytime" planning).

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

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

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.

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 ?p), (photo-possible ?loc ?p),
    ;; Type predicates
    (uav ?uav), (location ?loc), (photo ?p)
    

    Assume the problem instance contains the objects uav1, loc1, loc2, photo1 and photo2. 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, P photos and L locations (T=U+P+L objects in total).

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

    (at ?uav ?loc), (has-photo ?p), (photo-possible ?loc ?p)
    

    How many states will exist in this case, first for the small problem instance and then in the general case with U UAVs, P photos 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 ?p)
      :precondition (and (uav ?uav) (location ?loc) (photo ?p) (at ?uav ?loc)
                       (photo-possible ?loc ?p))
      :effect (has-photo ?p))
    

    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 photo1) 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, P photos and L locations (still T=U+P+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.

    NOTE: A "photo" is intended to be a "target" or a "photo opportunity". That is, if photos photo1 and photo2 exist, this means that these are two separate photos you want / two separate targets you want pictures of. Similarly, (has-photo ?p) means that you have a photo of a particular target. If (photo-possible ?loc ?p) is true, then you can take this photo at location ?loc.

    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. 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: 2021-05-27