TDDC17 Artificial Intelligence

TDDC17-Lab4

Aim

The aim of this lab is to help you understand:

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

In Part 1 of the lab, you will write your own model of a planning problem and experiment with different planners trying to solve the problem.

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 as in the book as well as in the lectures.

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.

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

The planners that we provide in this lab are research prototypes developed by various university research groups. For Part 1, 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 a mature implementation and gives rather legible error messages.

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:

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:

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:

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

After you finish the entire lab including Task 2, 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 a small empirical investigation of how different general planning heuristics affect a planner based on forward search in the state space.

As a basis for this lab, we will use Fast Downward – a planner that LAMA originated from, and has now been merged back into. The planner is extremely configurable. For example, it can use different state space search methods, heuristics, preferred queues and a lot more. Therefore, this is a planner that can effectively be used to compare different heuristics.

To be able to actually see what the planner does, we have developed our own extension that adds invasive logging. This means that the planner is considerably slower than the original, as every step must be logged into a log file. However, it also means that the planner logs more or less the whole search process, providing the input to our next piece of software, a search space visualizer.

In summary, you will run the planner with different configurations on a given domain and two problems. To measure the performance of the different problems you have to use the visualizer's statistics for heuristic calculations done, states expanded and states visited. (Measuring the search time isn't reliable since the logging increases the time considerably and not by the same amount for every search!) Finally, you will analyse the search procedure for some of them by viewing them in the search space visualizer.

Domain nomystery

The domain that you will use for this task is the nomystery domain. This is a domain from IPC-2011 (international planning competition 2011) that proved hard for many planners in the competition. The domain is essentially a delivery domain where a truck moves between different locations and delivers packages. Moving the truck between two locations consumes fuel which means that the truck can run out of fuel. Make sure that you download the domain and the two problems that you should use.

Experimental Setup and Log Generation

The first step of the experiment is to run Fast Downward on the three given problem instances and generate a set of logs. If you want to experiment on your own, you can read the general user manual. However, we will provide you with most of the pointers you need here in the lab description.

You run the modified version of Fast Downward as follows, on the IDA lab computers (can also be reached through Thinlinc, but be aware that many others may be using the same terminal servers to run their programs):

    $ /home/TDDC17/sw/fdlog/fast-downward.py DOMAIN PROBLEM CONFIGURATION [FLAGS]
  

The parameters are as follows:

If the flag --log-file FILE_NAME is specified, the log file will be saved under the given (meaningful) name. Otherwise it will simply be named stats.txt. For example, you can run astar search using the goal count heuristic and log the search to the file exp1.txt:

    $ /home/TDDC17/sw/fdlog/fast-downward.py DOMAIN PROBLEM --search "astar(goalcount())" --log-file exp1
  

For the experiment you should solve each of the two problems (p02 and p03) using each of the following three configurations (running Fast Downward six times). Note that the configurations are all using a simple greedy search strategy which means that we use satisficing, not optimal, planning.

We can get some insights into what the planner is doing from looking at the statistics that are generated for each search. These statistics include the following interesting numbers (which has a slightly different terminology than what you are most likely used to):

However, we can see far more if we use the graph visualizer.

The Graph VIsualizer

The Graph Visualiser is a tool that is written at IDA that is used to debug planners and other graph based algorithms. It can display graphs and more importantly go through a search log file step by step.

The Graph Visualiser requires that you run java version 1.8. This isn't the default java version on the linux machines. Therefore, you have to run it using the following:

/sw/jdk8/bin/java -jar /home/TDDC17/sw/fdvis/fdvis.jar path/to/log-file

Where path/to/log-file is the path to the log file that Fast Downward produced. For example

/sw/jdk8/bin/java -jar /home/TDDC17/sw/fdvis/fdvis.jar exp1.txt

if you named your log file as stated above and execute all commands from the same working directory.

