PDDL is the standard Planning Domain Definition Language.

The STRIPS representation uses a logical language to represent properties of states; actions are represented by their preconditions and add/delete effects; enables algorithms to exploit the structure of the problem.

The structure of strips representation

– logical language (predicates, connectives, variables, quantifiers, finite object set, no function)
– a property of states (a set S′ ⊆ S) is represented by a formula ∀x(block(x) → ontable(x) ∨ ∃r robot(r) ∧ holding(r, x)) all blocks are on the table or held by some robot
– the goal is often represented by a set of ground atoms for simplicity {on(C, B), handempty(R1)}
– a state s ∈ S is represented by a set of ground atoms under the closed world assumption
{on(A, B), clear(A), ontable(B), holding(R1, C)}

1.Use operators with logical pre-post conditions to represent actions:

– operator o has a name and parameters: pickup(r, x)

– precondition pre(o) is a set of positive literals that must be true for the action to be applicable: {ontable(x), clear(x), handempty(r)}

– effect (postcondition) eff(o) is a set of literals that are true in the re- sulting state: {holding(r, x), ¬ontable(x), ¬clear(x), ¬handempty(r)}

– the effect is often split into two sets of positive literals:
add list eff+(o) = {holding(r, x)}.
delete list eff−(o) = {ontable(x), clear(x), handempty(r)}

– an action a ∈ A is represented by an instance of an operator
e.g. pickup(R1,C).

2.Use the STRIPS rule to represent the transition function γ:

γ(s, a) =   
(s \ eff−(a)) ∪ eff+(a)   if pre(a) ⊆ s,
undefined                 otherwise (action not executable)

3.Example:
– s = {on(A, B), clear(A), ontable(B), holding(R1, C)}
– a = putdown(R1, C)
operator: putdown(r, x)
precondition: {holding(R1,C)}
effect: {ontable(C), clear(C), handempty(R1), ¬holding(R1, C)}
– γ(s, a) = {on(A, B), clear(A), ontable(B), ontable(C), clear(C), handempty(R1)}

4.Feature of STRIPS
A. Only positive literals in states closed world assumption unmentioned literals are false {Poor, Unknown}.
B. Effect {P, ¬Q} means add P delete Q.
C. No support for equality and types.
D. Only positive literals in prec. & goals {Rich,Famous}
E. Effects are sets (conjunctions)

5.Complexity of propositional STRIPS planning(all predicates and operators have been instanciated (grounded). Recall that for STRIPS, preconditions are positive.)

• n propositions can result in 2^n states; in the worst case, the shortest plan will visit them all and is exponentially long (2^n − 1 actions)
• PLANSAT: Does there exist a plan that solves the problem? PSPACE complete. Polynomial if all effects are positive
• PLANMIN: Does there exist a plan of length k or less?
Also PSPACE complete. NP-complete if all effects are positive
• both are NP-complete if the plan length is polynomially bounded

Propositional STRIPS planning is PSPACE-complete.

6.Complexity of STRIPS planning
We consider STRIPS in its first-order (a.k.a. lifted) form:
• n predicates with k arguments and m objects can give up to nm^k atomic propositions
• these can give 2^(nmk) states
• in the worst case, the shortest plan will visit all of them in 2^(nmk) −1 actions