Mau Archive Links Publications GitHub

01 September 2016
5 min read

PDDL

After years of planning research many planners were developed, each with a different input format, creating planners hard to compare. The planning community had no reason to use a common input format, there was no well defined formalism (only STRIPS-like). The planning community focus was on fast/correct planners, not compatible ones. ICAPS forced a standard description by setting a competition were researchers could publish their approaches. Such standard description was PDDL 1.2 from 98. This forced the planning community to share language, limitations and benchmarks. Planners that required more than what PDDL could express were forgotten or added new features to PDDL. PDDL is incremented from time to time to support such missing features, which may be modified or dropped as new use cases appear.

Planning elements

Domain

An implementation of the Tower of Hanoi is a good start, there is only one action and very clear initial and goal states. It starts with several disks in the leftmost of three pegs, each disk on top of a larger one. The goal is to move all disks to the rightmost peg, but there is a catch, only one disk can be moved at a time and never onto a smaller one. Three predicates are used to describe if the top of a disk is clear, which disk is on top of another and which disk is smaller than another. The move action has three parameters/free variables, prefixed by ?.

(define (domain hanoi) ; This is a comment, there are no multiline comments
  (:requirements :strips :negative-preconditions :equality)
  (:predicates (clear ?x) (on ?x ?y) (smaller ?x ?y) )
  (:action move
    :parameters (?disc ?from ?to)
    :precondition (and
       (smaller ?disc ?to) (smaller ?disc ?from)
       (on ?disc ?from)
       (clear ?disc) (clear ?to)
       (not (= ?from ?to))
    )
    :effect (and
      (clear ?from)
      (on ?disc ?to)
      (not (on ?disc ?from))
      (not (clear ?to))
    )
  )
)

Problem

For a problem with only three disks there are several smaller predicates in the initial state to describe which movements are possible. The disks are on top of each other on peg1 with the smaller disk1, peg2 and peg3 being clear. The goal only have the stack on peg3, but one could add (clear peg1) and (clear peg2). For more or less disks only a different problem description is needed, as they are new problem instances of the same domain.

(define (problem pb3) ; This is also a comment
  (:domain hanoi)
  (:objects peg1 peg2 peg3 d1 d2 d3)
  (:init
    (smaller d1 peg1) (smaller d1 peg2) (smaller d1 peg3)
    (smaller d2 peg1) (smaller d2 peg2) (smaller d2 peg3)
    (smaller d3 peg1) (smaller d3 peg2) (smaller d3 peg3)
    (smaller d1 d2) (smaller d1 d3)
    (smaller d2 d3)
    (clear d1) (clear peg2) (clear peg3)
    (on d1 d2) (on d2 d3) (on d3 peg1)
  )

  (:goal (and
    (on d1 d2) (on d2 d3) (on d3 peg3)
  ))
)

Requirements

Planners usually do not support every PDDL specification out there, as each version adds expressive power to support domains that otherwise would not be able to be described in PDDL. The expressive power is handled in layers of requirements in PDDL. Not to mention the many experimental requirements that are published without sufficient implementation details. A planner that support everything is too complex for developers that are interested in a subset of PDDL that solves their problem, they need to focus on something they can maintain and optimize for their use case. It is left to the user to select ideal/correct planner based on their requirements:

Common requirements:

Some planners may lack the desired requirements. instead of giving up and searching for a new planner, we can rewrite the PDDL description using simpler constructions. These are a few tricks to downgrade PDDL:

The following action shows how most common requirements take place:

(:action name
  :parameters (
    ?param1 ?param2 - type ; requires typing
    ?param3 ?param4 ; strips
  )
  :precondition (and
    (pred ?param1) ; strips
    (not (pred ?param2)) ; negative-preconditions
    (not (= ?param1 ?param2)) ; negative-preconditions and equality
    (or ; disjunctive-preconditions
      (pred ?param3)
      (pred ?param4)
    )
  )
  :effect (and
    (not (pred ?param1)) ; strips
    (pred ?param2) ; strips
    (when (pred2 ?param1) ; conditional-effects
      (not (pred2 ?param1))
    )
  )
)

Documentation

It is important to document the design decisions that were taken during domain and problem modeling, such as:

LaTeX listings

It is possible to add syntax highlighted PDDL to your papers/reports using LaTeX listings with a custom template. To simplify this process I created a repository with listings for planning descriptions.

References