TDDC17 Artificial Intelligence

TDDC17-Lab4

Aim

The aim of this lab is to practice modelling a problem using a formal language that can be understood by an automatic problem solver, in this case a planner. You will do this by writing a model of a planning problem and experimenting with different planners trying to solve the problem. The planners used in this lab are research prototypes developed by various university research groups.

Preparation

You should have read chapter 10.1-10.4 in the course book, and you should have a good grasp of heuristic search.

Modelling Languages

The planners you will use all accept the same form of input, a standardized Planning Domain Description Language called PDDL. This language provides a common syntax and semantics for planning formalisms with varying degrees of expressivity. The language is briefly discussed in section 10.1 of the book, and though the book does not use the standard syntax, the concepts discussed are the same.

Here is a short manual on How to write domain and problem definitions in PDDL. This manual also explains some general aspects of PDDL such as its support for STRIPS and ADL expressivity levels. You should read at least that introductory part before you continue reading below.

Most planners do not support more features than STRIPS, so if you want to use any ADL features in your own domains and problems, you may have to convert them to STRIPS first by using the adl2strips program, which can be found in ~TDDD17/bin.

Planners

There are many approaches to solving planning problems, and many implementations of these approaches.

We recommend that in the first place you use the planners LAMA, FF, IPP and VHPOP. They are good representatives of popular approaches, they perform reasonably well and are also quite stable. They also all support some subset of ADL. In particular we strongly recommend you to start with FF as it is the most mature implementation and gives rather legible error messages. Remember that these are to a large extent research prototypes!

LAMA (LandMarks) :
How to run LAMA (Linux Mint) / How to run LAMA (SunOS)

LAMA is the winner of the sequential satisficing track of the 2008 International Planning Competition (where "satisficing" means that the plans are not necessarily optimal). One heuristic used is based on a domain analysis phase extracting landmarks, variable assignments that must occur at some point in every solution plan. The landmark heuristic measures the distance to a goal by the number of landmarks that still need to be achieved.

LAMA occasionally gives assertion errors for certain domains and problem instances. If this happens, ignore it and try another planner – this is a bug in the implementation, not in your domain.

FF (Fast Forward) :
How to run FF (Linux Mint) / How to run FF (SunOS)

FF is a very successful forward-chaining heuristic search planner (see section 10.2 in the course book) producing sequential plans. Although it does not guarantee optimality, it tends to find good solutions very quickly most of the time, and it has been used as the basis of many other planners (such as LAMA). FF does a variation of hill-climbing search using a non-admissible heuristic, which is also derived from plan graphs (like that used by Graphplan, IPP and others).

IPP (Interference Progression Planner) :
How to run IPP (Linux Mint) / How to run IPP (SunOS)

IPP is a descendant of Graphplan (see section 10.3 in the course book). It produces optimal parallel plans. Graphplan-style planners perform iterative deepening A* search using an admissible heuristic, and use a special graph structure to compute the heuristic and store updates during search.

VHPOP (Versatile Heuristic Partial Order Planner) :
How to run VHPOP (Linux Mint) / How to run VHPOP (SunOS)

VHPOP is a partial-order causal-link planner (see section 10.4.4 in the course book). It can work with either ground or partially instantiated actions, and it can use a wide variety of heuristics and flaw selection strategies and different search algorithms (A*, IDA* and hill-climbing). Depending on the heuristic and search algorithm used, the solution may be optimal or not.

Task 1

In the first part of the lab, you will model a planning domain in PDDL. You can either extend a given domain, or write one from scratch. You should also create at least one problem for your domain, and verify that at least two different planners can solve it.

Feel free to use ADL features (conditional effects, quantified preconditions, etc.) as long as it's supported by at least some planner.

Below are some planning problems for you to choose from. If you want to make up your own problem to model, talk to your lab assistant and/or examiner first to check that it's ok.

Alternative 1: Invent your own domain

If you want, you can make up your own domain to model. If so, please talk to your lab assistant first and verify that your idea is reasonable (not too simple, not too complex).

Alternative 2: Shakey's World

Shakey's world, or versions thereof, is an AI classic. A robot, named Shakey, is moving around in a set of rooms, connected by doors. In some of the rooms there are light switches, so that the light in the room can be on or off. Spread throughout this world there are a number of big boxes and a number of smaller things (balls, blocks with letters on them, toy tractors and whatnot).

Here's an example of a rather small world layout:

 -------------------------------------------------------------------------
 |                       |                       |                       |
 |                       |                       |                       |
 |       light switch 1 -|- light switch2        |- light switch3        |
 |                       |                       |                       |
 |       ---             |                     door2                     |
 |       | |           door1      shakey         |                       |
 |       ---           (wide)                    |                       |
 |       box             |                       |                       |
 |                       |                     door3                     |
 |                       |                     (wide)                    |
 |        room1          |        room2          |         room3         |
 -------------------------------------------------------------------------
  

The following restrictions apply to Shakey's actions:

• Shakey can carry small objects, but only two at a time because he has only two grippers.

• For Shakey to be able to find a small object in a room, the light must be on in that room.

• Shakey can not carry boxes, but can push them around. Boxes can only be pushed through wide doors, not narrow ones.

