Fundamentals of Artificial Intelligence Chapter 07: Logical Agents Roberto Sebastiani

Fundamentals of Artificial Intelligence Chapter 07: Logical Agents

Roberto Sebastiani

DISI, Università di Trento, Italy – roberto.sebastiani@unitn.it http://disi.unitn.it/rseba/DIDATTICA/fai_2020/

Teaching assistant: Mauro Dragoni – dragoni@fbk.eu http://www.maurodragoni.com/teaching/fai/

M.S. Course “Artificial Intelligence Systems”, academic year 2020-2021

Last update: Tuesday 8^thDecember, 2020, 13:08

Copyright notice: Most examples and images displayed in the slides of this course are taken from [Russell & Norwig, “Artificial Intelligence, a Modern Approach”, Pearson, 3^rded.], including explicitly figures from the above-mentioned book, and their copyright is detained by the authors.

A few other material (text, figures, examples) is authored by (in alphabetical order):

Pieter Abbeel,Bonnie J. Dorr,Anca Dragan,Dan Klein,Nikita Kitaev,Tom Lenaerts,Michela Milano,Dana Nau,Maria Simi, who detain its copyright. These slides cannot can be displayed in public without the permission of the author.

1 / 91

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

3 / 91

Propositional Logic (aka Boolean Logic)

Basic Definitions and Notation

Propositional formula (aka Boolean formula or sentence)

>, ⊥ are formulas

a propositional atom A

, A

, A

, ... is a formula;

if ϕ

and ϕ

are formulas, then

¬ϕ

, ϕ

∧ ϕ

, ϕ

∨ ϕ

, ϕ

→ ϕ

, ϕ

← ϕ

, ϕ

↔ ϕ

, ϕ

⊕ ϕ

are formulas.

Atoms(ϕ): the set {A ₁ , ..., A _N } of atoms occurring in ϕ.

Literal: a propositional atom A _i (positive literal) or its negation

¬A _i (negative literal)

Notation: if l := ¬A

, then ¬l := A

Clause: a disjunction of literals W

j l _j (e.g., (A ₁ ∨ ¬A ₂ ∨ A ₃ ∨ ...)) Cube: a conjunction of literals V

j l _j (e.g., (A ₁ ∧ ¬A 2 ∧ A 3 ∧ ...))

5 / 91

Semantics of Boolean operators

Truth Table

α β ¬α α∧β α∨β α → β α ← β α ↔ β α⊕β

⊥ ⊥ > ⊥ ⊥ > > > ⊥

⊥ > > ⊥ > > ⊥ ⊥ >

> ⊥ ⊥ ⊥ > ⊥ > ⊥ >

> > ⊥ > > > > > ⊥ Note

∧, ∨, ↔ and ⊕ are commutative:

(α ∧ β) ⇐⇒ (β ∧ α)

(α ∨ β) ⇐⇒ (β ∨ α)

(α ↔ β) ⇐⇒ (β ↔ α)

Remark: Semantics of Implication “→” (aka “⇒”, “⊃”)

The semantics of Implication “α → β” may be counter-intuitive

α → β: “the antecedent (aka premise) α implies the consequent (aka conclusion) β” (aka “if α holds, then β holds” (but not vice versa))

does not require causation or relevance between α and β ex: “5 is odd implies Tokyo is the capital of Japan” is true in p.l.

(under standard interpretation of “5”, “odd”, “Tokyo”, “Japan”) relation between antecedent & consequent: they are both true is true whenever its antecedent is false

ex: “5 is even implies Sam is smart” is true (regardless the smartness of Sam)

ex: “5 is even implies Tokyo is in Italy” is true (!)

relation between antecedent & consequent: the former is false does not require temporal precedence of α wrt. β

ex: “the grass is wet implies it must have rained” is true (the consequent precedes temporally the antecedent)

7 / 91

Syntactic Properties of Boolean Operators

¬¬α ⇐⇒ α

(α ∨ β) ⇐⇒ ¬(¬α ∧ ¬β)

¬(α ∨ β) ⇐⇒ (¬α ∧ ¬β) (α ∧ β) ⇐⇒ ¬(¬α ∨ ¬β)

¬(α ∧ β) ⇐⇒ (¬α ∨ ¬β) (α → β) ⇐⇒ (¬α ∨ β) (α → β) ⇐⇒ (¬β ∧ ¬α)

¬(α → β) ⇐⇒ (α ∧ ¬β) (α ← β) ⇐⇒ (α ∨ ¬β)

¬(α ← β) ⇐⇒ (¬α ∧ β)

(α ↔ β) ⇐⇒ ((α → β) ∧ (α ← β))

⇐⇒ ((¬α ∨ β) ∧ (α ∨ ¬β))

¬(α ↔ β) ⇐⇒ (¬α ↔ β)

Tree & DAG Representations of Formulas

Formulas can be represented either as trees or as DAGS (Directed Acyclic Graphs)

DAG representation can be up to exponentially smaller in particular, when ↔’s are involved

(A ₁ ↔ A ₂ ) ↔ (A ₃ ↔ A ₄ )

⇓

(((A ₁ ↔ A 2 ) → (A ₃ ↔ A 4 ))∧

((A ₃ ↔ A ₄ ) → (A ₁ ↔ A ₂ )))

⇓

(((A ₁ → A 2 ) ∧ (A ₂ → A 1 )) → ((A ₃ → A 4 ) ∧ (A ₄ → A 3 ))) ∧ (((A ₃ → A ₄ ) ∧ (A ₄ → A ₃ )) → (((A ₁ → A ₂ ) ∧ (A ₂ → A ₁ ))))

