KRR: Logical agents
Chapter 7, 8, 9
Chapter 7, 8, 9
Copyright By PowCoder代写 加微信 powcoder
Logic is a prerequisite. If you need a refresher, visit
http://users.cecs.anu.edu.au/~jks/LogicNotes/
Chapter 7, 8, 9
Knowledge bases
Inference engine domain−independent algorithms Knowledge base domain−specific content
Knowledge base = set of sentences in a formal language Declarative approach to building an agent (or other system):
Tell it what it needs to know
Then it can Ask itself what to do—answers should follow from the KB
Agents can be viewed at the knowledge level
i.e., what they know, regardless of how implemented
Or at the implementation level
i.e., data structures in KB and algorithms that manipulate them
Chapter 7, 8, 9
A simple knowledge-based agent
function KB-Agent( percept) returns an action static: KB, a knowledge base
t, a counter, initially 0, indicating time
Tell(KB, Make-Percept-Sentence( percept, t)) action ← Ask(KB, Make-Action-Query(t)) Tell(KB, Make-Action-Sentence(action, t)) t←t+1
return action
The agent must be able to:
Represent states, actions, etc.
Incorporate new percepts
Update internal representations of the world Deduce hidden properties of the world Deduce appropriate actions
Chapter 7, 8, 9
Environment
Wumpus World PEAS description
Performance measure
gold +1000, death -1000
-1 per step, -10 for using the arrow
Squares adjacent to wumpus are smelly 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
Left turn, Right turn, Forward, Grab, Release, Shoot
Sensors Breeze, Glitter, Smell
Stench PIT Gold
Chapter 7, 8, 9
Observable?? Deterministic?? Episodic?? Static?? Discrete?? Single-agent??
Wumpus world characterization
Chapter 7, 8, 9
Exploring a wumpus world
Chapter 7, 8, 9
Exploring a wumpus world
Chapter 7, 8, 9
Exploring a wumpus world
Chapter 7, 8, 9
Exploring a wumpus world
Chapter 7, 8, 9
Can use a strategy of coercion:
shoot straight ahead
wumpus was there → dead → safe wumpus wasn’t there → safe
Breeze in (1,2) and (2,1) → no safe actions
Assuming pits uniformly distributed, (2,2) has pit w/ prob 0.86, vs. 0.31
Other tight spots
Smell in (1,1)
→ cannot move
Chapter 7, 8, 9
Models in the wumpus world
Situation after detecting nothing in [1,1], moving right, breeze in [2,1]
Consider possible models for ?s assuming only pits
3 Boolean choices → 8 possible models
Chapter 7, 8, 9
Wumpus models
Chapter 7, 8, 9
KB = wumpus-world rules + observations
Wumpus models
Chapter 7, 8, 9
Is it possible that [2,2] is safe???
Wumpus models
Chapter 7, 8, 9
SAT problems: examples 1
SAT representations of discrete problems
— Any case expressed as a set of yes/no decisions
Can encode sequences of moves (e.g. plans) in this vocabulary
Atomic propositions to describe state greenOnRed, blueOnGreen, etc.
More to describe possible moves GreenToTable, blueToGreen, etc.
Chapter 7, 8, 9
SAT problems: examples 2
♦ Meet-pass planning problems: getting the trains past each other using the given track sectors and the siding, obeying safety conditions
♦ First order problem representation is quite easy
♦ Reduces to SAT because everything is finite
♦ Still a “toy” example (270 atomic formulae) but closer to reality
Chapter 7, 8, 9
SAT applications
♦ Industrial scale problems with thousands of variables (or more)
♦ Some obviously discrete problems
— circuit analysis
— model checking for hardware / software verification
— classical planning
— diagnosis
— combinatorial design (experiments, cryptography, drug design, etc)
♦ Often used for sub-problems
— Generating test patterns
— Scheduling (applied in many domains) — Design and analysis of protocols
Chapter 7, 8, 9
♦ Brute force is hopeless!
SAT: the bad news
♦ Number of possible truth-value assignments grows exponentially
— with n atoms, 2n assignments of values (possible worlds)
— 22n sets of possible worlds (truth functions / propositions)
— Testing for satisfiability (SAT) is (probably) hard in the worst case
♦ Important SAT problems have thousands of variables – even millions
♦ SAT is the classic NP-complete problem
— All known solution methods require exponential time — Generally taken to be intractable
Chapter 7, 8, 9
SAT: the better news
♦ Work towards intelligent search for solutions
♦ First step: simplify the structure of formulae
♦ A↔Bequivalentto(A∧B)∨(¬A∧¬B)
♦ A→Bequivalentto¬A∨B
♦ Every formula has an equivalent using ∧ , ∨ and ¬ only
(p→q)→(r ∧ ¬(p ∧ ¬s)) ¬(p → q) ∨ (r ∧ ¬(p ∧ ¬s)) ¬(¬p ∨ q) ∨ (r ∧ ¬(p ∧ ¬s))
Chapter 7, 8, 9
SAT: better news continues
♦ ¬(A ∧ B) equivalent to ¬A ∨ ¬B
♦ ¬(A ∨ B) equivalent to ¬A ∧ ¬B
♦ ¬¬A equivalent to A
♦ Every formula has an equivalent using ∧ , ∨ and ¬ only, in which negation (¬) applies only to atoms
♦ This is Negation Normal Form (NNF) ¬(¬p ∨ q) ∨ (r ∧ ¬(p ∧ ¬s))
(¬¬p ∧ ¬q) ∨ (r ∧ ¬(p ∧ ¬s))
(p ∧ ¬q) ∨ (r ∧ ¬(p ∧ ¬s))
(p ∧ ¬q) ∨ (r ∧ (¬p ∨ ¬¬s)) (p ∧ ¬q) ∨ (r ∧ (¬p ∨ s))
Chapter 7, 8, 9
SAT: better and better news
♦ A∧BequivalenttoB∧A
♦ A∨BequivalenttoB∨A
♦ (A∧B)∨Cequivalentto(A∨C)∧(B∨C)
♦ (A∨B)∧Cequivalentto(A∧C)∨(B∧C)
♦ Every formula has an equivalent which is a conjunction ( ∧ ) of disjunctions ( ∨ ) of literals (atoms and negated atoms)
♦ This is Conjunctive Normal Form (CNF), aka Clause Form ♦ So any technique for reasoning with clauses can do propositional logic
Chapter 7, 8, 9
reduces to NNF
Reduction to CNF: example
(p→q)→(r ∧ ¬(p ∧ ¬s))
(p ∧ ¬q) ∨ (r ∧ (¬p ∨ s))
then moving conjunction outside disjunction:
(p ∨ (r ∧ (¬p ∨ s))) ∧ (¬q ∨ (r ∧ (¬p ∨ s)))
(p ∨ r) ∧ (p ∨ ¬p ∨ s) ∧ (¬q ∨ r) ∧ (¬q ∨ ¬p ∨ s)
Second conjunct is a tautology, so can be deleted without loss, giving a set of clauses equivalent to the original formula:
¬q ∨ ¬p ∨ s
Chapter 7, 8, 9
p1 ∨ … ∨ pn ∨ r1 ∨ … ∨ rm Alternatively, looking at a clause as a set of literals:
P1,3 ∨ P2,2, P1,3
Resolution is sound and complete for propositional logic
Resolution
Resolution is a logical inference rule which operates on clauses: p1 ∨ … ∨ pn ∨ q ¬q ∨ r1 ∨ … ∨ rm
Γ∆ (Γ\{q})∪(∆\{¬q})
B OK P? OK
Chapter 7, 8, 9
Resolution derivation (example)
Show {p ∨ q, p ∨ ¬q, ¬p ∨ r, ¬r ∨ s, ¬r ∨ ¬s} unsatisfiable
given given given given given 1, 2 4, 5 3, 6
(with factoring to reduce p ∨ p to p) (with factoring)
Chapter 7, 8, 9
Any assignment satisfying a set Γ of clauses must make any specific atom p that occurs in Γ either true or false.
The same holds for Γ′′, defined similarly using ¬p instead of p. Therefore the problem of deciding whether Γ is satisfiable can be replaced
A better idea: DPLL
ThereforeΓissatisfiableiffeitherΓ∪{p}issatisfiableorelseΓ∪{¬p} is satisfiable.
Let Γ′ be Γ with all clauses containing literal p deleted, and with ¬p removed from all clauses in which it occurs. Then Γ′ is satisfiable iff Γ ∪ {p} is satisfiable. Note that Γ′ contains
— fewer clauses than Γ — shorter clauses than Γ — fewer atoms than Γ
by the two strictly simpler problems of deciding satisfiability of Γ′ and Γ′′. Chapter 7, 8, 9
Unit propagation
♦ A pure literal is one whose complement does not appear anywhere
♦ Obviously any pure literal can be made true without bad consequences
♦ Therefore any clause containing a pure literal may be deleted
♦ A unit clause is a clause consisting of only one literal
♦ Obviously this literal has to be set to true
♦ Therefore its complement can be deleted from all clauses — Literal is then pure and triggers purity deletion
♦ Iterating these inference moves is unit propagation
♦ DPLL amounts to splitting plus unit propagation
Chapter 7, 8, 9
Improving DPLL
♦ Clause learning
— The search backtracks when it runs into a contradiction
— The decisions determining the branch can’t all be right
— Add complements of [a subset of] the chosen literals as a new clause — So we never backtrack twice for the same reason
Chapter 7, 8, 9
Improving DPLL even further
♦ Choosing good atoms for branching
— E.g. one that occurs most often in shortest clauses (MOMS) — Or one that occurs most often in currently satisfied clauses
♦ Intelligent backtracking
— Can obviously jump back to a variable in the latest nogood — May pay to jump back further
♦ Restarts
— Can jump right back to the root of the search tree and probe it — Depends heavily on learned clauses to prevent repeated work
Chapter 7, 8, 9
What about quantifiers?
♦ Sometimes need to reason about large or unspecified domains ♦ Reduction to SAT not possible in such cases
♦ Trivial example: subset transitivity:
∀x∀y(sub(x, y) ↔ ∀z(in(z, x) → in(z, y))) therefore
∀x∀y∀z((sub(x, y) ∧ sub(y, z)) → sub(x, z))
Chapter 7, 8, 9
♦ Moving quantifiers outside negation ¬∀xA equivalent to ∃x¬A ¬∃xA equivalent to ∀x¬A
Prenex normal form
♦ First problem: get all quantifiers to the front
Assume → and ↔ rewritten using ∧ , ∨ and ¬
So quantifiers may switch between universal and existential
♦ Moving quantifier binding x outside another one. E.g.: ∀xA(x) ∨ ∀xB(x) goes to ∀x(A(x) ∨ ∀xB(x))
Solution: rewrite variables:
∀x(A(x) ∨ ∀yB(y)) ∀x∀y(A(x) ∨ B(y))
Chapter 7, 8, 9
Removing the quantifiers
♦ Existential quantifiers removed by Skolemisation — Variable replaced by a new name or function — Then quantifier deleted
E.g. ∃x∀y∃zR(x, y, z) goesto ∀y∃zR(a,y,z) thento ∀yR(a,y,f(y))
♦ All quantifiers are now universal. They can be removed — Free variables are implicitly universal
♦ Note: Skolemised formula not equivalent to the original, but they are satisfiable if and only if the original is.
♦ Quantifier-free formula can be put into clause form
Chapter 7, 8, 9
First order resolution
♦ Resolution applies to first order clauses too
♦ Usually requires unification: substituting terms for variables in order to make literals match
P(x,a) ∨ ¬Q(x) and ¬P(b,y) ∨ R(y) [x ← b,y ← a]
P(b,a) ∨ ¬Q(b) and ¬P(b,a) ∨ R(a)
Resolvent: ¬Q(b) ∨ R(a)
Chapter 7, 8, 9
Example: subset transitivity (1)
∀x∀y(sub(x, y) ↔ ∀z(in(z, x) → in(z, y))) ¬∀x∀y∀z((sub(x, y) ∧ sub(y, z)) → sub(x, z))
clausifies to
¬sub(x,y) ∨ ¬in(z,x) ∨ in(z,y) in(f(x,y),x) ∨ sub(x,y) ¬in(f(x,y),y) ∨ sub(x,y) sub(a, b)
¬sub(a, c)
Chapter 7, 8, 9
10. ¬in(f (a, c), c)
11. in(f (a, c), b)
12. in(f (a, c), c)
Example: subset transitivity (2)
1. ¬sub(x, y) ∨ ¬in(z, x) ∨ in(z, y)
2. in(f (x, y), x) ∨ sub(x, y)
3. ¬in(f (x, y), y) ∨ sub(x, y)
4. sub(a, b)
from 1, 4 [x ← a, y ← b] from 1, 5 [x ← b, y ← c] from 2, 6 [x ← a, y ← c] from 3, 6 [x ← a, y ← c] from 7, 9 [z ← f(a,c)] from 8, 11 [z ← f(a,c)] from 10, 12
5. sub(b, c)
6. ¬sub(a, c)
7. ¬in(z, a) ∨
8. ¬in(z, b) ∨
9. in(f (a, c), a)
in(z, b) in(z, c)
Chapter 6.1, 6.2
Knowledge Representation and Reasoning: Constraint Satisfaction Problems
Chapter 6.1, 6.2
Chapter 6.1, 6.2
♦ Introduction
♦ Constraint Networks
♦ Assignments, Consistency, Solutions ♦ Backtracking
♦ Inference
Chapter 6.1, 6.2
Constraint Satisfaction Example: Minesweeper
Chapter 6.1, 6.2
Constraint Satisfaction: Car Sequencing
Chapter 6.1, 6.2
CSPs: a general class of problems
♦ General problem: find an arrangement agreeing with a set of constraints — distribution of mines and non-mines giving the right numbers
— order of cars so that every assembly job gets done smoothly
♦ Situation can be described by a set of variables
♦ Constraint is a condition the variables must meet
♦ Problem: find assignments of values satisfying all constraints
♦ May want any solution, all solutions, a good/best solution, . . .
Chapter 6.1, 6.2
Example: 8 queens problem
♦ Variables: positions of the 8 queens
♦ Domains: squares of the board
♦ Constraints: no 2 queens in the same row, column or diagonal
Chapter 6.1, 6.2
Binary constraint network
♦ Aconstraintnetworkisatriple⟨V,D,C⟩
♦ V a finite set of variables v1,…,vn
♦ D a set of [finite] sets Dv1,…,Dvn
♦ C a set of binary relations {Cu,v | u,v ∈ V,u ̸= v} Cu,v ⊆ Du × Dv
E.g. V = {a,b}. Suppose Da = {1,…,10} and Db = {8,…,20}. If we require a > b then Ca,b is the set {(9, 8), (10, 8), (10, 9)}.
Chapter 6.1, 6.2
Constraint network: notes
♦ A constraint Cu,v is the allowed pairs of assignments to u and v
♦ These are arbitrary relations: they need not have an intuitive reading
♦ Sometimes require domains to be finite (FD problem) Sometimes allow domains to be infinite (e.g. integers, reals)
♦ Extension to non-binary constraints is simple.
♦ SAT is the special case where all domains have just 2 values.
♦ Linear programming is the special case where domains are the real numbers and all constraints are linear inequalities.
Chapter 6.1, 6.2
Queens problem again
♦ Variables: V = {v1, v2, v3, v4}. Row of queen in each column
♦ Domains: For all v, Dv = {1,2,3,4}
♦ Constraints: For1≤i