Knowledge-Based Agents in Artificial Intelligence

Spring 2020 CSE 412: Artificial Intelligence Topic 6: Logical Agents

Topic Contents Knowledge-Based Agents Logic Propositional Logic: A Very Simple Logic Syntax Semantics A simple knowledge base Inference Equivalence, validity, and satisfiability

Architecture of a Simple Intelligent Agent Environment Agent Model of World (being updated) Prior Sensors Knowledge about the World Reasoning & Decisions Making List of Possible Actions Effectors Goals/Utility 3

Knowledge Based Agent Knowledge base: A knowledge base (abbreviated KB or kb) is a special kind of database for knowledge management. A knowledge base is an information repository that provides a means for information to be collected, organized, shared, searched and utilized. The part of an expert system that contains the facts and rules needed to solve problems. A collection of facts and rules for problem solving. 4

Knowledge Based Agent The agent must be able to: represent states, actions, etc. incorporate new percepts update internal representation of world deduce hidden properties of world deduce appropriate actions One of the core intelligent agent is knowledge representation: how to represent knowledge how to reason using that knowledge problems in developing an 5

Knowledge Bases (KB) ? A knowledge base: contains the domain-specific content for an agent is a set of representations of facts about the world ? is a set of sentences in a formal language Building the KB: learning: agent discovers what it knows telling: agent is given what it knows (declarative) 6

Knowledge Bases (KB) Main actions of intelligent agent: TELL information to KB in the form of percept ASK KB what to do in the form of action ? Answers should follow from KB. Agent should not make things up! ? An inference engine is composed of domain- independent algorithms determine what follows from the knowledge base. that are used to 7

Knowledge Bases (KB) View of agent (levels of abstraction): knowledge level: what the agent knows at a high level logic level: level of sentence encoding implementation level: level that runs on the architecture, detail of data structures and algorithms. 8

Algorithm 9

General Logic The world/environment in its knowledge base. Sentences are representations in some language. Facts are claims about the world that are true/false. agent internally represents its The Sky is blue. The sun is shining Sentences representation in agent world/environment Facts 10

General Logic Sentences represent facts in the world. Meaning connects sentences to their facts. A sentence is true if what it represents is actually the case in the current state of world. Sentences Time flies. representation in agent Meaning / Interpretation world/environment Facts 11

General Logic ensures that conclusions Proper inferred from the KB are consistent with reality. That means they represent new facts that actually follow from the original facts (represented by sentences in the KB). reasoning infer Knowledge Conclusions repr. world follows Facts New Facts 12

General Logic ? Computers don't know the meaning. A mechanical inference procedure is needed that derives conclusions without needing to know the meaning of the sentences. infer entails Knowledge Sentences Conclusions New Sentences repr. world follows Facts New Facts 13

Entailment KB Knowledge base KB entails sentence if and only if is true in all worlds where KB is true 14

Entailment KB Knowledge base KB entails sentence if and only if is true in all worlds where KB is true For example: KB: "sky is blue" = true, "sun is shining" = true entails : "sky is blue and sun is shining" = true represents a true fact as long as facts represented in KB are true if the sky was actually cloudy then KB isn't the true world state then wouldn't represent a true fact ? Entailment requires sentences in KB to be true. 15

Logical Inference Inference procedure can: generate new sentences entailed by KB determine whether or not a given sentence is entailed by KB (i.e. prove ) 16

General Logic Logics information from which conclusions can be drawn. are formal languages for representing 17

General Logic Logics are characterized by what they commit to as "primitives". Logic Propositional First-Order Temporal What Exists in World facts facts, objects, relations facts, objects, relations, times facts degree of truth Knowledge States true/false/unknown true/false/unknown true/false/unknown Probability Theory Fuzzy degree of belief 0..1 degree of belief 0..1 18

Propositional Logic (PL) Basics propositions: assertions about an aspect of a world that can be assigned either a true or false value e.g. SkyIsCloudy, JimIsHappy True, False are propositions meaning true and false 19

Logical Connectives of PL negation (not) conjunction (and) S1 and S2 are conjuncts disjunction (or) S1 and S2 are disjuncts implication/conditional (if-then) S1 is the antecedent/premise S2 is the consequent/conclusion equivalence/biconditional (if and only if) S S1 S2 S1 S2 S1 S2 S1 S2 20

Syntax of PL Models specify truth value for each proposition: e.g. S1= true, S2= false Rules for evaluating truth with respect to model m S is true iff S is false S1 S2 is true iff S1is true S1 S2 is true iff S1is true S1 S2 is true iff S1is true or is true iff S1is false or is false iff S1is false and S1 S2 is true iff S1 S2is true and S2 S1is true Operator Precedence: (highest) and or S2 is true S2 is true S2 is true S2 is true S2 is false (lowest) 21

Truth Tables A B C false false false false false true false true false false true true true false false true false true true true false true true true Given n symbols, 2npossible combinations of truth value assignments. here each row is an interpretation 22

Implication Truth Table A B A B true true false true B A true true false true false false false true true true false true A B is equivalent to B A 23

Validity A B C A A true true true true true true true true false false false false false true false true false false true true true false false true false true true true false true true true A sentence is valid if it's true in all interpretations: P1 P1 P1 P1 (tautologies) (i.e. its entire column is true) 24

Satisfiability A B C A B true true false false true true true true false false false false false true false true false false true true true false false true false true true true false true true true A sentence is satisfiable if it's true in some interpretations: P1 P2 P2 P1 (i.e. its column is true and false) 25

Unsatisfiability A B C C C false false false false false false false false false false false false false true false true false false true true true false false true false true true true false true true true A sentence is unsatisfiable if it's true in no interpretations: P1 P1 (inconsistent/contradiction) (i.e. its entire column is false) 26

Inference Proof Methods Model Checking: truth table enumeration sound and complete for propositional logic heuristic search in model space sound but incomplete Application of Syntactic Operations (i.e. Inference Rules): sound generation of new sentences from old could use inference rules as operators for search 27

Inference by Enumeration LET: KB = A C, B C = A B DOES: KB ? A B C RECALL: doesn't know the meaning of the proposition symbols. The computer false false false false false true false true false false true true true false false true false true true true false true true true So all logically distinct cases must be checked to prove that a sentence can be derived from a KB. 28

Inference by Enumeration LET: KB = A C, B C = A B DOES: KB ? A B C A C B C KB false true true false false true true true true true true false true true true true Rows where all of sentences in KB are true are the models of KB false false false false false true false true false false true true true false false true false true true true false true true true false false false true true false true true 29

Inference by Enumeration LET: KB = A C, B C = A B DOES: KB ? YES! is entailed by KB, if all models of KB are models of , i.e. all rows where KB is true, is true A B C A C B C KB false true true false false true true true true true true false true true true true A B false false true true true true true true KB true true true true true true true true false false false false false true false true false false true true true false false true false true true true false true true true false false false true true false true true In other words: KB is valid. 30

Inference by Enumeration Though complete for PL, the proofs using this enumeration grow exponentially in length as the number of symbols increases. There must be a better way. Natural deduction that uses sound inference rules to derive new sentences from the KB derived sentences until the conclusion sentence is derived. is an inference procedure and any previously 31

THANKS