Hide menu

TDDD48 Automated planning (6 ECTS)

Lab 1: Modeling classical planning domains

Written by Jonas Kvarnström.

Read the lab introduction page
before you start working on this lab!

The introduction contains important information that is common to all labs and exercises.

Updates

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

Introduction

The aim of the first two labs is (a) to practice modelling problems using a formal language that can be understood by an automated planner, and (b) to give a feeling for the capabilities and limitations of today's domain-independent planning technology.

You will do this by using the 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.

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 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. Please include any suggestions you may have for improving the lab or the instructions – we want your feedback!

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

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

    • Try to avoid using negative preconditions, which some planners do not handle correctly.
    • There is a PDDL mode for Emacs that can be of some help (see instructions in the introduction).

  2. Make sure you have read the instructions about running planners, including how you log in to Crabbofix to run planners there.

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

  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:

        python ./generate.py -u 1 -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 Competition in 2011. Here you must be aware of the rules of the competition, which rewards 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). Some of the planners also generate a great deal of output inbetween plans, which means you need to pipe the output through a tool such as "more" or "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.

You should use the following planners:

  • lama-2011, a heuristic search planner based on landmarks; the winner of the sequential satisficing competition in 2011.

  • yahsp2, another heuristic forward-chaining search planner.

  • madagascar-p, based on satisfiability checking rather than heuristic forward-chaining search.

  • Any other planners you want to try – but note that we have not tested all of them, simply compiled them, and it is quite possible that some of them do not work.

You should do the following:

  1. Run the largest problem you created earlier through these planners according to the planner instructions. How much time does it take before the first solution is generated? (If you encounter problems, please talk to your lab assistant rather than spending hours trying to resolve them yourself.)

  2. Continue creating larger problems and running them through the planners. How large problems can they solve within a one-minute time limit? Discuss your findings briefly in your report for lab 1.

Finishing and handing in the results

When you have finished the lab, you should once again ask a lab assistant to take a look at your final domain to briefly check whether the model you developed appears reasonable.

When you hand in your results:

  • Create a single ZIP file, named fffll111-fffll222-lab1.zip where fffll111 and fffll222 are your login names (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: 2013-03-28