PDDL 2.2
PDDL 2.2 was the language of the classical part of IPC 2004, by Stefan Edelkamp and Jörg Hoffmann. It kept levels 1 to 3 of PDDL 2.1 and added two features: derived predicates and timed initial literals.
Derived predicates
A derived predicate is not set by any action. It is defined by a rule, and its value follows from the other facts in each state. This brings back, in a restricted form, the axioms of PDDL 1.2.
; PDDL 2.2 derived predicates: whether two places are linked follows from
; the open roads. No action sets it; it is worked out in every state.
(define (domain courier-derived)
(:requirements :typing :derived-predicates :negative-preconditions)
(:types parcel location)
(:predicates
(road ?from ?to - location)
(blocked ?from ?to - location)
(parcel-at ?p - parcel ?l - location)
(linked ?from ?to - location))
; A road that is not blocked links its ends...
(:derived (linked ?from ?to - location)
(and (road ?from ?to) (not (blocked ?from ?to))))
; ...and links chain: the rule is recursive.
(:derived (linked ?from ?to - location)
(exists (?via - location)
(and (road ?from ?via) (not (blocked ?from ?via)) (linked ?via ?to))))
(:action clear-road
:parameters (?from ?to - location)
:precondition (blocked ?from ?to)
:effect (not (blocked ?from ?to)))
(:action send
:parameters (?p - parcel ?from ?to - location)
:precondition (and (parcel-at ?p ?from) (linked ?from ?to))
:effect (and (not (parcel-at ?p ?from)) (parcel-at ?p ?to))))(define (problem one-road-blocked)
(:domain courier-derived)
(:objects
book - parcel
depot market bridge harbour - location)
(:init
(parcel-at book depot)
(road depot market) (road market bridge) (road bridge harbour)
(blocked market bridge))
(:goal (parcel-at book harbour)))Rules can be recursive, as here: whether two places are linked depends on the roads, however long the route. Without derived predicates, every action that changes a road would have to update every pair of places. Autoplan's plan clears the blocked road and then sends the parcel:
(clear-road market bridge)
(send book depot market)
(send book market harbour)The paper sets three restrictions:
- A derived predicate may not appear in the effects of any action.
- The variables in a rule's head are pairwise different, and are exactly the free variables of its body.
- In negation normal form, the body may not use derived predicates in negated form.
The last rule rules out definitions that depend on their own negation, and the meaning of a set of rules is their least fixed point.
Timed initial literals
A timed initial literal, in the paper's words, is "a syntactically very simple way of expressing a certain restricted form of exogenous events": a fact that becomes true or false at a known time, whatever the plan does. They are written in :init, with a time greater than 0, and they need durative actions. Opening hours and delivery windows are the classic use.
; PDDL 2.2 timed initial literals: the market opens and closes at known
; times, so unloading there has to fit inside its opening hours.
(define (domain courier-deadline)
(:requirements :typing :fluents :durative-actions :timed-initial-literals)
(:types van parcel location)
(:predicates
(road ?from ?to - location)
(van-at ?v - van ?l - location)
(parcel-at ?p - parcel ?l - location)
(in ?p - parcel ?v - van)
(open ?l - location))
(:functions (distance ?from ?to - location))
(:durative-action drive
:parameters (?v - van ?from ?to - location)
:duration (= ?duration (distance ?from ?to))
:condition (and (at start (van-at ?v ?from)) (over all (road ?from ?to)))
:effect (and (at start (not (van-at ?v ?from)))
(at end (van-at ?v ?to))))
(:durative-action load
:parameters (?p - parcel ?v - van ?l - location)
:duration (= ?duration 1)
:condition (and (at start (parcel-at ?p ?l)) (over all (van-at ?v ?l)))
:effect (and (at start (not (parcel-at ?p ?l)))
(at end (in ?p ?v))))
(:durative-action unload
:parameters (?p - parcel ?v - van ?l - location)
:duration (= ?duration 1)
:condition (and (at start (in ?p ?v))
(over all (van-at ?v ?l))
(over all (open ?l)))
:effect (and (at start (not (in ?p ?v)))
(at end (parcel-at ?p ?l)))))(define (problem before-closing)
(:domain courier-deadline)
(:objects
van1 - van
book lamp - parcel
depot market harbour - location)
(:init
(van-at van1 depot)
(parcel-at book depot) (parcel-at lamp depot)
(road depot market) (road market depot)
(road depot harbour) (road harbour depot)
(= (distance depot market) 5) (= (distance market depot) 5)
(= (distance depot harbour) 8) (= (distance harbour depot) 8)
(open harbour)
; Timed initial literals: facts that change at known times.
(at 4 (open market))
(at 9 (not (open market))))
(:goal (and (parcel-at book market) (parcel-at lamp harbour))))The market is open from 4 to 9. The van cannot go to the harbour first, or it would miss the market, so the plan goes to the market first and has the unloading inside its hours:
0: (load book van1 depot) [1]
0: (load lamp van1 depot) [1]
1.001: (drive van1 depot market) [5]
6.002: (unload book van1 market) [1]
7.003: (drive van1 market depot) [5]
12.004: (drive van1 depot harbour) [8]
20.005: (unload lamp van1 harbour) [1]Requirement flags
:derived-predicates: predicates whose truth value is defined by a formula.:timed-initial-literals: literals in the initial state that take effect at a specified time. It implies durative actions.
Sources
- Stefan Edelkamp, Jörg Hoffmann. PDDL2.2: The Language for the Classical Part of the 4th International Planning Competition. Technical Report 195, University of Freiburg, 2004.
- Stefan Edelkamp, Jörg Hoffmann. PDDL2.2: The Language for the Classical Part of IPC-4. Extended abstract, IPC-4 booklet, 2-6, 2004.
- Jörg Hoffmann, Stefan Edelkamp. The Deterministic Part of IPC-4: An Overview. Journal of Artificial Intelligence Research 24, 519-579, 2005.