Transcript Logical Agents

Logical Agents
Chapter 7
Fall 2005
Copyright, 1996 © Dale Carnegie & Associates, Inc.
A knowledge-based agent
Accepting new tasks in explicit goals
Knowing about its world



current state of the world, unseen properties from
percepts, how the world evolves
help deal with partially observable environments
help understand “John threw the brick thru the
window and broke it.” – natural language
understanding
Reasoning about its possible course of actions
Achieving competency quickly by being told or
learning new knowledge
Adapting to changes by updating the relevant
knowledge
CS 471/598 by H. Liu
2
Knowledge Base
A knowledge base (KB) is a set of
representations (sentences) of facts about
the world.
TELL and ASK - two basic operations


to add new knowledge to the KB
to query what is known to the KB
Infer - what should follow after the KB has
been TELLed.
A generic KB agent (Fig 7.1)
CS 471/598 by H. Liu
3
Three levels of A KB Agent
Knowledge level (the most abstract)
Logical level (knowledge is of sentences)
Implementation level
Building a knowledge base



A declarative approach - telling a KB agent what it
needs to know
A procedural approach – encoding desired behaviors
directly as program code
A learning approach - making it autonomous
CS 471/598 by H. Liu
4
Specifying the environment
The Wumpus world (Fig 7.2) in PEAS





Performance: +1000 for getting the gold, -1000 for being dead, -1
for each action taken, -10 for using up the arrow
 Goal: bring back gold as quickly as possible
Environment: 4X4, start at (1,1) ...
Actions: Turn, Grab, Shoot, Climb, Die
Sensors: (Stench, Breeze, Glitter, Bump, Scream)
It’s possible that the gold is in a pit or surrounded by pits -> try
not to risk life, just go home empty-handed
The variants of the Wumpus world – they can be
very difficult



Multiple agents
Mobile wumpus
Multiple wumpuses
CS 471/598 by H. Liu
5
Acting & reasoning
Let’s play the wumpus game!
The conclusion: “what a fun game!”
Another conclusion: If the available
information is correct, the conclusion is
guaranteed to be correct.
CS 471/598 by H. Liu
6
Logic
The primary vehicle for representing
knowledge




Simple
Concise
Precise
Can be manipulated following rules
It cannot represent uncertain knowledge
well
We will learn Logic first and other
techniques later
CS 471/598 by H. Liu
7
Logics
A logic consists of the following:


A formal system for describing states of
affairs, consisting of syntax (how to make
sentences) and semantics (to relate
sentences to states of affairs).
A proof theory - a set of rules for deducing
the entailments of a set of sentences.
Some examples of logics ...
CS 471/598 by H. Liu
8
Propositional Logic
In this logic, symbols represent whole
propositions (facts)
e.g., D means “the wumpus is dead”
W1,1 Wumpus is in square (1,1)
S1,1 there is stench in square (1,1).
Propositional logic can be connected using
Boolean connectives to generate sentences
with more complex meanings, but does not
specify how objects are represented.
CS 471/598 by H. Liu
9
Other logics
First order logic represents worlds using
objects and predicates on objects with
connectives and quantifiers.
Temporal logic assumes that the world
is ordered by a set of time points or
intervals and includes mechanisms for
reasoning about time.
CS 471/598 by H. Liu
10
Other logics (2)
Probability theory allows the
specification of any degree of belief.
Fuzzy logic allows degrees of belief in a
sentence and degrees of truth.
CS 471/598 by H. Liu
11
Propositional logic
Syntax

A set of rules to construct sentences:
 and, or, imply, equivalent, not
 literals, atomic or complex sentences
 BNF grammar (Fig 7.7, P205)
Semantics


Specifies how to compute the truth value of
any sentence
Truth table for 5 logical connectives (Fig 7.8)
CS 471/598 by H. Liu
12
Knowledge Representation
Knowledge representation


Syntax - the possible configurations that can
constitute sentences
Semantics - the meaning of the sentences
 x > y is a sentence about numbers; or x+y=4;
 A sentence can be true or false
 Defines the truth of each sentence w.r.t. each possible world

What are possible worlds for x+y = 4
Entailment: one sentence logically follows
another


 |= , iff  is true,  is also true
Sentences entails sentence w.r.t. aspects follows
aspect (Fig 7.6)
CS 471/598 by H. Liu
13
Reasoning
KB entails sentence s if KB is true, s is true

Model checking (Fig 7.5) for two sentences/models
 Asking whether KB entails s given KB?


S1 = “There is no pit in [1,2]” -> yes or no?
S2 = “There is no pit in [2,2]” -> yes or no?
An inference procedure


