Swedish web site
TDDC17 Artificial Intelligence
TDDC17-Lab3
Aim
The aim of this lab is (a) to practice modelling a problem using a formal language that can be understood by an automatic problem solver, in this case a planner, and (b) to give a feel for the capabilities and limitations of today's domain-independent planning technology.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).
Preparation
You should have read chapter 11.1-11.4 in the course book, and have a good grasp of heuristic search.Modelling Language
The planners you will use all accept the same form of input, a planning domain description language called PDDL. PDDL provides a common syntax for planning formalisms with varying degrees of expressivity, such as STRIPS and ADL. This is discussed in section 11.1 of the book.Here is a short manual on How to write domain and problem definitions in PDDL.
Most planners do not support more features than STRIPS, so if you want to use any ADL features you have to convert the domain and problem to STRIPS first by using the adl2strips program, which can be found in the /planners directory.
Planners
There are many approaches to how to solve planning problems, and many implementations representing them.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.
- FF
- FF is a forward-chaining heuristic search planner (see section 11.2 in
the course book).
It produces sequential plans. Although it does not guarantee optimality,
it tends to find good solutions very quickly most of the time.
FF does a variation of hill-climbing search using a non-admissible heuristic,
which is also derived from plan graph (like that used by Graphplan, IPP and
others).
- Read the manual on How to run FF
- IPP
- IPP is a descendant of Graphplan (see chapter 11.4 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.
- Read the manual on How to run IPP
- VHPOP
- VHPOP is a partial-order planner (see chapter 11.3 in the course book).
It can work with either ground or partially instantiated actions, 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, solution may be optimal or not.
- Read the manual on How to run VHPOP
Here is a short manual on How to run the installed planning systems.
Part I: Task
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.
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 follwing 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).
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").
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 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 quite hard to do in PDDL (since there are no numbers), so you'll probably have to settle for classifying packages as "big" or "small" (or possibly "medium"). 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).
- Make it possible for trucks to drive between cities, but make it so that driving a truck between locations in different cities takes more than one "step" (i.e. more than one action). Note that it takes a minimum of nine steps (10 actions in a sequential plan) to transport a package from a location in one city to a location in another city (unless at least one of the locations is an airport), so unless you make "inter-city driving" take a longer time than that, the solution plans found will almost never use airplanes.
Puzzles and Games
Another AI favorite problem is puzzles and games. Among the examples in planning/strips you can find formalizations of the 8-puzzle (domain slidetile.pddl, example problems eight01.pddl and eight01x.pddl), the Towers-of-Hanoi problem (domain hanoi.pddl, example problem hanoi-3.pddl) and a chess problem (domain springer.pddl and example problem springer1.pddl). You can also find the different STRIPS Wumpus domains and problems (used in the lecture) (wumpus-a.pddl, wumpus-b.pddl, wumpus-c.pddl) together with the ADL version (domain wumpus-adl.pddl, example problem wumpus-adl-1.pddl).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.
The Dual-Traverse Blocksworld
The blocksworld is another standard AI planning benchmark. In this domain, there is a table on which a number of blocks are stacked. A block can be placed either on the table or on top of another block, but at most one block can be on top of any given block.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).
Part I: Examination
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.Part II: Task
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,
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.
Part II: Examination
You should hand in a written description of you experimental setup (the problem parameters you chose, how you varied themIf you're able, try to explain why changes in different problem parameters have (or don't have) different effects on different planners.
FAQ
Page responsible: Fredrik Heintz
Last updated: 2011-01-26
