PowerPoint Presentation
Means-Ends Analysis and Problem Reduction
Semantic Networks
Generate and Test
Problem Reduction
Means-Ends Analysis
Fundamentals
Production Systems
Lesson Preview
State spaces
Means-ends analysis
Problem solving with means-ends analysis
Problem reduction
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
A on B
B on C
C on Table
Move the blocks from the initial state to the goal state while obeying these rules:
1. You may only move one block at a time.
2. You may only move blocks that have nothing on top of them.
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
A on B
B on C
C on Table
Available Operators:
Move(Object, Location)
e.g.:
Move(C, Table)
moves C onto the table
Move(C, B)
moves C onto B
Move(C, Table)
Move(B, C)
Move(A, B)
Write a list of operators that will move the blocks into the goal state.
Initial State
Goal State
P1
P2
P3
P4
P5
P6
P7
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
A on B
B on C
C on Table
A
C
B
A on Table
B on C
C on A
A
C
B
A on Table
B on Table
C on Table
Initial State
Goal State
P1
P2
P3
P4
P5
P6
P7
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
Δ = 3
A on B
B on C
C on Table
Δ = 0
A
C
B
Δ = 3
A
C
B
Δ = 3
A
C
B
Δ = 2
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
Δ = 3
A on B
B on C
C on Table
Δ = 0
A
C
B
Δ = 3
A
C
B
Δ = 3
A
C
B
Δ = 2
A
C
B
A
C
B
Initial State
Goal State
A on Table
B on Table
C on A
Δ = 3
A on B
B on C
C on Table
Δ = 0
A
C
B
A on Table
B on C
C on Table
Δ = 1
A
C
B
A on Table
B on Table
C on Table
Δ = 2
Means-Ends Analysis
For each operator that can be applied:
Apply the operator to the current state
Calculate difference between new state and goal state
Prefer state that minimizes distance between new state and goal state
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
C
B
A
A
C
B
Initial State
Goal State
A on Table
B on C
C on Table
D on B
Δ = 3
A on B
B on C
C on D
D on Table
D
D
C
B
A
A
C
B
Initial State
Goal State
A on B
B on C
C on D
D on Table
D
D
A on D
B on C
C on Table
D on B
Δ = 3
A on Table
B on C
C on Table
D on A
Δ = 3
A on Table
B on C
C on Table
D on Table
Δ = 2
A on Table
B on C
C on Table
D on B
Δ = 3
What is the difference between each state and the goal state?
C
B
A
A
C
B
Initial State
Goal State
A on B
B on C
C on D
D on Table
D
D
A on D
B on C
C on Table
D on B
Δ = 3
A on Table
B on C
C on Table
D on A
Δ = 3
A on Table
B on C
C on Table
D on Table
Δ = 2
A on Table
B on C
C on Table
D on B
Δ = 3
Using means-ends analysis, which move will be chosen?
ο
ο
ο
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 Table
B on C
C on Table
D on Table
Δ = 2
How many possible next states are there?
How many of those states reduce the difference to the goal?
7
1
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
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
How many possible next states are there?
How many of those states reduce the difference to the goal?
3
0
Assignment
How would you use means-ends analysis to design an agent that could answer Raven’s Progressive Matrices?
Easier Problem
Easier Problem
Easier Problem
Hard Problem
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
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
C
D
C on D
D on Table
Subgoal
C
B
A
Current State
D
A on B
B on C
C on Table
D on Table
Δ = 1
C
D
C on D
D on Table
Subgoal
C
B
A
Current State
D
A on B
B on C
C on Table
D on Table
Δ = 1
C
D
C on D
D on Table
Subgoal
A on D
B on C
C on Table
D on Table
Δ = 1
A on B
B on C
C on Table
D on A
Δ = 2
A on Table
B on C
C on Table
D on Table
Δ = 1
C
B
A
Current State
D
A on Table
B on C
C on Table
D on Table
Δ = 1
C
D
C on D
D on Table
Subgoal
Move(B, Table)
Move(C, D)
Available Operators:
Move(Object, Location)
e.g.:
Move(C, Table)
moves C onto the table
Move(C, B)
moves C onto B
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 Table
B on Table
C on D
D on Table
Δ = 2
Move(B, C)
Move(A, B)
Available Operators:
Move(Object, Location)
e.g.:
Move(C, Table)
moves C onto the table
Move(C, B)
moves C onto B
Assignment
How would you use problem reduction to design an agent that could answer Raven’s Progressive Matrices?
To recap…
State spaces
Means-ends analysis
Problem solving with means-ends analysis
Problem reduction
Set of Transformations
Initial State
Goal State
Initial State
Goal State
delete
move
expand
Initial State
Goal State
delete
move
expand
Initial State
Goal State
delete
move
expand
delete
move
expand
/docProps/thumbnail.jpeg