9 / 91

Tree & DAG Representations of Formulas: Example

(((A ₁ → A ₂ ) ∧ (A ₂ → A ₁ )) → ((A ₃ → A ₄ ) ∧ (A ₄ → A ₃ ))) ∧ (((A ₃ → A 4 ) ∧ (A ₄ → A 3 )) → (((A ₁ → A 2 ) ∧ (A ₂ → A 1 ))))

A1 A2 A2 A1 A3 A4 A4 A3 A3 A4 A4 A3 A1 A2 A2 A1

Tree Representation

Basic Definitions and Notation [cont.]

Total truth assignment µ for ϕ:

µ : Atoms(ϕ) 7−→ {>, ⊥}.

represents a possible world or a possible state of the world Partial Truth assignment µ for ϕ:

µ : A 7−→ {>, ⊥}, A ⊂ Atoms(ϕ).

represents 2

total assignments, k is # unassigned variables Notation: set and formula representations of an assignment

µ can be represented as a set of literals:

EX: {µ(A

) := >, µ(A

) := ⊥} =⇒ {A

, ¬A

} µ can be represented as a formula (cube):

EX: {µ(A

) := >, µ(A

) := ⊥} =⇒ (A

∧ ¬A

)

11 / 91

Basic Definitions and Notation [cont.]

A total truth assignment µ satisfies ϕ (µ is a model of ϕ, µ |= ϕ):

µ |= A

⇐⇒ µ(A

) = >

µ |= ¬ϕ ⇐⇒ not µ |= ϕ

µ |= α ∧ β ⇐⇒ µ |= α and µ |= β µ |= α ∨ β ⇐⇒ µ |= α or µ |= β µ |= α → β ⇐⇒ if µ |= α, then µ |= β µ |= α ↔ β ⇐⇒ µ |= α iff µ |= β µ |= α ⊕ β ⇐⇒ µ |= α iff not µ |= β

M(ϕ)

= {µ | µ |= ϕ} (the set of models of ϕ)

A partial truth assignment µ satisfies ϕ iff all its total extensions satisfy ϕ

(Ex: {A

} |= (A

∨ A

)) because {A

, A

} |= (A

∨ A

) and

{A

, ¬A

} |= (A

∨ A

))

Properties & Results

Property

ϕ is valid iff ¬ϕ is unsatisfiable

Deduction Theorem

α |= β iff α → β is valid (|= α → β)

Corollary

α |= β iff α ∧ ¬β is unsatisfiable

Validity and entailment checking can be straightforwardly reduced to (un)satisfiability checking!

13 / 91

Complexity

For N variables, there are up to 2 ^N truth assignments to be checked.

The problem of deciding the satisfiability of a propositional formula is NP-complete

=⇒ The most important logical problems (validity, inference,

entailment, equivalence, ...) can be straightforwardly reduced to (un)satisfiability, and are thus (co)NP-complete.

⇓

No existing worst-case-polynomial algorithm.

Conjunctive Normal Form (CNF)

ϕ is in Conjunctive normal form iff it is a conjunction of disjunctions of literals:

L

^

i=1 K

_

j

=1

l _j

the disjunctions of literals W K

j

=1 l _j

are called clauses Easier to handle: list of lists of literals.

=⇒ no reasoning on the recursive structure of the formula

15 / 91

Classic CNF Conversion CNF (ϕ)

Every ϕ can be reduced into CNF by, e.g., (i) expanding implications and equivalences:

α → β =⇒ ¬α ∨ β

α ↔ β =⇒ (¬α ∨ β) ∧ (α ∨ ¬β) (ii) pushing down negations recursively:

¬(α ∧ β) =⇒ ¬α ∨ ¬β

¬(α ∨ β) =⇒ ¬α ∧ ¬β

¬¬α =⇒ α

(iii) applying recursively the DeMorgan’s Rule:

(α ∧ β) ∨ γ =⇒ (α ∨ γ) ∧ (β ∨ γ) Resulting formula worst-case exponential:

