PowerPoint Presentation
Planning
Planning
Logic
Planning
Lesson Preview
States, goals, and operators
Conflicts in planning
Partial-order planning
Hierarchical task networks
C
B
A
A
C
B
Current State
Goal State
A on B
B on C
C on D
D on Table
D
D
A on B
B on C
C on Table
D on Table
Δ = 1
Goals:
The ceiling is painted and the ladder is painted
In propositional logic:
Painted(Ceiling)
Goals:
The ceiling is painted and the ladder is painted
In propositional logic:
Painted(Ceiling)
Painted(Ladder)
Goal State:
Painted(Ceiling) ˄ Painted(Ladder)
How would we represent second part of the goal state?
How would we represent the goal state as a conjunction?
Goal State:
Painted(Ceiling) ˄ Painted(Ladder)
Initial State:
On(Robot, Floor) ˄
Dry(Ladder) ˄
Dry(Ceiling)
State:
Painted(Ceiling) ˄
On(Robot, Ladder)
Initial State:
On(Robot, Floor) ˄
Dry(Ladder) ˄
Dry(Ceiling)
How would we represent a state where the robot is on the ladder and the ceiling is painted?
Operator:
Climb ladder
In propositional logic:
climb-ladder:
Precondition:
On(Robot, Floor) ˄
Dry(Ladder)
Postcondition:
On(Robot, Ladder)
paint-ceiling:
Precondition:
On(Robot, Ladder)
Postcondition:
Painted(Ceiling) ˄ ¬Dry(Ceiling)
paint-ladder:
Precondition:
On(Robot, Floor)
Postcondition:
Painted(Ladder) ˄ ¬Dry(Ladder)
climb-ladder:
Precondition:
On(Robot, Floor) ˄
Dry(Ladder)
Postcondition:
On(Robot, Ladder)
descend-ladder:
Precondition:
On(Robot, Ladder) ˄
Dry(Ladder)
Postcondition:
On(Robot, Floor)
Initial State
Goal State
P1
P2
P3
P4
P5
P6
P7
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
On(Robot, Floor) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
climb-ladder
paint-ceiling
descend-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
On(Robot, Floor) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
climb-ladder
paint-ceiling
descend-ladder
paint-ceiling:
Precondition:
On(Robot, Ladder)
Postcondition:
Painted(Ceiling) ˄ ¬Dry(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
On(Robot, Floor) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
climb-ladder
paint-ceiling
descend-ladder
paint-ceiling:
Precondition:
On(Robot, Ladder)
Postcondition:
Painted(Ceiling) ˄ ¬Dry(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
On(Robot, Floor) ˄ Dry(Ladder) ˄ ¬Dry(Ceiling)
Painted(Ceiling)
climb-ladder
paint-ceiling
descend-ladder
paint-ceiling:
Precondition:
On(Robot, Ladder)
Postcondition:
Painted(Ceiling) ˄ ¬Dry(Ceiling)
Goal State:
Painted(Ladder) ˄ Painted(Ceiling)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
paint-ladder:
Precondition:
On(Robot, Floor)
Postcondition:
Painted(Ladder) ˄ ¬Dry(Ladder)
climb-ladder:
Precondition:
On(Robot, Floor) ˄
Dry(Ladder)
Postcondition:
On(Robot, Ladder)
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
Detecting Conflicts
For each precondition in current plan:
If precondition for an operator in the current plan is clobbered by a state inanother plan:
Promote current plan above other plan
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
climb-ladder:
Precondition:
On(Robot, Floor) ˄
Dry(Ladder)
Postcondition:
On(Robot, Ladder)
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
climb-ladder:
Precondition:
On(Robot, Floor) ˄
Dry(Ladder)
Postcondition:
On(Robot, Ladder)
Goal: Painted(Ladder)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Goal: Painted(Ceiling)
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
Result: Promote Painted(Ceiling) above Painted(Ladder)
Final Plan
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
Final Plan
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
?
Final Plan
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Ladder) ˄
Dry(Ladder) ˄ Dry(Ceiling)
climb-ladder
paint-ceiling
On(Robot, Ladder) ˄
Dry(Ladder) ˄ ¬Dry(Ceiling) ˄ Painted(Ceiling)
paint-ladder
On(Robot, Floor) ˄
Dry(Ladder) ˄ Dry(Ceiling)
On(Robot, Floor) ˄
¬Dry(Ladder) ˄ Dry(Ceiling) ˄ Painted(Ladder)
descend-ladder
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D) ˄ On(D, Table)
Syntax:
D is on B → On(D, B)
Top of D is clear → Clear(D)
Write the current and goal states in propositional logic.
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D)
Operator:
Move block x to block y
Move(x, y)
Precondition:
Clear(x) ˄ Clear(y)
Postcondition:
On(x, y)
Operator:
Move block x to table
Move(x, Table):
Precondition:
Clear(x)
Postcondition:
On(x, Table)
Syntax:
D is on B → On(D, B)
Top of D is clear → Clear(D)
Write the pre- and post-conditions for the two Move operators.
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D)
On(A, B):
Move(D, Table)
Move(B, Table)
Move(A, B)
On(B, C):
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(B, C)
On(C, D):
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(C, D)
D is on B → On(D, B)
Top of D is clear → Clear(D)
Put D on B → Move(D, B)
Put D on Table → Move(D, Table)
Write plans for accomplishing each goal.
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D)
On(A, B):
Move(D, Table)
Move(B, Table)
Move(A, B)
On(B, C):
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(B, C)
On(C, D):
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(C, D)
D is on B → On(D, B)
Top of D is clear → Clear(D)
Put D on B → Move(D, B)
Put D on Table → Move(D, Table)
Use partial-order planning to order the plans.
1
2
3
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D)
Final Plan:
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(C, D)
Move(B, C)
Move(A, B)
D is on B → On(D, B)
Top of D is clear → Clear(D)
Put D on B → Move(D, B)
Put D on Table → Move(D, Table)
Write a final plan for converting the current state to the goal state.
C
B
A
Current State
Goal State
D
E
F
G
H
I
L
J
K
M
P
N
O
H
F
G
E
L
J
K
I
P
N
O
M
A
C
B
D
Final Plan:
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(C, D)
Move(B, C)
Move(A, B)
Move(H, Table)
Move(F, Table)
Move(G, Table)
Move(G, H)
Move(F, G)
Move(E, F)
Move(K, Table)
Move(L, Table)
Move(J, Table)
Move(K, L)
Move(J, K)
Move(I, J)
Move(O, Table)
Move(N, Table)
Move(P, Table)
Move(O, P)
Move(N, O)
Move(M, N)
C
B
A
A
C
B
Current State
Goal State
D
D
On(D, B) ˄ On(B, A) ˄ On(A, C) ˄ On(C, Table)
On(A, B) ˄ On(B, C) ˄ On(C, D)
Final Plan:
Move(D, Table)
Move(B, Table)
Move(A, Table)
Move(C, D)
Move(B, C)
Move(A, B)
D is on B → On(D, B)
Top of D is clear → Clear(D)
Put D on B → Move(D, B)
Put D on Table → Move(D, Table)
unstack
stack-ascending
stack-ascending:
Precondition:
On(a, Table) ˄
On(b, Table) ˄
On(c, Table) ˄
On(d, Table)
Postcondition:
On(a, b) ˄
On(b, c) ˄
On(c, d) ˄
On(d, Table)
Method:
Move(c, d)
Move(b, c)
Move(a, b)
unstack:
Precondition:
On(w, x) ˄
On(x, y) ˄
On(y, z) ˄
On(z, Table)
Postcondition:
On(w, Table) ˄
On(x, Table) ˄
On(y, Table) ˄
On(z, Table)
Method:
Move(w, Table)
Move(x, Table)
Move(y, Table)
C
B
A
Current State
Goal State
D
E
F
G
H
I
L
J
K
M
P
N
O
H
F
G
E
L
J
K
I
P
N
O
M
A
C
B
D
Final Plan:
unstack(D, B, A, C)
stack-ascending(A, B, C, D)
unstack(H, F, G, E)
stack-ascending(E, F, G, H)
unstack(K, L, J, I)
stack-ascending(I, J, K, L)
unstack(O, N, P, M)
stack-ascending(M, N, O, P)
Assignment
How would you use planning to address Raven’s progressive matrices?
To recap…
Planning in propositional logic
Goal conflicts
Partial-order planning for conflict avoidance
Hierarchical task networks
/docProps/thumbnail.jpeg
Reviews
There are no reviews yet.