程序代写代做代考 algorithm CSC242: Introduction to Artificial Intelligence

CSC242: Introduction to Artificial Intelligence
Lecture 2.2
Please put away all electronic devices

Constraint Satisfaction Problem (CSP)
• X: Set of variables { X1, …, Xn } • D: Set of domains { D1, …, Dn }
• Each Di : set of values { v1, …, vk }
• C: Set of constraints { C1, …, Cm }
• Solution: Assign to each Xi a value from Di such that all the Cj are satisfied

Factored Representation
• Splits a state into factors (attributes, features, variables) that can have values
• Factored states can be more or less similar (unlike atomic states)
• Can also represent uncertainty (don’t know the value of some attribute)

Backtracking Search for
CSPs
• DFS search through the space of assignments
• Assign one variable at a time
• Because the representation of CSPs is standardized, no need to supply initial state, actions, transition model, or goal test!
• Early pruning of inconsistent states

Constraint Propagation
• Using the constraints to reduce the set of legal values of a variable, which can in turn reduce the legal values of another variable, and so on
• Not a search process!
• Part of state update in state-space search
• Atypeofinference:makingimplicit information explicit

Constraint Propagation
• Node consistency:
• Propagate unary constraints (once)
• Arc consistency
• Propagate binary constraints • AC-3 algorithm

Arc Consistency
Y=X2 XY
{ 0,1,2,3,4,5,6,7,8,9 }
# possible assignments: 10×10 = 100
{ 0,1,2,3,4,5,6,7,8,9 }

Arc Consistency
Y=X2 XY
{ 0,1,2,3,4,5,6,7,8,9 }
{ 0,1,2,3,4,5,6,7,8,9 }
Make X arc-consistent with respect to Y

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,2,3,4,5,6,7,8,9 }
X arc-consistent with respect to Y

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,2,3,4,5,6,7,8,9 }
Make Y arc-consistent with respect to X

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
Y arc-consistent with respect to X

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
X and Y arc-consistent

Arc Consistency
Y=X2 XY
{ 0,1,2,3 }
{ 0,1,4,9 }
X and Y arc-consistent
# possible assignments: 4×4 = 16

