[SOLVED] CS PowerPoint Presentation

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 Ravens 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 Ravens 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