can generate new valid sentences or verify if a sentence is valid given KB
is sound if it generates only entailed sentences
A proof is the record of operation of a sound inference
procedure
An inference procedure is complete if it can find a proof
for any sentence that is entailed.
Sound reasoning is called logical inference or deduction.
A reasoning system should be able to draw conclusions
that follow from the premises, regardless of the world to
which the sentences are intended to refer.
CS 471/598 by H. Liu
14
Equivalence, validity, and
satisfiability
Logical equivalence requires  |= and  |= 
Validity: a sentence  is true in all models


Valid sentences are tautologies (P v !P)
Deduction theorem: for any  and ,  |= iff the
sentence ( ) is valid
Satisfiability: a sentence is satisfiable if it is true
in some models
If  is true in a model m, then m satisfies 
  |= iff the sentence ( ^ !) is unsatisfiable or !(
^ !) is valid .
Validity and satisfiability:  is valid iff ! is
unstatisfiable; contrapositively,  is satisfiable iff ! is
not valid.

CS 471/598 by H. Liu
15
Inference
Truth tables can be used not only to define the
connectives, but also to test for validity:

If a sentence is true in every row, it is valid.
 What is a truth table for “Premises imply Conclusion”

A simple knowledge base for Wumpus
 Five rules (P208)
 What if we write R2 as B1,1 => (P1,2 v P2,1)


Think about the definition of =>
KB |= . Let’s check its validity (Fig 7.9)
 E.g., in Figure 7.9, there are three true models for the KB with
5 rules.

A truth-table enumeration algorithm (Fig 7.10)
 There are only finitely many models to examine, but it is
exponential in size of the input (n)

Can we prove this?
CS 471/598 by H. Liu
16
Reasoning Patterns in Prop Logic
 |= iff the sentence ( ^ !) is unstatisfiable


 are known axioms, thus true (T)
Proof by refutation (or contradiction): assuming  is F, !  is T,
we now need to prove !(^T) is valid, …
Inference rules


Modus Ponens, AND-elimination, Bicond-elimination
All the logical equivalences in Fig 7.11
A proof is a sequence of applications of inference rules

An example to conclude neither [1,2] nor [2,1] contains a pit
Monotonicity (consistency): the set of entailed
sentences can only increase as information is added to
KB


For  and , if KB |=  then KB^ |= 
Propositional logic and first-order logic are monotonic
CS 471/598 by H. Liu
17
Resolution – an inference rule
An example of resolution

R11, R12 (new facts added), R13, R14 (derived from
R11, and R12), R15 from R3, R16, R17 – P3,1 (there
is a pit in [3,1]) (P213)
Unit resolution: l1 v l2 …v lk, m = !li

We have seen examples earlier
Full resolution: l1 v l2 …v lk, m1 v…v mn where li
= mj

An example: (P1,1vP3,1, !P1,1v!P2,2)/P3,1v!P2,2
Soundness of resolution

Considering literal li,
 If it’s true, mj is false, then …
 If it’s false, …
CS 471/598 by H. Liu
18
Refutation completeness

Resolution can always be used to either confirm or
refute a sentence
Conjunctive normal form (CNF)



A conjunction of disjunctions of literals
A sentence in k-CNF has exactly k literals per clause
(l1,1 v … v l1,k) ^…^ (ln,1 v …v ln,k)
A simple conversion procedure (turn R2 to CNF,P.
215)
A resolution algorithm (Fig 7.12)

An example (KB= R2^R4, to prove !P1,2, Fig. 7.13)
Completeness of resolution

Ground resolution theorem
CS 471/598 by H. Liu
19
Horn cluases
A Horn clause is a disjunction of literals of which
at most one is positive




An example: (!L1,1 v !Breeze V B1,1)
An Horn sentence can be written in the form
P1^P2^…^Pn=>Q, where Pi and Q are nonnegated
atoms
Deciding entailment with Horn clauses can be done in
linear time in size of KB
Inference with Horn clauses can be done thru forward
and backward chaining
 Forward chaining is data driven
 Backward chaining works backwards from the query, goal-
directed reasoning
CS 471/598 by H. Liu
20
An Agent for Wumpus
The knowledge base (an example on p208)


Bx,y  …, Sx,y …
There is exactly one W: (1) there is at least one
W, and (2) there is at most one W
Finding pits and wumpus using logical inference
Keeping track of location and orientation
Translating knowledge into action

A1,1^EastA^W2,1=>!Forward
Problems with the propositional agent


too many propositions to handle (“Don’t go forward if…”)
hard to deal with change (time dependent propositions)
CS 471/598 by H. Liu
21
Summary
Knowledge is important for intelligent agents
Sentences, knowledge base
Propositional logic and other logics
Inference: sound, complete; valid sentences
Propositional logic is impractical for even very
small worlds
Therefore, we need to continue our AI class
...
CS 471/598 by H. Liu
22