Planning Problems in PDDL

The object of this class is to familiarize oneself with PDDL (Planning Domain Definition Language) — the standardized notation for representation of planning problems.

1 Preliminaries

Before starting this class it is recommended to do all the exercises from previous class (Automated Planning 101). This class further develops this subject and will refer to the solution of the blocks world problem using STRIPS planner.

2 Introduction

PDDL is designed to introduce uniform knowledge representation for the automated planning problems. The domain of a problem and its particular instances are separated from solvers, which are supposed to find a sequence of actions leading from given initial state to the goal state. Representation of a problem in PDDL consists of two files:

  1. file describing the domain
  2. file containing data for a given instance of the problem

2.1 Remarks on the Syntax

PDDL uses prefix notation, inspired by LISP (so-called S-expressions). In brief: every expression of the form (f a1 a2 a3) should be interpreted as f(a1, a2, a3), e.g. (= ?x (+ 3 2)) is equivalent to 5 = 3 + 2. Element of S-expression preceded by a question mark (e.g. ?x) represents a variable, whereas the brackets group a function name with its arguments. In particular, the whole LISP program constitutes a S-expression — which ensures easy parsing of a file and processing of code (useful for metaprogramming).

3 Domain Representation

The PDDL-file describing the domain of a problem consists of:

  1. section defining domain’s name: (define (domain <name>) …)
  2. section describing constructions used in the given model. This helps to establish if the given solver is able to process described domain: (:requirements <requirement1> <requirement2>). Some examples of such constructions are as follows:
    1. :typing enables grouping objects into categories
    2. :equality checks if two names refer to the same object
    3. :strips ensures support for describing problems according to STRIPS representation
    4. :adl means that given domain exceeds capabilities of the STRIPS representation and uses ADL features
  3. optional section defining types (requires typing)
  4. section defining predicates used to describe the state of the world (similar to Prolog): (:predicate (are_linked ?x ?y) < predicate2> …)
  5. section describing possible actions: (:action …). Every action is defined using:
    1. list of parameters used by the action: :parameters (?x ?y)
    2. list of requirements which must be satisfied if the action is to be executed: :preconditions (<condition>)
    3. list of effects of performing given action: :effects (?effect1, ?effect2)

Assignment

Please complete this model with three missing actions. You can refer to the definition of the blocks world problem, written using Prolog (see: preliminaries).

(define (domain blocksworld) 
  (:requirements :strips) 		; STRIPS required
  (:predicates (on ?x ?y) 		; block ?x is on block ?y
	       (ontable ?x)		; block ?x on the table
	       (clear ?x)		; no block is on block ?x
	       (handempty)		; robot’s arm is empty
	       (holding ?x)		; robot’s arm is holding ?x
	       )
  (:action pick-up			; action „pick up from the table”
	     :parameters (?block)
	     :precondition (and (clear ?block) (ontable ?block) (handempty))
	     :effect
	     (and (not (ontable ?block))
		  (not (clear ?block))
		  (not (handempty))
		  (holding ?block)))
  ; action „put on the table”
  ; action „put block A on block B” 
  ; action „take block A off block B” 
)

4 Representation of the problem's instance

The second PDDL file describes a specific problem instance and it consists of five sections:

  1. definition of the problem’s name: (define (problem <name>) … )
  2. information about the domain to which the given problem belongs: (:domain <domain>)
  3. available objects (possible arguments of predicates) of the given problem: (:objects a1 a2 a3 …)
  4. list of facts true in the initial state of the world: (:init (predicate argument) …)
  5. goal state of the world: (:goal (predicate argument))

4.1 Assignment

Please rewrite into PDDL two more difficult examples from the Prolog implementation of STRIPS (see: preliminaries), using the example given below:

(define (problem easy)
  (:domain blocksworld)
  (:objects a b c)
  (:init (ontable a) (ontable b) (ontable c) (clear a) (clear b) (clear c) (handempty))
  (:goal (and (on b c) (on a b)))
)

5 Automated Solving of Problems Written in PDDL

If you’re using a laptop in C2 316 classroom, Fast Forward solver should be already installed and added to PATH. It is then sufficient to run ff in the console.

  1. Please download the Fast Forward solver (you can find more information on the solver and its results on its home page). The FF.zip archive contains a catalog with source files and a binary file compiled for Ubuntu 64 bit (it should work on the university server). If needed, the compilation requires installing "flex" and "bison" tools and executing respectively:
    1. make veryclean
    2. make
  2. Please launch ff to solve problems defined in previous assignments. The solver is started by the command:
    • ./ff -o <path to file with domain> -f <path to file with problem instance>
  3. Please compare the efficiency of the solver with the Prolog solution from previous class (see: preliminaries)

If you use your own laptop, or just love web based technologies, you can use online IDE instead,

6 Typing

By adding :typing to the :requirements section you can expand PDDL capabilities to add types to existing objects, or parameters to actions. This way you can easily eliminate a large number of illegal actions.

Types are defined after :requirements section by adding: (:types name1 name2 …) for types named name1, name2, etc. Then, each predicate and action parameter must be given appropriate annotation specifying its type, for example: ?x – type means that the parameter ?x must be of type type in the given action or predicate

Similarly, in defining problem instance, each object must be given appropriate annotation (- typename) specifying its type.

6.1 Assignment

Please complete blocks world file with annotation and test if everything still works.

6.2 Hanoi Towers

As we have already tested the representation of blocks world problem, please generalise this problem by adding two additional elements:

  • the number of places on the table where you can put a block is limited
  • in order to put block A on block B, block B must be bigger than block A

Comments:

  • it is not required that there should be only one block of a given size
  • at the beginning we can assume that the number of the places on the table is constant (for example 3)
  • we can also assume that the number of blocks is specified
  • next, the model should be generalised so it could work on different numbers of free places and blocks, as defined in the problem instance

7 Action Description Language

The STRIPS representation is very limited and, in order to expand actions conditions with new constructions, one should add additional requirement :adl in :requirements section. ADL differs from STRIPS in, among others:

  1. it supports first order conditions (which means that quantifiers are added to the language): (forall (?x1 ?x1 …) <condition>), (exists (?x1 ?x2 …) <condition>)
  2. conditions may contain negative literals: (not <condition>)
  3. conditions may contain alternatives: (or <condition1> <condition2>)
  4. the world is open (in STRIPS, as in Prolog, the world is closed)

7.1 Assignment

Eliminate clear from the definition of blocks world domain using ADL.

en/dydaktyka/planning/pddl.txt · Last modified: 2017/07/17 08:08 (external edit)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0