ex: ||CNF( W

i=1

(l

∧ l

)|| =

Labeling CNF conversion CNF _label (ϕ)

Labeling CNF conversion CNF _label (ϕ) (aka Tseitin’s conversion) Every ϕ can be reduced into CNF by, e.g., applying recursively bottom-up the rules:

ϕ =⇒ ϕ[(l _i ∨ l j )|B] ∧ CNF (B ↔ (l _i ∨ l j )) ϕ =⇒ ϕ[(l _i ∧ l _j )|B] ∧ CNF (B ↔ (l _i ∧ l _j )) ϕ =⇒ ϕ[(l _i ↔ l _j )|B] ∧ CNF (B ↔ (l _i ↔ l _j )) l _i , l _j being literals and B being a “new” variable.

Worst-case linear!

Atoms(CNF _label (ϕ)) ⊇ Atoms(ϕ) CNF _label (ϕ) is equi-satisfiable w.r.t. ϕ:

M(CNF (ϕ)) 6= ∅ iff M(ϕ) 6= ∅

Much more used than classic conversion in practice.

17 / 91

Labeling CNF conversion CNF _label (ϕ) (cont.)

CNF (B ↔ (l _i ∨ l _j )) ⇐⇒ (¬B ∨ l _i ∨ l _j )∧

(B ∨ ¬l _i )∧

(B ∨ ¬l _j ) CNF (B ↔ (l _i ∧ l j )) ⇐⇒ (¬B ∨ l i )∧

(¬B ∨ l _j )∧

(B ∨ ¬l _i ¬l _j ) CNF (B ↔ (l _i ↔ l _j )) ⇐⇒ (¬B ∨ ¬l _i ∨ l _j )∧

(¬B ∨ l _i ∨ ¬l _j )∧

(B ∨ l _i ∨ l j )∧

(B ∨ ¬l _i ∨ ¬l _j )

Labeling CNF Conversion CNF _label – Example

−A3 A1 A5 −A4 −A3 A4 A2 −A6 A1 A4 A3 −A5 −A2 A6 A1 −A4

B1 B2 B3 B4 B5 B6 B7 B8

B9 B10 B11 B12

B13 B14

B15

CNF (B

↔ (¬A

∨ A

))∧

...∧

CNF (B

↔ (A

∨ ¬A

))∧

CNF (B

↔ (B

↔ B

))∧

...∧

CNF (B

↔ (B

∧ B

))∧

CNF (B

↔ (B

∨ B

))∧

CNF (B

↔ (B

∨ B

))∧

CNF (B

↔ (B

∧ B

))∧

B

=

(¬B

∨ ¬A

∨ A

) ∧ (B

∨ A

) ∧ (B

∨ ¬A

)∧

...∧

(¬B

∨ A

∨ ¬A

) ∧ (B

∨ ¬A

) ∧ (B

∨ A

)∧

(¬B

∨ ¬B

∨ B

) ∧ (¬B

∨ B

∨ ¬B

)∧

(B

∨ B

∨ B

) ∧ (B

∨ ¬B

∨ ¬B

)∧

...∧

(B

∨ ¬B

∨ ¬B

) ∧ (¬B

∨ B

) ∧ (¬B

∨ B

)∧

(¬B

∨ B

∨ B

) ∧ (B

∨ ¬B

) ∧ (B

∨ ¬B

)∧

(¬B

∨ B

∨ B

) ∧ (B

∨ ¬B

) ∧ (B

∨ ¬B

)∧

(B

∨ ¬B

∨ ¬B

) ∧ (¬B

∨ B

) ∧ (¬B

∨ B

)∧

B

19 / 91

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

Propositional Reasoning: Generalities

Automated Reasoning in Propositional Logic fundamental task AI, formal verification, circuit synthesis, operational research,....

Important in AI: KB |= α: entail fact α from knowledge base KR (aka Model Checking: M(KB) ⊆ M(α))

typically KB >> α

sometimes KB set of variable implications (A

∧ ... ∧ A

) → B All propositional reasoning tasks reduced to satisfiability (SAT)

KR |= α =⇒ SAT(KR ∧ ¬α)=false

input formula CNF-ized and fed to a SAT solver Current SAT solvers dramatically efficient:

handle industrial problems with 10

− 10

variables & clauses!

used as backend engines in a variety of systems (not only AI)

21 / 91

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

The Resolution Rule

Resolution: deduction of a new clause from a pair of clauses with exactly one incompatible variable (resolvent):

(

common

z }| { l

∨ ... ∨ l

∨

resolvent

z}|{ l ∨

C⁰

z }| {

l

∨ ... ∨ l

) (

common

z }| { l

∨ ... ∨ l

∨

resolvent

z}|{ ¬l ∨

C⁰⁰

z }| {

l

∨ ... ∨ l

) ( l

∨ ... ∨ l

| {z }

common

∨ l

∨ ... ∨ l

| {z }

C⁰

∨ l

∨ ... ∨ l

| {z }

C⁰⁰

)

Ex: ( A ∨ B ∨ C ∨ D ∨ E ) ( A ∨ B ∨ ¬C ∨ F ) ( A ∨ B ∨ D ∨ E ∨ F )

Note: many standard inference rules subcases of resolution:

(recall that α → β ⇐⇒ ¬α ∨ β) A → B B → C

A → C (trans.) A A → B

B (m. ponens) ¬B A → B

¬A (m. tollens)

23 / 91

Basic Propositional Inference: Resolution

Assume input formula in CNF

if not, apply Tseitin CNF-ization first

=⇒ ϕ is represented as a set of clauses

Search for a refutation of ϕ (is ϕ unsatisfiable?) recall: α |= β iff α ∧ ¬β unsatisfiable

Basic idea: apply iteratively the resolution rule to pairs of clauses with a conflicting literal, producing novel clauses, until either

a false clause is generated, or

the resolution rule is no more applicable

Correct: if returns an empty clause, then ϕ unsat (α |= β)

Complete: if ϕ unsat (α |= β), then it returns an empty clause

Very-Basic PL-Resolution Procedure

( c S. Russell & P. Norwig, AIMA)

25 / 91

Improvements: Subsumption & Unit Propagation

Alternative “set” notation (Γ clause set):

Γ, φ ₁ , ..φ _n Γ, φ ⁰ ₁ , ..φ ⁰ _n



e.g., Γ, C ₁ ∨ p, C 2 ∨ ¬p Γ, C ₁ ∨ p, C 2 ∨ ¬p, C 1 ∨ C 2 ,



Clause Subsumption (C clause):

Γ ∧ C ∧ (C ∨ W

i l _i ) Γ ∧ (C) Unit Resolution:

Γ ∧ (l) ∧ (¬l ∨ W

i l _i ) Γ ∧ (l) ∧ ( W

i l _i ) Unit Subsumption:

Γ ∧ (l) ∧ (l ∨ W

l _i )

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

27 / 91

The Davis-Putnam-Longemann-Loveland Procedure

Tries to build an assignment µ satisfying ϕ

At each step assigns a truth value to (all instances of) one atom Performs deterministic choices (mostly unit-propagation) first The grandfather of the most efficient SAT solvers

Correct and complete

Much more efficient than PL-Resolution

Requires polynomial space

The DPLL Procedure [cont.]

( c S. Russell & P. Norwig, AIMA)

Pure-Symbol Rule out of date, no more used in modern solvers.

29 / 91

DPLL: Example

DPLL search tree

ϕ = (A ₁ ∨ A ₂ ) ∧ (A ₁ ∨ ¬A ₂ ) ∧ (¬A ₁ ∨ A ₂ ) ∧ (¬A ₁ ∨ ¬A ₂ )

A1 −A1

A2 A2

Modern CDCL SAT Solvers

Non-recursive, stack-based implementations

Based on Conflict-Driven Clause-Learning (CDCL) schema inspired to conflict-driven backjumping and learning in CSPs learns implied clauses as nogoods

Random restarts

abandon the current search tree and restart on top level previously-learned clauses maintained

Smart literal selection heuristics (ex: VSIDS)

“static”: scores updated only at the end of a branch

“local”: privileges variable in recently learned clauses

Smart preprocessing/inprocessing technique to simplify formulas Smart indexing techniques (e.g. 2-watched literals)

efficiently do/undo assignments and reveal unit clauses Allow Incremental Calls (stack-based interface)

allow for reusing previous search on “similar” problems

Can handle industrial problems with 10 ⁶ − 10 ⁷ variables and clauses!

31 / 91

DPLL Chronological Backtracking: Drawbacks

Chronological backtracking always backtracks to the most recent branching point, even though a higher backtrack could be possible

=⇒ lots of useless search!

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A ₃ ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A 3 ∨ A 4

c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A ₆ ∨ A ₁₁ c ₆ : ¬A ₅ ∨ ¬A 6

c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A ₈

c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

... ^¬A

A

A

¬A

¬A

{..., ¬A ₉ , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ...}

(initial assignment)

33 / 91

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A 1 ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆

c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A 8

√ c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

...

A

¬A

A

A

¬A

¬A

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆

c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A 8

√ c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

... ^A _A

A

¬A

A

A

¬A

¬A

{..., ¬A 9 , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ..., A ₁ , A ₂ , A ₃ } (unit A ₂ , A ₃ )

35 / 91

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ √ c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c ₅ : ¬A 4 ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆

c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A 8

√ c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

...

A

A

A

A

¬A

A

A

¬A

¬A

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ √ c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ √ c ₅ : ¬A 4 ∨ A ₆ ∨ A ₁₁ √ c ₆ : ¬A 5 ∨ ¬A ₆ × c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A 8

√ c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

...

A

A

A

A

A

A

¬A

A

A

¬A

¬A

{..., ¬A 9 , ¬A ₁₀ , ¬A _1¬A

₁ , A ₁₂ , A ₁₃ , ..., A ₁ , A ₂ , A ₃ , A ₄ , A ₅ , A ₆ } (unit A 5 , A ₆ )=⇒ conflict

37 / 91

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ ...

A

A

A

A

A

¬A

A

A

¬A

¬A

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A 3 ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ ...

¬A

A

A

A

A

A

A

¬A

A

A

¬A

¬A

{..., ¬A 9 , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ..., ¬A 1 } (unit ¬A ₁ )

39 / 91

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A 3 ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆

c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A ₈ √ c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ × ...

A

A

¬A

A

A

A

A

A

¬A

A

A

¬A

¬A

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ ...

A

A

¬A

A

A

A

A

A

A

¬A

A

A

¬A

¬A

{..., ¬A 9 , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ...}

=⇒ backtrack to the most recent open branching point

41 / 91

DPLL Chronological Backtracking: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ ...

A

A

¬A

A

A

A

A

A

¬A

A

A

¬A

¬A

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

43 / 91

Backjumping and Learning (Original Strategy)

Idea: when a branch µ fails,

(i) conflict analysis: find the conflict set η ⊆ µ by generating the conflict clause C

= ¬η via resolution from the falsified clause, using the “Decision” criterion;

(ii) learning: add the conflict clause C to the clause set

(iii) backjumping: backtrack to the most recent branching point s.t. the stack does not fully contain η, and then

unit-propagate the unassigned literal on C

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A 2 ∨ ¬A 3 ∨ A ₄ √ c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ √ c ₅ : ¬A ₄ ∨ A ₆ ∨ A ₁₁ √ c ₆ : ¬A 5 ∨ ¬A 6 × c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A ₈ √ c ₉ : ¬A ₇ ∨ ¬A 8 ∨ ¬A 13

...

Conflict!

A

A

c

c

c

c

c

c

A

A

c

c

A

A

A

A

c

c

c

A

A

A

A

A

A

¬A

¬A

¬A

¬A

A

A

¬A

¬A

{..., ¬A ₉ , ¬A ₁₀ , ¬A _1¬A

₁ , A ₁₂ , A ₁₃ , ..., A ₁ , A ₂ , A ₃ , A ₄ , A 5 , A ₆ } (unit A ₅ , A ₆ ) =⇒ conflict;

falsified clause: ¬A 5 ∨ ¬A ₆

45 / 91

Conflict analysis

Criterium: “decision”

1. C := falsified clause 2. repeat

(i) resolve the current clause C with the antecedent clause of the last unit-propagated literal l in C

antecedent clause for l: causing the unit-propagation of on l until C contains only decision literals (“decision” criterion) Example

¬A

∨ A

∨ A

Falsified cl.

z }| {

¬A

∨ ¬A

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ √ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ √ c ₅ : ¬A 4 ∨ A ₆ ∨ A ₁₁ √ c ₆ : ¬A 5 ∨ ¬A ₆ × c 7 : A ₁ ∨ A 7 ∨ ¬A ₁₂ √ c ₈ : A ₁ ∨ A 8

√ c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ ...

Conflict!

A

A

c

c

c

c

c

c

A

A

c

c

A

A

A

A

c

c

c

A

A

A

A

A

A

¬A

¬A

¬A

¬A

A

A

¬A

¬A

=⇒ Conflict set: {¬A ₉ , ¬A ₁₀ , ¬A ₁₁ , A ₁ } ("decision" schema)

=⇒ learn the conflict clause c ₁₀ := A ₉ ∨ A 10 ∨ A 11 ∨ ¬A 1

47 / 91

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁ ...

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

A

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A 3 ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄

c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁ √ ...

¬A

c

c

c

¬A

A

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

A

{..., ¬A ₉ , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ..., ¬A ₁ } (unit ¬A 1 )

49 / 91

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ √ c ₂ : ¬A 1 ∨ A 3 ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄

c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆

c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ √

c ₈ : A ₁ ∨ A ₈ √

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁ √ ...

A

A

A

A

c

c

c

¬A

c

c

c

¬A

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

A

The Original Backjumping Strategy: Example

c ₁ : ¬A 1 ∨ A 2

√ c ₂ : ¬A ₁ ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄

c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c 5 : ¬A ₄ ∨ A ₆ ∨ A ₁₁ c ₆ : ¬A ₅ ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A 12

√

c ₈ : A ₁ ∨ A ₈ √

c ₉ : ¬A ₇ ∨ ¬A ₈ ∨ ¬A ₁₃ × c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A 1

√ ...

c

c

c

Conflict!

A

A

A

A

c

c

c

¬A

c

c

c

¬A

A

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

A

{..., ¬A 9 , ¬A ₁₀ , ¬A ₁₁ , A ₁₂ , A ₁₃ , ..., ¬A 1 , A ₇ , A ₈ } Conflict!

51 / 91

The Original Backjumping Strategy: Example

c ₁ : ¬A 1 ∨ A 2

√ c ₂ : ¬A ₁ ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄

c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c 5 : ¬A ₄ ∨ A ₆ ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A 12

√

c ₈ : A ₁ ∨ A ₈ √

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ × c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A 1

√ ...

c

c

c

Conflict!

A

A

A

A

c

c

c

¬A

c

c

c

¬A

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

A

The Original Backjumping Strategy: Example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁

c ₁₁ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A 12 ∨ ¬A 13

...

A

A

¬A

A

A

A

A

A

¬A

¬A

A

¬A

¬A

¬A

A

A

A

¬A

=⇒ backtrack to A ₁₃ =⇒ Lots of search saved!

53 / 91

The Original Backjumping Strategy: Example

c ₁ : ¬A 1 ∨ A 2

√ c ₂ : ¬A ₁ ∨ A ₃ ∨ A ₉ √ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄

c ₄ : ¬A ₄ ∨ A 5 ∨ A ₁₀ c 5 : ¬A ₄ ∨ A ₆ ∨ A ₁₁ c ₆ : ¬A ₅ ∨ ¬A ₆ c ₇ : A ₁ ∨ A 7 ∨ ¬A 12

c ₈ : A ₁ ∨ A ₈

c ₉ : ¬A ₇ ∨ ¬A ₈ ∨ ¬A ₁₃ √ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A 1

√ c ₁₁ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁₂ ∨ ¬A ₁₃ √ ...

¬A

¬A

c

c

¬A

c

c

c

c

c

¬A

A

A

¬A

A

A

A

A

¬A

¬A

A

A

A

¬A

¬A

¬A

¬A

Learning

Idea: When a conflict set η is revealed, then C = ¬η

added to ϕ

=⇒ the solver will no more generate an assignment containing η:

when |η| − 1 literals in η are assigned, the other is set ⊥ by unit-propagation on C

=⇒ Drastic pruning of the search!

55 / 91

Learning – example

c ₁ : ¬A ₁ ∨ A ₂ c ₂ : ¬A ₁ ∨ A 3 ∨ A ₉ c ₃ : ¬A ₂ ∨ ¬A ₃ ∨ A ₄ c ₄ : ¬A ₄ ∨ A ₅ ∨ A ₁₀ c ₅ : ¬A ₄ ∨ A 6 ∨ A ₁₁ c ₆ : ¬A 5 ∨ ¬A ₆ c ₇ : A ₁ ∨ A ₇ ∨ ¬A ₁₂ c ₈ : A ₁ ∨ A 8

c ₉ : ¬A 7 ∨ ¬A ₈ ∨ ¬A ₁₃ √ c ₁₀ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A ₁ √ c ₁₁ : A ₉ ∨ A ₁₀ ∨ A ₁₁ ∨ ¬A 12 ∨ ¬A 13

√ ...

¬A₉

¬A₁₁

¬A₁₀

¬A1

¬A₁₃ A12

¬A1

¬A13

c10

c10

¬A₁ c11

c₁₁

c11

c11

c10

¬A₁₃ A₇

A8

¬A₁ A2

A3

A4

A₅ A6

¬A10

¬A11

A12

A13

A₁

¬A9

¬A₉

¬A₁₀

A12

¬A₁₁

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

57 / 91

Horn Formulas

A Horn clause is a clause containing at most one positive literal a definite clause is a clause containing exactly one positive literal a goal clause is a clause containing no positive literal

A Horn formula is a conjunction/set of Horn clauses

Ex:

A

∨ ¬A

// definite A

∨ ¬A

∨ ¬A

// definite

¬A

∨ ¬A

∨ ¬A

// goal

A

// definite

Intuition: implications between positive Boolean variables:

A

→ A

(A

∧ A

) → A

(A

∧ A

∧ A

) → ⊥

A

Tractability of Horn Formulas

Property

Checking the satisfiability of Horn formulas requires polynomial time:

Hint:

1

Eliminate unit clauses by propagating their value;

2

If an empty clause is generated, return unsat

3

Otherwise, every clause contains at least one negative literal

=⇒ Assign all variables to ⊥; return the assignment

Alternatively: run DPLL, selecting always negative literals first

59 / 91

A simple polynomial procedure for Horn-SAT

function Horn_SAT(formula ϕ, assignment & µ) { Unit_Propagate(ϕ, µ);

if (ϕ == ⊥)

then return UNSAT;

else { µ := µ ∪ S

A

6∈µ {¬A _i };

return SAT;

} }

function Unit_Propagate(formula & ϕ, assignment & µ)

while (ϕ 6= > and ϕ 6= ⊥ and {a unit clause (l) occurs in ϕ}) do {

Example

¬A 1 ∨ A 2 ∨¬A 3

A ₁ ∨¬A ₃ ∨¬A ₄

¬A ₂ ∨¬A ₄ A ₃ ∨¬A 4

A ₄

61 / 91

Example

¬A 1 ∨ A 2 ∨¬A 3

A ₁ ∨¬A ₃ ∨¬A ₄

¬A ₂ ∨¬A ₄ A ₃ ∨¬A 4

A ₄

µ := {A ₄ := >}

Example

¬A 1 ∨ A 2 ∨¬A 3

A ₁ ∨¬A ₃ ∨¬A ₄

¬A ₂ ∨¬A ₄ A ₃ ∨¬A 4

A ₄ µ := {A ₄ := >, A ₃ := >}

63 / 91

Example

¬A 1 ∨ A ₂ ∨¬A 3

A ₁ ∨¬A ₃ ∨¬A ₄

¬A ₂ ∨¬A ₄ A ₃ ∨¬A 4

A ₄

µ := {A ₄ := >, A ₃ := >, A ₂ := ⊥}

Example

¬A 1 ∨ A ₂ ∨¬A 3 × A ₁ ∨¬A ₃ ∨¬A ₄

¬A ₂ ∨¬A ₄ A ₃ ∨¬A 4

A ₄

µ := {A ₄ := >, A ₃ := >, A ₂ := ⊥, A ₁ := >} =⇒ UNSAT

65 / 91

Example 2

A ₁ ∨¬A ₂

A ₂ ∨¬A 5 ∨¬A ₄ A ₄ ∨¬A 3

A ₃

Example 2

A ₁ ∨¬A ₂

A ₂ ∨¬A 5 ∨¬A ₄ A ₄ ∨¬A 3

A ₃ µ := {A ₃ := >}

67 / 91

Example 2

A ₁ ∨¬A ₂

A ₂ ∨¬A 5 ∨¬A ₄ A ₄ ∨¬A 3

A ₃

µ := {A ₃ := >, A ₄ := >}

Example 2

A ₁ ∨¬A ₂

A ₂ ∨¬A 5 ∨¬A ₄ A ₄ ∨¬A 3

A ₃ µ := {A ₃ := >, A ₄ := >} =⇒ SAT

69 / 91

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

Local Search with SAT

Similar to Local Search for CSPs Input: set of clauses

Use total truth assignments

allow states with unsatisfied clauses

“neighbour states” differ for one variable truth value steps: reassign variable truth values

Cost: # of unsatisfied clauses

Stochastic local search [see Ch. 4] applies to SAT as well random walk, simulated annealing, GAs, taboo search, ...

The WalkSAT stochastic local search

Clause selection: randomly select an unsatisfied clause C Variable selection:

prob. p: flip variable from C at random

prob. 1-p: flip variable from C causing a minimum number of unsat clauses

Note: can detect only satisfiability, not unsatisfiability Many variants

71 / 91

The WalkSAT Procedure

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

73 / 91

A Quote

You can think about deep learning as equivalent to ... our visual cortex or auditory cortex. But, of course, true intelligence is a lot more than just that, you have to recombine it into higher-level thinking and symbolic reasoning, a lot of the things classical AI tried to deal with in the 80s. ... We would like to build up to this symbolic level of reasoning - maths, language, and logic. So that’s a big part of our work.

Demis Hassabis, CEO of Google Deepmind

Knowledge Representation and Reasoning

Knowledge Representation & Reasoning (KR&R): the field of AI dedicated to representing knowledge of the world in a form a computer system can utilize to solve complex tasks

The class of systems/agents that derive from this approach are called knowledge based (KB) systems/agents

A KB agent maintains a knowledge base (KB) of facts collection of domain-specific facts believed by the agent expressed in a formal language (e.g. propositional logic) represent the agent’s representation of the world initially contains the background knowledge

KB queries and updates via logical entailment, performed by an inference engine

Inference engine allows for inferring actions and new knowledge domain-independent algorithms, can answer any question

( c S. Russell & P. Norwig, AIMA) 75 / 91

Reasoning

Reasoning: formal manipulation of the symbols representing a collection of beliefs to produce representations of new ones Logical entailment (KB |= α) is the fundamental operation Ex:

(KB acquired fact): “Patient x is allergic to medication m”

(KB general rule): “Anybody allergic to m is also allergic to m’.”

(KB general rule): “If x is allergic to m’, do not prescribe m’ for x.”

(query): “Prescribe m’ for x?”

(answer) No (because patient x is allergic to medication m’) Other forms of reasoning (last part of this course)

Probablistic reasoning

Other forms of reasoning (not addressed in this course)

Knowledge-Based Agents (aka Logic Agents)

Logic agents: combine domain knowledge with current percepts to infer hidden aspects of current state prior to selecting actions

Crucial in partially observable environments KB Agent must be able to:

represent states and actions incorporate new percepts

update internal representation of the world deduce hidden properties of the world deduce appropriate actions

Agents can be described at different levels

knowledge level (declarative approach): behaviour completely described by the sentences stored in the KB

implementation level (procedural approach): behaviour described as program code

Declarative approach to building an agent (or other system):

Tell the KB what it needs to know (update KB)

Ask what to do (answers should follow logically from KB & query)

77 / 91

Knowledge-Based Agent: General Schema

Given a percept, the agent

Tells the KB of the percept at time step t

ASKs the KB for the best action to do at time step t Tells the KB that it has in fact taken that action

Details hidden in three functions: M AKE -P ERCEPT -S ENTENCE , M AKE -A CTION -Q UERY , M AKE -A CTION -S ENTENCE

construct logic sentences

implement the interface between sensors/actuators and KRR core

Tell and Ask may require complex logical inference

Example: The Wumpus World

Task Environment: PEAS Description Performance measure:

gold: +1000, death: -1000 step: -1, using the arrow: -10 Environment:

squares adjacent to Wumpus are stenchy squares adjacent to pit are breezy glitter iff gold is in the same square shooting kills Wumpus if you are facing it shooting uses up the only arrow

grabbing picks up gold if in same square releasing drops the gold in same square Actuators:

Left turn, Right turn, Forward, Grab, Release, Shoot

Sensors:

Stench, Breeze, Glitter, Bump, Scream

One possible configuration:

( c S. Russell & P. Norwig, AIMA)

79 / 91

Wumpus World: Characterization

Fully Observable? No: only local perception Deterministic? Yes: outcomes exactly specified

Episodic? No: actions can have long-term consequences Static? Yes: Wumpus and Pits do not move

Discrete? Yes

Single-agent? Yes (Wumpus is essentially a natural feature)

Example: Exploring the Wumpus World

The KB initially contains the rules of the

environment.

Agent is initially in 1,1 Percepts:

no stench, no breeze

=⇒ [1,2] and [2,1] OK

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: Pit; BGS: bag of gold

81 / 91

Example: Exploring the Wumpus World

Agent moves to [2,1]

perceives a breeze

=⇒ Pit in [3,1] or [2,2]

perceives no stench

=⇒ no Wumpus in [3,1], [2,2]

Example: Exploring the Wumpus World

Agent moves to [2,1]

perceives a breeze

=⇒ Pit in [3,1] or [2,2]

perceives no stench

=⇒ no Wumpus in [3,1], [2,2]

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: Pit; BGS: bag of gold

81 / 91

Example: Exploring the Wumpus World

Agent moves to [1,1]-[1,2]

perceives no breeze

=⇒ no Pit in [1,3], [2,2]

=⇒ [2,2] OK

=⇒ pit in [3,1]

perceives a stench

=⇒ Wumpus in [2,2] or [1,3]!

Example: Exploring the Wumpus World

Agent moves to [1,1]-[1,2]

perceives no breeze

=⇒ no Pit in [1,3], [2,2]

=⇒ [2,2] OK

=⇒ pit in [3,1]

perceives a stench

=⇒ Wumpus in [2,2] or [1,3]!

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: Pit; BGS: bag of gold

81 / 91

Example: Exploring the Wumpus World

Agent moves to [2,2]

perceives no breeze

=⇒ no pit in [3,2], [2,3]

perceives no stench

=⇒ no Wumpus in [3,2], [2,3]

=⇒ [3,2] and [2,3] OK

Example: Exploring the Wumpus World

Agent moves to [2,2]

perceives no breeze

=⇒ no pit in [3,2], [2,3]

perceives no stench

=⇒ no Wumpus in [3,2], [2,3]

=⇒ [3,2] and [2,3] OK

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: Pit; BGS: bag of gold

81 / 91

Example: Exploring the Wumpus World

Agent moves to [2,3]

perceives a glitter

=⇒ bag of gold!

Example 2: Exploring the Wumpus World [see Ch 13]

Alternative scenario: apply coercion Feel stench in [1,1]

=⇒ Wumpus [1,2] or [2,1]

=⇒ Cannot move

Apply coercion: shoot ahead Wumpus was there

=⇒ Wumpus dead

=⇒ Safe

Wumpus wasn’t there

=⇒ Safe

82 / 91

Example 3: Exploring the Wumpus World [see Ch 13]

Alternative scenario: probabilistic solution (hints) Feel breeze in [1,2] and [2,1]

=⇒ pit in [1,3] or [2,2] or [3,1]

=⇒ no safe action

Probability analysis [see Ch 13]

(assuming pits uniformly distributed):

P(pit ∈ [2, 2]) = 0.86

P(pit ∈ [1, 3]) = 0.31

P(pit ∈ [3, 1]) = 0.31

Outline

1 Propositional Logic

2 Propositional Reasoning Resolution

DPLL

Modern CDCL SAT Solvers Reasoning with Horn Formulas Local Search

3 Knowledge-Based Agents

4 Agents Based on Propositional Reasoning

84 / 91

Propositional Logic Agents

Kind of Logic agents

Language: propositional logic

represent KB as set of propositional formulas

percepts and actions are (collections of ) propositional atoms in practice: sets of clauses

Perform propositional logic inference model checking, entailment

in practice: incremental calls to a SAT solver

Representation vs. World

Reasoning process (propositional entailment) sound

=⇒ if KB is true in the real world, then any sentence α derived from KB by a sound inference procedure is also true in the real world

sentences are configurations of the agent

reasoning constructs new configurations from old ones

=⇒ the new configurations represent aspects of the world that actually follow from the aspects that the old configurations represent

( c S. Russell & P. Norwig, AIMA) 86 / 91

Reasoning as Entailment

Scenario in Wumpus World

Consider pits (and breezes) only:

initial: ¬P

after detecting nothing in [1,1]:

¬B

move to [2,1], detect breeze: B

Q: are there pits in [1,2], [2,1], [3,1]?

3 variables: P _[1,2] ,P _[2,1] ,P _[3,1] ,

=⇒ 8 possible models

Reasoning as Entailment [cont.]

8 possible models

( c S. Russell & P. Norwig, AIMA)

88 / 91

Reasoning as Entailment [cont.]

KB: Wumpus World rules + observations =⇒ 3 models

Reasoning as Entailment [cont.]

Query α ₁ : ¬P _[1,2] =⇒ KB |= α ₁ (i.e M(KB) ⊆ M(α ₁ ))

( c S. Russell & P. Norwig, AIMA)

88 / 91

Reasoning as Entailment [cont.]

Query α ₂ : ¬P _[2,2] =⇒ KB 6|= α ₂ (i.e M(KB) 6⊆ M(α ₂ ))

Reasoning as Entailment [cont.]

In practice: DPLL(CNF (KB ∧ ¬α ₂ )) = sat

( c S. Russell & P. Norwig, AIMA)

88 / 91

Example: Exploring the Wumpus World

KB initially contains (the CNFized versions of) the following formulas:

breeze iff pit in neighbours, ∀i, j ∈ [1..4]

B _[i,j] ↔ (P _[i,j−1] ∨P _[i+1,j] ∨ P _[i,j+1] ∨ P _[i−1,j] ) stench iff Wumpus in neighbours,

∀i, j ∈ [1..4]

S _[i,j] ↔ (W _[i,j−1] ∨W _[i+1,j] ∨W _[i,j+1] ∨W _[i−1,j] ) safe iff no Wumpus and no pit there

OK _[i,j] ↔ (¬W _[i,j] ∧ ¬P _[j,i] ) glitter iff pile of gold there G _[i,j] ↔ BGS _[i,j]

in [1, 1] no Wumpus and no pit =⇒ safe

¬P _[1,1] , ¬W _[1,1] , OK _[1,1]

Example: Exploring the Wumpus World

KB initially contains:

¬P _[1,1] , ¬W _[1,1] , OK _[1,1]

B _[1,1] ↔ (P _[1,2] ∨ P _[2,1] ) S _[1,1] ↔ (W _[1,2] ∨ W _[2,1] ) OK _[1,2] ↔ (¬W _[1,2] ∧ ¬P _[2,1] ) OK _[2,1] ↔ (¬W _[2,1] ∧ ¬P _[1,2] ) ...

Agent is initially in 1,1

Percepts (no stench, no breeze):

¬S _[1,1] , ¬B _[1,1]

=⇒ ¬W _[1,2] , ¬W _[2,1] , ¬P _[1,2] , ¬P _[2,1]

=⇒ OK _[1,2] , OK _[2,1] ([1,2]&[2,1] OK) Add all them to KB

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: pit; BGS: glitter, bag of gold

90 / 91

Example: Exploring the Wumpus World

KB initially contains:

¬P _[1,1] , ¬W _[1,1] , OK _[1,1]

B _[2,1] ↔ (P _[1,1] ∨P _[2,2] ∨ P _[3,1] ) S _[2,1] ↔ (W _[1,1] ∨W _[2,2] ∨ W _[3,1] ) Agent moves to [2,1]

perceives a breeze: B _[2,1]

=⇒ (P _[3,1] ∨ P _[2,2] ) (pit in [3,1] or [2,2]) perceives no stench ¬S _[2,1]

=⇒ ¬W _[3,1] , ¬W _[2,2]

(no Wumpus in [3,1], [2,2])

Add all them to KB

Example: Exploring the Wumpus World

KB initially contains:

¬P _[1,1] , ¬W _[1,1] , OK _[1,1]

B _[2,1] ↔ (P _[1,1] ∨P _[2,2] ∨ P _[3,1] ) S _[2,1] ↔ (W _[1,1] ∨W _[2,2] ∨ W _[3,1] ) Agent moves to [2,1]

perceives a breeze: B _[2,1]

=⇒ (P _[3,1] ∨ P _[2,2] ) (pit in [3,1] or [2,2]) perceives no stench ¬S _[2,1]

=⇒ ¬W _[3,1] , ¬W _[2,2]

(no Wumpus in [3,1], [2,2]) Add all them to KB

A: Agent; B: Breeze; G: Glitter; S: Stench

OK: safe square; W: Wumpus; P: pit; BGS: glitter, bag of gold

90 / 91