Göm menyn

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:

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. To run the planners, execute the following commands to bind the paths to aliases:

~/Lab4$ alias IPP=/courses/729G78/Lab4/planners/IPP_400/plan-ipp
~/Lab4$ alias FF=/courses/729G78/Lab4/planners/FF/plan-ff

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

~/Lab4$ cp /courses/729G78/Lab4/strips/domain-delivery.pddl .
~/Lab4$ cp /courses/729G78/Lab4/strips/problem-delivery.pddl .

The file problem-delivery.pddl defines the problem that the planner is to solve. The domain file, domain-delivery.pddl, defines the actions, types and relations that exist in the domain. For instance, we can in this file say that there are objects called cars and that there is an action called drive. The problem file lists which specific things are where (i.e. the initial state) and what the goal the planner is to reach. Here we may, for example, say that a specific car named car1 exist at a location A and that the goal is for this car to be at location B.

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: 

    
       IPP domain-delivery.pddl problem-delivery.pddl
Go ahead and solve the delivery problem using the domain and problem file you downloaded earlier. You should see output looking like the lines below. This is the sequence of actions the planner has found that will achieve the goal state. 
    
	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: 

    
       FF domain-delivery.pddl problem-delivery.pddl
Running the example files you should see similar output as you did with IPP.
So far so good, now it is time to get our hands dirty.

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!

  • 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.


  • 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.


  • 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.


  • 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.


    Save this version of your modified domain and problem and make sure to comment your code where appropriate.


  • 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. Try adding additional packets and vehicles, more actions (possibly useless ones), or have some actions take in unnecessary parameters or preconditions.
    Complete Exercise 4.
PlanEx is now a delivery company success and training is thus completed, congratulations! If you are wearing a hat, now is the time to throw it up in the air.

VG only

(Create a copy of your files before solving the VG exercise. You should hand in the two solutions separately.)
  • 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.
  • Note: You may not be able to run the extended domain in IPP, but running FF is sufficient for this part.
  • 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ä