Transcript Slide 1

Knowledge Representation
Use of logic
Artificial agents





need Knowledge and reasoning power
Can combine GK with current percepts
Build up KB incrementally
Logic primary vehicle
K always definite ( T/F)
Problem for a robot






If red light is ON or it is morning shift or supervisor absent then
door is locked.
If door is locked it implies that the red light is turned ON or it is
morning shift or the supervisor is absent
If load is small in size or load is light then the conveyor belt
moves
If the conveyor belt is moving then it means the load has a
small size or load is light
The Red light is off, the Conveyor belt is not moving and the
Door is locked.
The robot wants to know if the load is heavy (not light).
Robot needs a Knowledge Base
and reasoning ability
Knowledge base



Central component of a K based agent
Set of sentences
INFERENCE
–

Deriving new info from old
Language to enable building KB
Interpretations

Language semantics defines TRUTH of each
sentence w.r.t. each possible world
Similarity with CSP


Constraint solving is a form of Logical
reasoning
Constraint languages: LOGICS
Wff and logical reasoning

Entailment:
–


Sentence follows logically from another sentence
KB |= s
iff in every model in which KB is true, s is
also true
Inference algorithm




Enumerate the models
Check if s is true in every model
(interpretation) for which KB is also true
Backtracking search – recursively assign
values to variables
Exponential complexity
definitions





Validity
Tautology
Deduction theorem
Satisfiability
inconsistancy
Reasoning patterns in
Propositional logic
Inference rules



Modus Ponens
And Elimination
Standard logical equivalances
–
–
–
–
De Morgan
Contra positive
Distributive laws
Associative laws
Deduction

With the knowledge base that the robot has,
and what it currently perceives
(more knowledge added to the KB),
the robot wants to deduce that
the load is not light
Knowledge that robot has




If red light is ON or it is morning shift or supervisor
absent then door is locked.
If door is locked it implies that the red light is turned
ON or it is morning shift or the supervisor is absent
If load is small in size or load is light then the
conveyor belt moves
If the conveyor belt is moving then it means the load
has a small size or load is light
Observations by the robot



Red light is off
Conveyor belt is not moving
Door is locked
What the robot wants to establish?

The load is not light
( or in other words it is heavy)
Knowledge + Observation (K.B.)







If red light is ON or it is morning shift or supervisor absent then
door is locked.
If door is locked it implies that the red light is turned ON or it is
morning shift or the supervisor is absent
If load is small in size or load is light then the conveyor belt
moves
If the conveyor belt is moving then it means the load has a
small size or load is light
Red light is off
Conveyor belt is not moving
Door is locked
Propositions







P: red light is ON
M: it is morning shift
N: supervisor absent
D: door is locked.
Q: load is small in size
R: load is light
B: the conveyor belt is moving
Next?

Now generate wffs and start the inference
process
Steps to help the robot (inferencing)





Consider a relevant rule for conveyor belt
Use And-elimination
Use contra-positive relation
Use modus ponens
Use de morgan’s law
PROOF?





PROOF: Sequence of application of Inference rules.
Finding proofs is like finding solutions to search
problems.
Successor function generates all possible application
of inference rules
In worst case, search for proof would be as bad as
enumerating all the models
Some irrelevant propositions can be ignored to
speed up search.
Monotonicity


Set of entailed sentences can only increase
as info is added to KB.
Rules can be applied wherever suitable
Resolution



What about completeness?
Can everything be inferred?
Resolution rule forms basis for a family of
complete inference procedures.
Refutation completeness
Resolution can be used to either
CONFIRM
or
REFUTE a sentence

Artificial Intelligence
Intelligent?
What is intelligence?

computational part of the ability to achieve
goals in the world