صفحه 1:
صفحه 2:
The planning problem
ا لش
Inputs: ©
A description of the world state .1
The goal state description .2
A set of actions .3
© Output:
A sequence of actions that if applied to the
initial state, transfers the world to the goal
state
صفحه 3:
An example - Blocks world
<< لل
" Blocks on a table
" Can be stacked, but only one block on top
of another
" A robot arm can pick up a block and move
to another position
* On the table
* On another block
© Arm can pick up only one block at a time
* Cannot pick up a block that has another one on
it
صفحه 4:
STRIPS Representation
١ شخ
State is a conjunction of positive ground 5
literals
On(B, Table) A Clear (A)
Goal is a conjunction of positive ground "
literals
Clear(A) A On(A,B) A On(B, Table)
STRIPS Operators ©
Conjunction of positive literals as preconditions *
* Conjunction of positive and negative literals as
effects
صفحه 5:
More on action schema
ليسي ا
©" Example: Move (b, x, y)
* Precondition:
Block(b) A Clear(b) A Clear(y) A On(b,x) A
(b # x) A(b # y) A (y # x)
* Effect:
=Clear(y) A ~On(b,x) A Clear(x) A On(b,y)
سپس سسپست
Deets best (Bet best
" An action is applicable in any state that
satisfies its precondition
صفحه 6:
STRIPS assumptions
۳
© Closed World assumption
* Unmentioned literals are false (no need to
explicitly list out)
© STRIPS assumption
* Every literal not mentioned in the “effect”
of an action remains unchanged
5 Atomic Time (actions are instantaneous)
صفحه 7:
STRIPS expressiveness
"_______ ا
“Literals are function free: Move (Block(x), y, Z)
© operators can be propositionalized
Move(b,x,y) and 3 blocks and table can be
expressed as 48 purely propositional actions
5 No disjunctive goals: On(B, Table) V On(B, C)
No conditional effects: On(B, Table) if -On(A,
Table)
صفحه 8:
Planning algorithms
—_ _ _ _
© Planning algorithms are search
procedures
= Which state to search?
* State-space search
™ Each node is a state of the world
™ Plan = path through the states
* Plan-space search
™ Each node is a set of partially-instantiated
operators and set of constraints
= Plan = node
صفحه 9:
State search
5* [آ[آ[كك سس سي
© Search the space of situations, which is
connected by operator instances
" The sequence of operators instances =
plan
© We have both preconditions and effects
available for each operator, so we can
try different searches: Forward vs.
Backward
صفحه 10:
Planning: Search Space
6
1
B ۱۱ (B
Aj |B IA] |C
B 0 2 A
0 عالظالفا 6 B
2 A} |B Al ع6
AI 2
اظ BI |C
اهاس
تداع
صفحه 11:
Forward state-space search
211592
ay
° Progression
5 Initial state: initial state of the problem
© Actions:
» Applied to a state if all the preconditions
are satisfied
* Succesor state is built by updating current
state with add and delete lists
= Goal test: state satisfies the goal of the
problem
صفحه 12:
Progression (forward
م77 لوعتقعع
ProgWS(world-state, goal-list, PossibleActions,
path)
If world-state satisfies all goals in goal-list,
1. Then return path.
2. Else Act = choose an action whose
precondition is true in world-state
) If no such action exists
Then fail
Else return ProgWS( result(Act, world-
state),
goal-list, PossibleActions,
concatenate(nath. Act) )
صفحه 13:
Forward search in the Blocks world
CS | es
35
و
_
Ie
ta Ho
/
صفحه 14:
Forward state-space search
a ل
cs
5 Advantages
* No functions in the declarations of goals J]
search state is finite
* Sound
* Complete (if algorithm used to do the
search is complete)
5 Limitations
* Irrelevant actions {j not efficient
* Need heuristic or pruning procedure
صفحه 15:
Backward state-space search (1)
a
© Regression
© Initial state: goal state of the problem
5 Actions:
* Choose an action that
= Is relevant; has one of the goal literals in its effect
set
= Is consistent; does not negate another literal
* Construct new search state
= Remove all positive effects of A that appear in goal
™ Add all preconditions, unless already appears
© Goal test: state is the initial world state
صفحه 16:
Regression (backward
path)
1 If initial-state satisfies all of current-goals
2. Then return path
3. Else Act = choose an action whose effect
matches one of current-goals
If no such action exists, or the effects of Act
contradict some of current-goals, then fail
». G = (current-goals - goals-added-
by(Act)) + preconds(Act)
If G contains all of current-goals, then fail
Return RegWS(initial-state, G,
PossibleActions,
concatenate(Act, path))
صفحه 17:
Backward state-space search (2)
7
5 Advantages
* Consider only relevant actions J much
smaller branching factor
5 Limitations
* Still need heuristic to be more efficient
صفحه 18:
Comparing ProgWS and
EE
° Both algorithms are
* sound (they always return a valid plan)
* complete (if a valid plan exists they will find
one)
| Running time is O(b")
where b = branching factor,
n = number of “choose” operators
صفحه 19:
Blocks world: STRIPS
wy OS OS سا7
5 Pickup(x) © OvGraok(x,y)
Pre: on(x, Table), ret va(x, v), oe
clear(x), ae et: va(x, y), oF
Del: on(x, Table), ae ل اك (v)
Add: holding(x)
"G x,
“ Putdown(x) er vleur(v)
Pre: holding(x) Oet: kokdicrey(x), chear(v)
Del: holding(x) Odd: va(x, y), 3
Add: on(x, Table), ae
صفحه 20:
STRIPS Planning
لها 5 [o]
۲ [1
© Current state:
* on(A,table), on(C, B), on(B,table), on(D,table), clear(A), clear(C),
clear(D), ae.
= Goal
» on(A,C), on(C,D)
صفحه 21:
STRIPS Planning
lan: Goalstackoniasc).onio.a) ا
on(A,C)
Stack(A, C)
holding(A), clear(C)
holding(A)
Pickup(A)
on(A,Table), clear(A), ae
جا
وله
۲
jtable), on(C, B), on(B,table), on(D,table), clear(A), clear(C), clear(D), ae
irrent State
صفحه 22:
STRIPS Planning
Plan: Goalstackoniac),onto.a) fl
on(A,C)
Stack(A, C)
Pickup(x) holding(A), clear(C)
Pre: on(x,Table), clear(x), ae holding(A)
Pickup(A)
Del: on(x, Table), ae,
Add: holding(x)
جا
وله
۲
(0)) له , (۱))انه ,)ان ,)9 ننه con((D) , (ها هر )۳۲ ,((۳ ibg(A), on(C,,
irrent State
صفحه 23:
STRIPS Planning
Plan: Goalstackoniac,onto.a) fl
Pickup(A) on(A,C)
Stack(A, C)
Stack(x, y)
Pre: holding(x), clear(y)
Del: holding(x), clear(y)
Add: on(x, y), ae
0
۳1
inGIAdNG( G) BONdB (Ebab)leo nD (fbicled adeGr| AdjadesDICheclear(D).
irrent State
صفحه 24:
STRIPS Planning
Pickup(A) on(D, A)
Stack(A, C) Stack(D,A)
holding(D), clear(A)
holding(D)
Pickup(D)
on(D,Table), clear(D), ae
“he
۳1
AD) ond CE) oon اجه اه [( راهن تلاصا و3 )0( ae.
irrent State
صفحه 25:
STRIPS Planning
Plan Goalstackaniac).onio.a fl
Pickup(A) on(D, A)
Stack(A, C) Stack(D,A)
Pickup(D) holding(D), clear(A)
holding(D)
0
1
۳1
M6) con{(C, EB), con( ER tedts), hen DIlecdeGk|Adeclear(D)
irrent State
صفحه 26:
STRIPS Planning: Getting it Wrong!
on(D,A)
Stack(D, A)
holding(D), clear(A)
holding(D)
Pickup(D)
on(D,Table), clear(D), ae
جا
وله
۲
.table), on(C, B), on(B,table), oo BitahD3), clen(), cisen(O), cltsan(), a€
irrent State
صفحه 27:
STRIPS Planning: Getting it Wrong!
Plans GoalstackoniA.c),onto.a)
Pickup(D) on(D,A)
Stack(D, A)
Hi
۳221
١ Herts), con((C, EB), cov( EB Heidt), Fooling LD | (۲)0هع۱ععع] هه که له
irrent State
صفحه 28:
STRIPS Planning: Getting it Wrong!
Plans Goalstackoniasc).onio.a) ا
Pickup(D)
Stack(D, A)
Now What?
— We chose the wrong goal first
— Ais no longer clear.
— stacking D on A messes up the preconditions for
actions to accomplish on(A, C)
SNS — either have to backtrack, or else we must undo
ga the previous actions
۳221
\,table), on(C, B), on(B,table), on(D,A), clear(C), clear(D), ae.
irrent State
صفحه 29:
STRIPS planning (Goalstack planning)
شش يفك
Works on one subgoal at a time "
Insists on completely achieving that 5
subgoal before considering other subgoals
May have to backtrack: |
* If it chooses the wrong order to work on the
subgoals
* If it chooses the wrong action to achieve a
subgoal
| Searches backwards from goal - uses goal
to guide choice of actions
صفحه 30:
Limitation of state-space search
© Linear planning or Total order planning
= Example
* Initial state: all the blocks are clear and on
the table
* Goal: On(A,B) A On(B,C)
* If search achieves On(A,B) first, then needs
to undo it in order to achieve On(B,C)
© Have to go through all the possible
permutations of the subgoals
صفحه 31:
Search through the space of plans
ص
© Nodes are partial plans, links are plan
refinement operations and a solution is a node
(not a path).
© This can be powerful if the plan representation
and refinements change the search space.
© POP creates partial-order plans following a
“least commitment” principle.
صفحه 32:
Partial Order Plans: Total Order Plans:
Start Start| |Start||Start| |Start|/Start| |Start
2 1 1 1 1 1 1
عم ]| تحونظ | غطونعا | [Left |[Right ]/ Lett
Left Right Sock | | Sock || Sock | | Sock |] Sock || Sock
Sock Sock | | | |
| | Left ]/ Left | [Right |[Right ] [Right] Left
on Right Sqckon | Sock || Sock |_| Sock || Sock | | Shoe | Shoe دي
Left Right 1 | 1 J
Shoe Shoe
Right] [Left |[Right]/ Left ] [Left |[Right
Shoe| | Sock || Shoe || Shoe | | Sock || Sock
Left ] [Right]/ Left ||Right|) Left | Right
Shoe| | Shoe || Shoe || Shoe || Shoe | Shoe
لا 1 ] |
Finish Finish Finish Finish Finish Finish
صفحه 33:
P.O. plans in POP
211101111111111
= Plan = (A, O, L), where
* Ais the set of actions in the plan
* Ois a set of temporal orderings between actions
* Lis a set of causal links linking actions via a literal
Causal link ,)مت رن means that Ac has
precondition Q that is established in the plan by Ap.
move-a-from-b-to-table ("=") move-c-from-d-to-
b
صفحه 34:
Threats to causal links
<<) آذآ
Step At threatens link —— if:
1. At has (~Q) as an effect
2. At could come between Ap and Ac, i.e., 0
is consistent with Ap < At < Ac
صفحه 35:
Threat Removal
" Threats must be removed to prevent a
plan from failing
© Demotion adds the constraint A, < A, to
prevent clobbering, i.e. push the
clobberer before the producer
4 Promotion adds the constraint A, < A, to
prevent clobbering, i.e. push the
clobberer after the consumer
صفحه 36:
Initial (Null) Plan
© Initial plan has
~A={A,A}
-O={A, <A}
*L={}
4 A, (Start) has no preconditions but all
facts in the initial state as effects.
© A, (Finish) has the goal conditions as
preconditions and no effects.
صفحه 37:
POP algorithm
1 If agenda is empty, return (A, O, L)
2. Pick (Q, An) from agenda
3. Ad = choose an action that adds Q.
If no such action exists, fail.
add the link Ad.) , Ac to L and the ordering Ad < Ac to
If Ad is new, add it to A.
« Remove (Q, An) from agenda. If Ad is new, for
each of its preconditions P add (P, Ad) to agenda.
s. For every action At that threatens any like —— > Pe
1. Choose to add At < Ap or Ac > At to O.
If neither choice is consistent, fail.
«. POP((A, O, L), agenda, PossibleActions)
صفحه 38:
Sussman Anomaly
ا اط
Po
(oO ®) فا و (cher O) (cer ®)
(os ®) ) 0 0( روصم
©
3
صفحه 39:
Work on open precondition (on B C)
Po
(oO ®) فا و (cher O) (cer ®)
(cer ®) (cea ©) یی B)
0: wove 0 مس ©
-(ownble ®) {ele ©) (vg 0)
(okt ©) — (ex ®®) (a OO)
©
3
صفحه 40:
Work on open precondition (on A B)
(ce ©) (eer) ی سس وم
(cea ®) (cer) — (ote ®)
2: wove © Prow Dab ® Loy end) 4 3
eee) (ماحطع OO), 0: wove © Prow Poble i 0
orb) -(cear ©) (oa ® OC)
(orkbeO) (oa) (a BO)
©
3
صفحه 41:
Work on open precondition (on-table C)
(or یی (ه ©( (2M. ©) (dew 0( (clear ®)
(0 ®) سم 0(
9: wore O Prow © ۵ Publ
(orth ©) (oa ®) (ck ®)
(cher @) (clear ®) (oerteble ©( (cea ®) (cea ©) یی ©(
OO: wre O Prow Table to © —_————O1: woe © Prow Doble by O
شنت 7° )® جام )® “(ort
(orb ©) (oa) (a BO)
©
3
صفحه 42:
Analysis
my
|" POP can be much faster than the state-
space planners because it doesn’t need to
backtrack over goal orderings (so less
branching is required).
© Although it is more expensive per node, and
makes more choices than RegWS, the
reduction in branching factor makes it
faster, i.e., 7 is larger but 6 is smaller!
صفحه 43:
More analysis
a
۲7 Does POP make the least possible
amount of commitment?
© Lifted POP: Using Operators, instead of
ground actions,
5 Unification is required
صفحه 44:
POP in the Blocks world
a
PutOn(x,y)
C(x), Cl(y), On(x,y), Cx),
On(x,z) ~Ci(y), ~On(x,z)
PutOnTable(x)
On(x, z) On(x,Table),
0100 Cl(x), ~On(x,z)
صفحه 45:
POP in the Blocks world
as
(On(A) OmA, Table) CKB) OMB, Table) CHC)
On(AB) 6980
FINISH
صفحه 46:
POP in the Blocks world
yy ۳
On{C,A) On(A, Table) CB) On(B, Table) CXC)
START
Puton(B,c)
گام _ دامن
FINISH
صفحه 47:
POP in the Blocks world
On(C,A) On(A, Table) ChB) On(B Table) CC)
۳ Puon(AB)
Clobbers رها
تست
2
«هله_« 40
OntAz) CIB) اس
-| Purons,c)
سا هبو [ ۳:۸
۱
واه _ همه
BEE
FINISH
صفحه 48:
POP in the Blocks world
(On(C.A) OniA, Table) CNB) On(B. Table) C1/C)
2
9:6
PutOn(A.8)
clobbers CHB)
SSorder after
PutOn(E.c)
PuOnTable(c) وه
لي
0001
واه عجامه واه 5
بح ره مه ره
.008نم ۳
PutOA.B)
١
onda.) onc)
FINISH
صفحه 49:
Example 2
سس اا
5 Ay: Start
» At(Home) Sells(SM,Banana) Sells(SM,Milk)
Sells(HWS, Drill)
oA, : Finish
* Have(Drill) Have(Milk) Have(Banana) At(Home)
Buy (y,x) GO (x,y)
At(x), Sells(x,y) | Have(y) At(x) At(y)
~At(x)
صفحه 50:
POP Example
1521 ع ات
start
1
finish
صفحه 51:
POP Example
2
start
Sells(SM, M) Sells(SM,B) At(H)
1
Have(M)} Have(B)
finish
صفحه 52:
POP Example
Sells(SM, M) Sells(SM,B) At(H)
١
At(x,) Sells(x,,M)
Buy (M,x,)
Have(M)
Have(M)} Have(B)
finish
صفحه 53:
POP Example
۲ تسه
start
Sells(SM, M) Sells(SM,B) At(H)
١
At(x,) Sells(x,,M)
Buy (M,x,)
Have(M)
Have(M)} Have(B)
finish
صفحه 54:
POP Example
2
start
Sells(SM, M) Sets(SM,B) At(H)
|
7
7
7
2
7
At(x,) Sells(x,,M) »”
Buy (M,x,)
Have(M) ۰
۰
۰
۷2۷۵ Have(B)
finish
صفحه 55:
POP Example
5 مح
start
Sells(SM, M) Sets(SM,B) At(H)
|
7
7
7
2
7
At(x,) Sells(x,,M) Ke At(x,) Sells(x,, B)
Buy (B,x2)
Have(B)
Buy (M,x,)
Have(M) ۰
۰
۰
۷2۷۵ Have(B)
finish
صفحه 56:
POP Example
211101111111111
start
Sells(SM, M) Sefs(SM,B) At(H)
7 0 َه
۰
۰
۰
7
7
2
7 ۰
At(x,) Sells(x,,M) Ke S\At(x,) Sells(x,, B)
Buy (B,x2)
*م _Have(B)
2
2
2
۳2/۵ saves)
finish
Buy (M,x,)
Have(M) 4
۰
١
١
١
١
I
1
١
١
1
1
۰ 1
١
صفحه 57:
POP Example
go
xX, = SM
start
Sells(SM, M) seinem.) At(H)
5 ۰
۰
۰
۰
۰
۰
S\At(x,) Sells(x,, B)
7
7
3
5
7
At(x,) Sells(x,,M) »”
Buy (B,x2)
Have(B)
Buy (M,x,)
Have(M) +
۰
Sy
FavetMy saves)
finish
2
2
صفحه 58:
POP Example
۲:
xX, = SM
x,=5M start
Sells(SM, M) sea 8) At(H)
Sy
1
7 1 ۰
At(x,) Sells(x,,M) »” 1 0اه “Sells(x,, B)
1
Buy (M,x,) ۱ Buy (B,x,)
۱۲۷۵۷۵۲۷ +. ۱ Have(B)
. i 3
0
FavetMy saves)
finish
صفحه 59:
POP Example
211101111111111
eg
xX, = SM
x, = SM stale At(x,)
Sells(SM, M) sea B) At(H) GO (x,5M)
5 3
۱ = At(SM)
9 ۰
5 1
2 i \
At(x,) Sells(x,,M) 2 At(x,) ,یل)کااع5 8(
Buy (M,x,) ۱ Buy (B,x,)
۱۲۱۵۷۵) 7+. ۱ Have(B)
. i 7
1
FavetMy saves)
finish
صفحه 60:
POP Example
xX, = SM
x, = SM stat At(x;)
Sells(SM, M) Sefs(SM.B) At(H) GO (x,,5M)
‘ 0 ۰
--77 7 At(SM)
4 ۰
At(x,) Sells(x,,M) acc om: ! SV At(x# 2 ells(x,, B)
Buy (M,x,) ۱ Buy (B,x,)
۱۲۷۵۷۵۲۷ +. ۱ Have(B)
۰ i er
1
Tan sete
صفحه 61:
ells(x,, B) ۳ ل
Buy (B,x2)
77 _Have(B)
start
POP Example
3
.
۰
xX, = SM
xX, = SM
At(x,) Sells(x;,M) g2-- 7
Buy (M,x,)
Have(M)
صفحه 62:
POP Example
ey tart 1
x, = SM Stal 14 At)
x= Sells(SM, M) S€FXSWB) AH) GO (x,,SM)
Zh
At(x,) Sells(x,,M) acc ar SV At(x# 2 ells(x,, B)
Buy (B,x2)
_Have(B) *م
Buy (M,x,)
Have(M) 4
۰
صفحه 63:
POP Example
xX, = SM fait
x = SM sta
” لس
At(x,) Sells(x,,M) acc ar SV At(x# 2 ells(x,, B)
Buy (B,x2)
_Have(B) *م
Buy (M,x,)
Have(M) 4
۰
