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 (almost) state-of-the-art research prototypes developed by various university research groups.
This lab has been developed by Patrik Haslum (pahas@ida.liu.se).
Here is a short manual on How to write domain and problem definitions in PDDL.
As far as possible, you should stick to using only the STRIPS subset of PDDL. Using the ADL features of the language limits your choice of planner, since most planners do not support more than STRIPS.
We recommend that in the first place you use the following three planners: 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.
Here is a short manual on How to run the installed planning systems.
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.
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 follwing restrictions apply to Shakey's actions:
Typical problems for Shakey may be to find a specifc 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 clear one of the rooms of all boxes and objects (the last problem may require ADL, since the goal is a "for all").
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 introduce some complications into the domain:
Examples of puzzles you can model are:
Maze: Moving a rectangular object around a maze. The object can move both length-wise and side-wise, depending on the width of a corridor. It can turn 90 degrees, but only if it's in a wide enough space (turning requires more space than moving side-wise).
Sokoban: You have a maze, in which a person (the "keeper") can move and push around boxes. To push a box in a direction, the keeper must be in the adjacent square on the opposite side. The keeper can never occupy the same square as a box, and neither can two boxes be in the same square. The goal is to push all boxes to a designated goal area (which must comprise at least as many squares as there are boxes, otherwise the problem is not solvable).
Note that this is a very hard problem: even the best planners will most likely only be able to solve small problem instances.
Flip: In this puzzle, you have a board with NxN squares, where each square can be either black or white. You can "flip" either a row or a column, which makes each square in the row resp. column change color, to white if it's black and to black if it's white. The goal is transform an initial configuration into a final one, e.g. an all-white or all-black board.
Note that to model this puzzle, you will have to use ADL actions (since the actions have an effect on all squares in a row or column, and since the effect depends on the previous state of each square). Also note that the number of reachable configurations from any given starting configuration is quite small: This means that if you take a random assignment of black and white squares and try to change it to e.g. an all-black board, there's approx. three-quarters chance that there is no solution. Pick your problem instances carefully.
There are two versions of blocksworld: Either there is a robot arm picks up and places the blocks, in which case only one block can be moved at a time, or the robot arm is omitted from the model, in which any number of blocks can be moved in parallel (as long as the moves are independent of each other). You can find an example of the later version in planning/strips/bw.pddl.
Now extend the domain as follows: There are two robot arms, each of which can hold at most one block at a time. To pick up or put down a block, an arm has to be above the stack or place on the table where the block is or is put. The arms are positioned beside each other (i.e. one is to the left and the other is to the right) and can not move past each other. For example, this means that the right arm can not pick up a block from a stack that is left of where the left arm is at the moment.
A simple approach to modelling this domain is to use "named" positions on the table, but this has several drawbacks: it makes the table capacity limited (which may make some problem instances unsolvable, although they would be solvable with a larger table) and it will have a negative effect on the performance of many planners (naming the table spaces creates a large state space in which many states are simple permutations of each other, and planners may spend much time doing unnecessary search). To model the domain properly, you will have to use ADL actions (to keep track of which blocks are left and right of each other; keep in mind that when you place block A left of, say, block B, block A also becomes left of all blocks that are to the right of B).
Next, create a suite of problems in your domain by scaling up your chosen
parameters. You should try different combinations,
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.
If you're able, try to explain why changes in different problem parameters have (or don't have) different effects on different planners.