729G78 Artificiell intelligens

Laboration 4: Planering

Aim

The aim of this lab is to give a feel for the capabilities and limitations of domain-independent planning technology, and to practice modelling a problem using a formal language that can be understood by an automatic problem solver - a planner.

You will do this by writing and extending planning problems and experimenting with two classical planners that will try to solve your problems. In other words, you are not going write your own planning algorithms - you are going to write problems that existing planners are to solve. The planners used in this lab are research prototypes developed by various university research groups.

Preparation

In preparation for this lab you should:

• Read chapter 11 in the course book.
• Download, open and rename the exercises document Lab4Exercises_LiU-ID-1_LiU-ID-2.odt to match your group's LiU-IDs.

Introducing the Planners

The planners you will use reads a planning domain description language called PDDL. Here is a short manual on How to write domain and problem definitions in PDDL. In the lab we will use the STRIPS subset of PDDL and we will use these two planners: IPP and FF. They are both good and popular representatives of planners, and they perform reasonably well.

Execute the following commands to bind the paths to aliases:

Next, download the two PDDL files you will be modifying from the course directory:

Based on what things you include in the domain and problem file, the planner will try to find a plan (i.e. a solution) that lists which actions are required to reach the goal state from the initial state. In the labe files, the predefined problem files the goal is to transport a package from one office building to another using a truck.

IPP

IPP is an optimal parallel planner based on Graphplan. It performs iterative deepening A^* search using an admissible heuristic (remember your search lingo from lab 2 and the lectures), and uses a graph structure to compute the heuristic and store updates during search. More information about IPP can be found here.

Make sure to bind the IPP alias as instructed above. Then, from the terminal you run IPP like this:

  time step    0: DRIVE TRUCK1 OFFICE2 OFFICE1 CITY1
  time step    1: LOAD PACKET1 TRUCK1 OFFICE1
  time step    2: DRIVE TRUCK1 OFFICE1 OFFICE2 CITY1
  time step    3: UNLOAD PACKET1 TRUCK1 OFFICE2

FF

FF on the other hand is a non-optimal sequential planner. In practice, it tends to find good solutions very quickly most of the time. FF does a hill-climbing search using a non-admissible heuristic, which is also derived from a graph (similar to that of IPP). More information about FF can be found here.

Using the alias, you run FF like this:

Tasks

As you have seen in the output from the planners, the example domain is about logistics: delivering packages between office buildings using delivery vehicles. This a standard benchmark often used in AI planning. In this domain, there are two cities and in each city there are office buildings, which are considered locations. The goal is to move packages from their initial places to their respective destinations. There are three actions available in the domain: 1) load a package into a vehicle, 2) unload a package from a vehicle, and 3) driving vehicles between locations.

The scenario is that the PlanEx delivery company uses this model of the world to plan their deliveries, but they think the model is, in its current state, rather small and useless. And as their newest employee it is your task to expand it!

1. The company needs more deliveries! In the problem file, add a second package and place it at office2. Change the goal-state to have packet1 delivered to office2 and packet2 to office1. To list multiple goals you can use the operator AND, like so: (AND (objective 1) (objective 2) ... ). Solve with both planners.
   Complete Exercise 1.
2. Let's include the PlanEx building in the model as a new location located in city1. The brand new delivery moped (model Scooty-Puff, jr) is parked at this location. In the domain file, create the new vehicle type moped and place it at the new PlanEx building in the problem file. Solve the problem again using both planners.
   Complete Exercise 2.
3. Countless accidents have occurred with the moped, possibly due to overloading in combination with delivery boy incompetence. To avoid this, you must somehow introduce a distinction between small and large packages. New safety regulations say that the mopeds are only allowed to deliver small packages, and (strangely) trucks are NOT allowed to deliver small packages. Make packet2 small by introducing one (or more) static predicate(s) in the domain and change how packages are allowed to be loaded into vehicles (unload should remain unchanged).
   Complete Exercise 3.
4. Good news everyone! We have received a delivery to office3. Both packet1 and packet2 are to be delivered to office3. As of now, the problem can be reduced to False. This is because no available vehicle can move between cities, and office3 is in city2. To transport small packages in city2, add a new moped at office3. Then, add a new vehicle type in the domain (e.g. airplanes or a space-ship with flames) and enable it to travel between dedicated locations in each city. To do this, you need to include at least:
   • A new vehicle type
   • A new location type
   • A new action to travel between locations in different cities
   Note: The new vehicle is only allowed to travel between locations of the new type.
   Implement and test one aspect at a time! This makes development and debugging much easier. As part of this, change the goal to test specific part of your problem (e.g., try moving an airplane from one airport to another). Make sure to verify that the planners solve the problem in a correct manner.
   Note: Make sure to save this version of your modified domain and problem before proceeding with the next task. Also, make sure to add comment to your code where appropriate.
5. After saving a copy of you files, play around with the problem and domain files and try to figure out what makes a problem difficult for a specific planner. For example, try adding additional:
   1. packets
   2. vechicles
   3. (useless) actions
   4. unnecessary preconditions to existing actions
   5. unnecessary parameters to existing actions
   Complete Exercise 5.
   Note: The planners are pretty good at excluding actions that are functionally equivalent to other actions (i.e., copying an action and just changing the name may have no effect at all).

VG only

• All vehicles must be loaded by a person standing at the location of the vehicle.
• No vehicle is allowed to go anywhere without a driver.
• A person should be able to enter and exit a vehicle.
• There should be at least one person at the same location as a vehicle in each city.
• Complete Exercise 5.

Hand-in

• Your modified domain and problem files. Make sure to provide comments for your actions and predicates!
• The exercises document as PDF.
• Upload your files to Lisam.

Sidansvarig: Robin Keskisärkkä