Note that /sw/jdk8 might not show up on the lab computers and remote.ida.liu.se due to dynamic loading of the /sw folder. However, the folder is there so you can always type the path manually without auto-completion.

Learning the Graph Visualizer

First, make sure you play around with the visualizer.

Choose an arbitrary log file among those that you generated, start the visualizer, step forward and back, and test the different options for Node coloring in the View pane. For example, "Colour Map[g]" lets you color nodes by their g value (the cost of reaching a node), while "Colour Map[h_goal_count]" refers to the goal count heuristic (red = high, green = low).

Use the mouse wheel to zoom in/out. Mark nodes using the left button and drag them with the middle button (or alt+left button). Drag the entire graph in the same way, if no nodes are selected and "auto fit graph" is disabled.

Step to the end of the search process and see how a path is highlighted in the graph. This path corresponds to the plan that the planner found.

More information (such as interaction with the graph, setting what to show in the graph, the terminology used in the visualiser, etc.) is shown in the manual!

Empirical Investigation

You should now investigate what the planner actually did for some of the configurations you tested! Answer the following questions based on running the visualizer on the specified problems (don't forget screenshots).

Note that we are not only interested in the final answers – we are even more interested in the process you go through in order to find the answers. This process is intended to give you a more concrete feeling for the general structure of a search space and the type of search performed by a forward state space planner, even outside the scope of the questions themselves. This is also a very good reason for playing around with the visualizer on your own and using it as an interactive learning tool.

  1. Comparing heuristics, problem 03:
    1. Start the Fast Downward visualizer twice, using the log files generated when solving problem 03 with the configuration that uses (a) FF-heuristic and (b) goal count heuristics, respectively.

    2. Step both visualisations to time step 40 manually or through auto-stepping. Don't use the "go to" functionality (entering a step number) because you will need to see nodes as they appear!

      How do the graphs differ, given the same problem and search method but different heuristics? Include screenshots in your report and discuss what you see!

    3. Do the different configurations use different actions? Zoom in on the edges to see which actions are used and discuss the differences.

    4. Step the FF visualisation to the end through auto-stepping (hint: set the Auto-steps per second to a value greater than 1 but small enough so that you can follow the search process). Don't use the go to functionality.

      At the beginning, the FF visualisation expanded nodes along a long path before it started expanding at other places. Are the nodes in this path used in the final plan? Hint: the nodes are numbered incrementally as they are expanded so this can be used to find the answer.

      Updates (11/10-2017): An hint was provided to how the original path can be identified.

  2. Comparing heuristics, problem 02:
    1. Start two instances of the Fast Downward visualization, using the log files generated when solving problem 02 with (a) the configuration that uses FF-heuristic and (b) the configuration using GC heuristics with preferred operators from FF.

    2. When the planner adds a new action to a branch in the search tree, this doesn't necessarily cause the heuristic function to decrease. In which time step does the planner first find a new lower value for the main heuristic function in each example (FF and GC, respectively)?

    3. Step both visualisation to time step 27 (the last time step with the configuration using FF as heuristic).

      How many goal predicates are left to solve according to the goal count heuristic (see the description of Eager greedy search, Goal count heuristic) in the state that has progressed the longest?

      Updates (11/10-2017): Corrected grammatical error and added reference.

    4. Auto-step the visualisation for the goal count heuristic to the end.

      Follow the marked path from the start node (the initial state) to the last node (the first found goal state) in the highlighted path in the graph (the plan). Does the solution ever increase the value of the goal count heuristic between one state and the next?

      Updates (11/10-2017): Terminology in the question is now explained.

  3. Run one of the configurations on your own domain and problem. Is the graph similar to any of those that you have examined above? Can you explain why or why not?

  4. Feel free to explore further, with different search methods and/or heuristics and/or problems! Everything you learn might help you on the exam..

Examination, Task 2

You should hand in a report describing you findings in this experiment. This should include (but don't hesitate to add more if you had findings outside the questions here):


FAQ

Questions/answers may be added during the course.