PowerPoint Presentation
Semantic Networks
Semantic Networks
Generate and Test
Problem Reduction
Means-Ends Analysis
Fundamentals
Production Systems
Lesson Preview
Knowledge representations
Semantic networks
Problem-solving with semantic networks
Represent & Reason
?
A
B
C
#
1
2
3
4
5
6
inside
above
above
above
unchanged
expanded
deleted
A
B
z
x
y
x
y
z
x
y
z
x
y
v
u
inside
v
u
unchanged
deleted
v
u
v
inside
above
above
above
unchanged
unchanged
deleted
The relationships between the pieces and the transformations between the frames.
C
5
r
s
t
r
s
t
r
s
t
r
s
inside
above
above
above
unchanged
expanded
deleted
A
B
z
x
y
x
y
z
x
y
z
x
y
Structure of Semantic Networks
Lexically: nodes
Structurally: directional links
Semantically: application-specific labels
x
y
z
inside
above
above
x
y
z
above
unchanged
expanded
deleted
Characteristics of Good Representations
Make relationships explicit
Expose natural constraints
Bring objects and relations together
Exclude extraneous details
Transparent, concise, complete, fast, computable
Guards & Prisoners Problem
Also known by other names (cannibals and missionaries, jealous husbands, brothers and sisters).
Originally appeared in the 1200-year-old text Propositiones ad Acuendos Juvenes.
Used by throughout AI for problem representation.
Guards & Prisoners Problem
Three guards and three prisoners must cross river.
Boat may take only one or two people at a time.
Prisoners may never outnumber guards on either coast, though prisoners may be alone on either coast).
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
⛵
Exercise: How many moves does it take to move everyone to the other side?
11
x
y
z
inside
above
above
x
y
z
above
unchanged
expanded
deleted
inside
above
above
above
unchanged
unchanged
deleted
x
y
z
x
y
A
B
C
5
r
s
t
r
s
t
r
s
t
r
s
expanded
unchanged
x
y
z
inside
above
above
x
y
z
above
unchanged
deleted
x
y
z
x
y
A
B
inside
above
above
above
unchanged
deleted
C
5
r
s
t
r
s
t
r
s
t
r
s
inside
above
above
above
unchanged
deleted
C
r
s
t
r
s
t
r
s
t
r
2
s
expanded
Is this the right answer to the problem? ο Yes ο No
x
y
z
inside
above
above
x
y
z
above
unchanged
expanded
deleted
x
y
z
x
y
A
B
x
y
z
inside
above
above
x
y
z
above
unchanged
deleted
inside
above
above
above
unchanged
deleted
x
y
z
x
y
A
B
expanded
expanded
Is this the right answer to the problem? ο Yes ο No
C
r
s
t
r
s
t
r
s
t
r
2
s
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
Transformation #1
Transformation #2
p
q
p
p
A
B
A
B
q
q
p
q
inside
q
unchanged
+5
p
deleted
+1
p
q
inside
q
deleted
+1
p
expanded
+2
Similarity Weights
5 points Unchanged
4 points Reflected
3 points Rotated
2 points Scaled
1 points Deleted
0 points Shape Changed
Similarity:
6 points
Similarity:
3 points
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
?
A
B
C
#
1
2
3
4
Similarity Weights
5 points Unchanged
4 points Reflected
3 points Rotated
2 points Scaled
1 points Deleted
0 points Shape Changed
Assignment
How would you use semantic networks to design an agent that can answer Raven’s Progressive Matrices?
To recap…
Representations
Semantic networks
Represent & Reason
Weights with Represent & Reason
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
What is the answer to this problem?
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
What is the answer to this problem?
q
q
q
q
q
q
reflected
q
q
rotated
cost: 1
cost: 2
A
B
A
B
Horizontal Reflection
180° Rotation
q
q
q
q
q
q
reflected
q
q
rotated
cost: 1
cost: 2
6
C
2
Horizontal Reflection
180° Rotation
C
What would the answer be? ο 2 ο 6
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
?
A
B
C
#
1
2
3
4
5
6
ο
ο
ο
ο
ο
ο
/docProps/thumbnail.jpeg