planning languages

STRIPS
SAS+
PDDL

These languages are from the simpler to the more complex. The language using in practice is PDDL, but many planners only implement a STRIPS-like subset of it.

what is in a planning problem

variables
actions
initial state
goal

STRIPS

⟨P,O,I,G⟩

P

fluents: set of propositional variables

O

operators (actions)
each is ⟨pre,add,del⟩

pre,add,del = sets of variables

if the current state has pre, then a can be executed
resulting in the addition of add and removal of del

I

initial state

G

goal: set of variables

STRIPS: details

⟨P,O,I,G⟩

⟨P,O⟩ represents the environment
variables and actions
⟨I,G⟩ is the specific problem to solve
initial state and goal

not in this formalization:
negative preconditions and goal
domain can be changed to avoid them
note: examples include negative preconditions

STRIPS: plans

⟨P,O,I,G⟩ plan = sequence of actions
applied on the initial state:
lead to the goal

satisficing planning = find a plan
optimal planning = find a plan of minimal length

cost of actions; where omitted, all have cost 1
optimality = plan of minimal cost

STRIPS: example

P = {loaded_gun, broken_vase} O = {<∅,{broken_vase},∅>, <∅,{loaded_gun},∅>, <{loaded_gun},{broken_vase},{loaded_gun}>} I = ∅ G = {broken_vase} mathematically simple
difficult to understand

next: explanation

STRIPS: explanation of `P`

P = {loaded_gun, broken_vase}

there are only two variables in this domain
the gun can be loaded or not
the vase can be broken or not

four possible states

STRIPS: explanation of `O`

O = {<∅,{broken_vase},∅>, <∅,{loaded_gun},∅>, <{loaded_gun},{broken_vase},{loaded_gun}>}

first action <∅,{broken_vase},∅>
throw the vase on the floor
no precondition; effect: broke it

second action <∅,{loaded_gun},∅>
load the gun

third action <{loaded_gun},{broken_vase},{loaded_gun}>
shot at the vase

STRIPS: actions

actions have no names in the representation
denoted by their preconditions and effects

mathematically simple
not a user-friendly language

modern planners invlude the STRIPS fragment of PDDL (below)
same expressivity, clearer language

STRIPS: initial state, goal and plans

initial state I=∅
variables both false initially

goal G={broken_vase}
make this variable true

plan: sequence [o₀, o₁, o₂, … o_n]
each o_i ∈ O
performing from the initial state leads to the goal

performing = ?

STRIPS: performing an action

performing action o={p,a,d} in state s

can only be done if all variables in p are true in s
effect is that variables in a are made true in s
and variables in d are made false

formally:

action o={p,a,d} executable in state s: p ⊆ s
the state that results from executing o={p,a,d} in s: s ∪ a \ d

The STRIPS planning language is very terse. The description of a domain is difficult to write and understand in STRIPS. On the other hand, it allows for a simple mathematical definition of a domain and a plan. This is useful for formal proofs, etc.

executing a plan

plan [o₀, o₁, o₂, … o_n] from state s

executable if o₀ is executable in s and
[o₁, o₂, … o_n] executable in s ∪ a \ d
result is the same as executing [o₁, o₂, … o_n] in s ∪ a \ d

recursive definition of plan executability and effect
mathematical formulation, can be used in formal proofs

SAS+

like STRIPS, but variables are not binary

each variable x has a set of possible values dom(x)

preconditions and effects: partial evaluations;
also the goal

PDDL

standard language for planning
many solvers

domain and problem

two files:

domain: states and actions
problem: initial state and goal

example domain

file domain.pddl:

(define
	(domain switch)

	(:predicates (light))

	(:action turnon
		:precondition (not (light))
		:effect (light)
	)
)

light can be true or false

action: turn it on if not already

In this example, there is a light that can be turned on.

The domain description comprises two parts: the conditions that describe the state of the domain and the actions that can chane it. In this case, the state is that the light can be on or off; such conditions can be represented by a single propositional variable light. The only considered action is that of turning the light on.

example problem

file problem-1.pddl:

(define
	(problem first)

	(:domain switch)

	(:init (not (light)))

	(:goal (light))
)

light initially off
goal: turn it on

another example problem

file problem-2.pddl:

(define
	(problem first)

	(:domain switch)

	(:init (light))

	(:goal (light))
)

same domain, different problem

nothing to do in this case
goal already achieved in the initial state

yet another example problem

