AI Labs - Planning using Strips

Lab 10/1/2007

The purpose of this lab session is to understand the STRIPS formalism for representing planning problems. You will be requested to write down STRIPS-style descriptions of a problem, as well as solve some problems by using a planning system.

The planning system we are going to use is BlackBox. It is already installed on the linux server russell.inf.unibz.it. A Windows version is available from the BlackBox website, but it requires Cygwin to work, so it is not installed on the Windows boot PCs in the laboratory (see details on Blackbox download page). You could reboot the PC into Linux and download the executable or log into the application server russel.inf.unibz.it, where Blackbox is available in the directory /home/AI/tools/BlackBox/. A version of Blackbox compiled for MacOS X on Intel is available here. A brief introduction to the use of the planner is available at the end of this document.

Exercise 1: Blocks World

The blocks world problem: this is adapted form Section 11.1 of the textbook (^ is used for conjunction)

Init: On(A,Table) ^ On(B,Table) ^ On(C,Table)

      ^ Block(A) ^ Block(B) ^ Block (C)

      ^ Clear(A) ^ Clear(B) ^ Clear(C)

    

Goal: On(A,B) ^ On(B,C)

    


Action(Move(b,x,y),

  PRECOND: On(b,x) ^ Clear(b) ^ Clear(y) ^ Block(b) ^ Block(y), 

  EFFECT: On(b,y) ^ Clear(x) ^

¬

On(b,x)
^

¬

Clear(y))

Action(MoveToTable(b,x),

  PRECOND: On(b,x) ^ Clear(b) ^ Block(b),

  EFFECT: On(b,Table) ^ Clear(x) ^

¬On(b,x))

1.1

To which blocks configuration corresponds the initial state? And the goal?

1.2

Encode the problem using PDDL and use the Blackbox planner to find a plan.

1.3

Use the same domain definition for the following initial state (same goal as before):

     C

  B  A

------------

Exercise 2: Monkey and Bananas

This exercise is adapted from Exercise 11.4 from the textbook.

The monkey-and-bananas problem is faced by a monkey in a laboratory with some bananas hanging out of reach from the ceiling. A box is available that will enable the monkey to reach the bananas if he climbs on it. There are few labelled positions at which monkey, bananas and box can be. Moreover each object can have an height (e.g. bananas on the ceiling are high and box is low).

Initially, the monkey is at A, the bananas at B, and the box at C. The monkey and box have height Low, but if the monkey climbs onto the box he will have height High, the same as the bananas.

The actions available to the monkey include Go from one place to another, Push an object from one place to another, ClimbUp onto or ClimbDown from an object, and Grasp or Ungrasp an object. Grasping results in holding the object if the monkey and object are in the same place at the same height.

2.1

Write down the PDDL domain definition file for the problem.

2.2

Assume that there are three locations: A, B and C. Initially, the monkey is at A, the bananas at B, and the box at C. The monkey and box have height Low (on the floor), while bananas are High, since they hangs from the ceiling. At the end, Monkey wants to stay on the floor with the bananas.

Write down the problem instance as PDDL problem description file.

2.3

Use the BlackBox planning system to solve the problem.

Using the BlackBox planner

To use BlackBox, you should log to the Linux server (using Putty, for example). The system runs from the command line, and it expects both the domain and problem definitions to be represented in the PDDL input language. We are going to use only the STRIPS sublanguage of PDDL.

You should write two different files, the first one with the description of the domain (predicates and actions) and the second with the problem instance (objects, initial state, and goal state). The syntax might seem intimidating, but it is rather simple once you get the main ideas.

As an example, below you can find the problem description for the Air cargo transport example shown during the lecture. You can use the two files as template for your own problem descriptions.

Domain definition file (cargo-dom.pddl):

;; STRIPS domain of the Air
cargo transport




(define (domain air-cargo)

  (:requirements :strips)

  (:predicates (In ?obj ?place)

           (At ?obj ?place)

           (Cargo ?obj)

           (Plane ?obj)


           (Airport ?obj))



  (:action LOAD

     :parameters (?c ?p ?a)

     :precondition (and (At ?c ?a) (At ?p ?a)

             (Cargo
?c) (Plane ?p) (Airport ?a))


     :effect (and (not (At ?c ?a)) (In ?c ?p)))

  

  (:action UNLOAD

     :parameters (?c ?p ?a)

     :precondition (and (In ?c ?p) (At ?p ?a)

             (Cargo
?c) (Plane ?p) (Airport ?a))


     :effect (and (not (In ?c ?p)) (At ?c ?a)))

  

  (:action FLY

     :parameters (?p ?from ?to)

     :precondition (and (At ?p ?from)

             (Plane
?p) (Airport ?from) (Airport ?to))


     :effect (and (not (At ?p ?from)) (At ?p ?to)))

  )

Problem instance definition file (cargo-pb1.pddl):

;; STRIPS Instance problem
for the Air cargo transport



(define (problem pb1)


  (:domain air-cargo)

  (:objects C1 C2

        P1 P2

        SFO JFK)

  (:init


   ;; types

   (Cargo C1) (Cargo C2)

   (Plane P1) (Plane P2)

   (Airport SFO) (Airport JFK)



   ;; locations

   (At C1 SFO) (At C2 JFK) (At P1 SFO) (At P2 JFK))




  (:goal

   (and (At C1 JFK) (At C2 SFO))))

Some points you should bear in mind while you read the PDDL files:

predicates and conditions are in prefix notation (lisp-like); that is a list whose first element is the predicate/function name and arguments between brackets (no commas, just space as separator).
variables start with a question mark
names are not case sensitive
conjunction of literals are represented by the operator (and ....)
note that :init feature of problem instance does not need the conjunction operator

The BlackBox executable on russel is /home/AI/tools/BlackBox/blackbox. Among others, it accepts the options '-o' to specify the domain definition file, and the option '-f' for the problem instance. An example of the interaction is the following:

$ /home/AI/tools/BlackBox/blackbox -o cargo-dom.pddl -f cargo-pb1.pddl blackbox version 42 command line: blackbox -o cargo-dom.pddl -f cargo-pb1.pddl Begin solver specification -maxint 0 -maxsec 10.000000 graphplan -maxint 0 -maxsec 0.000000 chaff End solver specification Loading domain file: cargo-dom.pddl Loading fact file: cargo-pb1.pddl Problem name: pb1 Facts loaded. time: 1, 14 facts and 6 exclusive pairs. time: 2, 16 facts and 12 exclusive pairs. time: 3, 18 facts and 16 exclusive pairs. Goals first reachable in 3 steps. 130 nodes created. #################################################### goals at time 4: at_c1_jfk at_c2_sfo ---------------------------------------------------- Invoking solver graphplan Result is Sat Iteration was 25 Performing plan justification: 0 actions were pruned in 0.00 seconds ---------------------------------------------------- Begin plan 1 (load c1 p1 sfo) 1 (load c2 p2 jfk) 2 (fly p1 sfo jfk) 2 (fly p2 jfk sfo) 3 (unload c2 p2 sfo) 3 (unload c1 p1 jfk) End plan ---------------------------------------------------- 6 total actions in plan 0 entries in hash table, 2 total set-creation steps (entries + hits + plan length - 1) 6 actions tried #################################################### Total elapsed time: 0.13 seconds Time in milliseconds: 132 ####################################################
The output is showing more information than you really need, just look at the plan
and the time spent to solve the problem. You can find more STRIPS examples in the directory /home/AI/tools/BlackBox/Examples/logistics-strips on russel or here.