• To switch the light in a room on or off Shakey must climb onto a box that is positioned below the switch (otherwise he can not reach the switch). This may in turn require moving the box into position, possibly from another room.

Typical problems for Shakey may be to find a specific object (e.g. the green block labeled "G") and bring it to a specific place, to turn the lights on/off in every room, or to remove all boxes and objects from one of the rooms (the last problem may require ADL, since the goal is a "for all").

Alternative 3: Logistics++

The logistics domain is a standard benchmark in AI planning. In this domain, there are a number of cities and in each city a number of places. The goal is to move a number of packages from their initial places to their respective destinations. Packages can be loaded into (and of course unloaded from) vehicles of different kinds: In the standard domain there are trucks and airplanes. Trucks can only move between places in the same city, while airplanes can only move between places of a certain kind, namely airports.

Here is a definition of the standard Logistics domain, using only the STRIPS subset of PDDL, and a small example problem. The domain and problem definitions are fairly well commented. In the planning/strips directory, there are several more Logistics problems. Files log-3-3.pddl through log-4-4.pddl define increasingly larger problems.

Now you should introduce some complications into the domain:

• Introduce some other kind of transportation, e.g. trains, between cities. Like airplanes, trains only "connect" to certain locations within a city. Construct problems in which some cities have only train stations, some have only airports, and some have both.

• Make packages of different sizes, and trucks (airplanes, trains, etc.) with different carrying capacity. Note that "counting" is a bit hard to do in the levels of PDDL generally supported by most planners (since there are no numbers), so you'll probably have to settle for classifying packages as "big", "medium" or "small". Note also that there are at least two variations on this theme: For example, you can let e.g. a "small truck" carry any number of "small" packages but no "big" packages, or you can try to formulate a restriction such as "a truck can carry either one big package or three small packages" (the second variant is much more complicated).

Alternative 4: Emergency Services Logistics

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.

In this lab, we use a comparatively simple version of emergency services logistics:

• There are at least three different kinds of crates: food, medicine, and water.

• Each injured person is at a distinct location, and either has or does not have a crate of any given type. That is, one person might have a crate of food but lack crates of medicine and water.

• The goal specifies which types of crate each person needs. For example, one person might need food and water but not medicine.

• Initially all crates are located at a single specific depot location.

• Two helicopters are available to deliver crates.

• Each 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 and deliver it directly to a specific person at that location. These are three distinct actions.

Your task is to model this domain in PDDL and construct a couple of problem instances of reasonable size. Solve the problems using several planners and verify that the plans generated are correct.

Hint: Remember that preconditions are generally conjunctive. Saying "there exists no crate that the helicopter is carrying" requires existential quantification, which is disjunctive and can't be handled by many planners. This is instead often commonly modeled by using a predicate "(empty ?uav)" which is set to true in the initial state, made false when you pick up something, and made true when you put something down.

Remember also that goals are generally specified as a single conjunction: (and (something) (somethingelse)). Very few planners handle complex formulas as goals.

Examination, Task 1

You should hand in your domain and problem definition files. The files should be well commented: Explain the way you represent the domain and motivate your choice of predicates, objects and operators.

Task 2

In the second part of the lab, you will conduct empirical investigation of the performance of different planners, using the domain you created in the first part. You will do this by creating a suite of problems of increasing size and complexity, running the planners on each problem and measuring runtime.

Experimental Setup

First, identify some "parameters" in your domain that you can use to create a scale of increasingly difficult problems. Such parameters can be the number of objects of different sorts, the number of atoms specified in the problem :goal, etc. For example, in the standard Logistics domain, one can vary the number of cities, the number of locations within each city, the number of packages that have to be moved, the number of packages that don't have to be moved (i.e. aren't mentioned in the goal), and so on. Note that increasing a number does not always lead to harder problems. Adding, for instance, more airplanes to a given logistics problem can make it simpler for some planners to solve, but more difficult for other planners – this depends on the properties on the planning algorithm. In most domains, you should be able to find many different problem parameters (though there are exceptions, e.g. some puzzle domains). If you can, choose at least two parameters to work with.

Next, create a suite of problems in your domain by scaling up your chosen parameters. You should try different combinations, i.e. scaling up one parameter while keeping the other constant, increasing the other alone, and increasing both at the same time. Make sure that your smallest problems are small enough to be solved by the planners.

Run at least two different planners on your problem suite and measure the time it takes them to solve each problem. Note that as problems grow larger, it's often the case that planners don't find solutions in any reasonable amount of time, so you will have to use a cut-off time: between 5 and 10 minutes should be sufficient. Your experiments should result in a sort of graph, showing how the difficulty of solving the problems changes with the changes in problem parameters. Different planners will probably show a different behaviour. Try to find the performance limit of each planner: how big or complicated problems are they able to solve?

It's a very hard problem to explain why the different planners react in various ways to scaling of a particular parameter. Concentrate on looking for the limits for each planner when scaling the different parameters.

Examination, Task 2

You should hand in a written description of your experimental setup (the problem parameters you chose, how you varied them etc.) and the results of the experiment, in the form of tables and/or graphs.

If you're able, try to explain why changes in different problem parameters have (or don't have) different effects on different planners.

---

FAQ

Questions/answers may be added during the course.