CS代考计算机代写 PowerPoint Presentation

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

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 in another plan:

Promote current plan above other plan

Postcondition:
On(Robot, Ladder)

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)

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)

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

Related Posts