CM3112 Artificial Intelligence
Planning Language
Steven Schockaert
SchockaertS1@cardiff.ac.uk
School of Computer Science & Informatics Cardiff University
Example: Blocks world
A CB BAC
Initial state Goal state
Example: Blocks world
C BA
Example: Blocks world
C
BA
Action: pick up block C from A
Preconditions:
The robot is not holding anything
There are no blocks on C C is on block A
Effects:
The robot holds C
There are no blocks on A
C is not on A anymore
Example: Blocks world
Action: put down C on table Preconditions:
The robot is holding C
Effects:
The robot is not holding anything
BA
C
Block C is on the table There are no blocks on C
Example: Blocks world
BC
Action: pick up B from table
Preconditions:
The robot is not holding anything
There are no blocks on B B is on the table
A
C
Effects:
The robot is holding B
Example: Blocks world
A
BC C
Action: put down B on C
Preconditions:
The robot is holding B
There are no blocks on C
Effects:
The robot is no longer holding B
B is on block C
STRIPS
To formalise a planning problem, we need
‣ a way to encode states, including an initial state and goal states ‣ a way to encode actions
One of the most common languages for encoding planning problems is STRIPS (“Stanford Research Institute Problem Solver”)
‣ Uses logic to encode states, and the preconditions and effects of actions
States in STRIPS are represented as conjunctions of atoms Closed-world assumption: every atom which is not asserted as
true, is assumed to be false
‣ No need to consider negation to represent states
STRIPS
Atoms are usually encoded using a predicate-argument structure
The atom says something about the objects block1 and block2
On(block1, block2)
The predicate on is used to denote a particular type of relationship
STRIPS
Atoms are usually encoded using a predicate-argument structure
On(block1, block2) Clear(block1)
The predicate clear is used to denote a particular type of property a block can have
STRIPS: states
Initial state:
ontable(B) ontable(A) on(C, A) clear(B) clear(C) empty
the robot is not holding anything
ontable(B) othnetreabislen(oAth)in g on(C,A) ontable(C) on(B, C) on(A, B) clear(A)
on block B
clear(B) clear(C) empty ontable(C) on(B, C) on(A, B) clear(A)
Goal state:
STRIPS: actions
Preconditions are encoded as conjunctions of literals
‣ Atoms encode which conditions need to be satisfied before the action can take place
‣ Negated atoms encode conditions that cannot be true when the action takes place (note: negated preconditions are not allowed in the standard STRIPS language)
Effects are encoded as conjunctions of literals
‣ Atoms encode which conditions become true after executing
the action
‣Negated atoms encode which conditions become false after executing the action
Variables are used to encode actions that can be applied to all objects that satisfy the preconditions, rather than a single object
clear(B) clear(C) empty ontable(C) on(B, C) on(A, B) clear(A)
STRIPS: actions
Action(PickUp(x, y),
Precond:on(x, y) clear(x) empty,
Effect:holding(x) clear(y) ¬empty ¬clear(x) ¬on(x, y))
Action(PickUpFromTable(x),
Precond:onTable(x) clear(x) empty, Effect:holding(x) ¬empty ¬onTable(x) ¬clear(x))
Action(PutDown(x, y),
Precond:holding(x) clear(y),
Effect:¬holding(x) empty clear(x) on(x, y) ¬clear(y))
Action(PutDownOnTable(x), Precond:holding(x),
Effect:¬holding(x) empty clear(x) onTable(x))
Example
C BA
ontable(B) ontable(A) on(C, A) clear(B) clear(C) empty
ontable(C) on(B, C) on(A, B) clear(A
)
Action(PutDown( )
Action(PutDownOnTable( )
x
)
Action(PutDownOnTable(x), Precond:holding(x),
x,y , Precond:holding(x) clear(y),
Effect:¬holding(x) empty clear(x) onTable(x)) Effect:¬holding(x) empty clear(x) on(x, y)
Example
Action(PickUp(C, A),
Precond:on(C, A) clear(C) empty, Effect:holding(ECf)f eccletar:(¬Ah)o ld¬ienmgp(xty) ¬ecmleaprt(yC) c¬leoanr((Cx,)A ))onTable(
Action(PutDownOnTable(x),
Precond:holding(x),
Action(PickUp(C, A),
clear(B) clear(C) empty PickUp(C,A)
ontable(B) ontable(A) on(C, A)
C
BA
ontable(C) on(B, C) on(A, B) clear(A)
ontable(B) ontable(A) clear(B) 1 holding(C) clear(A)
Precond:on(C, A) clear(C) empty,
Effect:holding(C) clear(A) ¬empty ¬clear(C
Precond:holding(x),
x
)
a
ontable(B) ontable(A) ¬on(C, A)
Effect:¬holding(x) empty clear(x) onTable(
Example
clear(B) ¬clear(C) ¬empty holding(C) clear(A)
Action(PickUp(C, A), Action(PutDownOnTable(C ),
Precond:on(C, A) clear(C) empty, Precond:holding(C ),
Effect:holding(C) clear(A) ¬empty ¬clear(C Effect:¬holding(C) empty clear(C) onTable(C))
ontable(B) ontable(A) clear(B)
1
holding(C) clear(A)
Action(PutDownOnTable(C ), Precond:holding(C ),
PutDownOnTable(C)
BAC
ontable(B) ontable(A) clear(B) Effect:¬holding(C) empty clear(C) onT
clear(C) empty
clear(A) onTable(C)
1
Example
ontable(B) ontable(A) ¬on(C, A)
clear(B) clear(C) empty
¬holding(C) clear(A) onTable(C)
ontable(B) ontable(A) clear(B)
clear(C) empty
clear(A) onTable(C)
Action(PickUpFromTable(B),
Precond:onTable(B) clear(B) empty, Effect:holding(B) ¬empty ¬onTable(B) ¬clear(B))
Action(PickUpFronmtaTbaleb(leB()B ),ontable(A) clear(B) clear(C) empty
Precond:onTable(B) clear(B) empty, clear(A) onTable(C)
Effect:holding(B) ¬empty ¬onTable(B)
B
AC
PickUpFromTable(B)
Action(PickUpFromTable(B), Precond:onTable(B) clear(B) empty,
ontable(A) clear(C) clear(A)
Effect:holding(B) ¬empty ¬onTable(B) onTable(C) holding(B)
¬
clear(A) onTable(C)
¬
)
Example
ontable(A) clear(C) clear(A) onTable(C) holding(B)
Action(PickUpFromTable(B),
ontable(A) clear(C) clear(A)
Precond:onTable(B) clear(B) empty, Action(PutDown(B, C), onTable(C) holding(B)
Effect:holding(B) ¬empty ¬onTable(B) Precond:holding(B) clear(C),
Effect:¬holding(B) empty clear(B) on(B, C) ¬clear(C)) Action(PutDown(B, C),
Precond:holding(B) clear(C), ontable(A) clear(C) clear(A)
ontable(A) clear(A) empty
Effect:¬holding(B) empty clear(B) on(B, C
onTable(C) clear( B)o nTona(bBl,eC(C) ) holding(B) PutDown(B,C)
B
ontable(A) clear(A) empty Action(PutDown(B, C),
AC
Effect:¬holding(B) empty clear(B) on(B, C)
onTable(C) clear(B) on(B, C) Precond:holding(B) clear(C),
holding( ) empty clear( ) on( ) ¬
a
ontable(AE)f fcelceatr:(¬A) emptBy B B,C onTable(C) clear(B) on(B, C)
Example
Action(PutDown(B, C),
ontable(A) clear(A) empty Precond:holding(B) clear(C),
Action(PickUpFromTable(A),
Effect:¬holding(B) empty clear(B) on(B, C)
onTable(C) clear(B) on(B, C) Precond:onTable(A) clear(A) empty,
Effect:holding(A) ¬empty ¬onTable(A) ¬clear(A)) Action(PickUpFromTable(A),
ontable(A) clear(A) empty Precond:onTable(A) clear(A) empty,
A
B C
holding(A)
2
PickUpFromTable(A)
onTable(C) clear(B) on(B, C)
onTable(C) clear(B) on(B, C) Effect:holding(A) ¬empty ¬onTable(A) ¬cle
onTable(C) clear(B) on(B, C) holding(A)
2
onTable(C) clear(B) on(B, C)
c
Action(PickUpFromTable(A),
Example
Action(PutDown(A, B), Precond:holding(A) clear(B),
Precond:onTable(A) clear(A) empty, Effect:holding(A) ¬empty ¬onTable(A) ¬
Effect:¬holding(A) empty clear(A) on(A, B) ¬clear(B)) Action(PutDown(A, B),
A B C
Precond:honldTinabgl(eA(C) ) clecalera(rB(B),) on(B, C) onTable(C) on(B, C) empty
Effect:¬holding (Aho)l dienmg(pAty) clear(A) on(A, B) clear(A) on(A, B)
PutDown(A,B)
2
onTable(C) on(B, C) empty
clear(A) on(A, B)
Example
Goal state:
ontable(B) ontable(A) on(C, A) clear(B) clear(C) empty
ontable(C) on(B, C) on(A, B) clear(A) Action(PutDown(A, B),
Precond:holding(A) clear(B), Effect:¬holding(A) empty clear(A) on(A, B)
A B C
onTable(C) on(B, C) empty clear(A) on(A, B)
Example
Formalise the 8-puzzle as a STRIPS planning problem. Provide a full specification of all actions, as well as the initial and final states which are illustrated below:
Example
Strategy: Assign labels to the rows and columns (e.g. a, b, c, d, e, f ) and explicitly encode which rows/columns are adjacent to each other.
terleaved. [3]
Preconditions: At(u, x, y) ^ adjacentCol(y, z) ^ clear(x, z)
terleaved. [3] (b) • An ordering constraint A B indicates that action A needs to be executed
(b) • An ordering constraint A B indicates that action A needs to be executed before action B. [1]
before action B. [1] • A causal link A ! B indicates that the effect p of action A is used as a
Example p
precondition for B, i.e. that A achieves p for action B.
• A causal link A ! p B indicates that the effect p of action A is used as a
precondition for B, i.e. that A achieves p for action B.
• Orderingconstraintsareaddedtopreventactionsthathave¬pasaneffectto
• Orderingconstraintsareaddedtopreventactionsthathave¬pasaneffectto pp
Strategy: Assign labels to the rows and columns (e.g. a, b, c, d, e, f ) taketapklaecpelabcetwbetewneAenaAndanBd.BS.pSecpieficcifiacllayl,lyi,f iaf acacuasuaslalilniknkAA! ! Biissaadded,
and explicitly encode which rows/columns are adjacent to each other.
forafnoyrancytiaocntiConaClreaalrdeyadinytihnethpearptaiartliapllapnlawnhwihcihchahsas¬¬ppasasaanneefffeecctt,,eiitther the ordering constraint C A or B C is added. [4]
[1] [1]
the ordering constraint C A or B C is added. [4] (c) One possibility is to represent the initial state as follows: [4]
(c) One possibility is to represent the initial state as follows: [4]
Initial state:
adjacentRow(a,b) ^ adjacentRow(b,c) ^ adjacentRow(b,a) ^ adjacentRow(c,b)
adjacentRow(a,b) ^ adjacentRow(b,c) ^ adjacentRow(b,a) ^ adjacentRow(c,b) ^ adjacentCol(d,e) ^ adjacentCol(e,f) ^ adjacentCol(e,d) ^ adjacentCol(f,e)
^ adjacentCol(d,e) ^ adjacentCol(e,f) ^ adjacentCol(e,d) ^ adjacentCol(f,e) ^at(7,a,d)^at(2,a,e)^at(4,a,f)^at(5,b,d)^clear(b,e)^at(6,b,f)
^at(7,a,d)^at(2,a,e)^at(4,a,f)^at(5,b,d)^clear(b,e)^at(6,b,f) ^at(8,c,d)^at(3,c,e)^at(1,c,f)
^at(8,c,d)^at(3,c,e)^at(1,c,f)
and the final state as: [1]
and the final state as: [1]
Goal state:
clear(a,d)^at(1,a,e)^at(2,a,f)^at(3,b,d)^at(4,b,e)^at(5,b,f) clear(a,d)^at(1,a,e)^at(2,a,f)^at(3,b,d)^at(4,b,e)^at(5,b,f)
^at(6,c,d)^at(7,c,e)^at(8,c,f) ^at(6,c,d)^at(7,c,e)^at(8,c,f)
and the actions as: and the actions as:
Action: Action:
[7] [7]
MoveHorizontally(x, y, z, u) MoveHorizontally(x, y, z, u)
^ adjacentCol(d,e) ^ adjacentCol(e,f) ^ adjacentCol(e,d) ^ adjacentCol(f,e)
^at(7,a,d)^at(2,a,e)^at(4,a,f)^at(5,b,d)^clear(b,e)^at(6,b,f) ^at(8,c,d)^at(3,c,e)^at(1,c,f)
Example
and the final state as: [1]
clear(a,d)^at(1,a,e)^at(2,a,f)^at(3,b,d)^at(4,b,e)^at(5,b,f) ^at(6,c,d)^at(7,c,e)^at(8,c,f)
Actions:
and the actions as:
[7]
Action: Preconditions: Effects:
Action: Preconditions: Effects:
MoveHorizontally(x, y, z, u)
At(u, x, y) ^ adjacentCol(y, z) ^ clear(x, z)
At(u, x, z) ^ clear(x, y) ^ ¬At(u, x, y) ^ ¬clear(x, z)
MoveVertically(x,y,z,u)
At(u, x, y) ^ adjacentRow(x, z) ^ clear(z, y)
At(u, z, y) ^ clear(x, y) ^ ¬At(u, x, y) ^ ¬clear(z, y)