boolean AC3(csp) {
Set queue = all arcs in csp
while (queue is not empty) {
boolean revise(csp, i, j) {
boolean changed = false
foreach vi in Di {
boolean ok = false
foreach vj in Dj {
if ( satisfies Cij )
ok = true
}
= queue.removeFirst()
if (revise(csp, i, j)) {
if Di is empty {
return false
}}
foreach k in neighbors(i) {
add to queue
} }
}}
return true
}
return changed
AC-3
}
}
if (!ok) {
delete vi from Di
changed = true
{

AC-3 Analysis
• CSP with n variables, domain size O(d),
c constraints (arcs)
• Each arc can be inserted in the queue at
most d times
• Checking a single arc takes O(d 2) time
• Total time: O(cd 3)
Independent of n
•

Constraint Propagation
• “Afterconstraintpropagation,weare left with a CSP that is equivalent to the original CSP—they both have the same solutions—but the new CSP will in most cases be faster to search because its variables have smaller domains.”

Constraint Propagation (inference)
State-Space Search

Interleaving Search and
Inference
• Aftereachchoiceduringsearch,we can perform inference to reduce future search

Interleaving Search and Inference
Node Consistency Inconsistent? Fail
Inconsistent?
CSP:
• Variables
• Domains
• Constraints
Arc Consistency (AC-3) Solved? Yes Done!
No Yes Assign a variable
OK
No
Backtrack
No

Constraint Satisfaction
• Impose a structure on the representation of states: Variables, Domains, Constraints
• Backtracking (DFS) search for complete, consistent assignment of values to variables
• Inference (constraint propagation) can reduce the domains of variables
Preprocessing and/or interleaved with search
• Useful problem-independent heuristics
•

Hunt The Wumpus

Hunt The Wumpus
4 3 2
1
1234
Stench
PIT
Stench
Gold
PIT
Stench
START
PIT
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
• Move fwd, turn left/ right
• Shoot arrow (once)
• Grab gold
• Climb out (from [1,1])
• Costs:
-1 per move -10 to shoot
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
• •
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
• Get gold and climb out: +1000
• Fall in pit or get eaten by wumpus: -1000
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
?
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Boolean CSP
• All variables must be Booleans • Domains all { true, false }

WW Boolean CSP
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
For each room:
Has pit? true, false, idk
Has wumpus? true, false, idk
Has gold? true, false, idk
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean[][] P =
new Boolean[n][n];
Boolean[][] W =
new Boolean[n][n];
Boolean[][] G =
new Boolean[n][n];
// P[i][j] == Boolean.TRUE
// if there’s a pit at [i,j]
// P[i][j] == Boolean.FALSE
// if there’s no pit at [i,j]
// P[i][j] == null
// if we don’t know
// W[i][j] ditto for wumpus
// G[i][j] ditto for gold
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
// P_ij == Boolean.TRUE
// if there’s a pit at [i,j]
// P_ij == Boolean.FALSE
// if there’s no pit at [i,j]
// P_ij == null
// if we don’t know
// W_ij ditto for wumpus
// G_ij ditto for gold
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Position pos =
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
// L_ij == Boolean.TRUE
// if agent is at location [i,j]
// else Boolean.FALSE
// Note: The agent always knows
// where it is.
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
enum Orientation = { N,S,E,W };
Orientation orientation;
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
// FacingN == Boolean.TRUE
if agent is facing north
// Ditto for the other directions
// Note: The agent always knows
// which way it is facing
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Hunt The Wumpus
• Breeze • Stench • Glimmer • Bump
• Scream
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean S_11, S_12, S_13, …,
S_21, S_22, …;
Boolean B_11, B_12, B_13, …,
B_21, B_22, …;
…
// S_ij == Boolean.TRUE
// if a stench perceived @[i,j]
// S_ij == Boolean.FALSE
// if no stench @[i,j]
// S_ij == null
// if we don’t know
// B_ij ditto for breeze
// Ditto for other percepts
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

WW Boolean CSP
Boolean P_11, P_12, P_13, …,
P_21, P_22, …;
Boolean W_11, W_12, W_13, …,
W_21, W_22, …;
Boolean G_11, G_12, G_13, …,
G_21, G_22, …;
Boolean L_11 = true,
L_12 = false,
L_13 = false,
…;
Boolean Facing_N, Facing_S,
Facing_E, Facing_W;
Boolean S_11, S_12, S_13, …,
S_21, S_22, …;
Boolean B_11, B_12, B_13, …,
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
…
B_21, B_22, …;
B
B
B
B
B
B
e
e
e e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Constraints

Constraints
• Constraints are Boolean functions of the variables
WA ≠ NT
T2 ≥ T1 + 10 AllDiff(A1,A2,A3,B1,B2,B3,C1,C2,C3)
•
•
•

Constraints
• Constraints are Boolean functions of the variables
WA ≠ NT
T2 ≥ T1 + 10
• AllDiff(A1,A2,A3,B1,B2,B3,C1,C2,C3)
• Constraints on Boolean variables are Boolean functions of Boolean values
• •

Aristole George Boole (384BC – 332BC) (1815-1864)

Propositional Logic (Boolean Algebra)
A Programming Language for Knowledge!

Propositions
• Propositions: things that can be true or false

Propositions
• Propositions: things that can be true or false
• Atomic propositions:
• “It is raining”
• “Socrates was a person”
• “The wumpus is in room [2,2]”

Connectives
(Operators)
• Combine propositions into larger propositions
• ¬,∧,∨,⇒,⇔
• ¬Raining
• Raining ∧ Cold, Raining ∨ Sunny
• Raining ∧ BelowFreezing ⇒ Slippery

Connectives
(Operators)
• Combine propositions into larger propositions
• ¬,∧,∨,⇒,⇔
Syntax
• ¬Raining
• Raining ∧ Cold, Raining ∨ Sunny
• Raining ∧ BelowFreezing ⇒ Slippery

Connectives
(Operators)
• Combine propositions into larger propositions
• ¬,∧,∨,⇒,⇔
• Each connective represents a Boolean
function of its (Boolean) arguments
Semantics
Syntax

Connectives
p
¬p
F
T
T
F

Connectives
p
q
¬p
p∧q
p∨q
p⇒q
p⇔q
F
F
T
F
F
T
T
F
T
F
F
T
T
F
T
F
F
T
F
F
T
T
T
T
T
T

Sentences
(Expressions)
• Every sentence of propositional logic represents (“denotes”) a Boolean function of its (Boolean) arguments

Sentences
(Expressions)
• Every sentence of propositional logic represents (“denotes”) a Boolean function of its (Boolean) arguments
• The meaning of a sentence (the Boolean function that it denotes) is the composition of its parts (“compositional semantics”)

L1,1: True if the agent is in room [1,1] W1,2: True if the wumpus is in room [1,2] W2,1: True if the wumpus is in room [2,1]

Possible Worlds
L1,1
W1,2
W2,1
F
F
F
F
F
T
F
T
F
F
T
T
T
F
F
T
F
T
T
T
F
T
T
T

A Sentence
L1,1 ∧ (W1,2∨W2,1)
L1,1
W1,2
W2,1
F
F
F
F
F
T
F
T
F
F
T
T
T
F
F
T
F
T
T
T
F
T
T
T

Meaning of a Sentence
L1,1 ∧ (W1,2∨W2,1)
L1,1
W1,2
W2,1
W1,2∨W2,1
L1,1∧ (W1,2∨W2,1)
F
F
F
F
F
F
F
T
T
F
F
T
F
T
F
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
T
T
F
T
T
T
T
T
T
T

Truth Table
L1,1 ∧ (W1,2∨W2,1)
L1,1
W1,2
W2,1
W1,2∨W2,1
L1,1∧ (W1,2∨W2,1)
F
F
F
F
F
F
F
T
T
F
F
T
F
T
F
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
T
T
F
T
T
T
T
T
T
T

Propositional Logic
and Boolean CSPs
• Every sentence of propositional logic represents (“denotes”) a Boolean function of its (Boolean) arguments
• Constraints on Boolean variables are Boolean functions of Boolean values

Satisfiability
L1,1 ∧ (W1,2∨W2,1)
L1,1
W1,2
W2,1
W1,2∨W2,1
L1,1∧ (W1,2∨W2,1)
F
F
F
F
F
F
F
T
T
F
F
T
F
T
F
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
T
T
F
T
T
T
T
T
T
T

Inconsistency
L1,1 ∧ (W1,2∨W2,1)
L1,1
W1,2
W2,1
W1,2∨W2,1
L1,1∧ (W1,2∨W2,1)
F
F
F
F
F
F
F
T
T
F
F
T
F
T
F
F
T
T
T
F
T
F
F
F
F
T
F
T
T
T
T
T
F
T
T
T
T
T
T
T

L1,1
T
T
T
W1,2
F
T
T
W2,1
T
F
T
W1,2∨W2,1
T
T
T
L1,1∧ (W1,2∨W2,1)
T
T
T
Inconsistency
L1,1 ∧ (W1,2∨W2,1)
FFFFF FFTTF FTFTF FTTTF TFFFF

L1,1
T
T
T
W1,2
F
T
T
W2,1
T
F
T
W1,2∨W2,1
T
T
T
L1,1∧ (W1,2∨W2,1)
T
T
T
Models
L1,1 ∧ (W1,2∨W2,1)
FFFFF FFTTF FTFTF FTTTF TFFFF

L1,1
T
T
T
W1,2
F
T
T
W2,1
T
F
T
W1,2∨W2,1
T
T
T
{ L1,1, (W1,2∨W2,1) }
T
T
T
Models
{ L1,1, (W1,2∨W2,1) }
FFFFF FFTTF FTFTF FTTTF TFFFF

Unsatisfiable
L1,1 ∧W1,2 ∧ ¬W1,2
L1,1
W1,2
L1,1 ∧W1,2
¬W1,2
L1,1 ∧W1,2 ∧ ¬W1,2
F
F
F
T
F
F
T
F
F
F
T
F
F
T
F
T
T
T
F
F

Unsatisfiable
{ L1,1, W1,2, ¬W1,2 }
L1,1
W1,2
¬W1,2
{ L1,1,W1,2, ¬W1,2 }
F
F
T
F
F
T
F
F
T
F
T
F
T
T
F
F

Propositional Logic
and Boolean CSPs
• Every sentence of propositional logic represents a Boolean function of its atomic propositions
• Each assignment of true or false to the atomic propositions is one possible world
• That world is consistent with the sentence if the function denoted by the sentence is true given that assignment

4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

P1,1, P1,2, … : There is a pit at [1,1], [1,2], … W1,1, W1,2, … : The wumpus is at [1,1], [1,2], …
…
B1,1, B1,2, … : You perceived a breeze at [1,1], …
S1,1, S1,2, … : You perceived a stench at [1,1], … …
L1,1, L1,2, … : The agent is at [1,1], … FacingN, FacingS, FacingE, FacingW

Background Knowledge

Background Knowledge
• You perceive a breeze in a room if that room is adjacent to a room that contains a pit

Background Knowledge
• You perceive a breeze in a room only if that room is adjacent to a room that contains a pit

Background Knowledge
• You perceive a breeze in a room if and only if that room is adjacent to a room that contains a pit
• Rooms adjacent to pits are breezy.

Background Knowledge
• You perceive a breeze in a room if and only if that room is adjacent to a room that contains a pit
• Rooms adjacent to pits have breezes.
Bi,j ⇔ Pk,l for some room [k,l] adjacent to [i,j] ?

Background Knowledge
• You perceive a breeze in a room if and only if that room is adjacent to a room that contains a pit
• Rooms adjacent to pits have breezes.
• You perceive a breeze in [1,1] iff there is a pit in [1,2] or [2,1]
B1,1 ⇔ P1,2 ∨ P2,1

Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1 …

Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1
…
S1,1 ⇔ W1,2 ∨ W2,1
S1,2 ⇔ W1,1 ∨ W2,2 ∨ W3,1
S2,2 ⇔ W1,2 ∨ W2,3 ∨ W3,2 ∨ W2,1 …

Background Knowledge
• A room is safe (“OK”) if and only if it does not contain either a pit or the wumpus

Background Knowledge
• A room is safe (“OK”) if and only if it does not contain either a pit or the wumpus
OK1,1 ⇔ ¬(P1,1 ∨ W1,1)
OK1,2 ⇔ ¬(P1,2 ∨ W1,2)
OK2,1 ⇔ ¬(P2,1 ∨ W2,1) …

Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.

Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.
• There is a wumpus in at least one of the rooms AND a wumpus cannot be in two rooms.

Background Knowledge
• There is exactly one wumpus.
• The wumpus is in exactly one room.
• There is a wumpus in at least one of the rooms AND a wumpus cannot be in two rooms.
W1,1 ∨W1,2 ∨…∨W3,4 ∨W4,4
¬(W1,1 ∧ W1,2), ¬(W1,1 ∧ W1,3), …, ¬(W3,4 ∧ W4,4)

Background Knowledge
B1,1 ⇔ P1,2 ∨ P2,1
B1,2 ⇔ P1,1 ∨ P2,2 ∨ P3,1
B2,2 ⇔ P1,2 ∨ P2,3 ∨ P3,2 ∨ P2,1
…
S1,1 ⇔ W1,2 ∨ W2,1
OK1,1 ⇔ ¬(P1,1 ∨ W1,1)
OK1,2 ⇔ ¬(P1,2 ∨ W1,2)
OK2,1 ⇔ ¬(P2,1 ∨ W2,1)
S1,2 ⇔ W1,1 ∨ W2,2 ∨ W3,1
S2,2 ⇔ W1,2 ∨ W2,3 ∨ W3,2 ∨ W2,1 …
W1,1 ∨W1,2 ∨…∨W3,4 ∨W4,4
¬(W1,1 ∧ W1,2), ¬(W1,1 ∧ W1,3), …, ¬(W3,4 ∧ W4,4)
…

Knowledge-Based Agents

Knowledge-Based Agents
• Maintain a knowledge base (KB) of sentences believed to be true

Knowledge-Based Agents
• Maintain a knowledge base (KB) of sentences believed to be true
• Perceives the world (and updates its beliefs)

Knowledge-Based Agents
• Maintain a knowledge base (KB) of sentences believed to be true
• Perceives the world (and updates its beliefs)
• Infers what to do next

Knowledge-Based Agents
• Maintain a knowledge base (KB) of sentences believed to be true
• Perceives the world (and updates its beliefs)
• Infers what to do next
• Performs an action (and updates its beliefs)

Knowledge-Based Agents Perceive
KB
Act
Infer

Knowledge-Based Agents
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Knowledge-Based Agents
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
L1,1, ¬L1,2, … ¬L3,4, ¬L4,4
FacingE, ¬FacingN, ¬FacingS, ¬FacingW
OK1,1
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

Perception
4 3 2
1
1234
Stench
PIT
Stench
Stench
Gold
PIT
START
PIT
¬B1,1, ¬S1,1
B
B
B
B
B
B
e
e
e
e
e e
e
e
e
e
e
e
e
e
e
e
e
e
r r
r
r
r
r
z
z
z
z
z
z

• Given what I know… • What should I do?
See AIMA 7.7
Inference

Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe?

Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe? • Is room [2,1] safe?

Inference
• Given what I know…
• What should I do?
• Is room [2,1] or [1,2] safe?
• Is room [2,1] safe?
• Is there no pit in room [2,1]?

Inference
Given what I know… Is there no pit in room [2,1]?
KB ¬P2,1?

Inference
Given what I know… Is there no pit in room [2,1]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
¬B1,1
¬P2,1?

Inference
Possible Worlds
P1,1
P1,2
P2,1
B1,1
F
F
F
F
F
F
F
T
F
F
T
F
…
T
T
F
T
T
T
T
F
T
T
T
T

Inference
Knowledge
P1,1
P1,2
P2,1
B1,1
R1
R2
¬B1,1
¬P2,1
F
F
F
F
T
T
T
F
F
F
T
T
F
F
F
F
T
F
T
F
T
…
…
T
T
F
T
F
T
F
T
T
T
F
F
F
T
T
T
T
T
F
T
F

Inconsistent Worlds
Knowledge
P1,1
P1,2
P2,1
B1,1
R1
R2
¬B1,1
¬P2,1
F
F
F
F
T
T
T
F
F
F
T
T
F
F
F
F
T
F
T
F
T
…
…
T
T
F
T
F
T
F
T
T
T
F
F
F
T
T
T
T
T
F
T
F

Models
Knowledge
P1,1
P1,2
P2,1
B1,1
R1
R2
¬B1,1
¬P2,1
F
F
F
F
T
T
T
F
F
F
T
T
F
F
F
F
T
F
T
F
T
…
…
T
T
F
T
F
T
F
T
T
T
F
F
F
T
T
T
T
T
F
T
F

Inference
Query
P1,1
P1,2
P2,1
B1,1
R1
R2
¬B1,1
¬P2,1
F
F
F
F
T
T
T
T
F
F
F
T
T
F
F
F
F
T
F
T
F
T
…
…
T
T
F
T
F
T
F
T
T
T
F
F
F
T
T
T
T
T
F
T
F

Entailment
• αentailsβ:α⊨β
• Everymodelofαisalsoamodelofβ

Entailment
• αentailsβ:α⊨β
• Everymodelofαisalsoamodelofβ
• Whenever α is true, so is β
• β is true in every world consistent with α
• Models(α) ⊆ Models(β) • β logically follows from α

Entailment • Is very conservative
Only accepts a conclusion that is guaranteed to be true whenever the premises are true
•

Entailment • Is very conservative
Only accepts a conclusion that is guaranteed to be true whenever the premises are true
• Ifβisfalseineverymodelofα, then α ⊨ ¬β
•

Entailment • Is very conservative
Only accepts a conclusion that is guaranteed to be true whenever the premises are true
•
• Ifβisfalseineverymodelofα,
then α ⊨ ¬β
• Otherwise: don’t know!

Entailment
Given what I know… Is there no pit in room [2,1]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
¬B1,1
¬P2,1? KB ⊨ ¬P2,1

Entailment
Given what I know… Is there no pit in room [1,2]?
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
¬B1,1 B2,1
¬P1,2?

Inference
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Possible Worlds
Inference
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Inference
Knowledge
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Impossible Worlds
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Models
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Inference
KB ⊨ ¬P1,2
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F

Inference
KB ⊭ P2,2 KB ⊭ ¬P2,2
B1,1
B1,2
P1,1
P1,2
P2,1
P2,2
P3,1
R1
R2
R3
R4
R5
KB
F
F
F
F
F
F
F
T
T
T
T
F
F
F
F
F
F
F
F
T
T
T
F
T
F
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
F
T
F
F
F
F
T
T
F
T
T
F
F
T
F
F
F
F
T
T
T
T
T
T
T
F
T
F
F
F
T
F
T
T
T
T
T
T
F
T
F
F
F
T
T
T
T
T
T
T
T
F
T
F
F
T
F
T
F
F
T
T
F
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
⋮
T
T
T
T
T
T
T
F
T
T
F
T
F
F
F

Entailment Given what I know…
R1: ¬P1,1
R2: B1,1 ⇔ (P1,2 ∨ P2,1)
¬P1,2? ¬B1,1 KB ⊨ ¬P1,2
R3: B2,1 ⇔ (P1,1 ∨ P2,2 ∨ P3,1)
B2,1 KB ⊭ P2,2 KB ⊭ ¬P2,2

Computing Entailment
• Given knowledge α and query β • For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β • Conclude that α ⊨ β

Model Checking
• Given knowledge α and query β • For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β • Conclude that α ⊨ β

Computing Entailment
AIMA Fig. 7.10
boolean TT_Entails?(KB,α)
symbols ⟵ proposition symbols used in KB and α return TT_Check_All(KB, α, symbols, {})
boolean TT_Check_All(KB, α, symbols, model) if empty?(symbols) then
if PL_True?(KB,model) then return PL_True(α,model)
else return true // when KB is false, always return true else
P ⟵ first(symbols) rest ⟵ rest(symbols)
return TT_Check_All(KB, α, rest, model ∪ {P=true})
&& TT_Check_All(KB, α, rest, model ∪ {P=false})

But…

Model Checking
• Given knowledge α and query β • For every possible world w
• If α is satisfied by w
• If β is not satisfied by w
• Conclude that α ⊭ β • Conclude that α ⊨ β

Model Checking
n propositions m sentences, O(k) connectives
P1,1
P1,2
…
OK1,1
OK2,1
R1
R2
…
¬B1,1
¬S1,1
OK2,1
F
F
…
F
F
F
…
…
…
T
…
…
F
F
…
T
T
T
T
…
…
T
T
…
…
T
T
…
F
T
F
…
…
…
F
T
T
…
T
F
T
F
…
…
T
T
T
…
T
T
T
T
…
…
F

Model Checking
n propositions m sentences, O(k) connectives
P1,1
P1,2
…
OK1,1
OK2,1
R1
R2
…
¬B1,1
¬S1,1
OK2,1
F
F
…
F
F
F
…
…
…
T
…
…
F
F
…
T
T
T
T
…
…
T
T
…
…
T
T
…
F
T
F
…
…
…
F
T
T
…
T
F
T
F
…
…
T
T
T
…
T
T
T
T
…
…
F
O(k)

Model Checking
n propositions m sentences, O(k) connectives
P1,1
P1,2
…
OK1,1
OK2,1
R1
R2
…
¬B1,1
¬S1,1
OK2,1
F
F
…
F
F
F
…
…
…
T
…
…
F
F
…
T
T
T
T
…
…
T
T
…
…
T
T
…
F
T
F
…
…
…
F
T
T
…
T
F
T
F
…
…
T
T
T
…
T
T
T
T
…
…
F
O(mk)

Model Checking
n propositions m sentences, O(k) connectives
P1,1
P1,2
…
OK1,1
OK2,1
R1
R2
…
¬B1,1
¬S1,1
OK2,1
F
F
…
F
F
F
…
…
…
T
…
…
F
F
…
T
T
T
T
…
…
T
T
…
…
T
T
…
F
T
F
…
…
…
F
T
T
…
T
F
T
F
…
…
T
T
T
…
T
T
T
T
…
…
F
2n

Model Checking
n propositions m sentences, O(k) connectives
P1,1
P1,2
…
OK1,1
OK2,1
R1
R2
…
¬B1,1
¬S1,1
OK2,1
F
F
…
F
F
F
…
…
…
T
…
…
F
F
…
T
T
T
T
…
…
T
T
…
…
T
T
…
F
T
F
…
…
…
F
T
T
…
T
F
T
F
…
…
T
T
T
…
T
T
T
T
…
…
F
O(2nmk)
Intractable!

Propositional Logic
• Programming language for knowledge • Factored representation (Boolean CSP)
Propositions, connectives, sentences • Possible worlds, satisfiability, models • Entailment: α ⊨ β
Every model of α is a model of β Model checking intractable!
•
• •

For next time: AIMA Ch. 7.5

Related Posts