Representation for Classical Planning

Need for Representation

• Explicit enumeration of states is not feasible
• Remember state-space search
• Need a representation for states
• Values corresponding to a set of variables
• Set of ground atoms in first-order language
• Model state transitions as operators
• Define implicit state-space
• Define the initial state
• Use operators to get to the other states

Types of Representation

• Classical Representation
• Set-theoretic Representation
• State-variable Representation
• Example with DWR and Blocks World
• Comparison between Representation Schemes

Classical Representation

• Function free First-Order Logic
• Finitely many predicate symbols and constant symbols but no function symbols
• Example: DWR Domain
• Locations: l1, l2, …
• Containers: c1, c2, …
• Piles: p1, p2, …
• Robot carts: r1, r2, …
• Cranes: k1, k2, …

​

Classical Representation

• Atom: predicate symbols with arguments
• To represent both rigid and dynamic relations

adjacent(l,l’) attached(p,l) belong(k,l)

occupied(l) at(r,l)

loaded(r,c) unloaded(r)

holding(k,c) empty(k)

in(c,p) on(c,c’)

top(c,p) top(pallet,p)

​

​

Classical Representation

Defining State

• State: a set of ground atoms
• The atoms represent the things that are true in one of Σ’s states
• Only finitely many ground atoms, so only finitely many possible states

​