file problem-3.pddl:

(define
	(problem first)

	(:domain switch)

	(:init (light))

	(:goal (not (light)))
)

light on, turn it off

no plan in this domain!

action turnoff missing

In this case the description of the domain was incorrect since it did not include the action turnoff. In other cases, the domain is correct but there are no solution because there is no way to reach the goal from the initial state.

fast-downward

get the gzipped file from http://hg.fast-downward.org/

./build.py release64
or
./build.py

./fast-downward.py --build release64 domain.pddl problem-1.pddl --search "astar(add())"
or
./fast-downward.py domain.pddl problem-1.pddl --search "astar(add())"
run A* with the h^add heuristics (to be seen)

note: --search is after domain and problem

planner output

on domain.pddl and problem-1.pddl:

…
Solution found!
Actual search time: 0.00212685s [t=0.00486016s]
turnon  (1)
Plan length: 1 step(s).
…

plan found: action turnon only

no plan

on domain.pddl and problem-3.pddl:

…
Initial state is a dead end.
…
Completely explored state space -- no solution!
…

no plan exists

other examples

envelope: domain, problem-1, problem-2, problem-3: two variables
variables not in the initial state are false
wash: domain, problem-1, problem-2, problem-3: delete effects: washing the car makes the bucket empty
over: domain, problem-1, problem-2, problem-3: a conditional effects:
putting the gift over the box leaves it in or over,
depending on the whether the box is open or closed
not all heuristics support this
break: domain, problem-1, problem-2, problem-3: predicates with variables
various objects that can be broken
move: domain, problem-1, problem-2, problem-3: types: objects can be moved from positions to positions
of course, positions cannot be moved over objects or over other positions
hospital: domain, problem-1, problem-2, problem-3: hierarchy of types
all doctors can perform CPR
only surgeons can do surgery
cake: domain, problem; domain, problem: minimize the cost of actions
same scenario, two problems
minimize money spent, minimize time

from PDDL to the search space

example domain + example problem ⇒ search space

search space:

possible states
transitions between them

example domain

(define
	(domain simple)

	(:requirements :strips)

	; boolean variables x and y
	(:predicates
		(x)
		(y)
	)

	; if x is true, this action makes both x and y false
	(:action a
		:precondition (x)
		:effect (and (not (x)) (not (y)))
	)
	
	; if x is false, this action makes y true
	(:action b
		:precondition (not (x))
		:effect (y)
	)
)

example problem

(define
	(problem simple1)

	(:domain simple)

	; initial state
	(:init
		(x)
	)

	; goal
	(:goal
		(y)
	)
)

plan: a,b

the search space

expressed by the domain in PDDL

(:predicates (x) (y)): variables are x and y
(:action a :precondition (x) :effect (and (not (x)) (not (y)))): if x is true then action a can be executed
makes both x and y false
(:action b :precondition (not (x)) :effect (y)): if x is false then action b can be executed
makes y true

search space

a state for each assigment to the variables

a transition if there is an action that is executable in one state and results in the other

states

two binary variables
four states

action `a`

if x is true,
both x and y become false

two states where a is executable

action `b`

if x is false,
then y becomes true

both actions

search space with all arrows
for both action a and action b

initial state and goal

depend on the particular problem

problem 1: initial state x¬y, goal y
problem 2: initial state ¬xy, goal x

problem 1

(:init (x))
(:goal (y))

initial state x¬y, goal y

Every variable not mentioned in the initial state is false. On the contrary, the variables not in the goal can take arbitrary values. This is why this problem has one initial state and two goal states.

The goal is reached from the initial state by following the a arrow and then the b arrow.

problem 2

(:init (y))
(:goal (x))

initial state ¬xy, goal x

The goal cannot be reached from the initial state. The only arrow from it leads to the same state.

planning languages

what is in a planning problem

STRIPS

STRIPS: details

STRIPS: plans

STRIPS: example

STRIPS: explanation of P

STRIPS: explanation of O

STRIPS: actions

STRIPS: initial state, goal and plans

STRIPS: performing an action

executing a plan

SAS+

PDDL

domain and problem

example domain

example problem

another example problem

yet another example problem

fast-downward

planner output

no plan

other examples

from PDDL to the search space

example domain

example problem

the search space

search space

states

action a

action b

both actions

initial state and goal

problem 1

problem 2

STRIPS: explanation of `P`

STRIPS: explanation of `O`

action `a`

action `b`