Transcript Logical Agents

Agents That Reason
Logically
Chapter 6
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
Reasoning about its possible course of
actions
Achieving competency quickly by being told
or learning new 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.
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 learning approach - making it autonomous
CS 471/598 by H. Liu
4
Specifying the environment
The Wumpus world (Fig 6.2)
Percepts: (Stench, Breeze, Glitter, Bump, Scream)
Actions: Turn, Grab, Shoot, Climb, Die
Goal: bring back gold as quickly as possible
Environment: 4X4, start at (1,1) ...
The variants of the Wumpus world
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!”
CS 471/598 by H. Liu
6
Representation
Knowledge representation
Syntax - the possible configurations that can
constitute sentences
Semantics - the meaning of the sentences
x > y is a sentence about numbers; the sentence
can be true or false
Entailment: sentences entails sentence w.r.t.
Facts follows fact (Fig 6.5)
CS 471/598 by H. Liu
7
Reasoning
KB entails sentence s if KB is true, s is true
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.
CS 471/598 by H. Liu
8
Inference
Sound reasoning is called logical inference or
deduction.
A sentence is valid or necessarily true iff it is
true under all possible interpretations in all
possible worlds.
A sentence is satisfiable iff there is some
interpretation in some world for which it is
true.
CS 471/598 by H. Liu
9
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).
The 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
10
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
11
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
12
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.
A summary of various of logics can be
found in Fig 6.7.
CS 471/598 by H. Liu
13
Propositional logic
Syntax
A set of rules to construct sentences:
and, or, imply, equivalent, not
literals, atomic or complex sentences
BNF grammar (Fig 6.8,P167)
Semantics
Truth table for 5 logical connectives (Fig 6.9)
CS 471/598 by H. Liu
14
Validity and 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.
A truth table for “Premises imply Conclusion”
((P or H) and !H) => P
Let’s check its validity (Fig 6.10)
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
15
Rules of inference
:  can be derived from  by inference
Seven commonly used inference rules
(Fig. 6.13, P172)
An inference rule is sound if the conclusion is
true in all cases where premises are true.
Using a truth table to verify soundness of
Resolution (Fig. 6.14)
CS 471/598 by H. Liu
17
Complexity of Prop
Inference
Complexity of a truth table is ...
A logic is monotonic if ...
Prop logic and first-order logic are monotonic
Horn sentences has the form
P1^P2^…^Pn=>Q
where Pi and Q are nonnegated atoms.
CS 471/598 by H. Liu
18
An Agent for Wumpus
The knowledge base
facts about squares 1,1;2,1;1,2 (Fig 6.15)
4 rules (!S1,1; !S2,1; !S1,2;S1,2) about Wumpus
Finding the wumpus using facts and rules
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
19
Summary
Knowledge is important for intelligent agents
Sentences, knowledge base
Propositional logic and other logics
Inference: sound, complete; valid sentences
Propositional logic impratical for even very
small worlds
Therefore, we need to continue our AI class
...
CS 471/598 by H. Liu
20