s₁ = {attached(p1,loc1), in(c1,p1), in(c3,p1), top(c3,p1), on(c3,c1), on(c1,pallet), attached(p2,loc1), in(c2,p2), top(c2,p2), on(c2,palet), belong(crane1,loc1), empty(crane1), adjacent(loc1,loc2), adjacent(loc2,loc1), at(r1,loc2), occupied(loc2, unloaded(r1)}

Defining Operators

Operator: Example

Actions

• Action is a ground instance of an operator
• θ = {k ← crane1, l ← loc1, c ← c3, d ← c1, p ← p1}

​

Crane crane1 at location loc1 takes c3 off of c1 in pile p1

Notation

Notation: Example

Applicability of an Action

Executing an Applicable Action

Executing an Applicable Action

Executing an Applicable Action

Planning Domain

Planning Problem

Planning Problems

Plans and Solutions

Executing an Applicable Action

Example

〈move(r1,loc2,loc1), �take(crane1,loc1,c3,c1,p1), �move(r1,loc1,loc2), �move(r1,loc2,loc1), �load(crane1,loc1,c3,r1), �move(r1,loc1,loc2)〉

〈take(crane1,loc1,c3,c1,p1), �put(crane1,loc1,c3,c2,p2), �move(r1,loc2,loc1), �take(crane1,loc1,c3,c2,p2), �load(crane1,loc1,c3,r1), �move(r1,loc1,loc2)〉

Two redundant solutions

Irredundant and shortest solution

〈move(r1,loc2,loc1), take(crane1,loc1,c3,c1,p1), load(crane1,loc1,c3,r1), move(r1,loc1,loc2)〉

Set Theoretic Representation

• Similar to classical representation but restricted to propositional logic
• All atoms are treated to be ground
• States:
• Instead of ground atoms, use propositions (Boolean variables):

{on(c1,pallet), on(c1,r1), on(c1,c2), …, at(r1,l1), at(r1,l2), …}

​

{on-c1-pallet, on-c1-r1, on-c1-c2, …, at-r1-l1, at-r1-l2, …}

​

Set Theoretic Representation

No operators, just actions:

• Instead of ground atoms, use propositions
• Instead of negative effects, use a delete list
• If there are any negative preconditions, create new atoms to represent them
• E.g., instead of using ¬foo as a precondition, use not-foo
• Delete foo iff you add not-foo
• Delete not-foo iff you add foo

​

Exponential Blowup

State Variable Representation

• Use ground atoms for properties that do not change, e.g., adjacent(loc1,loc2)
• For properties that can change, assign values to state variables
• Classical and state-variable representations take similar amounts of space
• Each can be translated into the other in low-order polynomial time

​

​

State Variable Representation

s₁ = {top(p1)=c3,� cpos(c3)=c1,� cpos(c1)=pallet,� holding(crane1)=nil,� rloc(r1)=loc2,� loaded(r1)=nil, …}

Example: Blocks World

• Infinitely wide table, finite number of children’s blocks
• Ignore where a block is located on the table
• A block can sit on the table or on another block
• There’s a robot gripper that can hold at most one block
• Want to move blocks from one configuration to another

​

​

​

​

• Like a special case of DWR with one location, one crane, some containers, and many more piles than you need

​

c

a

b

c

a

b

e

d

Initial state

Goal state

Classical Representation: Symbols

• Constant symbols:
• The blocks: a, b, c, d, e
• Predicates:
• ontable(x) - block x is on the table
• on(x,y) - block x is on block y
• clear(x) - block x has nothing on it
• holding(x) - the robot hand is holding block x
• handempty - the robot hand isn’t holding anything

​

c

a

b

e

d

unstack(x,y)

Precond: on(x,y), clear(x), handempty

Effects: ¬on(x,y), ¬clear(x), ¬handempty,� holding(x), clear(y)

stack(x,y)

Precond: holding(x), clear(y)

Effects: ¬holding(x), ¬clear(y),� on(x,y), clear(x), handempty

pickup(x)

Precond: ontable(x), clear(x), handempty

Effects: ¬ontable(x), ¬clear(x),� ¬handempty, holding(x)

putdown(x)

Precond: holding(x)

Effects: ¬holding(x), ontable(x),� clear(x), handempty

c

a

b

c

a

b

c

a

b

c

a

b

Classical Operators

Set Theoretic Representation: Symbols

• For five blocks, there are 36 propositions
• Here are 5 of them:

ontable-a - block a is on the table

on-c-a - block c is on block a

clear-c - block c has nothing on it

holding-d - the robot hand is holding block d

handempty - the robot hand isn’t holding anything

​

c

a

b

d

e

unstack-c-a

Pre: on-c-a, clear-c, handempty

Del: on-c-a, clear-c, handempty

Add: holding-c, clear-a

stack-c-a

Pre: holding-c, clear-a

Del: holding-c, clear-a

Add: on-c-a, clear-c, handempty

pickup-b

Pre: ontable-b, clear-b, handempty

Del: ontable-b, clear-b, handempty

Add: holding-b

putdown-b

Pre: holding-b

Del: holding-b

Add: ontable-b, clear-b, handempty

60 actions, 50 if we exclude nonsensical ones, e.g., unstack-e-e

​

c

a

b

c

a

b

c

a

b

c

a

b

Set-Theoretic Actions

State Variable Representation: Symbols

• Constant symbols:

a, b, c, d, e of type block

0, 1, table, nil of type other

• State variables:

pos(x) = y if block x is on block y

pos(x) = table if block x is on the table

pos(x) = nil if block x is being held

clear(x) = 1 if block x has nothing on it

clear(x) = 0 if block x is being held or has another block on it

holding = x if the robot hand is holding block x

holding = nil if the robot hand is holding nothing

​

c

a

b

e

d

unstack(x : block, y : block)

Precond: pos(x)=y, clear(y)=0, clear(x)=1, holding=nil

Effects: pos(x)←nil, clear(x)←0, holding←x, clear(y)←1

stack(x : block, y : block)

Precond: holding=x, clear(x)=0, clear(y)=1

Effects: holding←nil, clear(y)←0, pos(x)←y, clear(x)←1

pickup(x : block)

Precond: pos(x)=table, clear(x)=1, holding=nil

Effects: pos(x)←nil, clear(x)←0, holding←x

putdown(x : block)

Precond: holding=x

Effects: holding←nil, pos(x)←table, clear(x)←1

c

a

b

c

a

b

c

a

b

c

a

b

State-Variable Operators

Expressive Power

• Any problem that can be represented in one representation can also be represented in the other two
• Can convert in linear time and space in all cases except one:
• Exponential blowup when converting to set-theoretic

​

Classical

representation

State-variable

representation

Set-theoretic

representation

Trivial:

Each proposition is a 0-ary predicate

P(x₁,…,x_n)

becomes

f_P(x₁,…,x_n)=1

Write all of

the ground�instances

f(x₁,…,x_n)=y

becomes

P_f(x₁,…,x_n,y)

Comparison

• Classical representation
• The most popular for classical planning, partly for historical reasons

​

• Set-theoretic representation
• Can take much more space than classical representation
• Useful in algorithms that manipulate ground atoms directly
• e.g., planning graphs, satisfiability
• Useful for certain kinds of theoretical studies

​

• State-variable representation
• Equivalent to classical representation in expressive power
• Less natural for logicians, more natural for engineers and most computer scientists
• Useful in non-classical planning problems as a way to handle numbers, functions, time

​