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


===== - Preliminaries =====

Before starting this class it is recommended to do all the exercises from [[en:dydaktyka:planning:intro|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.

<WRAP center round important 60%>
Due to the COVID-19 outbreak, all files related to this class are stored in the [[https://gitlab.com/agh-krr/2019-2020/labs-planning|Gitlab repository]]. This class uses files stored in the ''01_pddl'' folder. Please refer to the ''Readme.md'' on how to submit the solutions.
</WRAP>


===== - 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:

  - file describing the domain
  - file containing data for a given instance of the problem

==== - Remarks on the Syntax ====

PDDL uses prefix notation, inspired by [[https://en.wikipedia.org/wiki/Lisp_(programming_language)#Symbolic_expressions_.28S-expressions.29|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).


===== - Domain Representation =====

The PDDL-file describing the domain of a problem consists of:
  - section defining domain’s name: ''(define (domain <name>) ...)''
  - 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:
    - '':typing'' enables grouping objects into categories 
    - '':equality'' checks if two names refer to the same object
    - '':strips'' ensures support for describing problems according to STRIPS representation
    - '':adl'' means that given domain exceeds capabilities of the STRIPS representation and uses ADL features
  - optional section defining types (requires typing)
  - section defining predicates used to describe the state of the world (similar to Prolog): ('':predicate (are_linked ?x ?y)'' < predicate2> …)
  - section describing possible actions: ''(:action ...)''. Every action is defined using:
    - list of parameters used by the action: '':parameters (?x ?y)''
    - list of requirements which must be satisfied if the action is to be executed: '':preconditions (<condition>)''
    - 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).

<code lisp>
(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” 
)

</code>

===== - Representation of the problem's instance =====

The second PDDL file describes a specific problem instance and it consists of five sections:
  - definition of the problem’s name:  ''(define (problem <name>) … )''
  - information about the domain to which the given problem belongs: ''(:domain <domain>)''
  - available objects (possible arguments of predicates) of the given problem: ''(:objects a1 a2 a3 ...)''
  - list of facts true in the initial state of the world: ''(:init (predicate argument) ...)''
  - goal state of the world: ''(:goal (predicate argument))''

==== - Assignment ====

Please rewrite into PDDL two more difficult examples from the Prolog implementation of STRIPS (see: preliminaries), using the example given below:
<code lisp>
(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)))
)
</code>

===== - Automated Solving of Problems Written in PDDL =====

<WRAP center round tip 60%>
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.
</WRAP>

  - Please clone [[ https://gitlab.com/agh-krr/2019-2020/labs-planning |repository with the Fast Forward solver]] (you can find more information on the solver and its results on its [[https://fai.cs.uni-saarland.de/hoffmann/ff.html|home page]]). The repository contains precompiled binaries for several platforms. 
  - Please launch appropriate''ff'' (i.e. ''ff-win64.exe'' on Windows 64bit) to solve problems defined in previous assignments. Also the ''01_pddl'' folder contains files related to this class. The solver is started by the command:
    * ''./ff -s 0 -o <path to file with domain> -f <path to file with problem instance>''
  - Please compare the efficiency of the solver with the Prolog solution from previous class (see: preliminaries)

<WRAP center round tip 60%>
If you use your own laptop, or just love web based technologies, you can use [[http://editor.planning.domains/#| online IDE]] instead,
</WRAP>

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

==== - Assignment ====

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

==== - 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

===== - 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. [[http://en.wikipedia.org/wiki/Action_description_language|ADL]] differs from STRIPS in, among others:

  - it supports first order conditions (which means that quantifiers are added to the language): ''(forall (?x1 ?x1 ...) <condition>)'', ''(exists (?x1 ?x2 ...) <condition>)''
  - conditions may contain negative literals: ''(not <condition>)''
  - conditions may contain alternatives: ''(or <condition1> <condition2>)''
  - the world is [[https://en.wikipedia.org/wiki/Open-world_assumption|open]] (in STRIPS, as in Prolog, the world is [[http://en.wikipedia.org/wiki/Closed-world_assumption|closed]])

==== - Assignment ====

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